网站建设的教程视频,深圳网站设计灵点网络品牌,大连旅顺口,关键词挖掘长尾词题1 水壶问题
描述 有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶#xff0c;从而可以得到恰好 z升 的水#xff1f; 如果可以#xff0c;最后请用以上水壶中的一或两个来盛放取得的 z升 水。 你允许#xff1a; 装满任意一个水壶 清空…题1 水壶问题
描述 有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶从而可以得到恰好 z升 的水 如果可以最后请用以上水壶中的一或两个来盛放取得的 z升 水。 你允许 装满任意一个水壶 清空任意一个水壶 从一个水壶向另外一个水壶倒水直到装满或者倒空 示例 1: (From the famous “Die Hard” example) 输入: x 3, y 5, z 4 输出: True 示例 2: 输入: x 2, y 6, z 5 输出: False 题解
思路首先判断极端情况如果x和y的容量和小于z永远不可能装满。如果z的容量等于x或y或xy倒一次水就可以装满。
在任意一个时刻我们可以且仅可以采取以下几种操作 假设x y 1.把 X 壶的水灌进 Y 壶直至灌满或倒空 X壶cur_x-y Y壶y 2.把 Y 壶的水灌进 X 壶直至灌满或倒空 X壶cur_xy Y壶-y 3.把 X 壶灌满 x 4.把 Y 壶灌满 y 5.把 X 壶倒空 -x 6.把 Y 壶倒空。 -y 每次操作只会让桶里的水总量增加 x增加 y减少 x或者减少 y。
找到一对整数 a,b 使得 axbyz 而只要满足 z ≤ xy且这样的 a, b存在那么我们的目标就是可以达成的。
贝祖定理axbyz有解当且仅当 z 是 x, y的最大公约数的倍数。因此我们只需要找到 x, y的最大公约数并判断 z 是否是它的倍数即可
gcd找x和y的最大公约数
class Solution {public boolean canMeasureWater(int x, int y, int z) {if(x y z) return false;if(z 0 || z x y || z x || z y) return true;int gcd gcd(x, y);return z % gcd 0;}public int gcd(int a, int b){if(b 0){return a;}return gcd(b, a % b);}
}题2 删除排序数组重复项
描述 给定一个排序数组你需要在 原地 删除重复出现的元素使得每个元素只出现一次返回移除后数组的新长度。 不要使用额外的数组空间你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。 示例 1: 给定数组 nums [1,1,2], 函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 你不需要考虑数组中超出新长度后面的元素。 示例 2: 给定 nums [0,0,1,1,1,2,2,3,3,4], 函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。 你不需要考虑数组中超出新长度后面的元素。 说明: 为什么返回数值是整数但输出的答案是数组呢? 请注意输入数组是以「引用」方式传递的这意味着在函数里修改输入数组对于调用者是可见的。 你可以想象内部操作如下: // nums 是以“引用”方式传递的。也就是说不对实参做任何拷贝 int len removeDuplicates(nums); // 在函数里修改输入数组对于调用者是可见的。 // 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。 for (int i 0; i len; i) { print(nums[i]); } 题解1 两个指针
思路i指针来记录最后返回的数组j指针遇到相同的则向后移动如果遇到不同的则向前覆盖。
// 使用双指针if(numsnull || nums.length 1){return nums.length;}int i 0,j 1;while(jnums.length){if(nums[i]nums[j]){j;}else{i;nums[i]nums[j];j;}}return i1;官方题解
思路相同 数组完成排序后我们可以放置两个指针 i 和 j其中 i 是慢指针而 j 是快指针。只要 nums[i] nums[j]我们就增加 j 以跳过重复项。 当我们遇到 nums[j] ≠ nums[i] 时跳过重复项的运行已经结束因此我们必须把它nums[j]的值复制到 nums[i 1]。然后递增 i接着我们将再次重复相同的过程直到 j 到达数组的末尾为止。
public int removeDuplicates(int[] nums) {if (nums.length 0) return 0;int i 0;for (int j 1; j nums.length; j) {if (nums[j] ! nums[i]) {i;nums[i] nums[j];}}return i 1;
}
