Array201604總結(jié)

2019-11-08 02:07:45

字體：大中小

供稿：網(wǎng)友

Array26

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

2.Else If 在修改當(dāng)前array時候注意改后的值對當(dāng)前條件句的影響

一下是一個把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循環(huán)第一個if里面如果沒有后兩個else，則在[1,1,2,3]會出狀況因為當(dāng)i = 2也就是nums[2]執(zhí)行完畢,nums會變?yōu)閇1,2,3,3]，如果沒有else if則直接跳跳入三行以后的那個if,則結(jié)果變?yōu)閇1,2,3,3] index = 4

Array 1 Two sum

1. 需要return indices的時候，只需要找result的兩個值的位置就行了

2. 沒必要寫一個對應(yīng)index的二維數(shù)組，只要不在原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; }

應(yīng)該用nums.clone(),得出了兩個數(shù)值再放在原數(shù)組里查找位置就可以

3. 最初想法，沒有考慮負(fù)數(shù)情況 (主要看第二個for循環(huán)對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循環(huán)兩次 O(n^2)

因此，應(yīng)該想到排序后從最右面和最左面開始找，這也是求two sum的基本思想才對。

4. 查找index溢出

以下代碼會發(fā)生溢出

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; } }

這是為什么呢？原因是前者當(dāng)nums2[min] nums2[max]相等的時候，前者代碼同時加了兩次.比如輸入數(shù)列為[-5, -4, -4, 90] target = -8, 也就是result[0] = result[1] = 1， result[2] = result[3] = 1 result當(dāng)然溢出。而用或的時候，最多加兩次。當(dāng)然離不開題目的前提，“You may assume that each input would have exactly one solution.”

Array 88

提高1：修改兩數(shù)組之一的特殊性

因為在nums1上面修改，當(dāng)nums1剩的值比nums2剩的值多的時候，其本身就不用改變。因此當(dāng)兩個array的index中的一個到了0之后，只需要在nums2沒到0的情況下把剩下的復(fù)制進(jìn)去，而不用管nums1

Array 118 Pascal’s Triangle

提高1：充分獲取數(shù)列特點(diǎn)，比如第i個數(shù)列個數(shù)和i有關(guān)系

提高2：首行的特殊性

已經(jīng)意識到了第一二行有特殊特點(diǎn)，但我只是單獨(dú)create這兩行數(shù)列，深入發(fā)掘會知道，無需單獨(dú)建。主要代碼如下

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)就是它的特殊性，找到收尾這個性質(zhì)，代碼可以減少很多行

上一篇：LinkedList 201604 題目小結(jié)

下一篇：PAT 1062