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

找的是任意一个重复的数字，所以只找重复就可以了。
首先我想到的是建一个数组，当输入2的时候，我就把下标为2 的位置填入1，最后遍历一遍，这样做甚至是可以把所有的数字出现次数打印出来。

如果随便找一个，我不需要把这个流程走完，只需要在给数组赋值的时候，进行一次判断，如果为1，就可以直接返回了。

  1. class Solution {
  2.     public int findRepeatNumber(int[] nums) {
  3.         int len = nums.length;
  4.         int[] arr = new int[len];
  5.         for(int i : nums){
  6.             if(arr[i]!=0) return i;
  7.             else{
  8.                 arr[i] = 1;
  9.             }
  10.         }
  11.         return 0;
  12.     }
  13. }

这样的话，我开辟了一个数组，空间复杂度应该是还可以优化的。
其实可以用到HashSet，因为HashSet是不会存入重复元素的。HashSet的add方法是会判断元素是否存在的，如果存在会返回false,所以，代码可以改成这样。

class Solution {
    public int findRepeatNumber(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for(int i:nums){
            if(!set.add(i)) return i;
        }
        return 0;
    }
}

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

拿到这个题目，如果直接暴力的话，的确是很简单的，直接来一次遍历就可以了，但这样的话，题目中给的行和列都是递增这个条件就浪费掉了，如果是一维数组，直接使用二分法应该就可以了。

考虑到二分法的话，感觉对行和列来进行二分都不太好，根据题目，我可以得到一个结论，那就是右下角的元素是最大的。所以我在想，可不可以经过二分法，将我需要判断的元素精确定位到某行或列，然后对这一行和列进行查找，效率会高一些。这样写应该是可以做，但是好像还是很麻烦。进行了3次二分查找才找出来，对角线来一次，找到所在的行和列分别也要来一次，感觉好复杂。
我写完了代码，才发现题目看错了，这样是不行的。

// 错误代码
class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if(matrix.length==0 || matrix[0].length == 0) return false;
        return BinarySearchResult(matrix,target);
    }

    public int BinarySearch(int[][] matrix, int target){
        int m = matrix.length;
        int left = 0,right = m-1;
        while(left<=right){
            int mid = left+(right-left)/2;
            if(matrix[mid][mid]>target){
                right = mid-1;
            }else if(matrix[mid][mid]<target){
                left = mid+1;
            }else{
                // 对角线上就有这元素，直接返回
                return -1;
            }
        }
        return left;
    }

    public boolean BinarySearchResult(int[][] matrix, int target){
        int n = BinarySearch(matrix,target);
        if(n==-1){
            return true;
        }
        int left = 0,right = n;
        while(left<=right){
            int mid = left+(right-left)/2;
            if(matrix[n][mid]>target){
                right = mid-1;
            }else if(matrix[n][mid]<target){
                left = mid+1;
            }else{
                // 对角线上就有这元素，直接返回
                return true;
            }
        }
        left = 0;
        right = n;
        while(left<=right){
            int mid = left+(right-left)/2;
            if(matrix[mid][n]>target){
                right = mid-1;
            }else if(matrix[mid][n]<target){
                left = mid+1;
            }else{
                // 对角线上就有这元素，直接返回
                return true;
            }
        }
        return false;
    }
}

之所以保留上面的代码，就是为了给自己提醒。

  • 首先，题意看错了，二维数组是nm而不是nn，所以，从一开始我的思路就错了，
  • 其次，忘记判断特殊情况，数组为空怎么办
  • 最后，对于数组最常见的数组越界错误没有敏感。

其实，对于二分应该还可以精简，但我硬生生是写了三遍，只是为了好理解，这些 ，都是需要改进的地方。

看了一下官方思路，是从右上角，如果目标比右上角大，就下移，如果目标比右上角小，就左移。

class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        // 需要先进行判断
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
        int rows = matrix.length;
        int cols = matrix[0].length;
        int i = 0;
        int j = cols-1;
        while(i < rows && j >= 0){
            int num = matrix[i][j];
            if(num == target) return true;
            else if(num>target) j--;
            else i++;
        }
        return false;
    }
}

剑指 Offer 05. 替换空格

这个题目考的是StringBuilder，把不可变的字符串用可变的StringBuilder来重写。
这里面还有个charAt()函数，也可以记一下。

class Solution {
    public String replaceSpace(String s) {
        StringBuilder sb = new StringBuilder();
        for(int i = 0;i<s.length();i++){
            char c = s.charAt(i);
            if(c == ' ') sb.append("%20");
            else sb.append(c);
        }
        return sb.toString();
    }
}

剑指 Offer 06. 从尾到头打印链表

这个题目就是多了个数组返回，如果不是数组，本来是想直接把链表的元素放到list里面，然后reverse一下的。
因为题目中要数组，所以连reverse这个操作都不需要了，在list转array的时候，倒着往数组写值就可以了。

class Solution {
    public int[] reversePrint(ListNode head) {
        List<Integer> list = new ArrayList<>();
        if(head == null) return new int[]{};
        ListNode p = head;
        while(p!=null){
            list.add(p.val);
            p = p.next;
        }
        int len = list.size();
        int[] res = new int[len];

        for(int li: list){
            res[--len] = li;
        }
        return res;
    }
}

剑指 Offer 07. 重建二叉树(重写)

这个题目的代码是我看着答案写的，其实思路是有的，但是自己写不出来。
这个题目还是要重新写。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {

    private Map<Integer,Integer> indexMap;

    public TreeNode myBuildTree(int[] preorder,int[] inorder,int preorder_left,int preorder_right,
                                int inorder_left,int inorder_right){
        if(preorder_left > preorder_right){
            return null;
        }               
        // 前序遍历的第一个节点就是根节点
        int preorder_root = preorder_left; 
        // 在中序遍历中定位根节点
        int inorder_root = indexMap.get(preorder[preorder_root]);
        // 先把根节点建立起来
        TreeNode root = new TreeNode(preorder[preorder_root]);
        // 得到左子树的节点数目
        int size_left_subtree = inorder_root - inorder_left;
        // 递归的构造左子树，并连接到根节点
        root.left= myBuildTree(preorder,inorder,preorder_left+1,preorder_left+size_left_subtree,
                               inorder_left,inorder_root-1);
        // 递归的构造右子树，并连接到根节点
        root.right = myBuildTree(preorder,inorder,preorder_left+size_left_subtree+1,preorder_right,
                                 inorder_root+1,inorder_right);
        return root;
    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        indexMap = new HashMap<>();
        for(int i = 0;i<n;i++){
            indexMap.put(inorder[i],i);
        }
        return myBuildTree(preorder,inorder,0,n-1,0,n-1);
    }
}

剑指 Offer 09. 用两个栈实现队列

题目实际上不难，算是简单题，主要就是需要注意一下栈的写法比较多，可以定义为Stack，也可以使用List。

class CQueue {

    LinkedList<Integer> stack1;
    LinkedList<Integer> stack2;

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

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

    public int deleteHead() {
        if(!stack2.isEmpty()){
            return stack2.remove();
        }else{
            if(stack1.isEmpty()){
                return -1;
            }else{
                for(int i = 0;i<stack1.size();i++){
                    stack2.add(stack1.remove());
                }
                return stack2.remove();
            }
        }
    }
}

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue obj = new CQueue();
 * obj.appendTail(value);
 * int param_2 = obj.deleteHead();
 */

剑指 Offer 10- I. 斐波那契数列

现在再做这个题就感觉好简单啊~~哈哈哈

class Solution {
    int[] res = new int[105];
    public int fib(int n) {
        res[0] = 0;
        res[1] = 1;
        for(int i = 2;i<=n;i++){
            res[i] = res[i-1]+res[i-2];
            res[i]%=1000000007;
        }
        return res[n];
    }
}

剑指 Offer 11. 旋转数组的最小数字

这个是可以优化的，但是目前我不知道怎么优化。

class Solution {
    public int minArray(int[] numbers) {
        int min = Integer.MAX_VALUE;

        for(int number: numbers){
            if(number<min){
                min = number;
            }
        }
        return min;
    }
}

剑指 Offer 12. 矩阵中的路径

class Solution {
    public boolean exist(char[][] board, String word) {
        int h = board.length, w = board[0].length;
        boolean[][] visited = new boolean[h][w];
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                boolean flag = check(board, visited, i, j, word, 0);
                if (flag) {
                    return true;
                }
            }
        }
        return false;
    }

    public boolean check(char[][] board, boolean[][] visited, int i, int j, String s, int k) {
        if (board[i][j] != s.charAt(k)) {
            return false;
        } else if (k == s.length() - 1) {
            return true;
        }
        visited[i][j] = true;
        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        boolean result = false;
        for (int[] dir : directions) {
            int newi = i + dir[0], newj = j + dir[1];
            if (newi >= 0 && newi < board.length && newj >= 0 && newj < board[0].length) {
                if (!visited[newi][newj]) {
                    boolean flag = check(board, visited, newi, newj, s, k + 1);
                    if (flag) {
                        result = true;
                        break;
                    }
                }
            }
        }
        visited[i][j] = false;
        return result;
    }
}

剑指 Offer 15. 二进制中1的个数

这个题目是位运算的题目，我掌握的很不好

public class Solution {
    public int hammingWeight(int n) {
        int ret = 0;
        for (int i = 0; i < 32; i++) {
            if ((n & (1 << i)) != 0) {
                ret++;
            }
        }
        return ret;
    }
}

剑指 Offer 16. 数值的整数次方(重写)

使用快速幂，可是我不会写。
还有，我的位运算还不太理解，位运算也需要再搞一搞。

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

剑指 Offer 17. 打印从1到最大的n位数

这个题目我用的是最蠢的方法。
因为题目要返回的是int数组，所以不会越界，题目就变简单了。

class Solution {
    public int[] printNumbers(int n) {
        // n 是位数
        int sum = 9;
        for(int i = 1;i<n;i++){
            sum = sum*10 + 9;
        }
        List<Integer> list = new ArrayList<>();
        for(int i = 1;i<=sum;i++){
            list.add(i);
        }
        int[] res = new int[list.size()];
        int t = 0;
        for(int i : list){
            res[t++] = i;
        }
        return res;
    }
}

剑指 Offer 18. 删除链表的节点

class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        ListNode dummy = new ListNode();
        dummy.next = head;
        ListNode p = dummy;
        while(head!=null){
            if(head.val==val){
                p.next = head.next;
            }

            head = head.next;
            p = p.next;
        }
        return dummy.next;
    }
}

剑指 Offer 21. 调整数组顺序使奇数位于偶数前面

用双指针去做，还是比较简单的。

class Solution {
    public int[] exchange(int[] nums) {
        int len = nums.length;
        int i = 0,j = len-1;
        while(i<=j){
            if(nums[i]%2==0){
                int temp = nums[j];
                nums[j] = nums[i];
                nums[i] = temp;
                j--;
            }else{
                i++;
            }
        }
        return nums;
    }
}

剑指 Offer 22. 链表中倒数第k个节点

这个题目也是用双指针去做，比较简答。

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode p = head;
        ListNode q = head;
        while(q!=null){
            q = q.next;
            k--;
            if(k<0){
                p = p.next;
            }
        }
        return p;
    }
}

剑指 Offer 24. 反转链表

这个题目我做了好多遍了，每次都做不好。

class Solution {
    public ListNode reverseList(ListNode head) {
        return recur(head,null);
    }
    ListNode recur(ListNode cur,ListNode pre){
        // 终止条件
        if(cur==null) return pre;
        // 递归后继结点
        ListNode res = recur(cur.next,cur);
        // 修改结点引用指向
        cur.next = pre;
        // 返回反转链表的头结点
        return res;
    }
}

剑指 Offer 25. 合并两个排序的链表

就是简单的二路归并。

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode p = l1;
        ListNode q = l2;
        ListNode dummy = new ListNode();
        ListNode r = dummy;
        while(p!=null&&q!=null){
            if(p.val<=q.val){
                r.next = p;
                p = p.next;
            }else{
                r.next = q;
                q = q.next;
            }
            r = r.next;
        }
        if(p!=null){
            r.next = p;
        }
        if(q!=null){
            r.next = q;
        }
        return dummy.next;
    }
}

剑指 Offer 27. 二叉树的镜像(重写)

很简单的递归，可我没写出来。

class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        // 递归交换左右子树
        if(root==null) return null;
        TreeNode left = mirrorTree(root.left);
        TreeNode right = mirrorTree(root.right);
        root.left = right;
        root.right = left;
        return root;
    }
}

剑指 Offer 28. 对称的二叉树

看到这题的时候，简单画了画，就得出了一个错误的结论: 对称二叉树的中序遍历是回文串。我原本以为这样是可行的，提交的时候发现有样例过不了。
重新找思路，感觉，以后二叉树就用递归去做了。二叉树对称，所以二叉树的每个结点的左右字数都对称。
其实这个题目我在半个月之前做过啊，难顶~~

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return root==null?true: recur(root.left,root.right);
    }

    boolean recur(TreeNode L,TreeNode R){
        if(L==null && R==null) return true;
        if(L==null || R == null || L.val!=R.val) return false;
        return recur(L.left,R.right) && recur(R.left,L.right);
    }
}

剑指 Offer 35. 复杂链表的复制(抄)

class Solution {
    public Node copyRandomList(Node head) {
        if(head == null) return null;
        Node cur = head;
        Map<Node, Node> map = new HashMap<>();
        // 3. 复制各节点，并建立 “原节点 -> 新节点” 的 Map 映射
        while(cur != null) {
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }
        cur = head;
        // 4. 构建新链表的 next 和 random 指向
        while(cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        // 5. 返回新链表的头节点
        return map.get(head);
    }
}

剑指 Offer 39. 数组中出现次数超过一半的数字

这个题目我只会用哈希表去做，评论里有说腾讯考到了，要求用空间复杂度为O(1)去做。
这个题目的最优解法是摩尔投票法，就是相互抵消，站到最后的必定是超过一半的。

class Solution {
    public int majorityElement(int[] nums) {
        int len = nums.length;
        Map<Integer,Integer> mp = new HashMap<>();
        for(int i = 0;i<len;i++){
            if(mp.containsKey(nums[i])){
                mp.put(nums[i],mp.get(nums[i])+1);
            }else{
                mp.put(nums[i],1);
            }

            if(mp.get(nums[i]) > len/2){
                return nums[i];
            }
        }
        return -1;
    }
}

剑指 Offer 53 - I. 在排序数组中查找数字 I

class Solution {
    public int search(int[] nums, int target) {
        //两次二分查找，第一次找左边，第二次找右边
        int left = searchLeft(nums,target);
        int right = searchRight(nums,target);
        if(left==-1||right==-1){
            return 0;
        }
        return right-left+1;
    }
    public int searchLeft(int[] nums,int target){
        int left = 0;
        int right = nums.length-1;
        int res = -1;
        while(left<=right){
            int mid = left+(right-left)/2;
            if(nums[mid]<target){
                left = mid+1;
            }else if(nums[mid]>target){
                right = mid-1;
            }else{
                res = mid;
                right = mid-1;
            }
        }
        return res;
    }
    public int searchRight(int[] nums,int target){
        int left = 0;
        int right = nums.length-1;
        int res = -1;
        while(left<=right){
            int mid = left+(right-left)/2;
            if(nums[mid]<target){
                left = mid+1;
            }else if(nums[mid]>target){
                right = mid-1;
            }else{
                res = mid;
                left = mid+1;
            }
        }
        return res;
    }
}

剑指 Offer 53 - II. 0～n-1中缺失的数字

class Solution {
    public int missingNumber(int[] nums) {
        int len = nums.length;
        int i = 0;
        for(i = 0;i<len;i++){
            if(nums[i]!=i){
                return i;
            }
        }
        return i;
    }
}