- swap the unordered neighbor, you can prove that after swap the correct order still hold for the previous series
- Binary SearchFind the first value greater then target
- Same as Unique pathExcept when init, every thing after obstacle is 0And in the double loop, if obstacle then 0
- Another outer loop from 3sum, need to check for duplicates in each loop
- hashmap记录inorder值于index的对应然后dfs，preorder第一个为root然后通过map找到root的index，和inStart，inEnd比较的到左右的大小然后再在preorder里找到根据左右大小找到left的root和right的root，如此迭代 public TreeNode build(int pre, int inStart, int inEnd, int[] preorder, HashMap<Integer,Integer> map){ if(pre >= preorder.length || inStart > inEnd) { return null; } TreeNode root = new TreeNode(preorder[pre]); if(inStart == inEnd) { return root; } int index = map.get(preorder[pre]); int leftSize = index - inStart; int rightSize = inEnd - index; int leftRoot = pre + 1; int rightRoot = pre + leftSize + 1; root.left = build(leftRoot, inStart, index-1, preorder, map); root.right = build(rightRoot, index+1, inEnd, preorder, map); return root; }
- 对撞型指针 int left = 0, right = numbers.length - 1; while (left < right) { int sum = numbers[left] + numbers[right]; if (sum < target) { left++; } else if (sum > target) { right--; } else { break; } } return new int[] {left + 1, right + 1};
- BacktrackingSimiliar to SubsetsUse if (i != idx && nums.get(i) == nums.get(i - 1)) { continue; }to avoid duplicates
- backtracking public void backtracking(List<List<Integer>> res, List<Integer> tmp, int num, int tmpSum, int k, int n) { if (tmp.size() == k && tmpSum == n) { res.add(new ArrayList<Integer>(tmp)); return; } for (int i = num; i <= 9; i++) { if (tmpSum + i <= n) { tmp.add(i); backtracking(res, tmp, i + 1, tmpSum + i, k, n); tmp.remove(tmp.size() - 1); } } }
- Two pointers因为可能一次要增加两个，所以外层也用while里程while要记录old_j，然后和j比较来确定duplicate的个数 int n = nums.length; int i = 0, j = 0; while (i < n) { int old_j = j; while (j < n && nums[j] == nums[old_j]) { j++; } nums[i++] = nums[old_j]; if (j - old_j > 1) { nums[i++] = nums[old_j]; } if (j == n) { break; } } return i;
- 上下左右4个变量 while(xh > xl && yh > yl){ int x, y; for(x=xl, y=yl; x<xh; x++) res.add(matrix[y][x]); for(x=xh-1, y=yl+1; y<yh; y++) res.add(matrix[y][x]); for(x=xh-2, y=yh-1; x>=xl && y>yl; x--) res.add(matrix[y][x]); for(x=xl, y=yh-2; y>yl && x<xh-1; y--) res.add(matrix[y][x]); xl++; xh--; yl++; yh--; }
- Two pointers for (i = 0; i < n; i++) { while (j < n && sum < s) { sum += nums[j]; j++; } if (sum >= s) { res = Math.min(res, j - i); } sum -= nums[i]; }
- counting sort?把值为i的放到i - 1位置上最后遍历，不对应的就是缺失的 for (int i = 0; i < nums.length; i++) { while (nums[i] != i + 1 && nums[i] != nums[nums[i] - 1]) { int tmp = nums[i]; nums[i] = nums[tmp - 1]; nums[tmp - 1] = tmp; } } List<Integer> res = new ArrayList<Integer>(); for (int i = 0; i < nums.length; i++) { if (nums[i] != i + 1) { res.add(i + 1); } }
- 上下左右4个变量 while (left <= right) { // top for (int i = left; i <= right; i++) { matrix[top][i] = cnt; cnt++; } top++; // right for (int i = top; i <= bottom; i++) { matrix[i][right] = cnt; cnt++; } right--; // bottom for (int i = right; i >= left; i--) { matrix[bottom][i] = cnt; cnt++; } bottom--; // left; for (int i = bottom; i >= top; i--) { matrix[i][left] = cnt; cnt++; } left++; }
- 通过循环的询问可以找到candidate，每次询问排除两者之一最后检查一下这个candidate是否valid int candidate = 0; for(int i = 1; i < n; i++){ if(knows(candidate, i)) { candidate = i; } } for(int i = 0; i < n; i++){ if(i != candidate && (knows(candidate, i) || !knows(i, candidate))) { return -1; } } return candidate;
- Similar to maximum subarray II with left and right array, the only difference is one of them can be 0 (left[0] = 0 and right[n - 1] = 0)
- Binary Search1. Treat as a 1-D array2. find the last start less then target, then binary search
- • state: f[x][y]从起点走到x,y的min• function: f[x][y] = min(f[x-1][y], f[x][y-1]) + A[x][y]• intialize: f[i][0] = sum(0 - i) f[0][i] = sum(0 - j)• answer: f[n-1][m-1]
- k = k%n; reverse(nums,0,n-k-1); reverse(nums,n-k,n-1); reverse(nums,0,n-1);
- 先swap upside down，再symmetric （转置） // first upside down for(int i=0; i<n/2; i++){ for(int j=0; j<n; j++){ int temp = matrix[i][j]; matrix[i][j] = matrix[n-1-i][j]; matrix[n-1-i][j] = temp; } } // then swap symmetrically for(int i=0; i<n; i++){ for(int j=i+1; j<n; j++){ int temp = matrix[i][j]; matrix[i][j] = matrix[j][i]; matrix[j][i] = temp; } }
- Backtrackingsort the array first, during backtracking, tmpSum, use this if (i != idx && candidates[i] == candidates[i - 1]) { continue; }to avoid duplicates