- Using prices[i] - prices[i - 1] is same to find the maximum subarray int profit = 0;; int max = 0; for (int i = 1; i < prices.length; i++) { if (profit <= 0) { profit = prices[i] - prices[i - 1]; } else { profit += prices[i] - prices[i - 1]; } max = Math.max(max, profit); }
- Hashmap store previous value and indexor sort and use two pointers
- 最简单的做法是通过swap把每个数字放到自己的位置上，比如5就放到idx = 4的地方，第一个不符合的位置就是缺的位置因为每个数字最多通过2次就能换到适当的位置上所以时间是O(n)，空间是O(1)也可以用union-find做，但是代码过于复杂
- DPinit: 0, 1then add 1 to the head写出2进制来就可以找到规律
- Every level has a stringbuilderuse a flag to determine the direction
- greey int sum = 0; int max = Integer.MIN_VALUE; for (int i = 0; i < nums.length; i++) { if (sum <= 0) { sum = nums[i]; } else { sum += nums[i]; } max = Math.max(max, sum); }
- 首先要弄清两个function的使用情况来确定用什么数据结构用Binary Index Tree会比segment tree写起来更简单，更省空间，但是会比较难理解
- use a preProd，then loop from right to left, having a cumulated prod variable int prod = 1; for (int i = n - 1; i >= 0; i--) { res[i] = prod * preProd[i]; prod *= nums[i]; }
- if(n%4 == 0) return false; else return true;
- BacktrackingKeep a counter and tmp stringeach step you have two ways: keep the char, add counter to tmp string and set counter to 0, or abbreviate it and increase the counter
- If already sorted, using binary searchbinary search: using idx as search range, h can be obtained by len - idx, then check if mid > h or mid < h or mid = hO(n) solution using hashmap count each number's apperance
- There is a formula for thatnum - 9 * (int)Math.floor((num - 1) / 9)
- int ones = 0; while(n != 0) { ones = ones + (n & 1); n = n>>>1; } return ones;
- O(n) iteration can do the job, the problem is edge cases: duplicates, lower == upper and overflow
- if(i < s.length() - 1 && hm.get(s.charAt(i)) < hm.get(s.charAt(i + 1))) { res -= hm.get(s.charAt(i));} else { res += hm.get(s.charAt(i)); }
- Divide and conquerFind character that occur less then k, using it to split the string int[] counts = new int[26]; for (char c: s.toCharArray()) { counts[c - 'a']++; } for (int i = 0; i < 26; i++) { if (counts[i] > 0 && counts[i] < k) { int max = 0; String[] subs = s.split((char)(i + 'a') + ""); for (String sub: subs) { max = Math.max(max, longestSubstring(sub, k)); } return max; } } return s.length();https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/
- Backtracking + 记忆化搜索类似区间型DP状态转移复杂，从大状态搜索到小状态搜索所有可能性，得到的结果如果对方不能赢，你就赢
- Use carryDon't forget to include carry time and check carry in the end
- dummy headusing cur.next not curhttps://leetcode.com/problems/insertion-sort-list/
- chap-1: Si deux normes sont équiva-lentes à une même troisième norme, alors elles sont équivalentes entre elles.