剑指Offer

03 找出重复数字

public int findRepeatNumber(int[] nums) {
        int temp;
        for(int i=0;i<nums.length;i++){
            while (nums[i]!=i){
                if(nums[i]==nums[nums[i]]){
                    return nums[i];
                }
                temp=nums[i];
                nums[i]=nums[temp];
                nums[temp]=temp;
            }
        }
        return -1;
    }

原地置换，时间O(n),空间O(1);

04 (有序)二维数组查找

public boolean findNumberIn2DArray(int[][] matrix, int target) {
    int i = matrix.length - 1, j = 0;
    while(i >= 0 && j < matrix[0].length)
    {
        if(matrix[i][j] > target) i--;
        else if(matrix[i][j] < target) j++;
        else return true;
    }
    return false;
}

按边查找

07 重建二叉树

给出前序中序，重建二叉树。
三种方法：

1. 递归，
   • 找到根节点后，再分别构建左右子树。
2. 迭代，
   • 使用前序遍历一直构造左子树，通过与中序比对找到对应右节点位置。
3. 索引，
   • 让前序遍历的序列有中序序列的索引，再遍历前序时按照二叉排序树的方式插入。（左节点比根节点索引小，右节点比根节点索引大）
   • 此方法学自Q-WHai大佬的重建二叉树三种方法

递归：

class Solution {
    private Map<Integer,Integer> indexMap; 

    private TreeNode reBuildTree(int[] pre,int preStart,int preEnd,int[] in,int inStart,int inEnd) {
        if(preStart>preEnd || inStart>inEnd) { 
            return null;
        }
        int pre_root = preStart;
        int in_root = indexMap.get(pre[pre_root]);
        TreeNode cur_root = new TreeNode(pre[pre_root]); //构建当前树的根节点
        cur_root.left = reBuildTree(pre,preStart+1,preStart+in_root-inStart,in,inStart,in_root-1);
        cur_root.right = reBuildTree(pre,preStart+in_root-inStart+1,preEnd,in,in_root+1,inEnd);
        return cur_root;
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        indexMap = new HashMap<>(); //方便查找中序遍历中的节点位置
        for (int i = 0; i < preorder.length; i++) {
            indexMap.put(inorder[i], i);
        }
        TreeNode root = reBuildTree(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
        return root;
    }
}

09 用两个栈实现队列

stack1 用于实现队尾插入，stack2 用于实现队头弹出
小技巧是不必每次都将stack1倒入stack2。

class CQueue {
    private Stack<Integer> stack1;
    private Stack<Integer> stack2;

    public CQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }

    public void appendTail(int value) {
        stack1.push(value);
    }

    public int deleteHead() {
        if(stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        if(stack2.isEmpty()) {
            return - 1;
        } else {
            return stack2.pop();
        }
    }
}

11 旋转数组的最小数字

二分查找不只在有序数组中能使用，二分减治思想是分治的特殊情况，只要划分出一个有序的查找区间，就能使用二分法。

class Solution {
    public int minArray(int[] numbers) {
        int n = numbers.length;
        int left = 0;
        int right = n-1;
        while (left < right) {
            int mid = (left + right) / 2;
            if(numbers[mid] < numbers[right]) {
                right = mid;
            } else if(numbers[mid] > numbers[right]) {
                left = mid+1;
            } else {  //相等的时候丢弃最右边的
                right -= 1;
            }
        }
        return numbers[left];
    }
}

12 矩阵中的路径

中规中矩的DFS

class Solution {
    public boolean exist(char[][] board, String word) {
        char[] words = word.toCharArray();
        for(int i = 0; i < board.length; i++) {
            for(int j = 0; j < board[0].length; j++) {
                if(dfs(board, words, i, j, 0)) return true;
            }
        }
        return false;
    }
    private boolean dfs(char[][] board, char[] word, int i, int j, int k) {
        if(i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != word[k]) return false;
        if(k == word.length - 1) return true;
        board[i][j] = '\0'; //标记为空，防止重复搜索
        boolean res = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1) ||
                dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i , j - 1, k + 1);
        board[i][j] = word[k];
        return res;
    }
}