剑指offer刷题
2022-06-16  学习

剑指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];
        }
    }