剑指offer刷题

剑指offer从头刷一遍

1. 剑指03

   //数组中重复的数字，当一个数和其下标不对应时，就把它交换到正确的位置，
   //如果正确的位置有一个同样的值（就找到重复的了），
   //while中每次都会有一个值处在正确的位置，时间复杂度O(n)
   class Solution {
       public int findRepeatNumber(int[] nums) {
           int n = nums.length;
           for(int i=0; i<n; ++i){
               while(nums[i] != i){
                   if(nums[nums[i]] == nums[i]){
                       return nums[i];
                   }
                   swap(nums, i, nums[i]);
               }
           }
           return -1;
       }
   }

2. 剑指07

   //根节点以前序遍历下标为准，子树范围是中序遍历的
   class Solution {
       private int[] preorder;
       private Map<Integer, Integer> inorderMap = new HashMap<>();
   
       public TreeNode buildTree(int[] preorder, int[] inorder) {
           this.preorder = preorder;
           int n = inorder.length;
           for(int i=0; i<n; ++i){
               inorderMap.put(inorder[i], i);
           }
           return recur(0, 0, n-1);
       }
   
       private TreeNode recur(int preRootIdx, int inLeftIdx, int inRightIdx){
           if(inLeftIdx > inRightIdx){
               return null;
           }
           int preRootVal = preorder[preRootIdx];
           int inRootIdx = inorderMap.get(preRootVal);
           TreeNode root = new TreeNode(preRootVal);
           root.left = recur(preRootIdx+1, inLeftIdx, inRootIdx-1);
           root.right = recur(preRootIdx + inRootIdx - inLeftIdx + 1, inRootIdx + 1, inRightIdx);
           return root;
       }
   }

3. 剑指09：用两个栈实现队列。stack2只push，弹出时当stack1非空时弹出stack1，否则将stack2中所有元素出栈并入栈stack1，stack1再出栈。

4. 154

   //旋转数组最小值，有重复
   //比较mi和hi，相同时hi左移
   class Solution {
       public int findMin(int[] nums) {
           int lo = 0, hi = nums.length - 1;
           while(lo < hi) {
               int mi = lo + (hi - lo) / 2;
               if(nums[mi] < nums[hi]){
                   hi = mi;
               }else if(nums[mi] > nums[hi]){
                   lo = mi + 1;
               }else{
                   hi = hi - 1;
               }
           }
           return nums[lo];
       }
   }

5. 79 回溯的题
6. 343整数拆分

   //如果一个因子大于4，拆成2和n-2一定更大
   //4，拆成2+2
   class Solution {
       public int integerBreak(int n) {
           if(n < 4){
               return n - 1;
           }
           int a = n / 3, remainder = n % 3;
           if(remainder == 0) return (int)Math.pow(3, a);
           if(remainder == 1) return (int)Math.pow(3, a-1) * 4;
           return (int)Math.pow(3, a) * 2;
       }
   }

7. 二进制中1的个数

   //n & (n-1)会消掉最低位的1
   class Solution {
       // you need to treat n as an unsigned value
       public int hammingWeight(int n) {
           int count = 0;
           while(n != 0){
               n = n & (n - 1);
               ++count;
           }
           return count;
       }
   }

8. 快速幂

   class Solution {
       public double myPow(double x, int n) {
           double ans = 1.0;
           long b = n;
           if(b < 0){
               b = -b;
               x = 1/x;
           }
           while(b != 0){
               if((b & 1) == 1){
                   ans *= x;
               }
               x *= x;
               b >>= 1;
           }
           return ans;
       }
   }

9. 大数打印

   //记住就完事了
   class Solution {
       private StringBuilder curr = new StringBuilder();
       private int[] ans;
       private int count = 0;
   
       public int[] printNumbers(int n) {
           ans = new int[(int)Math.pow(10, n) - 1];
           for(int i=1; i<=n; ++i){
               dfs(0, i);
           }
           return ans;
       }
   
       private void dfs(int x, int len) {
           if(x == len){
               ans[count++] = Integer.parseInt(curr.toString());
               return;
           }
           int start = (x == 0 ? 1 : 0);
           for(int i=start; i<10; ++i){
               curr.append(i);
               dfs(x+1, len);
               curr.deleteCharAt(curr.length()-1);
           }
       }
   }

10. 正则表达式

    class Solution {
        public boolean isMatch(String s, String p) {
            int m = s.length(), n = p.length();
            boolean[][] dp = new boolean[m+1][n+1];
            //s,p都为空默认匹配
            dp[0][0] = true;
            //s为空, p为.*也能匹配
            for(int j = 1; j<=n; ++j){
                if(p.charAt(j-1) == '*'){
                    dp[0][j] = dp[0][j-2];
                }
            }
    
            for(int j=1; j<=n; ++j){
                for(int i=1; i<=m; ++i){
                    if(p.charAt(j-1) == '*'){
                        if(s.charAt(i-1) == p.charAt(j-2) || p.charAt(j-2) == '.'){
                            //匹配0次或多次
                            dp[i][j] = dp[i][j-2] || dp[i-1][j];
                        }else{
                            //只能匹配0次
                            dp[i][j] = dp[i][j-2];
                        }
                    }else{
                        if(s.charAt(i-1) == p.charAt(j-1) || p.charAt(j-1) == '.'){
                            dp[i][j] = dp[i-1][j-1];
                        }
                    }
                }
            }
    
            return dp[m][n];
        }
    }