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

162. Find Peak Element
这道题出得也是很怪异，要求必须二分法。强行增加难度。

思路就是看上坡还是下坡，也就是mid和mid+1比较一下。若是下坡mid > mid + 1就取左边，上坡就取右边。
然后要考虑使用什么模板，因为是比较mid和mid+1，也就是若是mid > mid + 1的时候 也许mid就是答案，所以我们要保留mid，r = mid。若是mid < mid + 1的话，我们倒是可以确定mid肯定不是答案，所以 l = mid + 1;

其实我一直有个疑问就是相等怎么办？不过看起来op是保证一定是有上坡或者下坡的。

代码
class Solution {
    public int findPeakElement(int[] nums) {
        int l = 0;
        int r = nums.length - 1;
        
        while(l < r) {
            int mid = l + ((r - l) >> 1);
            if(nums[mid] > nums[mid + 1]) {
                r = mid;
            }else l = mid + 1;
        }
        return l;
    }
}

164. Maximum Gap
此题非常难，我认为非常不适合做面试题。本质上他是个数学问题，数学问题通常都涉及到需要运用某种数学定理，除了背诵定理几乎没有什么办法。而且本题的定理不是特别直观 ：设数组中有n个元素，其中最大值为Max，最小值为Min，则排序后相邻两个元素的差值的最大值不会小于ceil((Max - Min)/(n - 1))
ceil表示向上取整。

这个定理据说可以用反证法证明。可以假设最大值会小于这个数值，然后有三个数字排好顺序的数列 [1 ， x，10]，那么1 < x < 10。
根据定理，我们有 一个相邻元素的最大值的最小值应该为，ceil(10 - 1) / (3 - 1) = 5。
根据反证法假设，若是定理不正确，那么也就是在一个x使得 x - 1 < 5 ,  且 10 - x < 5。也就是 x < 4 且 x >5。这显然是不可能的，也就是反证法的假设不正确。

好，证明完定理之后，我们就可以解题了。

此题故意不允许排序还要求线性时间复杂度，那么就是桶排序了。
那么我们怎么安排桶呢？此时就要用到我们的定理了，因为相邻两个数字差值的最大值不会小于ceil((Max - Min)/(n - 1))

也就是假设 [1  7 14  20]  4个数字的数组，它们两两之间的差值最大值不会小于 ceil 1 9/ 3 = 7
那么我们把数字放进桶里面的时候，此时，最大值要么在同一个桶里面，要么在 不同的桶之间。
若是我们把每一个桶的容量设置成7。那么就会出现好处，若是整个数列中相邻数组最大值肯定在不同桶之间。
还是上面的例子,我们用容量7的桶去装数字
0号桶  - 1 2 3 4 5 6 7
1号桶  - 8 9 10 11 12 13 14
2号桶- 15 16 17 18 19 20 21

那么数列中数字装的结果是
0号桶  -1  7
1号桶  -14
2号桶- 20

每一个桶当中，两个数字最大值不会超过7， 比如一号桶，最大值num[1] = 7，最小值num[0] = 1，是桶的极限，它们的差值为6 < 7。
也就是，桶中任何一个数字，若是它的相邻数字的间距大于6，那么它们一定在不同的桶里面。
比如nums[2] = 14 。这个14与上一个数字间隔是7，超过了6，所以它们一个在0号桶，一个在1号桶。

此时，它们之间的距离7就是最终的答案。

可能有的人会问，若是我给数组增加一个数字8,它会被安排到第二个桶，那最大值不就是6了吗？
0号桶  -1  7
1号桶  -8 14
2号桶- 20

若是你这么想，说明你已经累了，因为此时它们之间差值最大值的最小值已经变了，也就是桶的容量变了ceil(20 - 1) / ( 5 - 1) = 5
此时会有4个桶
0号桶 - 1  
1号桶 - 7
2号桶 - 14
3号桶 - 20

很神奇。
所以这道题就证明完毕了。我们可以写代码。本题代码也不太好写，我们要用两个数列，当作桶，分别记录桶的最大值和最小值。
生成完毕之后，用每一个桶的最小值去减之前一个桶的最大值，最后最大差值就是答案。

1. class Solution {
   
2.     public int maximumGap(int[] nums) {
   
3.         int n = nums.length;
   
4.         if(n < 2)
   
5.             return 0;
   
6.         int max = Integer.MIN_VALUE;
   
7.         int min = Integer.MAX_VALUE;
   
8.         for(int num : nums) {
   
9.             max = Math.max(num, max);
   
10.             min = Math.min(num, min);
    
11.         }
    
12.         if(max == min)
    
13.             return 0;
    
14.         int[] maxBucket = new int[n];
    
15.         int[] minBucket = new int[n];
    
16.         
    
17.         Arrays.fill(maxBucket, Integer.MIN_VALUE);
    
18.         Arrays.fill(minBucket, Integer.MAX_VALUE);
    
19.         
    
20.         int bucketSize = (int)Math.ceil((double)(max - min) / (n - 1));
    
21.         for(int num : nums) {
    
22.             int idx = (num - min) / bucketSize;
    
23.             maxBucket[idx] = Math.max(maxBucket[idx], num);
    
24.             minBucket[idx] = Math.min(minBucket[idx], num);
    
25.         }
    
26.    
    
27.         int rs = 0;
    
28.         int pre = maxBucket[0];
    
29.         for(int i = 1; i < minBucket.length; i++) {
    
30.             if(minBucket[i] == Integer.MAX_VALUE)
    
31.                 continue;
    
32.             rs = Math.max(rs, minBucket[i] - pre);
    
33.             pre = maxBucket[i];
    
34.         }
    
35.         
    
36.         return rs;
    
37.         
    
38.     }
    
39. }

复制代码

165. Compare Version Numbers
这道题没有算法，硬编程题，就是把字符串按照点拆开，比较每一个位置的大小，若是前面完全相同，但是某一个版本号有更多的位数，则看它是不是有非零的数字，若是有则是它更大，若都是零则一样大。

1. class Solution {
   
2.     public int compareVersion(String version1, String version2) {
   
3.         
   
4.         String[] s1 = version1.split("\\.");
   
5.         String[] s2 = version2.split("\\.");
   
6.         
   
7.         int i = 0;
   
8.         for(; i < Math.min(s1.length, s2.length); i++) {
   
9.             int n1 = Integer.parseInt(s1[i]);
   
10.             int n2 = Integer.parseInt(s2[i]);
    
11. 
    
12.             if(n1 > n2) return 1;
    
13.             else if(n1 < n2) return -1;
    
14.         }
    
15.         if(s1.length > s2.length){
    
16.             while(i < s1.length) {
    
17.                 if(Integer.parseInt(s1[i++]) != 0) return 1;
    
18.             }
    
19.         }
    
20.         else if(s1.length < s2.length){
    
21.             while(i < s2.length) {
    
22.                 if(Integer.parseInt(s2[i++]) != 0) return -1;
    
23.             }
    
24.         }
    
25.         return 0;
    
26.     }
    
27. }

复制代码

166. Fraction to Recurring Decimal
这道题也是挺不好的，有理数相除，要么是整数，要么是小数，要么是无限循环小数。
此题难点在于如何产生循环。

1. class Solution {
   
2.     public String fractionToDecimal(int numerator, int denominator) {
   
3.         StringBuilder sb = new StringBuilder();
   
4.         if((numerator > 0 && denominator < 0) || (numerator < 0 && denominator > 0)) {
   
5.             sb.append("-");
   
6.         }
   
7.         
   
8.         long n1 = Math.abs((long)numerator);
   
9.         long n2 = Math.abs((long)denominator);
   
10.         
    
11.         sb.append(n1 / n2);
    
12.         long remain = n1 % n2;
    
13.         if(remain == 0) return sb.toString();
    
14.         
    
15.         sb.append(".");
    
16.         
    
17.         
    
18.         Map<Long, Integer> map = new HashMap<>();
    
19.         while(remain != 0) {
    
20.              System.out.println(remain);
    
21.             if(map.containsKey(remain)) {
    
22.                 sb.insert(map.get(remain), "(");
    
23.                 sb.append(")");
    
24.                 return sb.toString();
    
25.             }
    
26.             
    
27.             map.put(remain,sb.length());
    
28.             
    
29.             remain *= 10;
    
30.             sb.append(remain / n2);
    
31.             remain %= n2;
    
32.            
    
33.         }
    
34.         return sb.toString();
    
35.             
    
36.     }
    
37. }

复制代码

174. Dungeon Game
本题并不难，还是二维dp。但是是从终点往起点走。先初始化最后一行和最后列，终点初始化为 1 - m[h][w]， 因为至少要一点血。然后转移公式就是dp[x][y] = min(dp[x - 1][y], dp[x][y - 1]) - m[x][y];

注意，dp[x][y] < = 0的话，说明到此格，只要有1点血即可，所以若是计算出来小于0，就初始化为1.
然后我们从dp[h -1][w - 1]开始，从右往左，从下往上，依次填充dp即可

1. class Solution {
   
2.     public int calculateMinimumHP(int[][] dungeon) {
   
3.         // -2 -3   3
   
4.         // -5 -10  1
   
5.         // 10  30 -5
   
6.         
   
7.         //  7  5   2
   
8.         //  6  11  5
   
9.         //  1  1   6
   
10.         
    
11.         int h = dungeon.length;
    
12.         int w = dungeon[0].length;
    
13.         int[][] dp = new int[h][w];
    
14.         
    
15.         dp[h - 1][w - 1] = (1 - dungeon[h - 1][w - 1]  > 0) ? 1 - dungeon[h - 1][w - 1] : 1;
    
16.         for(int i = h - 2; i >= 0; i --) {
    
17.             dp[i][w - 1] = dp[i + 1][w - 1] - dungeon[i][w - 1];
    
18.             if(dp[i][w - 1] <= 0)  dp[i][w - 1] = 1;
    
19.         }
    
20.         
    
21.         for(int i = w - 2; i >= 0; i--) {
    
22.             dp[h - 1][i] = dp[h - 1][i + 1] - dungeon[h - 1][i];
    
23.             if(dp[h - 1][i] <= 0) dp[h - 1][i] = 1;
    
24.         }
    
25.         
    
26.         if(h == 1 || w == 1) {
    
27.             return dp[0][0];
    
28.         }
    
29.         
    
30.         for(int i = h - 2; i >= 0; i--) {
    
31.             for(int j = w - 2; j >= 0; j--) {
    
32.                 int min = Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
    
33.                 dp[i][j] = Math.max(1, min);
    
34.             }
    
35.         }
    
36. 
    
37.         return dp[0][0];
    
38.     }
    
39. }

复制代码

173. Binary Search Tree Iterator
这题也不难，就是先遍历一遍树，按照中序遍历依次存储到一个数据结构中，linkedlist, list, deque, queue,甚至stack都可以。

然后next就是从数据结构中依次取出节点，hasnext就是检查数据结构是否为空

1. class BSTIterator {
   
2. 
   
3.     Stack<TreeNode> stack;
   
4.     public BSTIterator(TreeNode root) {
   
5.         stack = new Stack<>();
   
6.         while(root != null){
   
7.             stack.push(root);
   
8.             root = root.left;
   
9.         }
   
10.     }
    
11.    
    
12.     /** [url=home.php?mod=space&uid=160137]@return[/url] the next smallest number */
    
13.     public int next() {
    
14.         TreeNode node = stack.pop();
    
15.         int val = node.val;
    
16.         
    
17.         node = node.right;
    
18.         while(node != null){
    
19.             stack.push(node);
    
20.             node = node.left;
    
21.         }
    
22.         
    
23.         return val;
    
24.     }
    
25.    
    
26.     /** @return whether we have a next smallest number */
    
27.     public boolean hasNext() {
    
28.         return !stack.isEmpty();
    
29.     }
    
30. }

复制代码

172. Factorial Trailing Zeroes
数学题，挺难的。代码不难，但是思路很难想到。

数末尾有多少个0，也就是乘数中有多少个10，10的来源有两个，一个是本来就有10，一个是5 x 2得来。
显然，n!中，2的数量远远多于5 ，并且10也能拆成5 * 2。所以，我们只要数5的个数，就是末位零的个数了。因为只要乘数中包含5，那么它最后一定能变成至少一个10，使得结果多一个末尾0。这里说至少有一个10是因为25有两个5 ，它最后会变成100，使得末尾零多出来两个。

代码写法很多，最简洁的写法是递归，一行代码就可以搞定

1. class Solution {
   
2.     public int trailingZeroes(int n) {      
   
3.         return n == 0 ? 0 : n / 5 + trailingZeroes(n / 5);
   
4.     }
   
5.    
   
6. }

复制代码

167. Two Sum II - Input Array Is Sorted
这个题其实用滑动窗口的思路是最优解。
我们用两个指针放在开头和结尾，因为数组是有序的，所以一定是最大值和最小值。
然后我们看它们的和比target更大还是更小，更大就说明要减少右边的最大值，更小就要减少左边的最小值。
若是最后相遇，说明没有答案，若是中间有等于target的情况，说明我们找到了答案

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

复制代码

179. Largest Number

1. class Solution {
   
2.     public String largestNumber(int[] nums) {
   
3.         String[] strs = new String[nums.length];
   
4.         int i = 0;
   
5.         for(int num : nums) {
   
6.             strs[i++] = String.valueOf(num);
   
7.         }
   
8.         
   
9.         Arrays.sort(strs, (a,b) -> {
   
10.             String order1 = a + b;
    
11.             String order2 = b + a;
    
12.             return order2.compareTo(order1);
    
13.         });
    
14.         
    
15.         if(strs[0].equals("0")) return "0";
    
16.         StringBuilder sb = new StringBuilder();
    
17.         for(String s : strs) {
    
18.             sb.append(s);
    
19.         }
    
20.         return sb.toString();
    
21.             
    
22.     }
    
23. }

复制代码

187. Repeated DNA Sequences

1. class Solution {
   
2.     public List<String> findRepeatedDnaSequences(String s) {
   
3.         Map<String, Integer> map = new HashMap<>();
   
4.         
   
5.         for(int i = 0; i <= s.length() - 10;i++) {
   
6.             String sub = s.substring(i, i + 10);
   
7.          
   
8.             map.put(sub, map.getOrDefault(sub, 0) + 1);
   
9.         }
   
10.         
    
11.         List<String> rs = new ArrayList<>();
    
12.         for(String key : map.keySet()) {
    
13.             if(map.get(key) > 1) {
    
14.                 rs.add(key);
    
15.             }
    
16.         }
    
17.         return rs;
    
18.     }
    
19. }

复制代码