剑指 Offer（第 2 版）7/4 1-4

1.剑指 Offer 03. 数组中重复的数字 简单

解法一：hash

class Solution {
    
        public int findRepeatNumber(int[] nums) {
    
            Set<Integer> set = new HashSet<>();
            for (int x:nums) {
    
                if (set.contains(x))return x;
                set.add(x);
            }
            return -1;
        }
    }

解法二：排序
此解法不适用，只有基数排序没有超时

2.剑指 Offer 04. 二维数组中的查找 中等

方法一：对数组中的每一维进行二分查找
时间复杂度O(NlogN)

class Solution {
    
        public boolean findNumberIn2DArray(int[][] matrix, int target) {
    
            for (int i = 0; i < matrix.length; i++) {
    
                if (search(matrix[i],target))return true;
            }
            return false;
        }
        public boolean search(int[] arr,int tar){
    
            int l = 0;
            int r = arr.length - 1;
            while (l <= r){
    
                int mid = (l + r) / 2;
                if (arr[mid] > tar){
    
                    r = mid - 1;
                }else if (arr[mid] < tar){
    
                    l = mid + 1;
                }else {
    
                    return true;
                }
            }
            return false;
        }
    }

方法二：线性查找
根据此题二维数组的特性

    class Solution {
    
        public boolean findNumberIn2DArray(int[][] matrix, int target) {
    
            int n = matrix.length;
            if (n == 0)return false;
            int m = matrix[0].length;
            if (m == 0)return false;

            int hor = 0;
            int ver = m - 1;
            while (hor < n && ver >= 0){
    
                int num = matrix[hor][ver];
                if (num == target){
    
                    return true;
                }if (num < target){
    //num < target 则肯定可以在下方查找
                    hor++;
                }if (num > target){
    //num > target 则在左侧查找
                    ver--;
                }
            }
            return false;
        }
    }

3.剑指 Offer 05. 替换空格 简单

class Solution {
    
        public String replaceSpace(String s) {
    
            StringBuilder res = new StringBuilder();
            for (int i = 0; i < s.length(); i++) {
    
                if (s.charAt(i) == ' '){
    //是空格就替换
                    res.append("%20");
                }else {
    
                    res.append(s.charAt(i));
                }
            }
            return res.toString();
        }
    }

4.剑指 Offer 07. 重建二叉树 中等

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {
    
        public TreeNode buildTree(int[] preorder, int[] inorder) {
    
           return build(preorder,0,preorder.length - 1,inorder,0,inorder.length - 1);
        }
        public TreeNode build(int[] pre,int l,int r,int[] ino,int l2,int r2){
    
            if (l > r)return null;
            TreeNode root = new TreeNode(pre[l]);
            if (l == r)return root;
            int rootIdx = 0;//找到根节点在中序数组中的位置
            for (int i = l2; i <= r2; i++) {
    
                if (pre[l] == ino[i])
                    rootIdx = i;
            }
            root.left = build(pre,l + 1,l + (rootIdx - l2),
                    ino,l2,rootIdx - 1);
            root.right = build(pre,l + (rootIdx - l2) + 1,r,
                    ino,rootIdx + 1,r2);
            return root;
        }
    }