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

189. Rotate Array

1. class Solution {
   
2.     public void rotate(int[] nums, int k) {
   
3.         k %= nums.length;
   
4.         helper(nums, 0, nums.length - 1 - k);
   
5.         helper(nums, nums.length - k, nums.length - 1);
   
6.         helper(nums, 0, nums.length - 1);
   
7.         
   
8.     }
   
9.     private void helper (int[] nums, int l, int r) {
   
10.         while(l < r) {
    
11.             int temp = nums[l];
    
12.             nums[l] = nums[r];
    
13.             nums[r] = temp;
    
14.             l++;
    
15.             r--;
    
16.         }
    
17.     }
    
18. }

复制代码

186. Reverse Words in a String II

1. class Solution {
   
2.     public void reverseWords(char[] s) {
   
3.         int l = 0;
   
4.         int i = 0;
   
5.         while(s[i] == ' ') {
   
6.             l++;
   
7.             i++;
   
8.         }
   
9.         for(; i < s.length; i++) {
   
10.             if(s[i] == ' ') {
    
11.                 reverse(s, l, i - 1);
    
12.                 l = i + 1;
    
13.             }
    
14.         }
    
15.         
    
16.         if(i - 1 > l) {
    
17.             reverse(s, l, i - 1);
    
18.         }
    
19.         reverse(s, 0, i - 1);
    
20.      
    
21.     }
    
22.    
    
23.     private void reverse(char[] s, int l , int r) {
    
24.         while(l < r) {
    
25.             char c = s[l];
    
26.             s[l] = s[r];
    
27.             s[r] = c;
    
28.             l++;
    
29.             r--;
    
30.         }
    
31.     }
    
32. }

复制代码

188. Best Time to Buy and Sell Stock IV

1. class Solution {
   
2.     public int maxProfit(int k, int[] prices) {
   
3.         int len = prices.length;
   
4.         if(len == 0 || k == 0) return 0;
   
5.         int[][][] dp = new int[len][k + 1][2];
   
6.         
   
7.       
   
8.         for(int i = 0; i < len; i++) {
   
9.             for(int j = k; j > 0; j--) {
   
10.                 if(i == 0) {
    
11.                     dp[i][j][0] = 0;
    
12.                     dp[i][j][1] = -prices[i];
    
13.                 }else{
    
14.                     dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i- 1][j - 1][0] - prices[i]);
    
15.                
    
16.                     dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
    
17.                 }
    
18.                
    
19.             }
    
20.         }
    
21.         
    
22.         return dp[len - 1][k][0];
    
23.     }
    
24. }

复制代码

198. House Robber
class Solution {
    public int rob(int[] nums) {
        // 0 1 2 3 1
        // 0 1 2 4 4
        int[] dp = new int[nums.length + 1];
        dp[1] = nums[0];
        for(int i = 2; i < dp.length; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
        }
        
        return dp[nums.length];
        //
    }
}

200. Number of Islands

1. class Solution {
   
2.     int rs = 0;
   
3.     public int numIslands(char[][] grid) {
   
4.         int a = grid.length;
   
5.         int b = grid[0].length;
   
6.         for(int i = 0; i < a; i++) {
   
7.             for(int j = 0; j < b; j++) {
   
8.                 if(grid[i][j] == '1') {
   
9.                     rs++;
   
10.                     helper(grid, i, j);
    
11.                 }
    
12.             }
    
13.         }
    
14.         return rs;
    
15.     }
    
16.    
    
17.     private void helper(char[][] grid, int i, int j) {
    
18.         int a = grid.length;
    
19.         int b = grid[0].length;
    
20.         if(i > a - 1|| i < 0 || j > b - 1 || j < 0 || grid[i][j] == '0')
    
21.             return;
    
22.         
    
23.         grid[i][j] = '0';
    
24.         helper(grid, i -1 , j);
    
25.         helper(grid, i + 1, j);
    
26.         helper(grid, i , j + 1);
    
27.         helper(grid, i , j - 1);
    
28.         return;
    
29.     }
    
30. }

复制代码

199. Binary Tree Right Side View

1. class Solution {
   
2.     int rs = 0;
   
3.     public int numIslands(char[][] grid) {
   
4.         int a = grid.length;
   
5.         int b = grid[0].length;
   
6.         for(int i = 0; i < a; i++) {
   
7.             for(int j = 0; j < b; j++) {
   
8.                 if(grid[i][j] == '1') {
   
9.                     rs++;
   
10.                     helper(grid, i, j);
    
11.                 }
    
12.             }
    
13.         }
    
14.         return rs;
    
15.     }
    
16.    
    
17.     private void helper(char[][] grid, int i, int j) {
    
18.         int a = grid.length;
    
19.         int b = grid[0].length;
    
20.         if(i > a - 1|| i < 0 || j > b - 1 || j < 0 || grid[i][j] == '0')
    
21.             return;
    
22.         
    
23.         grid[i][j] = '0';
    
24.         helper(grid, i -1 , j);
    
25.         helper(grid, i + 1, j);
    
26.         helper(grid, i , j + 1);
    
27.         helper(grid, i , j - 1);
    
28.         return;
    
29.     }
    
30. }

复制代码

201. Bitwise AND of Numbers Range
位操作数学题，所有数字的与，其实就是找所有数字二进制的共同prefix。所以先右移边界直到二者相同，同时记录步数i，再把任意一个左右边界的数字左移i

1. class Solution {
   
2.     public int rangeBitwiseAnd(int left, int right) {
   
3.         int i = 0;
   
4.         while(left != right) {
   
5.             left >>= 1;
   
6.             right >>= 1;
   
7.             i++;
   
8.         }
   
9.         return left <<= i;
   
10.     }
    
11. }

复制代码

203. Remove Linked List Elements
移除某一个值的节点，有一个特殊案例就是所有的节点都要移除。所以需要一个dummy，然后判断dummy.next的是否需要移除，移除的方法就是node.next= node.next.next;

注意若是移除了next，那么我们不要移动node，而是继续判断next是不是需要移除。只有当前节点不需要移除的时候我们才会node = node.next

1. class Solution {
   
2.     public ListNode removeElements(ListNode head, int val) {
   
3.         ListNode dummy = new ListNode();
   
4.         dummy.next = head;
   
5.         ListNode node = dummy;
   
6.         while(node != null && node.next != null) {
   
7.             if(node.next.val == val) {
   
8.                 node.next = node.next.next;
   
9.             }else
   
10.                 node = node.next;
    
11.         }
    
12.         return dummy.next;
    
13.     }
    
14. }

复制代码

204. Count Primes
数学题 - 埃拉托斯特尼筛法。

1. class Solution {
   
2.     public int countPrimes(int n) {
   
3.         boolean[] prime = new boolean[n];
   
4.         int rs = 0;
   
5.         for(int i = 2; i < n; i++) {
   
6.             if(prime[i]) continue;
   
7.             rs++;
   
8.             for(int j = 2; i * j < n; j++) {
   
9.                 prime[i * j] = true;
   
10.             }
    
11.         }
    
12.         return rs;
    
13.     }
    
14. }

复制代码

202. Happy Number
这题挺难的，还是数学题。若某一个数字不是happy number，那么它们就会进入一个循环。永远也到不了1。有点类似判断链表是否有环。

1. class Solution {
   
2.     public boolean isHappy(int n) {
   
3.         Set<Integer> seen = new HashSet<>();
   
4.         while(n != 1 && !seen.contains(n)) {
   
5.             seen.add(n);
   
6.             n = getNext(n);
   
7.         }   
   
8.         return n == 1;
   
9.     }
   
10.    
    
11.     private int getNext(int n) {
    
12.         int rs = 0;
    
13.         while(n > 0) {
    
14.             int l = n % 10;
    
15.             n /= 10;
    
16.             rs += l * l;
    
17.         }
    
18.         return rs;
    
19.     }
    
20. }

复制代码