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

8. 4Sum
题目大意
给你一个数组，和一个目标值，从数组中找出四个数，其和等于目标值，返回所有这样的四个数的组合。

题目分析和解答

这个题就是ksum的最后一道了，面试中可以是一个很好的follow up。这个题如同3sum一样，就是再多一个循环。

思路还是，因为要在数组中找数字，并且是固定的四个，而且四个可以不连续，所以我们定义四个指针，并且给数组排序。

暴力解就是四个for循环，为了加快速度，我们进行一些剪枝。首先第一个数字 i ，我们可以只校验到nums.length - 3即可，因为它后面必须有三个数字。然后如同3sum，若是重复的数字我们都跳过。因为固定同样的数字，它的答案一定是重复的，所以必须排除 。
同理，固定第二个数字 j 如法炮制，只校验到length - 2。重复的跳过。

第三个和第四个数字，我们就直接定义两个指针，一个定义在 j+ 1， 一个定义在nums.length - 1。然后看四个数字之和sum和target目标值的大小，若是sum更大，说明hi太大了,hi -1往小了挪动，若是sum更小，说明lo太小了，lo++往大移动，若是sum == target，那么我们就找到了一个答案存起来。同样，我们都跳过重复都的数字，直到lo  hi相遇。

所以代码就是

1. class Solution {
   
2.     public List<List<Integer>> fourSum(int[] nums, int target) {
   
3.         List<List<Integer>> rs = new ArrayList<>();
   
4.         if(nums.length  < 4){
   
5.             return rs;
   
6.         }
   
7.         Arrays.sort(nums);
   
8.       
   
9.         for(int i = 0; i < nums.length - 3; i++){
   
10.             if(i > 0 && nums[i] == nums[i - 1]) continue;
    
11.             
    
12.             for(int j = i+ 1; j < nums.length - 2; j++){
    
13.                 if(j > i + 1 && nums[j] == nums[j - 1]) continue;
    
14.                 int lo = j + 1;
    
15.                 int hi = nums.length - 1;
    
16.                
    
17.                 while(lo < hi){
    
18.                     int sum = nums[i] + nums[j] + nums[lo] + nums[hi];
    
19.                     //System.out.println(String.format("i=%s j=%s lo=%s hi=%s sum =%s",i,j,lo,hi,sum));
    
20.                     if(sum == target){
    
21.                         rs.add(Arrays.asList(nums[i],nums[j],nums[lo],nums[hi]));
    
22.                         lo++;
    
23.                         hi--;
    
24.                         while(lo < hi && nums[lo] == nums[lo - 1]) lo++;
    
25.                         while(lo < hi && nums[hi] == nums[hi + 1]) hi--;
    
26.                     }else if(sum < target){
    
27.                         lo++;
    
28.                         while(lo < hi && nums[lo] == nums[lo - 1]) lo++;
    
29.                     }else{
    
30.                         hi--;
    
31.                         while(lo < hi && nums[hi] == nums[hi + 1]) hi--;
    
32.                     }
    
33.                 }
    
34.             }
    
35.         }
    
36.         return rs;
    
37.     }
    
38.    
    
39.    
    
40. }
    

复制代码

19. Remove Nth Node From End of List
题目大意
给你一个链表，和一个数字n，让你找出倒数第n个node，并且把它删除。
题目分析
这是一道很好的面试题。代码简单，但是逻辑很巧妙。
先分析一下解题思路，这个题给了我们链表，链表的题型，大都是找出某些node，或者让你重新链接节点，产生一个新的链表。这道题都涉及了，先让你找node，再让你重新链接。
链表一个最大的问题，就是你并不知道 链表有多长，那么想一次性找出第n个位置的node，就必须用快慢指针。这个套路非常重要，看到找node第一反应就是要去用快慢指针。
方法也很简单，让快指针先走n步，然后快慢一起走，当快指针到达终点，那么慢指针就一定在倒数第n个节点上。
此时就很简单了，我们把slow.next指向slow.next.next。链表的指针重新链是个很重要的考点，一定要熟悉各种操作的写法，必须背下来 － 如何删除一个节点，如何添加一个节点，翻转节点，复制一个节点，等等。

这个node.next =node.next.next就是删除一个节点的固定写法。

所以这道题代码就是

1. class Solution {
   
2.     public ListNode removeNthFromEnd(ListNode head, int n) {
   
3.         
   
4.         ListNode dummy = new ListNode();
   
5.         dummy.next= head;
   
6.         
   
7.         ListNode fast = dummy;
   
8.         ListNode slow = dummy;
   
9.         for(int i = 0; i < n; i++){
   
10.             if(fast == null) return null;
    
11.             fast = fast.next;
    
12.         }
    
13.         if(fast == null){
    
14.             return null;
    
15.         }
    
16.         
    
17.         while(fast.next != null){
    
18.             fast = fast.next;
    
19.             slow = slow.next;
    
20.         }
    
21.         slow.next = slow.next.next;
    
22.         return dummy.next;
    
23.         
    
24.     }
    
25.    
    
26. }
    

复制代码

20. Valid Parentheses
题目大意，给你一个字符串，然后让你验证，是不是所有括号都是合法闭合的。

题目分析和解答。

这个题很简单，但是思想很重要。首先分析题型，它给我们一个字符串，让我们所有的两个括号是否合法匹配。这道题严格来说也是找元素，但是我们不知道它要找多少个元素，因为验证括号合法与否，我们要保存所有的左括号，然后看它的右括号的位置是不是正确的。
在没有看到右括号之前，我们得一直保存左括号。并且验证的时候，还要验证

需要保存的元素数量可变的时候，就必须考虑实用某种数据结构。比如滑动窗口我们可以用deque。同样，找左边和右边的题目，比如找括号，或者找什么矩阵的左右两边，都可以考虑stack。

这个题就是经典的stack题，我们用一个stack保存左边，每次遇到左边就入栈，遇到右边就出栈，然后看看栈顶弹出的和当下右边的是否匹配，若是不匹配，就一定是有问题的。若是匹配就继续，直到走完最后一个字符。

这题还有几个难点，挺考验细节的，第一个是只有右括号的情况，所以我们在遇到右扩号的时候，在弹出栈之前要判断一下栈有没有值，没有值也要返回false。
然后就是只有左括号或左括号有多余的情况，我们要在循环结束后，看看stack是否还有值，若是还有没有匹配的左括号，也要返回false。
所以代码就是

1. class Solution {
   
2.     public boolean isValid(String s) {
   
3.         char[] sc = s.toCharArray();
   
4.         
   
5.         Stack<Character> stack = new Stack<>();
   
6.         for(int i = 0 ; i < sc.length; i++){
   
7.             char c= sc[i];
   
8.             if(c == '(' || c == '[' || c == '{'){
   
9.                 stack.push(c);
   
10.             }else {
    
11.                 if(stack.size() == 0) return false;
    
12.                 char left = stack.pop();
    
13.                 if((left == '(' && c != ')') ||
    
14.                   (left == '{' && c != '}') ||
    
15.                   (left == '[' && c != ']'))
    
16.                     return false;
    
17.             }
    
18.         }
    
19.         return stack.size() == 0;
    
20.     }
    
21. }

复制代码

21. Merge Two Sorted Lists 23. Merge k Sorted Lists
这两个题解法一模一样，所以放一起做。
给n个linkedlist，节点是已经排好序的，从小到大。让后让我们合并成一个，合并之后节点依然是从小到大排好序的。

题目分析和解答
先看解题思路，给了我们linkedlist，那么我们就要看它要考什么，然后我们看到要求我们产生一个新的链表。
通常，要求我们产生新的链表，还在再分两种情况，
一种是不允许产生新的节点，在原有的节点上重新链接，
一种是允许产生新的节点。

这个题是第二种情况，允许产生新的节点，那么这个题一般就不会涉及复杂的指针指向内容。而是重点放在如何查找对应的节点。

在连表中查找某一个节点，本质和array没有区别。所以我可以把链表转换成array，然后合并排序，再生产链表。只是这么做比较笨拙。
更好的思路就是我们再看看，n个array，我们要合并，还要求从小到大，意味着我们每次都要从n个linkedlist中取出一个节点，然后比较值，哪个值小，我们就存到新的linkedlist里面。

更进一步，比较大小，等于是我们是对n个node的值进行排序。所以，我们可以用priorityqueue帮助我们自动排序，每次取出pq的头部，就是最小的，然后把取出的节点的,next再存进pq。若是出去的节点没有next了，就不存了。然后再循环，取出pq的一个节点，然后存。
这样一直到pq里没有东西了，那么我们这道题就完成了，
所以代码就是

1. class Solution {
   
2.     public ListNode mergeKLists(ListNode[] lists) {
   
3.         ListNode dummy = new ListNode();
   
4.         PriorityQueue<ListNode> pq = new PriorityQueue<>( (a,b) -> {
   
5.             return a.val - b.val;
   
6.         });
   
7.         if(lists.length == 0) return dummy.next;
   
8.         for(ListNode node : lists){
   
9.             if(node == null) continue;;
   
10.             pq.offer(node);
    
11.         }
    
12.          
    
13.         ListNode head = new ListNode();
    
14.         dummy = head;
    
15.         while(pq.size() > 0){
    
16.             ListNode curr = pq.poll();
    
17.          
    
18.             head.next = new ListNode(curr.val);
    
19.             head = head.next;
    
20.             if(curr.next != null){
    
21.                 pq.offer(curr.next);
    
22.             }
    
23.         }
    
24.         return dummy.next;
    
25.     }
    
26. }
    

复制代码

22. Generate Parentheses
给一个数字n，产生一个包含n对括号的字符串，要求括号格式是合法的。

题目分析和解答
让我们产生字符串，那就是array的题，并且不是查找，而是产生array。产生array其实本质就是考树或者图了。因为array就是树或者图的一个路径。

所以这个题就是两个考点，
1、怎么生成树，
2、怎么去遍历这个树，以产生一些符合规则的路径。

生成树，回溯法一定是能用的 －每一次产生一个节点，然后看看它的孩子有哪些，然后递归地进入某一个孩子，重复看孩子的孩子。直到叶节点。然后再退回到上一层。
同样，这么生成，显然就是dfs，也就是先走到一格叶节点，再退回一步，走另一个分支，直到产生另外一个路径。

所以这个题的基础方向就是这么做了。
但是还有细节，那就是我们要让括号匹配是合法的。这种附加条件，其实就是剪枝的条件。我们当然可以不考虑括号是否合法，每一次生成一个节点，我们下一层我们永远产生两个孩子，一个“(”，一个“）”。这样树就是一个满二叉树，高度是n*2。然后我们用dfs遍历，走到头就校验一下合法性。

但是这么做肯定效率不高，能不能只走正确的路径呢？当然是可以的，观察一下合法性的规则，那就是半路上，左括号必须多于右括号，因为左括号必须先于右括号生成吗。然后左括号必须小于等于n，这也容易理解，因为n对括号就是n个左括号。
所以剪枝叶条件就是定义两个数left 、right ，记录左右括号的数量，然后left <= n的时候，我们才产生左括号。right < left的时候我们才产生右括号。
这样，我们就进行了剪枝，并且保证一定走在能产生合法结果的路径上。

所以代码就是 －

1. 
   
2. class Solution {
   
3.     public List<String> generateParenthesis(int n) {
   
4.         //(
   
5.         List<String> rs = new ArrayList<>();
   
6.         helper(n, 0, 0, new StringBuilder(), rs);
   
7.         return rs;
   
8.     }
   
9.     private void helper(int n, int l, int r, StringBuilder str, List<String> rs){
   
10.         
    
11.         if(str.length() == n * 2){
    
12.             
    
13.             rs.add(str.toString());
    
14.             return;
    
15.         }
    
16.         
    
17.         if(l < n){
    
18.             str.append("(");
    
19.             helper(n, l + 1, r, str, rs);
    
20.             str.deleteCharAt(str.length() - 1);
    
21.         }
    
22.         if(r < l){
    
23.             str.append(")");
    
24.             helper(n, l , r + 1, str, rs);
    
25.             str.deleteCharAt(str.length() - 1);
    
26.         }        
    
27.     }     
    
28. }
    

复制代码

随手点进来看了一下，楼主给你点小建议，你的代码格式可以参考https://google.github.io/styleguide/javaguide.html
就我看你的代码时而符合上面链接的格式，时而又不符合，就比如你这个         
if(str.length() == n * 2){
按照“正确”(打引号是因为这种东西没有一定的正确和错误之分，只是那些行业大佬们约定俗成的习惯)的格式应该是
if (str.length() == n * 2) {
我多打这两个空格你看着觉得没什么，但可能在一些面试官看来就是区别有经验和新手的分界线
建议养成习惯

howardhs03 发表于 2022-4-14 10:38
随手点进来看了一下，楼主给你点小建议，你的代码格式可以参考https://google.github.io/styleguide/javagu ...

感谢分享经验，我一定培养一下好习惯～

24. Swap Nodes in Pairs
给一个链表，要求两两翻转节点，若是剩余一个就不翻转。

题目分析和解答
这个题开始出现链表指针的操作了。给我们一个链表，这回不仅仅是找什么节点，而是要翻转一下链表。

翻转的操作需要三个指针，pre， curr和next。步骤如下。
0 . 初始状态 － pre -> curr -> next
1. 把pre的下一个节点，指向next。pre.next = next;  此时状态 curr/pre->next。也就是curr和pre 都指向了next。
2. 把curr下一个节点指向pre。curr.next =pre；此时状态 curr -> pre -> next; 也就是pre和curr翻转完成。
3.pre = next。这样我们就移动到了下一个需要翻转的位置了。新的curr = pre.next, next ＝ curr.next;然后再从1开始操作。

循环退出条件，就是curr 或者next为null。此时不足三个指针，自然也无法翻转了～
心得，翻转链表，一定需要三个节点；同样，画图是理清思路的唯一手段。
所以代码就是 ：

1. public ListNode swapPairs(ListNode head) {
   
2.         ListNode dummy = new ListNode();
   
3.         dummy.next = head;
   
4.         ListNode p = dummy;
   
5.         
   
6.         while(p.next != null && p.next.next != null)  {
   
7.             ListNode n1 = p.next;
   
8.             ListNode n2 = p.next.next;
   
9.             
   
10.             p.next = n2;
    
11.             n1.next = n2.next;
    
12.             n2.next = n1;
    
13.             
    
14.             p = n1;
    
15.         }
    
16.         return dummy.next;
    
17.     }

复制代码

25. Reverse Nodes in k-Group
题目大意
给一个链表，和一个数字k。让你以k长度为一组，翻转链表，若是剩余不足就不翻转。
比如 1 2 3 4 5.  k = 3。 那么就翻转前三个 3 2 1 4 5。后面两个4 5因为长度不足3所以不翻转。

题目分析和解答。
这个题是一个非常好的题，我若是考官，可能会用此题去为难其他面试者，哈哈哈～
此题需要你知道，如何翻转一整个链表。这个题目是206. Reverse Linked List.
翻转整个链表的方法我就不写在这里了，这个知识点很重要，一定要背诵，闭着眼睛也能写出来。

有了翻转整个链表，那么接下来自然而然就会想到，我们先把原来的链表截取出来一个k长的子链表，然后翻转这个链表，再把它接回去就好了。

比如 1 > 2 > 3 > 4> 5.  k = 3。那么我们先找到第一组的尾部，也就是3。然后把它指向null，也就是断开。此时链表状态是 1 > 2 > 3       4 > 5。
然后，我们翻转一下123。变成 3 > 2 > 1    4  > 5。
最后我们把它接回去 3 > 2 > 1 > 4 > 5
大功告成～

且慢，这个思路很好想，但是实现起来非常麻烦，因为把它翻转并不难，难的是，你要如何把它接回去。
接回去若是用指针记录的话，是非常麻烦的，上个例子中，由于我们要断开链表，所以我们要记录一下4 ，防止链表丢失，然后还要记录一下前一个链表的尾部，也就是dummy。然后再翻转，而且我还要记录下翻转之后的3 和1 ，用于接回去。也就是我们需要记录四个节点，然后两两把他们接回去。

所以，这里我看了看其他人的解法，认为最佳答案，是递归。
递归的关键，是每次我们翻转之后，原来子链表head 就变成了新的链表的尾部。
比如
1 > 2 > 3 > 4 > 5 > 6 > 7  k = 3
例子中，我们断开了 3和4  －  1 > 2 >3   4 > 5 > 6 > 7。
此时 1  > 2 > 3的head 就是1这个节点。
当调用子方法翻转完之后，head 还指向1，但是此时1变成了尾部
3 > 2 > 1    4 > 5 > 6 >7
那么1 的next指向谁呢？其实就是指向递归地下一段链表的新的头部。也就是，我们递归地先把后面处理了，得到下一个链表的头部之后，再它接回来。
按照例子就是
我递归地处理下一段4 5 6，先把他们断开
3 > 2 > 1   4 > 5 > 6     7
再翻转 456为654
3 > 2 > 1     6 > 5 > 4  7

然后456中的head 为4, new head为6，我们把6 返回给上一层，让4.next = 6，这样就接回去了。同样，在返回6之前，我们还是要递归地进入下一层，就是处理7 ，由于只有一个7不足3个节点，所以我们不做处理直接返返回7.所以，让head.next  = 7（这一层head 是4）
3 > 2 >1   6 > 5 > 4 > 7
然后再返回6给上一层
3 > 2 > 1 >6 >5 >4 >7
这样就完成了～非常巧妙
由于递归不太好理解，我建议通过代码直接揣摩

1. class Solution {
   
2.     public ListNode reverseKGroup(ListNode head, int k) {
   
3.          if(head == null)
   
4.              return null;
   
5.                   
   
6.         ListNode p = head;
   
7.         for(int i = 0; i < k - 1; i++)  {
   
8.             p = p.next;
   
9.             if(p == null) return head;
   
10.         }  
    
11.         
    
12.         ListNode next = p.next;
    
13.         
    
14.         p.next = null;
    
15.         ListNode newHead = reverse(head);
    
16.         
    
17.         head.next = reverseKGroup(next, k);
    
18.         return newHead;
    
19.         
    
20.     }
    
21.    
    
22.     private ListNode reverse(ListNode curr)  {
    
23.         ListNode pre = null;
    
24.         while(curr != null)  {
    
25.             ListNode next = curr.next;
    
26.             
    
27.             curr.next = pre;
    
28.             pre = curr;
    
29.             curr= next;
    
30.         }
    
31.         return pre;
    
32.     }
    
33. }

复制代码

今天有事，加上easy题很多，没有做完hard，不过做了4道题，也算保量了吧
26. Remove Duplicates from Sorted Array
给一个排序好的数组，要求删除重复的数字，并且把前面一段变成没有重复的数组，返回其不重复的长度。

题目解答，
这个题出得不是很好，有很多很多限制，要求不能创建新的数组，必须把不重复的数字放在前面。返回一个长度，但是却要检验数组的正确性。

解题思路，看到数组，还要求删除，那么肯定就是找数字的题了，因为先得找到数字之后才能进行删除吗。找数字那么要么是指针，要么是滑动窗口。这个题显然是指针，一个慢指针指向生成新数字的位置，一个快指针指向依次指向不重复的数字。
用一个for循环，从第二位开始依次移动快指针，因为第一位肯定要保留吗。然后每次都和慢指针比较，因为此时，慢指针的位置是上一次更新的位置，也就是不重复子数组的最后一位上，若是二者不相同，说明我们找到了一个新的数字，所以我们先把慢指针向后移动一位，再把快指针的数字复制到慢指针的位置上。如此循环，直到快指针走到数组的末尾。最后返回数组的长度，就是慢指针 ＋ 1。因为慢指针是下标，长度需要＋1

代码：

1. public int removeDuplicates(int[] nums) {
   
2.         int fast = 1, slow = 0;
   
3.         while(fast < nums.length){
   
4.             if(nums[slow] != nums[fast])  {
   
5.                 slow++;
   
6.                 nums[slow] = nums[fast];
   
7.             }
   
8.             fast++;
   
9.         }
   
10.         return slow +1;
    
11.         
    
12.     }

复制代码