深圳市建设银行网站,wordpress 去掉顶部,网站建设设计服务商,门户网站的优点674 Longest Continuous Increasing Subsequence
问题#xff1a;比较简单#xff0c;直接看代码。问题是速度更快的代码是什么样子#xff1f; 代码
665 Non-decreasing Array
思路#xff1a;非降序数组#xff0c;能有一次修改的机会。那就是查找 array[i1]arr…674 Longest Continuous Increasing Subsequence
问题比较简单直接看代码。问题是速度更快的代码是什么样子 代码
665 Non-decreasing Array
思路非降序数组能有一次修改的机会。那就是查找 array[i1]array[i]array[i1]array[i]array[i+1] 整个数组中出现了两次或更多就返回false。否则返回true。 问题当只有一处错误的时候也要考虑下能修改吗修改后能称为非降数组吗例如[4,2,3] idx0的时候nums[idx1]nums[idx]nums[idx1]nums[idx]nums[idx+1]这个时候修改idx1就不能达到目的因为nums[idx1]4并且nums[idx1]3nums[idx1]4并且nums[idx1]3nums[idx+1]>=4 并且 nums[idx+1]是做不到的。而修改nums[idx]就可以达到目的nus[i]2即可nus[i]2即可nus[i]。但是例如[3,4,2,3] 当idx1的时候nums[idx1]nums[idx]nums[idx1]nums[idx]nums[idx+1]这个时候修改nums[idx1]要求的范围是[4,3]没有数据修改nums[idx]要求的范围是[3,2]还是没有数据。所以不能满足要求。 进一步分析[4,2,3] idx0的时候nums[idx1]nums[idx]nums[idx1]nums[idx]nums[idx+1]这个时候应该修改nums[idx]nums[idx1]2。因为nums[idx1]越大对后面形成非降数组越不利。 [3,4,2,3] 当idx1的时候nums[idx1]nums[idx]nums[idx1]nums[idx]nums[idx+1]因为nums[idx-1]nums[idx1]所以就不能修改nums[idx]只能修改nums[idx1]nums[idx]4。在后面的判断会继续出现第二次错误最终返回false。 代码
661 Image Smoother
思路这种查找二维数组周围的题目一定要用到数组new int[]{-1,0,1}。 代码
189 Rotate Array
思路For example, with n 7 and k 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].首先我的思路是循环队列一次移动一个位置移动k次分别为[7,1,2,3,4,5,6] [6,7,1,2,3,4,5] [5,6,7,1,2,3,4]接着查找规律一次移动k个需要借助长度为k的数组。 学习题目要求O(1)的额外空间完成。学习到了倒转的思路。倒转数组。例如a [1,2,3,4,5,6,7]首选倒转整个数组得到[7,6,5,4,3,2,1]接着倒转0到k-1前半部分数组得到[5,6,7,4,3,2,1]最后倒转k到末尾数组得到[5,6,7,1,2,3,4]。为什么有效没有找到答案。 代码
219 Contains Duplicate II
思路把每个值对应的下标存起来遇到相同的比较一下是不是最多相差k 学习另外一种思路是当前判断nums[i]那集合中只保留i-k,i-k1,…i-1范围内的nums值其他值去掉 代码
268 Missing Number
思路一可以计算0,1,2,…n的和然后再减去数组中的值留下的就是丢失的数据。 思路二将nums数组排序二分查找的left值就是丢失的数据。 思路三将0,1,2,…n异或的值与nums数组中每个值异或最后的结果就是丢失的数据。
66 Plus One
思路从低位开始加如果不发生进位则加法结束。如果发生进位则前进到前一位做加1操作。最后判断如果digits[0]0则说明存在进位需要扩展数组。 学习思路跟上面差不多。不同之处是加法结束直接返回如果所有位数遍历完还没有返回则说明是 9991则需要扩展数组将首位修改为1。这样速度更快。 代码
283 Move Zeroes
思路idx记录不等于0的数组的存放下标从左向右遍历。之后把idx到n之间的值填充为0。
532 K-diff Pairs in an Array
思路每处理一个nums[i]需要判断j从i1到n的数组值是否符合|nums[i]-nums[j]|k。去重部分使用set。例如nums[i]2,k3则需要找到数值5,-1。当需要处理nums[i]5的时候因为2已经匹配过了所以需要找到数值8。
public int findPairs(int[] nums, int k) {if (k 0)return 0;int count 0;SetInteger set new HashSetInteger();// 存放已经计算过的数值for (int i 0; i nums.length; i) {if (!set.contains(nums[i])) {SetInteger list new HashSetInteger();if (!set.contains(nums[i] - k)) {list.add(nums[i] - k);}if (!set.contains(nums[i] k)) {list.add(nums[i] k);}for (int j i 1; j nums.length !list.isEmpty(); j) {if (list.contains(nums[j])) {count;list.remove((Integer) (nums[j]));}}set.add(nums[i]);}}return count;}
思路二处理数组。首先因为需要去重那就把数组排序并且去掉重复的数据。还是依据上述的思路只是不再考虑去重。这里要注意的是当k0的时候需要知道有多少数据重复。
public int findPairsV2(int[] nums, int k) {if (k 0)return 0;Arrays.sort(nums);int idx 0;// 新的长度int sameMatcherCount 0;for (int i 0; i nums.length; i) {nums[idx] nums[i];if (i 1 nums.length nums[i 1] nums[i]) {sameMatcherCount;}while (i 1 nums.length nums[i 1] nums[i]) {i;}}if (k 0)return sameMatcherCount;int newLength idx;int count 0;for (int i 0; i newLength; i) {for (int j i 1; j newLength; j) {if (Math.abs(nums[i] - nums[j]) k) {count;}}}return count;}
学习到的统计每个数值出现次数。在处理某个数值n的时候判断map的key值中是否存在nk。时间复杂度降到了O(n)。
public int findPairsV3(int[] nums, int k) {if (nums null || nums.length 0 || k 0)return 0;MapInteger, Integer map new HashMap();int count 0;for (int num : nums) {map.put(num, map.get(num) ! null ? map.get(num) 1 : 1);}for (Map.EntryInteger, Integer entry : map.entrySet()) {if (k 0) {if (entry.getValue() 2) {count;}} else {// 只判断entry.getKey()k避免重复if (map.keySet().contains(entry.getKey() k)) {count;}}}return count;}
代码
