Leetcode--剑指Offer

🎉🎉🎉写在前面：
博主主页：🌹🌹🌹戳一戳，欢迎大佬指点！
博主秋秋：QQ：1477649017 欢迎志同道合的朋友一起加油喔💪
目标梦想：进大厂，立志成为一个牛掰的Java程序猿，虽然现在还是一个小菜鸟嘿嘿
-----------------------------谢谢你这么帅气美丽还给我点赞！比个心-----------------------------

---

---

第五期：

一，二维数组中的查找

Leetcode传送门》》》

class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
         if(matrix == null || matrix.length == 0){ //数组为null和长度是0是不一样的概念
             return false;
         }
         int row = 0;//记录行的位置
         int col = matrix[0].length -1;//记录列的位置
         while(row < matrix.length && col >= 0){
             if(matrix[row][col] < target){
                 row++;
             }else if(matrix[row][col] > target){
                 col--;
             }else{
                 return true;
             }
         }
         return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

由题意可以知道，我们在每一行上从左往右是递增的，在每一列上从上往下是递增的。所以我们就可以直接从右上角开始，利用每一行的最大值与target比较，先确定出它可能是在哪一行，然后再在这一行里面去确定是在哪一列。
根据评论区的大神提点，换种方法进行理解，其实从右上角看，整个数组就像是一个二叉搜索树。
row++就是在往右子树找，col–就是在往左子树找。

---

二，旋转数组的最小数字

Leetcode传送门》》》

class Solution {
    public int minArray(int[] numbers) {
        //暴力解法
        // int min = numbers[0];
        // for(int i = 1;i < numbers.length;i++){
        //     if(numbers[i] < min){
        //         min = numbers[i];
        //     }
        // }
        // return min;

        //二分解法
        int left = 0;
        int right = numbers.length - 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 = right - 1;
            }
        }
        return numbers[right];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

首先暴力解法，就别管这个数组是不是旋转了，就是找最小值的问题。题目说原数组是有序的，那其实就是可以往二分查找上思考。就可以看成是两个有序的数组拼接到一起，找的就是两个数组的交界处。(注意这个数组的特点，反转到后面的部分的数值肯定是比前半部分的值都要小的)

两种情况：

1，不存在重复的元素

不存在重复元素的时候，上述例子原数组反转之前是【1 2 3 4 5】,因为我们是可以通过numbers[mid]的大小来确定他是在最小值的右边还是左边。如果是numbers[mid] < numbers[right]，我们可以知道现在mid位置还是在一个子有序数组（反转到后面的那部分）里面，那么最小值肯定是在mid位置及以前。如果是numbers[mid] > numbers[right]，那么最小值肯定是在mid位置以后。

2，存在重复的元素

存在重复元素，那么就有可能存在numbers[mid] == numbers[right]的情况，这个时候你就确定不了mid的位置到底是在最小值的左边还是右边，这个时候就只能暴力的缩小范围了，right = right - 1,至于为什么不会影响到结果，因为最小值肯定是唯一的，所以就不可能是这个重复的元素了，right - 1也就没有什么问题。

---

三，第一个只出现一次的字符

Leetcode传送门》》》

class Solution {
    public char firstUniqChar(String s) {
        //哈希表的思想
        int[] arr = new int[26];
        Arrays.fill(arr,0);
        for(int i = 0;i < s.length();i++){
            arr[s.charAt(i) - 97]++;
        }
        for(int i = 0;i < s.length();i++){
            if(arr[s.charAt(i) - 97] == 1){
                return s.charAt(i);
            }
        }
        return ' ';
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

哈希表的思想，因为字符串都是小写字母。利用字符值 - 97对应到数组的指定的位置上，然后统计所有字母出现的次数，最后在遍历一遍字符串，结合其在数组中统计的次数，就可以知道谁是第一个只出现一次的字符了。

---

第六期：

一，从上到下打印二叉树

Leetcode传送门》》》

class Solution {
    public int[] levelOrder(TreeNode root) {
        //就是层序遍历二叉树进行输出
        if(root == null){
            return new int[0];
        }
        Queue<TreeNode> queue = new LinkedList<>();
        List<Integer> list = new ArrayList<>();
        //首先就把根节点入队列
        queue.offer(root);
        while(!queue.isEmpty()){
            //把队头元素出队
            TreeNode node = queue.poll();
            //判断，左右子树不为空就要入队
            list.add(node.val);
            if(node.left != null){
                queue.offer(node.left);
            }
            if(node.right != null){
                queue.offer(node.right);
            }
        }
        int[] ret = new int[list.size()];
        for(int i = 0;i < list.size();i++){
            ret[i] = list.get(i);
        }
        return ret;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

这个题考察的其实就是层序遍历整个二叉树，需要利用队列进行辅助操作，从根节点开始，根节点先入队，后面每出一个节点，就把它的left，right节点入队。当然每一个出对的元素就按照顺序存储在ArrayList里面，后序只需要将其转到数组里面就好。

---

二，从上到下打印二叉树II

Leetcode传送门》》》

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        if(root == null){
            return list;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int len = queue.size();
            List<Integer> list1 = new ArrayList<>();
            //分层进行保存，输出
            while(len != 0){
                TreeNode node = queue.poll();
                list1.add(node.val);
                if(node.left != null){
                    queue.offer(node.left);
                }
                if(node.right != null){
                    queue.offer(node.right);
                }
                len--;
            }
            list.add(list1);
        }
        return list;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

这个题相对于上一个题就是每一层上的节点需要独立出来。所以这里就是一个二维数组。每一次在进行出队元素的时候需要先看一下这个时候队列中的元素个数是多少，然后循环出就把这个一层的元素出完，再把这个记录着这一层元素的List作为一个元素添加到一个二维的List里面。

---

三，从上到下打印二叉树III

Leetcode传送门》》》

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        if(root == null){
            return list;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int level = 1;
        while(!queue.isEmpty()){
            int len = queue.size();
            List<Integer> list1 = new ArrayList<>();
            //分层进行保存，输出
            while(len != 0){
                TreeNode node = queue.poll();
                if(level % 2 != 0){
                    list1.add(node.val);//直接尾插
                }else{
                    list1.add(0,node.val);//进行头插
                }
                if(node.left != null){
                    queue.offer(node.left);
                }
                if(node.right != null){
                    queue.offer(node.right);
                }
                len--;
            }
            level++;
            list.add(list1);
        }
        return list;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

这个题在上一个题的基础之上，又加了一个要求，就是偶数层数上的节点输出的时候需要从右往左输出，奇数层数上的正常从从左往右输出。其实整体的思路是一样的，只不过在添加到那个List的时候需要考虑一下是奇数层还是偶数层，偶数层就是用头插法插入元素就好，就达到了从右往左的效果。

---

第七期：

一，树的子结构

Leetcode传送门》》》

class Solution {
    public boolean isSameTree(TreeNode p,TreeNode q){
        //判断是不是子树，其实也就是从某个节点开始判断两个树是不是一样的
        //每两个几点对比的时候有三种情况

        if(p == null && q != null){//其中有一个节点是空
            return false;
        }

        if(p != null && q == null){//这种情况比较特殊，相当于B树遍历完了而A树没有，就是B树是A的一部分，这种情况在这个题里面也是算的子树
            return true;
        }

        if(p == null && q == null){//两个都是空
            return true;
        }

        if(p.val != q.val){
            return false;//走到这里两个都不是空
        }

        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        //判断是不是子树
        if(A == null || B == null){
            return false;
        }
        //先判断是不是从根节点处就是相同的
        if(isSameTree(A,B)){
            return true;
        }

        return isSubStructure(A.left,B) || isSubStructure(A.right,B);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

判断是不是子树，如果A，B两棵树中有一个直接是null，那就直接不是子树了按照题目意思。先判断从根节点开始是不是就是子树，然后再是左子树，再是右子树。每一次判断是不是子树的过程，其实就是两颗树一个个几点进行对比。

---

二，二叉树的镜像

Leetcode传送门》》》

// class Solution {
//     public void toMirrorTree(TreeNode root){
//         if(root == null){
//             return ;
//         }
//         TreeNode tmp = root.left;
//         root.left = root.right;
//         root.right = tmp;
//         toMirrorTree(root.left);
//         toMirrorTree(root.right);
//     }
//     public TreeNode mirrorTree(TreeNode root) {
//         if(root == null){
//             return null;
//         }
//         toMirrorTree(root);
//         return root;
//     }
// }

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

上面一共写了两种方法，一个思路是从上面往下面进行调整，一个是从下面往上面进行调整，左右进行交换的时候注意要先把值保存下来，不然交换的时候就会被覆盖掉。

三，对称的二叉树

Leetcode传送门》》》

class Solution {

    public boolean check(TreeNode A,TreeNode B){
        //是否对称比较的也是对应位置上的节点的关系，也是下面三种情况
        if(A == null && B != null || A != null && B == null){
            return false;
        }

        if(A == null && B == null){
            return true;
        }

        if(A.val != B.val){
            return false;
        }

        return check(A.left,B.right) && check(A.right,B.left); 
    }
    
    public boolean isSymmetric(TreeNode root) {
        if(root == null){//如果根节点就是空的了。那就直接是对称的
            return true;
        }

        return check(root.left,root.right);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

判断是不是对称的树，首先根节点只有一个节点不需要考虑，重点就是对比树的左子树与右子树。对比的过程就是对应节点的进行比较。

---

第八期：

一，斐波那契数列

Leetcode传送门》》》

class Solution {
    public int fib(int n) {
        //注意n是从0开始的
        if(n < 2){
            return n;
        }

        int a = 0;
        int b = 0;
        int c = 1;
        for(int i = 2;i <= n;i++){
            a = b;
            b = c;
            c = (a + b)%1000000007;
        }
        return c;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

斐波那契数列，这种题比较简单了，注意下从第几项开始，然后通过递推公式循环计算就好。最好不要用递归，因为中间会有很多的重复计算，效率太低。

---

二，青蛙跳台阶问题

Leetcode传送门》》》

class Solution {
    public int numWays(int n) {
        if(n < 2){
            return 1;
        }
        int a = 1;
        int b = 1;
        int c = 0;
        for(int i = 2;i <= n;i++){
            c = (a + b)%1000000007;
            a = b;
            b = c;
        }
        return c;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

这其实就是一个换了种说法的斐波那契数列的问题。注意这个题有一个点就是n = 0的时候还有一种跳法，虽然不是很理解，但是我们还是得考虑到这种情况。

至于为什么是斐波那契数列，当n>2的时候，到最后一个台阶就有两种方法，可以是在某个基础之上跳一步，或者是跳两步。如果是跳一步，那么剩下的就是n-1个台阶的跳法，如果是跳两步，那么剩下的就是n-2个台阶的跳法。其实得到的公式也就是F(n-1) + F(n-2)，所以其实也就是斐波那契数列。

---

三，股票的最大利润

Leetcode传送门》》》

class Solution {
    public int maxProfit(int[] prices) {
        // //暴力
        // int profits = 0;
        // for(int i = prices.length - 1;i > 0;i--){
        //     for(int j = 0;j < i;j++){
        //         if(prices[j] < prices[i] && (prices[i] - prices[j]) > profits){
        //             profits = prices[i] - prices[j];
        //         }
        //     }
        // }
        // return profits;

        //一次遍历
        int profits = 0;
        int minprice = Integer.MAX_VALUE;//记录最小价格
        for(int i = 0;i < prices.length;i++){
            if(prices[i] < minprice){//更新最小值
                minprice = prices[i];
            }else if(prices[i] - minprice > profits){//走这里就说明可以进行卖出
                profits = prices[i] - minprice;
            }
        }
        return profits;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

首先暴力解法就是两层循环，一种种情况的求解，最终找到那个最小值。这里主要是要学习第二种解法，也即是官方的解法。也很好理解，就是我们在遍历的时候，一直去更新最小值，因为我们想要得到最大的利润肯定是想低价的时候买入，高价的时候卖出。prices[i] < minprice的时候，说明价格还在低，所以就继续更新最小值。当这个条件不满足的时候，说明当前的价格比我们的最小值高，也就是可以进行卖出，这个时候profits就会记录我们的prices[i] - minprice的差值，当让profits也会实时更新的，最终保存的是最大的。

---