Goolloo

推导一下公式 ``` hashBase = 1658598167 needleHashBase = hashStep ^ (needle.length - 1) hash = hash - charToRemove * needleHashBase => (hash - charToRemove * needleHashBase) % hashBase // this is...

### 76 Java 版 ```java public String minWindow(String s, String t) { Map need = new HashMap(); Map window = new HashMap(); for (char c : t.toCharArray()) { need.put(c, need.getOrDefault(c,...

### 76 Java 通过减数法节省一个Map ```java public String minWindow(String s, String t) { Map validCharToCountMap = new HashMap(); for(char c : t.toCharArray()) { validCharToCountMap.put(c, validCharToCountMap.getOrDefault(c, 0) + 1); } // moving...

来个最夸张的Java LinkedHashMap版本，没有一丝操作，所以面试也不可以用，lol Constructor的参数分别是初始容量，扩容的比例阈值（0～1），排序机制——true按访问排序，false按插入排序 因为容量最大只会到capacity+1，所以设置初始容量capacity+2和100%阈值，就永远不会扩容了。 ```java class LRUCache { private LinkedHashMap map; public LRUCache(int capacity) { map = new LinkedHashMap(capacity + 2, 1, true) { protected boolean removeEldestEntry(Map.Entry eldest) { return...

```java int lengthOfLIS(int[] nums) { // 定义：dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度 int[] dp = new int[nums.length]; // base case：dp 数组全都初始化为 1 Arrays.fill(dp, 1); for (int i = 0; i < nums.length;...

```java // envelopes = [[w, h], [w, h]...] public int maxEnvelopes(int[][] envelopes) { int n = envelopes.length; // 按宽度升序排列，如果宽度一样，则按高度降序排列 Arrays.sort(envelopes, new Comparator() { public int compare(int[] a, int[] b) {...

Note: 236的解法，当LCA是pq其中一点情况时，会跳过剩余的子树。 检查pq找到以后直接返回的解法，必须搜索到pq两个node，但是能跳过剩余未搜索的树。 两种解法互相有tradeoff，没有完美解🙃

笔记： partition 里面有`while(i

### Java, 0-indexed binary search ```java class Solution { private int[] sums; private int sum; private Random random; public Solution(int[] w) { sums = new int[w.length]; random = new Random();...

捉个小虫，最后恢复后一半链表的时候不需要更改前一半的最后一个node。也就是相对于`q.next = reverse(headOfReversedSecondHalf)`，直接使用`reverse(headOfReversedSecondHalf)`。 根据你画的反转过的链表图，其实前一半最后一个节点一直指向第二半的第一个节点。 ``` 1→2→3→4→3→2→1 ↓ 1→2→3→4→3←2←1 ``` 所以最后只需要再次把后一半链表反转足矣 ```cpp boolean isPalindrome(ListNode head) { ListNode slow, fast; slow = fast = head; while (fast != null && fast.next !=...