Leetcode 剑指 Offer 03 - 10 Java题解

1. 暴力循环，超时TAT

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

2. 利用 Set 特性【不可重复】，用 list.contains()也可以实现，不过会超时！

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

3. 排序 + 遍历

class Solution {
    public int findRepeatNumber(int[] nums) {
        Arrays.sort(nums);
        for (int i = 1; i < nums.length; i++) {
            if (nums[i - 1] == nums[i]) return nums[i];
        }
        return -1;
    }
}

1. 常规遍历二维数组查找

class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == target) return true;
            }
        }
        return false;
    }
}

2. 根据数组 从左到右，从上到下 递增特性，从右上方开始查找

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

1. 调用 API：str.replace()

class Solution {
    public String replaceSpace(String s) {
        return s.replace(" ", "%20");
    }
}

2. 构建StringBuilder拼接，遍历字符串，遇到空格append("%20")

class Solution {
    public String replaceSpace(String s) {
        StringBuilder sb = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (c == ' ') sb.append("%20");
            else sb.append(c);
        }
        return sb.toString();
    }
}

• 遍历链表获取链表个数 n，新建长度为 n 的新数组
  遍历链表，同时数组反向赋值（即链表第一个值给数组最后一个值…）

class Solution {
    public int[] reversePrint(ListNode head) {
        int n = 0;
        ListNode cur = head;
        while (cur != null) {
            n++;
            cur = cur.next;
        }
        int[] arr = new int[n];
        cur = head;
        for (int i = n - 1; i >= 0; i--) {
            arr[i] = cur.val;
            cur = cur.next;
        }
        return arr;
    }
}

• 给出前序遍历和中序遍历，构建二叉树
• 根据前中序或中后序构造二叉树：
  前序遍历：根-左-右
  中序遍历：左-根-右
  后序遍历：左-右-根

1. 首先找到根的前序（第一个）或后序（最后一个）找到根节点的值
2. 找到根节点在中序遍历所处的位置，记录索引为 index
3. 已知中序遍历中，左子树在 index 左侧，右子树在 index 右侧
4. 数组不变，我们通过改变两个数组的左右指针来控制构造二叉树，其中要注意借助 leftSize = index - inStart 这个点得到左子树个数，以 leftSize 作传值

• 只需得到 ？中的数值即可
  root.left = build(preorder, ?, ?, inorder, ?, ?);
  root.right = build(preorder, ?, ?, inorder, ?, ?);

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int len = preorder.length;
        if (len == 0) return null;
        int rootValue = preorder[0];
        int rootIndex = 0;
        for (int i = 0; i < len; i++) {
            if (inorder[i] == rootValue) {
                rootIndex = i;
                break;
            }
        }
        TreeNode root = new TreeNode(rootValue);
        root.left = buildTree(Arrays.copyOfRange(preorder,1,rootIndex + 1),Arrays.copyOfRange(inorder,0,rootIndex));
        root.right = buildTree(Arrays.copyOfRange(preorder,1+rootIndex,len),Arrays.copyOfRange(inorder,rootIndex+1,len));
        return root;
    }
}

• 如果使用Stack的方式来做这道题，会造成速度较慢； 原因是Stack继承了Vector接口，而Vector底层是一个Object[]数组，那么就要考虑空间扩容和移位的问题
• 可以使用linkedList来做Stack的容器，因为linkedList实现了Deque接口，所以Stack能做的事linkedList都能做，其本身结构是个双向链表，扩容消耗少
• 但不是直接使用一个 linkedList 当做队列，不符题意

class CQueue {
    linkedList stack1;
	linkedList stack2;
    public CQueue() {
        stack1 = new linkedList<>();
		stack2 = new linkedList<>();
    }
    
    public void appendTail(int value) {
        stack1.add(value);
    }
    
    public int deleteHead() {
        if (stack2.isEmpty()){
       		//两个栈都为null，说明此时无元素，返回 -1
            if (stack1.isEmpty()) return -1;
            //只有 stack2 为空，将stack1的元素添加到stack2中，同时返回栈顶值
            while (!stack1.isEmpty()) {
                stack2.add(stack1.pop());
            }
            return stack2.pop();
        }
        //stack2 不为空，直接返回栈顶值
        return stack2.pop(); 
    }
}

1. 递归

class Solution {
    public int fib(int n) {
        if (n == 0 || n == 1) return n;
        return fib(n - 1) + fib(n - 2);
    }
}

2. 定义 dp 数组，动态规划

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

3. 进阶：不用数组，定义三个临时遍历存储值，节省空间

class Solution {
    public int fib(int n) {
        if (n == 0 || n == 1) return n;
        int a = 0, b = 1, c = 0;
        for (int i = 2; i <= n; i++) {
            c = (a + b) % 1000000007;
            a = b;
            b = c;
        }
        return c;
    }
}