[每天两道题]坚持找到工作为止

140. Word Break II
这道题是难题里面算简单的，我认为可能不应该是hard难度。
首选思路一看就是回溯法。有了132的基础，我们很快就能想到，每次，我们从一个点把s切成两半，若是左边s[start, i]是字典里的单词，那么我们就递归地继续去看 能不能继续切s[i + 1, len]。所以我们这个start就是用来标记切点的，一开始我们从start = 0开始切，一直试到s.len。也就是试一试整个字符串是不是在字典里。
然后递归的结束条件就是start == s.len也就是我们前面都切完了，此时我们用于记录的list<string> curr里面就是一组答案。这个题出得不太好的地方就是非要我加工一下返回成一个字符串，感觉是硬凑了一个难度，其实返回一个lis<list<string>>能有什么不同吗？

剩下的就是标准的回溯写法了，相信若是你也跟我一样是一道一道刷过来的，应该对回溯模版写得已经非常熟练了。

1. class Solution {
   
2.      List<String> rs = new ArrayList<>();
   
3.     public List<String> wordBreak(String s, List<String> wordDict) {
   
4.         helper(s, wordDict, new ArrayList<>(), 0);
   
5.         return rs;
   
6.     }
   
7.    
   
8.     private void helper(String s, List<String> d, List<String> curr, int start) {
   
9.         //System.out.println(start + " " + curr);
   
10.         if(start == s.length()){
    
11.             StringBuilder sb = new StringBuilder();
    
12.             for(String str : curr) {
    
13.                 sb.append(str).append(" ");
    
14.             }
    
15.             
    
16.             rs.add(sb.toString().trim());
    
17.             return;
    
18.         }
    
19.         
    
20.         for(int i = start + 1; i <= s.length() ; i++) {
    
21.             String sub = s.substring(start, i);
    
22.             if(d.contains(sub)) {
    
23.                 curr.add(sub);
    
24.                 helper(s, d, curr, i);
    
25.                 curr.remove(curr.size() - 1);
    
26.             }
    
27.         }
    
28.     }
    
29. }

复制代码

139. Word Break
这道题有了131的基础，也非常简单，这是我很难得一遍就free bug过的题。
一看排列组合，但是只让你确认有没有答案，肯定就是dp了。
这个题就是个一维dp，dp[i] = t /f表示s[0,i]有没有答案。

假设我们现在要看s[0,i]这个字符串，我们想想怎么缩小问题规模，从后面看，若是s[j, i]这个字符串在字典里， 那么显然dp[i] = dp[j]。也就是dp[i]有没有答案只取决于s[0,j]有没有答案，这样就缩小了问题规模，转移方程也就写好了
dp[i] = dic.contains(s[j, i]) && dp[j]

初始化，我们多定义一位空位dp[0]，因为我们需要它去取完整的字符串，初始化我们设置dp[0] = ture;

所以代码就是

1. class Solution {
   
2.     public boolean wordBreak(String s, List<String> wordDict) {      
   
3.         int len = s.length();
   
4.         
   
5.         boolean[] dp = new boolean[len + 1];
   
6.         
   
7.         dp[0] = true;
   
8.         
   
9.         for(int i = 1; i < dp.length; i++) {
   
10.             for(int j = i ; j >= 0; j--) {
    
11.                 String sub = s.substring(j,i);
    
12.                 if(wordDict.contains(sub) && dp[j]) {
    
13.                     dp[i] = true;
    
14.                 }
    
15.             }
    
16.         }
    
17.         
    
18.         return dp[len];
    
19.     }
    
20. }

复制代码

138. Copy List with Random Pointer
这个题也挺重要的，也挺无聊的。其实它就是133. Clone Graph，复制一个图，基本上照搬答案即可。当然本题有多种解法，也有不需要map 的解法，但是我没有写。有兴趣的可以深研究一下。

我定义了一个map保存一下已经生成了哪些node的clonenode，这样做的目的是保证不会重复生成新的错误节点。
然后我们先遍历一遍原linkedlist，不考虑random指正，只产生复制节点，并且把它们的next都链接起来。

然后我们再遍历一遍，把random链接好，但是此时我们就不用产生新的节点了，直接从map取出已经产生好的节点即可。

1. /*
   
2. // Definition for a Node.
   
3. class Node {
   
4.     int val;
   
5.     Node next;
   
6.     Node random;
   
7. 
   
8.     public Node(int val) {
   
9.         this.val = val;
   
10.         this.next = null;
    
11.         this.random = null;
    
12.     }
    
13. }
    
14. */
    
15. 
    
16. class Solution {
    
17.     public Node copyRandomList(Node head) {
    
18.         if(head == null) return null;
    
19.         Map<Node, Node> map = new HashMap<>();
    
20.         Node newHead = new Node(head.val);
    
21.         map.put(head, newHead);
    
22.         
    
23.         Node p = head;
    
24.         Node q = newHead;
    
25.         
    
26.         p = p.next;
    
27.         while(p != null) {
    
28.             Node temp = new Node(p.val);
    
29.             q.next = temp;
    
30.             map.put(p, temp);
    
31.             
    
32.             p = p.next;
    
33.             q = temp;
    
34.         }
    
35.         
    
36.         p = head;
    
37.         q = newHead;
    
38.         
    
39.         while(p != null) {
    
40.             q.random = map.get(p.random);
    
41.             
    
42.             p = p.next;
    
43.             q = q.next;
    
44.         }
    
45.         
    
46.         return newHead;
    
47.     }
    
48. }

复制代码

137. Single Number II
这道题我感觉还是挺难的，因为位操作的技巧确实不熟悉。

不同于上一道题，本题不能用异或来解答。所以办法是这样的，假设数组是 [13, 13, 13, -14]，那么我可以先统计个位数的数字[3, 3, 3, 4] 。
然后我们把它们加起来对3取模，是不是就可以过滤出4了呢？

但是很快发现不行，因为3 + 3+ 3+ 4 =  13 % 3 = 1。显然不是我们想要的答案，而且这个符号怎么处理呢？
但是很快发现，十进制不行，但是二进制是可行的，比如数列是[3 3 3 4] 那么二进制就是 [11, 11 , 11, 100] 那么我就取每一个二进制的个位数相加 再对3取模
1 + 1+ 1 + 0 = 3 % 3 = 0 显然就是最后答案的二进制的个位数，继续计算“十位数” 1 + 1 + 1 + 0 = 3 % 3 = 0，"百位数 " = 1 % 3 = 1
所以最后拼出来的二进制数字就是100 = 4，显然是可以的。
而且这样我们就不用考虑负数了，因为负号在二进制计算机里也是用同样的位数来表达的。（补码）

所以，我最后就可以先把每一个数字变成二进制，然后分别计算它们每一个位置上的二进制的数字的和，再对3取模，余数就是最后答案对应位置的二进制位数，最后就是我们要的数字了。

不过思路有了，代码也不太好写。有几个技巧，
第一我们要写一个循环从0到32，因为我们每一个int一共有32位。然后我们第二个循环就是遍历数组，其实就是要取出每一个数字里第i个位置的二进制位数。
然后就是如何取位数。
首先，我们把数字 num 右移 i 位。这样，我们就把要取出来的二进制的位数放到了最后一位上，比如1011，我们要取中间这个0，我们就右移2次，0010。然后我们把右移后的数字和1 取“相位与”。也就是 0010 & 0001 = 0000。
相信你也发现了，这个技巧其实就是二进制数字取最后一位位数，方法就是 num & 1。

这样我们就取出num在第i位的二进制数字是什么了，然后我们把它们都加起来  sum += (num >> i) & 1
加起来之后，对3取模，就是我们要的最后答案种第i位的数字，但是我们怎么把它再回填进答案呢？
方法就是左移i次，比如0001 应该是左数第二个数字，所以我们左移两次，0100吗，然后把它相位或回最后答案。也就是 rs | 0100。就是我们要的结果了。
所以最终代码就是

1. class Solution {
   
2.     public int singleNumber(int[] nums) {
   
3.         int rs = 0;
   
4.         for(int i = 0; i <32; i++) {
   
5.             int sum = 0;
   
6.             for(int num : nums) {
   
7.                 sum += (num >> i) & 1;
   
8.             }
   
9.             rs |= (sum % 3) << i;
   
10.         }
    
11.         return rs;
    
12.     }
    
13. }

复制代码

141 142. Linked List Cycle I && II
这两个题放一起讨论。本题本人人生第一次面算法题的时候店面原题。记忆很深刻，后来还手推了一下原理。
第一题就是球有没有环，我们用快慢指针，也就是龟兔赛跑法，若是有环，那么最终快指针一定能追上慢指针。若是走到了尽头，说明没有环。

好了，接下来就是如何找出循环的入口。
假设起点到入口的长度为x,
快慢指针相遇的位置距离入口的长度为y。
环的长度为l。
所以，相遇的时候，假设慢指针走了m圈，快指针走了n圈。
那么相遇的时候，
快指针一共走了  x + n * l + y 步
慢指针一共走了  x + m * l + y 步

由于快指针走的步数是慢指针的2倍，所以有 2 ( x + m * l + y ) = x + n * l + y
整理后有 x + y = (n - 2m)l。
也就是说，最后二者相遇的地方，到起点的长度，一定等于环的倍数，其实若是第一相遇也就是环的长度。
那么我们想要找入口，其实也就是找x是多少。 我们不用真的计算出x的长度，由上面公式可知，最后第一次相遇的位置，到环入口的长度是x，同时x也是起点到入口的长度。那么此时，若是我们在快慢指针相遇后，再重新用一个新指针p3从起点出发，一步一步地走，同时慢指针也继续从相遇点走，那么当p3和慢指针二者相遇的时候，就一定是环的入口了，因为他们都走了x步。

所以逻辑就是，先用快慢指针相遇一次，然后再从起点开一个新的慢指针，继续前进，当新老两个慢指针相遇，就是环的入口。

代码就是

1. public class Solution {
   
2.     public ListNode detectCycle(ListNode head) {
   
3.         if(head == null || head.next == null) return null;
   
4.         ListNode fast = head.next;
   
5.         ListNode slow = head;
   
6.         
   
7.         while(fast != slow) {
   
8.             if(fast == null || fast.next == null) {
   
9.                 return null;
   
10.             }
    
11.             
    
12.             fast = fast.next.next;
    
13.             slow = slow.next;
    
14.         }
    
15.         
    
16.         fast = head;
    
17.         while(fast != slow.next) {
    
18.             fast = fast.next;
    
19.             slow = slow.next;
    
20.         }
    
21.         return fast;
    
22.     }
    
23. }

复制代码

143. Reorder List
这个题还是考链表的翻转，重新链接。我感觉链表的考点挺单一的，都是让你做各种拆解再重连。做法也是画清楚过程就可以了。

本题还是一样，其实就是把链表后半段截取出来，然后翻转，再一个一个间隔地插入到前半段中。所以是个缝合怪题，先考快慢指针找中点，然后考翻转，最后考merge链表。

基本上就是三个esay题的代码照搬一遍

1. lass Solution {
   
2.     public void reorderList(ListNode head) {
   
3.         ListNode fast = head;
   
4.         ListNode slow = head;
   
5.         
   
6.         while(slow != null && fast != null && fast.next != null && fast.next.next != null) {
   
7.             fast = fast.next.next;
   
8.             slow = slow.next;
   
9.         }
   
10.         
    
11.         ListNode trail = slow.next;
    
12.         slow.next = null;
    
13.         
    
14.         ListNode trailHead = null;
    
15.         while(trail != null) {
    
16.             ListNode temp = trail.next;
    
17.             trail.next = trailHead;
    
18.             trailHead = trail;
    
19.             trail = temp;
    
20.         }
    
21.         
    
22.         ListNode curr = head;
    
23.         while(trailHead!= null && curr != null) {
    
24.             ListNode currNext = curr.next;
    
25.             ListNode trailNext = trailHead.next;
    
26.             
    
27.             curr.next = trailHead;
    
28.             trailHead.next = currNext;
    
29.             
    
30.             curr = currNext;
    
31.             trailHead = trailNext;
    
32.         }
    
33.       
    
34.     }
    
35. }

复制代码

146. LRU Cache
linkedhashmap可以简单解答。不过最好还是老老实实写linkedlist比较好。
此题就是定义一个双向链表，和一个hashmap，map存key和listnode。 主要用于快速取出node，以及判断当前内存的大小。linkedlist用于记录试用顺序。

我的写法是，每次访问某一个节点，都把它往list的尾巴后面放。这样尾巴的节点就是最新的，而head的节点就是最旧没有访问过的，所以当我们需要删除的时候，就删除head节点即可。

注意这里有一个坑就是update的情况，若是put两次key是一样的，但是value不同，我们要更新而不是增加。当然这个设定其实是降低难度，否则map就不好用了。

这样我们就完成了，代码的时候注意，最好把具体功能的代码都分开，这样比较清晰。

1. class LRUCache {
   
2.     Map<Integer, ListNode> map = new HashMap<>();
   
3.     int size = 0;
   
4.     ListNode head;
   
5.     ListNode trail;
   
6.     public LRUCache(int capacity) {
   
7.         size = capacity;
   
8.         head = new ListNode();
   
9.         trail = new ListNode();
   
10.         head.next = trail;
    
11.         trail.pre = head;
    
12.         
    
13.         map.put(-1, head);
    
14.         map.put(-2, trail);
    
15.     }
    
16.    
    
17.     public int get(int key) {
    
18.         if(!map.containsKey(key)) return -1;      
    
19.         moveNodeToTrail(key);        
    
20.         return map.get(key).val;
    
21.     }
    
22.    
    
23.     public void put(int key, int value) {
    
24.         if(map.containsKey(key)) {
    
25.            moveNodeToTrail(key);
    
26.            ListNode temp = map.get(key);
    
27.            temp.val = value;
    
28.            map.put(key, temp);
    
29.            
    
30.            return;
    
31.         }
    
32.         if(map.size() - 2 == size) {
    
33.             deleteNode(head.next);
    
34.         }
    
35.         
    
36.         ListNode newNode = new ListNode(key, value);
    
37.         map.put(key, newNode);
    
38.         moveNodeToTrail(key);
    
39.     }
    
40.     private void deleteNode(ListNode node) {
    
41.         node.pre.next = node.next;
    
42.         node.next.pre = node.pre;
    
43.         map.remove(node.key);
    
44.     }
    
45.     private void moveNodeToTrail(int key) {
    
46.         ListNode node = map.get(key);
    
47.         
    
48.         ListNode pre = node.pre;
    
49.         ListNode next = node.next;
    
50.         
    
51.         if(pre != null && next != null) {
    
52.             pre.next = next;
    
53.             next.pre = pre;
    
54.         }
    
55.    
    
56.         trail.pre.next = node;
    
57.         node.pre = trail.pre;
    
58.         
    
59.         node.next = trail;
    
60.         trail.pre = node;   
    
61.     }
    
62. }
    
63. 
    
64. class ListNode {
    
65.     ListNode pre;
    
66.     ListNode next;
    
67.     int key;
    
68.     int val;
    
69.    
    
70.     public ListNode(){}
    
71.     public ListNode(int key, int val){
    
72.         this.key = key;
    
73.         this.val = val;
    
74.     }   
    
75. }
    
76. 
    
77. /**
    
78. * Your LRUCache object will be instantiated and called as such:
    
79. * LRUCache obj = new LRUCache(capacity);
    
80. * int param_1 = obj.get(key);
    
81. * obj.put(key,value);
    
82. */

复制代码

147. Insertion Sort List
也是linkedlist的操作题，据说比较难，但是我觉得还好。
有难度主要还是因为有删除操作，插入排除，动作是先找到要插入的位置，然后把node从原来的位置摘出来，再接回去。因为有摘出来的动作，所以就必须知道要摘除节点的上一个节点是什么的，好把断开的链条再接回去。没什么算法的东西，多画画图就清晰了。

代码

1. /**
   
2. * Definition for singly-linked list.
   
3. * public class ListNode {
   
4. *     int val;
   
5. *     ListNode next;
   
6. *     ListNode() {}
   
7. *     ListNode(int val) { this.val = val; }
   
8. *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
   
9. * }
   
10. */
    
11. class Solution {
    
12.     public ListNode insertionSortList(ListNode head) {
    
13.         ListNode dummy = new ListNode(-5001);
    
14.         dummy.next = head;
    
15.         
    
16.         ListNode curr = head;
    
17.         while(curr.next != null) {
    
18.          
    
19.             if(curr.next.val >= curr.val){
    
20.                 curr = curr.next;
    
21.             }else{
    
22.                 ListNode p1 = dummy;
    
23.                 while(p1 != null && p1.next != null &&
    
24.                       p1.next.val <= curr.next.val && p1.next != curr) {
    
25.                     p1 = p1.next;
    
26.                 }
    
27.             
    
28.                 ListNode temp1 = curr.next;//2
    
29.                 ListNode temp2 = curr.next.next;//1
    
30.                 ListNode temp3 = p1.next;//4
    
31.                
    
32.                 p1.next = temp1;
    
33.                 curr.next = temp2;
    
34.                 temp1.next = temp3;
    
35.             }
    
36.         }
    
37.         return dummy.next;
    
38.     }
    
39. }

复制代码

149. Max Points on a Line

这道题是数学题，很自然地想到计算y = ax  + b中的a和b，然后作为Key，每次遇到一个a,b相同的点，我们就计入value + 1。最后我们看哪个斜率的value最大即可。
这道题难度在于代码实现，起来有几个坑：
1、两个for循环，每次里循环取该点之后的点，也就是两两配对只要遍历一次。
2、我们并不是用一个大map来记录所有的点，而是每次定好一个p1，就建立一个新的map，只用于记录经过P1所有直线，每一个直线上面的点有多少个。这样的好处是，我们不需要计算b了（不理解的可以思考一下）。只需要计算斜率a即可。
3. 斜率a = x1 - x2 / y1 - y2。
这道题改过题目，过去点是有可能有重复的，但是现在点都不重复了，等于降低了难度，所以我们就不用考虑x1= x2 && y1 = y2的情况了。而且我们不用把a真的算出来，因为小数点精度可能难以控制，并且还要考虑y1 - y2 = 0这种特殊情况。为了简化，我们我们就存一个String = x1 - x2 + "-" + y1 - y2。
但是这么存，我们就要计算一下x = x1 - x2 和 y = y1 - y2，x和y的最大公约数，因为假如两个直线 ，斜率是 4 / 2 和2 / 1。它们其实在同一个直线上，但是4 / 2显然要计算一下，把x 和 y都除以最大公约数2.
4. 如何计算最大公约数。这个东西也是一个考题，就是欧几里得算法。gcd(a, b) = gcd(b, a %b)。这东西的数学证明各位自己自动搜索，证明有点复杂，代码倒是很简单必须背诵。

5.有了斜率，我们就可以添加进map了，每次更新map对应key的value。然后我们建一个临时的max，用于保存map中最大的value。当里循环结束的时候，这个max就是经过p1的直线中，包含的最多的点的数量。然后我们把max和最终rs比较，更新rs。
6.注意，max中保存的数字是不包含p1的点的数量，所以里循环结束更新rs的时候,max = max + 1;

代码

1. class Solution {
   
2.     public int maxPoints(int[][] points) {      
   
3.         if(points.length < 3) return points.length;
   
4.         int rs = 0;  
   
5.         for(int i = 0; i < points.length - 1; i++) {
   
6.             int[] p1 = points[i];
   
7.             Map<String, Integer> map = new HashMap<>();
   
8.             int max = 0;
   
9.             for(int j = i + 1; j < points.length; j++) {
   
10.                 int[] p2 = points[j];
    
11.                 int x = p1[0] - p2[0];
    
12.                 int y = p1[1] - p2[1];
    
13.                
    
14.                 int gcd = gcd(x, y);
    
15.                
    
16.                 x /= gcd;
    
17.                 y /= gcd;
    
18.                
    
19.                 String key = x + "-" + y;
    
20.                 map.put(key, map.getOrDefault(key, 0) + 1);
    
21.                 max = Math.max(max, map.get(key));
    
22.             }
    
23.             
    
24.             rs = Math.max(rs, max + 1);
    
25.         }
    
26.         return rs;
    
27.     }
    
28.    
    
29.     private int gcd(int a, int b){
    
30.         if(b == 0) return a;
    
31.         return gcd(b, a % b);
    
32.     }
    
33. }

复制代码

148. Sort List
本题我觉得挺难的，是比较难的中等难度题，已经比一些hard更难了。
首先linkedList比较容易实现的排序是归并排序，因为我们没法直接根据index取出某一个Node。也没法从后往前找节点。所以归并排序是最适合的。

归并排序分两步，我们每次把list拆成等分的两段，然后左右两段继续拆，直到拆到剩一个节点，然后我们开始合并左右两个List，此时问题就变成了合并两个sort linkedlist.
这样就做完了。

看着很简单，但是知识点挺邪门的，
第 一做肯定想不到用归并排序。这个只能依赖做题经验。
第二 如何merge sorted linkedlist我发现自己之前做的根本不是最优解，最优解有两个写法，一个是递归。另一个我更中意就是直接把list1,拼接到list2上，
第三 拆分就是快慢指针，找出中间点，有个小窍门是fast = head.next。这样slow.next最后就是right的head。否则你要多建一个pre节点。另外就是拆分，我们先递归右边部分，这样slow.next直接传入，不用建临时节点，然后再把slow.next = null，也就是断开，然后再去递归左边的节点。这样可以节省一些代码。

最后代码就是

1. class Solution {
   
2.     public ListNode sortList(ListNode head) {
   
3. 
   
4.         if(head == null || head.next == null) return head;
   
5. 
   
6.         ListNode fast = head.next;
   
7.         ListNode slow = head;
   
8.         while(fast != null && fast.next != null) {
   
9.             fast = fast.next.next;
   
10.             slow = slow.next;
    
11.         }
    
12.         ListNode right = sortList(slow.next);
    
13.         slow.next = null;
    
14.         ListNode left = sortList(head);
    
15.         
    
16.         return merge(left, right);
    
17.         
    
18.     }
    
19.     public ListNode merge(ListNode list1, ListNode list2) {
    
20.         ListNode head = new ListNode();
    
21.         ListNode node = head;
    
22.         
    
23.         while(list1 != null && list2 != null) {
    
24.             if(list1.val < list2.val) {
    
25.                 node.next = list1;
    
26.                 list1 = list1.next;
    
27.             }else{
    
28.                 node.next = list2;
    
29.                 list2 = list2.next;
    
30.             }
    
31.             node = node.next;
    
32.         }
    
33.         
    
34.         node.next = list1 != null ? list1 : list2;
    
35.         return head.next;
    
36.     }
    
37. }

复制代码