- two pointers for (i = 0; i < n; i++) { while (j < n && nums[j] == val) { j++; } if (j == n) { break; } nums[i] = nums[j]; j++; }
- Binary SearchRemember the graph!Choose the last number as targetthe condition is the first number less then the target
- for (i = 0; i < n; i++) { while (j < n && !set.contains(s.charAt(j))) { set.add(s.charAt(j)); j++; } max = Math.max(max, j - i); set.remove(s.charAt(i)); }
- sort 并用two pointers while (i < nums1.length && j < nums2.length ) { if (nums1[i] < nums2[j]) { i++; } else if (nums1[i] > nums2[j]) { j++; } else { res.add(nums1[i]); i++; j++; } }
- 比Shortest Word Distance I 多了一个word1.equals(word2)的条件 for (int i = 0; i < words.length; i++) { if (words[i].equals(word1) || words[i].equals(word2)) { if (index != -1 && (word1.equals(word2) || !words[index].equals(words[i]))) { min = Math.min(i - index, min); } index = i; } }
- Use Sieve of Eratosthenes algorithm public int countPrimes(int n) { boolean[] isPrime = new boolean[n]; for(int i = 2; i < n; i++) { isPrime[i] = true; } for(int i = 2; i * i < n; i++) { if(!isPrime[i]) { continue; } else { for(int j= i * i; j < n; j += i) { isPrime[j] = false; } } } int counter = 0; for(int i = 2; i < n; i++) { if(isPrime[i]) { counter++; } } return counter; }
- 按照公式不断循环但是要避免死循环，这里n=4就会进入死循环一种更好的方法就是快慢指针判断死循环
- 我当时的做法是一个hashmap, key是值，val是list of 值的 position，然后没来一个相同的值，判断他和所有的pos是不是冲突一种更简单的方法是双循环for i, j， 每次i循环用3个hashset检查第i行, 第i列和第i个方块 for(int i = 0; i<9; i++){ HashSet<Character> rows = new HashSet<Character>(); HashSet<Character> columns = new HashSet<Character>(); HashSet<Character> cube = new HashSet<Character>(); for (int j = 0; j < 9;j++){ if(board[i][j]!='.' && !rows.add(board[i][j])) return false; if(board[j][i]!='.' && !columns.add(board[j][i])) return false; int RowIndex = 3*(i/3); int ColIndex = 3*(i%3); if(board[RowIndex + j/3][ColIndex + j%3]!='.' && !cube.add(board[RowIndex + j/3][ColIndex + j%3])) return false; } }
- O(n）的方法是用一个hashmapO(1)的方法是先在后面连一个新的然后第二次遍历赋random的值并取下来连城新的
- 1. HashSet2. Sort and two pointers merge3. Sort and binary search
- Use 2 hashmap starts and endsthen for (int i = 0; i < length; i++) { if (starts.containsKey(i)) { val += starts.get(i); } res[i] = val; if (ends.containsKey(i)) { val -= ends.get(i); } }也有一种tricky一点的方法，start index存val，end + 1存 - val， 然后一路求和过来就可以
- 先找个地方insert （binary search 可以，但是对时间复杂度没有影响）然后在从头merge interval就好了
- hashmap，把每个str sort一下最后hashmap 编程list<list<>>的时候可以这样new ArrayList<List<String>>(map.values());
- Using stack to store indexfor loop if height[i] > height[stack.peek()], pushelse pop until stack is empty or height[stack.peek()] < height[i]area = (i - idx) * height[i]don't forget to deal with the remaining element in stack in the end
- // 这个问题在面试中不会让实现完整程序 // 只需要举出能够最坏情况的数据是 [1,1,1,1... 1] 里有一个0即可。 // 在这种情况下是无法使用二分法的，复杂度是O(n) // 因此写个for循环最坏也是O(n)，那就写个for循环就好了 // 如果你觉得，不是每个情况都是最坏情况，你想用二分法解决不是最坏情况的情况，那你就写一个二分吧。 // 反正面试考的不是你在这个题上会不会用二分法。这个题的考点是你想不想得到最坏情况。
- keep an index for record the most recent index for both words for (int i = 0; i < words.length; i++) { if (words[i].equals(word1) || words[i].equals(word2)) { if (index != -1 && !words[index].equals(words[i])) { min = Math.min(i - index, min); } index = i; } }
- • state: f[x][y]从起点走到x,y的最短路径• function: f[x][y] = min(f[x-1][y], f[x][y-1]) + A[x][y]• intialize: f[i][0] = sum(0,0 ~ i,0) f[0][i] = sum(0,0 ~ 0,i)• answer: f[n-1][m-1]
- 对撞型指针 for(int i = 0; i < nums.length; i++){ int lo = i + 1; int hi = nums.length - 1; while(lo < hi){ if (nums[lo] + nums[hi] < target - nums[i]) { res += hi - lo; lo++; } else { hi--; } } }
- 和preorder那题相似，只是从后往前遍历的。还是用inorder来的到左边和右边的size，用postorder来的到root public TreeNode build(int[] inorder, int[] postorder, int inStart, int inEnd, int post, HashMap<Integer, Integer> map){ int index = map.get(postorder[post]); int leftSize = index - inStart; int rightSize = inEnd - index; int left = post - rightSize -1; int right = post - 1; TreeNode root = new TreeNode(postorder[post]); if(leftSize > 0) { root.left = build(inorder, postorder, inStart, index-1, left, map); } if(rightSize > 0) { root.right = build(inorder, postorder, index+1, inEnd, right, map); } return root; }
- 首先找到最后一段递减的区间反转这段区间然后从这段区间的开头开始找到第一个比这段区间前一个值大的值，交换 int i = len - 1; while(i > 0 && nums[i] <= nums[i - 1]) { i--; } if(i == 0) { Arrays.sort(nums); return; } for(int j = 0; j < (len - i) / 2; j++) { swap(nums, i + j, len - 1 - j); } for(int j = i; j < len; j++){ if(nums[j] > nums[i - 1]) { swap(nums, j, i - 1); break; } }