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

152. Maximum Product Subarray
这道题一看，是排列组合选数字，但是不要求返回选出什么数字，所以可以用dp。
我们要保存两个dp，因为数字可能两个负数相乘，或者两个正数相乘。
所以我们dp定义为，dp1[i]为[0，i]最大乘积，dp2[i]为最小乘积。dp1[i] = Max(nums[i], nums[i] * dp1[i - 1])，也就是要么是重新开始，要么是乘以之前的最大乘积，但是注意若是nums[i]为负数 ，那么dp1[i] = Max(nums[i], nums[i] * dp2  [i - 1])。也就是我用负数去乘以最小值，这样才能保证不会尽量小。也就是dp[1] = Max( nums[i],   nums[i] < 0 ? dp2[i - 1] : dp1[i - 1]);
dp2采取同样的策略，只是反过来。然后每次我们填写完dp1[i], 我们用一个rs 来更新最大值，rs = max(dp[i] , rs);最后返回。

然后我们发现我们不用真的去保存每一个结果，因为我们dp只和前一个值有关系，所以我们只要用两个int h , l就可以了，这样可以节约空间复杂度。

所以最后代码就是
class Solution {
    public int maxProduct(int[] nums) {
        int h = nums[0], l = nums[0];
        
        int rs = nums[0];
         for(int i = 1; i < nums.length; i++) {
            if(nums[i] < 0) {
                h = h ^ l;
                l = h ^ l;
                h = h ^ l;
            }
            h = Math.max(nums[i], nums[i] * h);
            l = Math.min(nums[i], nums[i] * l);
            rs = Math.max(rs, h);
         }
        return rs;
    }
}

151. Reverse Words in a String
这题很简单，算不上什么中等难度。思路就是split出string[]，然后要么用栈，要么就是从后往前遍历。逆序生成新的字符串
class Solution {
    public String reverseWords(String s) {
        Stack stack = new Stack();

        String[] strArray = s.split(" ");

        for (String str : strArray) {
            if(!str.equals(""))stack.push(str);
        }

        StringBuilder sb = new StringBuilder();
        while (!stack.empty()) {
            sb.append(stack.pop()).append(" ");
        }
        return sb.toString().trim();
    }
}

150. Evaluate Reverse Polish Notation
逆波兰表达式。这题非常重要，后面实现计算题，就是这道题的扩展。
本题算法不难，就是用一个栈保存数字，然后遇到符号就弹出两个数字，运算之后把运算结果再入栈。
最后结果就保存在栈里。

本题代码略微繁琐，比较考验语言基本能力

1. class Solution {
   
2.     public int evalRPN(String[] tokens) {
   
3.         Stack<Integer> stack = new Stack<>();
   
4.         String operators = "+-*/";
   
5.         
   
6.         for(String s : tokens) {
   
7.             if(operators.indexOf(s) < 0) {
   
8.                 stack.add(Integer.parseInt(s));
   
9.             }else{
   
10.                 int a = stack.pop();
    
11.                 int b = stack.pop();
    
12.                
    
13.                 switch (s) {
    
14.                     case "+" :
    
15.                         stack.add(a + b);
    
16.                         break;
    
17.                     case "-" :
    
18.                         stack.add(b - a);
    
19.                         break;
    
20.                     case "*" :
    
21.                         stack.add(a * b);
    
22.                         break;
    
23.                     case "/" :
    
24.                         stack.add(b / a);
    
25.                         break;
    
26.                         
    
27.                 }
    
28.             }
    
29.         }
    
30.         return stack.pop();
    
31.     }
    
32. }

复制代码

153. Find Minimum in Rotated Sorted Array

1. class Solution {
   
2.     public int findMin(int[] nums) {
   
3.         //[3,4,5,1,2]
   
4.         //l < m > r  l = m + 1;
   
5.         int l  = 0;
   
6.         int h = nums.length - 1;
   
7.         while(l <= h) {
   
8.             int mid = l + ((h - l) >>1);
   
9.             if(nums[mid] == nums[h]) return nums[mid];
   
10.             if(nums[mid] < nums[h]) h = mid;
    
11.             else l = mid + 1;
    
12.             
    
13.         }
    
14.         
    
15.         return nums[l];
    
16.     }
    
17. }

复制代码

154. Find Minimum in Rotated Sorted Array II

1. class Solution {
   
2.     public int findMin(int[] nums) {
   
3.         //[0,1,4,4,5,6,7]
   
4.         // ^
   
5.         //             ^
   
6.         
   
7.         int l = 0;
   
8.         int r = nums.length - 1;
   
9.         while(l < r) {
   
10.             int mid = l + ((r - l) >> 1);
    
11.             
    
12.             if(nums[r] < nums[mid]) {
    
13.                 l = mid + 1;
    
14.             }else if(nums[mid] < nums[r]) {
    
15.                 r = mid;
    
16.             }else r--;
    
17.         }
    
18.         return nums[l];
    
19.     }
    
20. }

复制代码

158. Read N Characters Given read4 II - Call Multiple Times
这道题浪费了一晚上，其实很简单。很容易想歪。
逻辑要清晰一些，我们肯定要定义一个内存，和idx。
接下来是难点，我们怎么判断要不要重新读取？

此时很容易想错，去想用n和已经读取的长度进行比较。这是错误的，或者说太复杂。
更好的方法是这样的，我们要返回的buf[]，长度一定是n。因为题目说保证有足够的空间返回。

那么我们就用一个for循环，i = [0,n]去填buf[]。但是填写的过程中，
若是我们发现内存已经用完了，那么我们就重新读取read4。
若是内存没有用完，我们填写完毕就完毕，返回n，此时我们更新了idx和内存依然保留。

这样讨论，其实我们就可以避免讨论复杂的n和buf到底谁先结束的情况。
然后就是第二难点，怎么知道内存用完了，简单的想是内存的idx ==4，但是其实还不一定，因为若是最后一次读取，read4可能<4。所以，我们就用一个size来标记内存的大小。若是idx = size。说明我们用完了所有的内存，需要从新读取。若是读取出来的size = 0，那么就说明我们已经读完了文件，返回i即可。不返回n是因为i 也许比n更小。

然后还有第三个坑，若是sizee = 0，我们返回i之前，必须要把idx重新置为0，为什么呢？因为可能还有下一次call这个方法，若是idx 不复位到0，那么size == idx就会失效，导致会写入错误的空值。所以一定要把参数都复位成初始状态。

最后代码非常简单

1. public class Solution extends Reader4 {
   
2.     /**
   
3.      * @param buf Destination buffer
   
4.      * @param n   Number of characters to read
   
5.      * [url=home.php?mod=space&uid=160137]@return[/url]    The number of actual characters read
   
6.      */
   
7.     char[] read = new char[4];//abcd
   
8.     int read_idx = 0;
   
9.     int write_idx = 0;
   
10.     public int read(char[] buf, int n) {
    
11.        for(int i = 0 ; i < n; i++) {
    
12.            if(read_idx == write_idx) {
    
13.                write_idx = read4(read);
    
14.                read_idx = 0;
    
15.                if(write_idx == 0) return i;
    
16.            }
    
17.            buf[i] = read[read_idx++];
    
18.        }
    
19.         return n;
    
20.     }
    
21. }

复制代码

156. Binary Tree Upside
这道题出得非常不好，有隐藏的条件没有说明，那就是右子树不用处理。
做法很多用dfs就可以了。

1. class Solution {
   
2.     public TreeNode upsideDownBinaryTree(TreeNode root) {
   
3.         if(root == null) return null;
   
4.         if(root.left == null && root.right == null) return root;
   
5.         
   
6.         
   
7.         TreeNode newRoot = upsideDownBinaryTree(root.left);
   
8.         root.left.left = root.right;
   
9.         root.left.right = root;
   
10.         root.left = null;
    
11.         root.right = null;
    
12.         //System.out.println(newRoot.val);
    
13.         return newRoot;
    
14.             
    
15.     }
    
16. }

复制代码

161. One Edit Distance
这个题乍一看是dp，其实dp也应该可以做，不过实际上dp还是为难自己。此题用直接比较更简单。
不用dp那么肯定是双指针。

由于两个字符串肯定是只相差一个字符，要么多一个，要么少一个，要么长度相同多，但是有一个不一样。
那么事情就好办了，我们用双指针一直比较两个字符串相同位置的字符，看看它们是否相同。若是不相同，那么就分上面三个情况讨论。
若是 s更长，那么此时我们就是要删除s里面这个不相同字符，也就是我们跳过s[i],直接看比较s[i + 1. len]  是否 == t[i,len]
同理，若是t更长，那么就此时就是要增加s，也就是我们要跳过t［i］这个字符，直接比较s[i,len], t[i+1,len]
若是同样长，我们就是要替换，也就是我们要跳过s[i],t[i]，比较s[i+1,len] t [i +1,len]；

这样就是最优解了。

1. class Solution {
   
2.     public boolean isOneEditDistance(String s, String t) {
   
3.         
   
4.     for (int i = 0; i < Math.min(s.length(), t.length()); i++) {
   
5.         if (s.charAt(i) != t.charAt(i)) {
   
6.             if (s.length() == t.length()) {
   
7.                 return s.substring(i + 1).equals(t.substring(i + 1));
   
8.             }else if (s.length() < t.length()) {
   
9.                 return s.substring(i).equals(t.substring(i + 1));
   
10.             }else{
    
11.                 return t.substring(i).equals(s.substring(i + 1));
    
12.             }   
    
13.         }
    
14.     }      
    
15.     //All previous chars are the same, the only possibility is deleting the end char in the longer one of s and t
    
16.     return Math.abs(s.length() - t.length()) == 1;
    
17.      
    
18.     }
    
19. }

复制代码

160. Intersection of Two Linked Lists
这个题也挺有意思的，最优解非常巧妙，我们用双指针，同时从两个起点开始向后走，若是走到头了，我们让走到头的那个指针从另外一个链表再开始走。那么二者肯定会在第二圈的时候，在交汇点相遇。

为什么呢？想一想也非常简单，因为假设a的长度是 A + L 。L是交汇点之后公共链条的长度， A是a自己的节点长度。 同理 b = B +L。
那么p1从a开始走，走到第二圈交汇点的时候它走了 A + L + B步。p2从b开始走，到了第二圈交汇点的时候，它走了 B + L + A步。
显然它们走了一样的步数，此时一定会在交汇点相遇。非常巧妙

1. public class Solution {
   
2.     public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
   
3.         ListNode p1 = headA;
   
4.         ListNode p2 = headB;
   
5.         
   
6.         while(p1 != p2) {
   
7.             p1 = p1 == null ? headB : p1.next;
   
8.             p2 = p2 == null ? headA : p2.next;
   
9.         }
   
10.         return p1;
    
11.     }
    
12. }

复制代码

159. Longest Substring with At Most Two Distinct Characters
这个题很简单，乍一看还是dp，但是其实用双指针滑动窗口更简单。
用一个map保存窗口里，字母的数量。从左到右遍历字符，表示窗口每次向右扩展一格， 每次s[i]进入map，当map的size超过2的时候，就表示窗口超出容量，我们要缩小窗口左边界。用一个while缩小左边，每缩小一次，就把map里对应值减1，当减到0的时候从map里移除这个字符。然后缩小就停止。

那么我们什么时候计算窗口长度呢？计算的时机就是当我们添加了一个字符进入map，发现map大小超过2的时候，也就是即将要缩小窗口之前，此时窗口的大小 i－l就是当下最大长度，我们把它和最终答案比较并且更新即可

1. class Solution {
   
2.     public int lengthOfLongestSubstringTwoDistinct(String s) {
   
3.       
   
4.         Map<Character, Integer> map = new HashMap<>();
   
5.         char[] sc = s.toCharArray();
   
6.         
   
7.         int l = 0, rs = 0;
   
8.         for(int i = 0; i < sc.length; i++) {
   
9.             char c = sc[i];
   
10.             map.put(c, map.getOrDefault(c, 0) + 1);
    
11.             if(map.size() > 2) {
    
12.                 rs = Math.max(rs, i - l);
    
13.                 while(map.size() > 2) {
    
14.                     int temp = map.get(sc[l]);
    
15.                     temp--;
    
16.                     if(temp == 0)
    
17.                         map.remove(sc[l]);
    
18.                     else map.put(sc[l], temp);
    
19.                     l++;
    
20.                 }
    
21.             }
    
22.         }
    
23.         return Math.max(rs, sc.length - l);
    
24.     }
    
25. }

复制代码