Array201604总结

2019-11-08 02:07:45

字体：大中小

来源：转载

供稿：网友

Array26

1.在前面的特殊情况排查中，慎用else,主程序有可能unreachable

2.Else If 在修改当前array时候注意改后的值对当前条件句的影响

一下是一个把duplicate消除的array的主要代码

for (int i = 0; i < nums.length - 1; i++) { if ( i == nums.length - 2) {//if i and i + 1 is the last two in array if (nums[i] != nums[i + 1] && dup == 0) { nums[index++] = nums[i]; nums[index++] = nums[i + 1]; } else if (nums[i] != nums[i+1] && dup == 1) { nums[index++] = nums[i + 1]; } else if (nums[i] == nums[i+1] && dup == 0) { nums[index++] = nums[i]; } } else { //i is the first of duplicated i's if (nums[i] == nums[i+1] && dup == 0) { nums[index++] = nums[i]; dup = 1; } //i is the one that different from the one before and after it if (nums[i] != nums[i+1] && dup == 0) { nums[index++] = nums[i]; dup = 0; } //i is the last of duplicated i's if (nums[i] != nums[i+1] && dup == 1) { dup = 0; } } }

这段代码的for循环第一个if里面如果没有后两个else，则在[1,1,2,3]会出状况因为当i = 2也就是nums[2]执行完毕,nums会变为[1,2,3,3]，如果没有else if则直接跳跳入三行以后的那个if,则结果变为[1,2,3,3] index = 4

Array 1 Two sum

1. 需要return indices的时候，只需要找result的两个值的位置就行了

2. 没必要写一个对应index的二维数组，只要不在原array上面排序就好了啊

//Get the indices and value int[][] arrayIndices = new int[nums.length][2]; for (int i = 0; i < nums.length; i++) { arrayIndices[i][0] = nums[i]; arrayIndices[i][1] = i; }

应该用nums.clone(),得出了两个数值再放在原数组里查找位置就可以

3. 最初想法，没有考虑负数情况 (主要看第二个for循环对biggest的处理）

原来代码，从最小的依次到大凑出target值的，以下情况只考虑了target > nums.minimum 的情况//Find the pairs whose sum equals the target value Arrays.sort(nums);//sort the array int biggest = target; //define the biggest values of search if (nums[0] < 0) {biggest = target - nums[0];} int[] values = new int[2]; for (int i = 0; i < nums.length - 1; i++) { for ( int j = i + 1;j < nums.length && j <= biggest; j++) { if (nums[i] + nums[j] == target) { values[0] = nums[i]; values[1] = nums[j]; System.out.PRintln(values[0] + "," + values[1]); } } } }

但是即便如此，也睡溢出time limit，因为很有可能把所有的值都for循环两次 O(n^2)

因此，应该想到排序后从最右面和最左面开始找，这也是求two sum的基本思想才对。

4. 查找index溢出

以下代码会发生溢出

int[] result = new int[2]; int k = 0; for ( int i = 0; i < nums.length; i++) { if (nums[i] == nums2[min]) { result[k ++] = i; } if (nums[i] == nums2[max]) { result[k++] = i; } }

以下代码就不会

int[] result = new int[2]; int k = 0; for ( int i = 0; i < nums.length; i++) { if (nums[i] == nums2[min] || nums[i] == nums2[max]) { result[k ++] = i; } }

这是为什么呢？原因是前者当nums2[min] nums2[max]相等的时候，前者代码同时加了两次.比如输入数列为[-5, -4, -4, 90] target = -8, 也就是result[0] = result[1] = 1， result[2] = result[3] = 1 result当然溢出。而用或的时候，最多加两次。当然离不开题目的前提，“You may assume that each input would have exactly one solution.”

Array 88

提高1：修改两数组之一的特殊性

因为在nums1上面修改，当nums1剩的值比nums2剩的值多的时候，其本身就不用改变。因此当两个array的index中的一个到了0之后，只需要在nums2没到0的情况下把剩下的复制进去，而不用管nums1

Array 118 Pascal’s Triangle

提高1：充分获取数列特点，比如第i个数列个数和i有关系

提高2：首行的特殊性

已经意识到了第一二行有特殊特点，但我只是单独create这两行数列，深入发掘会知道，无需单独建。主要代码如下

for (int i = 0; i < numRows; i++) { List<Integer> newrow = new ArrayList<Integer>(); for (int j = 0; j < i + 1; j++) { if (j == 0 || j == i) { newrow.add(1); } else { List<Integer> lastrow = result.get(i - 1); newrow.add(lastrow.get(j) + lastrow.get(j - 1)); } } result.add(newrow); }

其中的if (j == 0 || j == i)就是它的特殊性，找到收尾这个性质，代码可以减少很多行

上一篇：LinkedList 201604 题目小结

下一篇：PAT 1062