reverse ListNode

步步拆解：如何递归地反转链表的一部分 - 反转链表 II - 力扣（LeetCode）

1️⃣翻转整个链表

206. 反转链表

难度简单2760

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

  • 基本的迭代写法, 不再赘述
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null||head.next==null) return head;
        ListNode pre=null;
        ListNode cur=head;
        while(cur!=null){
            ListNode tmp=cur.next;
            cur.next=pre;
            pre=cur;
            cur=tmp;
        }
        return pre;
    }
}

递归翻转链表

1
2
3
4
5
6
7
ListNode reverse(ListNode head) {
    if (head.next == null) return head;
    ListNode last = reverse(head.next);
    head.next.next = head;
    head.next = null;
    return last;
}

具体来说，我们的 reverse 函数定义是这样的：

输入一个节点 head，将「以 head 为起点」的链表反转，并返回反转之后的头结点。

明白了函数的定义，在来看这个问题。比如说我们想反转这个链表：

base

那么在我们输入reverse(head)后 , 会在这里递归

ListNode last = reverse(head.next);

这里不要去想递归的过程,

简单的递归还可以去想想, 复杂的递归凭空想象难以进行

我们直接来看递归的结果

递归作用示意图

结果:

递归结果示意图

再来看reverse的定义, 会在返回链表之后返回函数的头结点, 也就是上面的last

现在再来看下面的代码：

head.next.next = head;

接下来：

head.next = null; return last;

这样一来,我们可以发现整个链表已经翻转过来了

1
2
3
4
5
6
7
ListNode reverseListNode(ListNode head){
    if(head.next==null) return null; // 递归截止条件: 当前节点没有子节点
   	ListNode last=reverseListNode(head.next); // 翻转头结点之后的链表
    head.next.next=head; // 更改当前节点的下一个节点的指向(翻转当前节点)
    head.next=null;//头结点指空
    return last;// 返回翻转之后的头结点
}

2️⃣反转链表前 N 个节点

问题:给定链表头结点 n, 翻转链表前n个节点

  • 保证n>=节点个数

翻转前n个节点, 我们需要多做的一步就是让最开始的 head 指向第n+1个节点

那么我们需要做的操作就是

  1. 保存第n+1 个节点
  2. 让最开始的头结点指向第n+1个节点

这里可以在递归终止的时候去保存第n+1 个节点

1
2
3
4
5
6
7
8
9
10
11
12
// 翻转以head 为头结点的n个节点, 
ListNode succerror=null;
ListNode reverseListNode(ListNode head,int n){
    if(n==1){
       succerror=head.next;// 此时的head 的节点其实就是 第n个节点, 我们保存他指向的节点即可
        return head;
    }
    ListNode last=reverseListNode(head.next,n-1);
   	head.next.next=head;
    head.next=succerror;// 使头结点指向 n+1 个节点
    return last;
}z`

3️⃣翻转指定范围的节点

经过了上面的解释, 那么对于当前的这个问题, 也就迎刃而解了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    ListNode succerror=null;
        // 对于一个递归函数,不应该太过于在意他的过程,应该注重结果, 利用好截止条件以及返回值,
    public ListNode reverseBetween(ListNode head, int left, int right){
        // 那么我们这个递归方法的作用就是 翻转 一个链表指定范围的 节点并返回链表的头结点
        //利用好 翻转方法返回翻转的区间的最后的一个节点的特性
        if(left==1){
            return reverseListNode(head,right);
        }
        head.next=reverseBetween(head.next,left-1, right-1);
        return head;
    }
    ListNode reverseListNode(ListNode head,int n){
        if(n==1){
            succerror=head.next;// 此时的head 的节点其实就是 第n个节点, 我们保存他指向的节点即可
            return head;
        }
        ListNode last=reverseListNode(head.next,n-1);
        head.next.next=head;
        head.next=succerror;// 使头结点指向 n+1 个节点
        return last;
    }
}

92. 反转链表 II

难度中等1397

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

迭代

把链表的节点储存在List中, 交换节点

  • 这样的做法可以达到题目的要求, 但是曲解了题意
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if(head.next==null||left==right) return head;
        ListNode cur=head;
        List<ListNode> list=new ArrayList<>();
        list.add(new ListNode());// 链表的下标从1 开始, 添加一个垫底的
        while(cur!=null){
            list.add(cur);
            cur=cur.next;
        }
        int len=right-left;
        for (int i = 0; i < (len+1)/2; i++) {
            int tmp=list.get(right-i).val;
            list.get(right-i).val=list.get(left+i).val;
            list.get(left+i).val=tmp;
        }
        return head;
    }
}

322. 零钱兑换 :DP

难度中等2131

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

  1. dp数组含义 : dp[j]：凑足总额为j所需钱币的最少个数为dp[j]

  2. 确定递推公式

    得到dp[j]（考虑coins[i]），只有一个来源，dp[j - coins[i]]（没有考虑coins[i]）。

    凑足总额为j - coins[i]的最少个数为dp[j - coins[i]]，

    那么只需要加上一个钱币coins[i]即dp[j - coins[i]] + 1就是dp[j]（考虑coins[i]）

    所以dp[j] 要取所有 dp[j - coins[i]] + 1 中最小的。

    递推公式：dp[j] = min(dp[j - coins[i]] + 1, dp[j]);

    可以大致理解为 :

    遍历硬币的金额, 其实就是物品, amount 就是背包的容量
    当前需要的金额大于金币的面值, 也就是可以装金币
    那么如果装了当前的金币, 剩余的需要的面值就是 j-coins[i] ,

    这个时候我们就需要dp[j-coins[i]] dp[j] = Math.min(dp[j],dp[j-coins[i]]+1);

    • 对于替换较小金币为较大金币的问题, 可以在遍历金币的过程中更新对应的数值

  3. dp数组初始化 :

    • 首先凑足总金额为0所需钱币的个数一定是0，那么dp[0] = 0;

    • 考虑到递推公式的特性，dp[j]必须初始化为一个较大的数字，

      否则就会在min(dp[j - coins[i]] + 1, dp[j])比较的过程中被初始值覆盖。所以下标非0的元素都是应该是最大值。

    这里将数组除了0之外的元素初始化为一个特殊的元素即可 114514

  4. 返回值 : 题目要求计算返回可以凑成总金额所需的 最少的硬币个数 , 因此我们返回dp[amount] 即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int coinChange(int[] coins, int amount) { //先物品再背包
        // 本题 coins 的每个硬币的面额就相当于value ,  每个硬币的weight 都是1 , dp[i]的i 就相当于 bagWeight ,
        int[]dp=new int[amount+1];// dp[i] 表示可以凑成 I 金额需要的最少硬币个数
        Arrays.fill(dp,114514);
        dp[0]=0;
        // 需要想办法统计 当前的金额是否可以凑出
        for (int i = 0; i < coins.length; i++) {// 遍历硬币的金额, 其实就是物品
            for (int j = coins[i]; j <= amount; j++) { // amount 就是背包的容量
                // if(j-coins[i]>0){// 当前需要的金额大于金币的面值, 也就是可以装金币
                if(dp[j-coins[i]]!=114514){// 当前需要的金额大于金币的面值, 也就是可以装金币
                    // 那么如果装了当前的金币, 剩余的需要的面值就是 j-coins[i] , 这个时候我们就需要dp[j-coins[i]]
                    dp[j] = Math.min(dp[j],dp[j-coins[i]]+1);
                }
            }
        }
        return dp[amount]==114514?-1:dp[amount];
    }
}

518. 零钱兑换 II

难度中等919

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。

  1. dp数组含义 : dp[j] 表示可以凑成j金额 的方法的种数

  2. 状态转移 : dp[j]（考虑coins[i]的组合总和） 就是所有的dp[j - coins[i]]（不考虑coins[i]）相加。

    dp[j]+=dp[j-coins[i]]

    求装满背包有几种方法，一般公式都是：dp[j] += dp[j - nums[i]];

  3. dp数组初始化: 对于 0 ,根据dp数组的含义应该初始化为1, 对于其他的位置, 应该初始化为0,

  4. 返回值 : 题目要求计算并返回可以凑成总金额的硬币组合数, 因此我们返回dp[amount] 即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int change(int amount, int[] coins) {
        int[]dp=new int[amount+1];// dp[i] 表示可以凑成 i 金额 的方法的种数 (排列数)
        dp[0]=1;
        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <=amount; j++) {
                dp[j]+=dp[j-coins[i]];
            }
            /* 上面的代码其实是这个的简化版本
            for (int j = 1; j <=amount; j++) {
            	if(j<coins[i])
            		continue;
                dp[j]+=dp[j-coins[i]];
            }
            */
        }
        return dp[amount];
    }
}

主要注意的是, 本题必须要先遍历物品, 在遍历容量, 如果先遍历容量的话dp[i] 表示的就是 凑成 i 金额 的方法的方法数 (组合数)

组合不强调元素之间的顺序，排列强调元素之间的顺序。

可以看下面的代码

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
@Test
public  void printTest(){
    changeTest(5,new int[]{1,2,5});
}
public int changeTest(int amount, int[] coins) {
    int[]dp=new int[amount+1];// dp[i] 表示可以凑成 i 金额 的方法的种数
    dp[0]=1;
    for (int i = 1; i <= amount; i++) {
        for (int j = 0; j < coins.length; j++) {// 1 2 5
            if(i>=coins[j]){
                dp[i]+=dp[i-coins[j]];
            }
        }
    }
    print(dp);
    Arrays.fill(dp,0);
    dp[0]=1;
    for (int i = 0; i < coins.length; i++) {
        for (int j = coins[i]; j <=amount; j++) {
            dp[j]+=dp[j-coins[i]];
        }
    }
    print(dp);
    return dp[amount];
}
public void print(int[]dp){
    for (int i : dp) {
        System.out.print(i+" ");
    }
    System.out.println();
}

代码打印的结果是:

1 1 2 3 5 9
1 1 2 2 3 4

🗝️279. 完全平方数

难度中等1496

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

数学解法

首先要知道一个数学定理

  • 四平方定理

任何一个正整数都可以表示成不超过四个整数的平方之和。 推论：满足四数平方和定理的数n（四个整数的情况），必定满足 n=4^a(8b+7)

那么我们同个这个定理来实现代码即可

推论: 满足四数平方和定理的数n（四个整数的情况），必定满足 n=4^a(8b+7)

  • 利用这个推论来讨论4个平方数的情况

代码如下

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
class Solution {
    public int numSquares(int n) {
        /**那么我们来讨论四种情况即可*/
         // 四个平方数的情况  推论：满足四数平方和定理的数n（四个整数的情况），必定满足 n=4^a(8b+7)
        while(n % 4 == 0) n /= 4;  //判4
        if(n % 8 == 7) return 4;
        for (int i = 0; i*i <= n; i++) {//1个平方数的情况
            if(i*i==n){
                return 1;
            }
        }
        
        for (int i = 0; i*i <= n; i++) {//两个平方数的情况
            for (int j = i; j*j <= n; j++) {
                if(j*j+i*i==n){
                    return 2;
                }
            }
        }
//        三个平方数的情况, 不要做三层循环, 直接在前面排除 2 1 4 的情况, 那么最后只能是3
//        for (int i = 0; i < n; i++) {
//            for (int j = i+1; j < n; j++) {
//                for (int k = j+1; k < n; k++) {
//                    if(j*j+i*i+k*k==n){
//                        return 2;
//                    }
//                }
//            }
//        }
        return 3;
    }
}

377. 组合总和 Ⅳ

难度中等693

给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

  • 看到组合就想到回溯, 但是本题元素不可重复, 如果nums[i] , 较小,target较大,就会导致回溯的次数极多,

举个例子, num[0]=1, target=1000 , 仅仅是第一个元素我们就需要回溯1000次

回溯代码

使用函数传递参数比直接使用全局变量速度要快, 但是算法时间优化的问题不足以被弥补

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    LinkedList<Integer> track=new LinkedList<>();
    int res=0;
    int[]nums;
    public int combinationSum4(int[] nums, int target) {
        this.nums=nums;
        backTrack(0,target);
        return  res;
    }
    void backTrack(int start,int target){
        if(target==0){
            res++;
            return ;
        }
        for (int i = start; i <nums.length ; i++) {
            // 相同的元素可以重复利用
            if(target<nums[i]) continue;
            track.add(nums[i]);
            backTrack(start,target-nums[i]);
            track.removeLast();
        }
    }
}

动态规划

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
class Solution {

    // 本题问的是组合数, 112 与211 是两种, 因此需要吧背包放在外面, 
        // 这个题目跟昨天的零钱兑换I 一样, 完全背包问题
        public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];// dp[i]表示 0~i 可以构成 target的元素组合的个数
        dp[0] = 1;
        for (int i = 1; i <= target; i++) {
            for (int num : nums) {
                if (num <= i) {
                    dp[i] += dp[i - num];
                }
            }
        }
        return dp[target];
    }
    /*
        public int combinationSum4I(int[] nums, int target) {
        int[]dp=new int[nums.length+1];// dp[i]表示 0~i 可以构成 target的元素组合的个数
        dp[0]=1;
        // or dp[i] 为 构成 target=i 的组合的种数  错误
        // 这个题目跟昨天的零钱兑换I 一样, 完全背包问题
        // for (int i = 0; i < nums.length; i++) {
        //     for (int j = nums[i]; j <=target ; j++) {
        //         dp[j]+=dp[j-nums[i]];
        //     }
        // }
        
        return dp[nums.length];
    }
    */
}

15. 三数之和

难度中等5244

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

**注意：**答案中不可以包含重复的三元组。

双指针

思路:

  1. 对数组进行排序

  2. 先设定一个前置的值

    • 然后定义两个指针, 指向当前的值得后面的元素 l=i+1 , r=len-1 , 这里类似于二分的思想
      • 随后遍历数组 , 移动指针, 根据情况来调整 l r 的位置,

  3. 注意对结果的去重

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
37
38
39
40
41
42
43
/*
思路:
1, 对数组进行排序
2, 先设定一个前置的值
   - 然后定义两个指针, 指向当前的值得后面的元素  l=i+1 , r=len-1   , 这里类似于二分的思想
   - 随后遍历数组 , 移动指针, 根据情况来调整 l r 的位置, 
3, 注意对结果的去重 
*/
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        if(nums==null||nums.length<3) return null;
        List<List<Integer>> res=new ArrayList<>();
        Arrays.sort(nums); // 排序, 避免出现重复的 元素
        for (int i = 0; i < nums.length; i++) {
            if(nums[i]>0){// 如果当前的元素 >0, 那么 nums[l] nums[r] 都大于0 
                return res;
            }
            if(i>0&&nums[i]==nums[i-1]) continue;
            int left=i+1, right=nums.length-1; // 注意不可以有重复的元素
            // 我们定义两个指针, 分别从当前元素的右边 以及数组的最后一个元素进行 遍历, 如果相加等于0 那么就添加
            while(left<right){ // 这里类似于二分的思想
                int sum=nums[i]+nums[left]+nums[right];
                if(sum==0){
                    List<Integer> tmp=new ArrayList<>();
                    tmp.add(nums[i]);
                    tmp.add(nums[left]);
                    tmp.add(nums[right]);
                    res.add(tmp);
                    // 需要对结果去重, 做法是跳过相同的元素
                    while(left<right&&nums[left]==nums[left+1]) left++;
                    while(right>left&&nums[right]==nums[right-1]) right--;
                    left++;
                    right--;
                }else if(sum<0){
                    left++;
                }else if(sum>0){
                    right--;
                }
            }
        }
        return res;
    }
}

56. 合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

**思路 **

一个区间可以表示为 [start, end]，先按区间的 start 排序：

  1. 我们首先按照左临界点, 对区间进行排序 ,

  2. 对于每一个临界点, 我们遍历他之后的区间, 并且在这个过程中不断地扩充右临界点 r=Math.max(intervals[j][1],r);

    • 当我们找到了一个区间 : 该区间满足其左临界点 ==等于== 我们保存的右临界点, 这个时候我们需要合并区间, 并且 直接跳到下一个需要计算的区间

      不需要再次计算当前的区间, 因为他的右临界点已经被包含了]\

    • 如果我们找到区间 : 该区间满足其**左临界点 **==大于== 我们保存的右临界点, 此时我们直接直接添加保存的左临界点以及右临界点, 并且以这个区间为基础再次开始计算即可

    上述两种情况的区别体现在 前者为 i=j , 后者为i=j-1 , 因为对于后者, 其左临界点不属于之前的区间, 因此需要再次对其计算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int[][] merge(int[][] intervals) {
        LinkedList<int[]> res=new LinkedList<>();
        Arrays.sort(intervals,(a,b)->{// 将数组按照 starti 排序
            return  a[0]-b[0];
        });
        res.add(intervals[0]);
        for (int i = 1; i < intervals.length; i++) {
            int[]cur=intervals[i];
            int[]last=res.getLast();
            if(cur[0]>last[1]){ // 当前区间的范围大于之前区间的右临界点
             	res.add(cur);   
            }else{
                last[1]=Math.max(cur[1],last[1]);  // 链接
            }
        }
        return  res.toArray(new int[0][0]);
    }
}

169. 多数元素

难度简单1571

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

摩尔投票法

首先定义res 作为众数, vote 表示投票数

  • 当遍历到num[i]时
    • 如果vote==0 , 那么我们就直接假设当前的这个num 就是众数 ,并且vote+1
    • 如果vote!=0 , 那么就直接进行运算, 如果num与当前假设的众数相同, 那么就vote+1 ,反之 vote-1

因为题目给的众数的个数超过数组长度的一半, 所以可以假设数组中只有两种数值的数字

  • res :众数
  • 其他的数字

如果前面都是其他的数字, 那么 就相当于这些数字在内耗, 3,2,4,6,5,6,2,2,7,8,1,1,1,2,2,2,2,2,2

如果众数的分布比较集中, 那么就是数量碾压 (**数组中有一个数字出现的次数超过数组长度的一半 **)

代码如下

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int majorityElement(int[] nums) {
        int res=nums[0],vote=0;
        for (int i = 1; i < nums.length; i++) {
            res=vote<0?nums[i]:res;
            vote+=nums[i]==res?1:-1;
            
        }
        return res;
    }
}

75. 颜色分类

难度中等1402

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，**原地**对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库的sort函数的情况下解决这个问题。

思路

统计三种颜色的个数, 然后覆盖原有的颜色即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public void sortColors(int[] nums) {
        int a=0,b=0,c=0;// 统计 0, 1 ,2 的数量
        for (int i : nums) {
            if(i==0)a++;
            else if(i==1)b++;
            else if(i==2)c++;
        }
        int idx=0;
        while(a--!=0){
            nums[idx++]=0;
        }
        while(b--!=0){
            nums[idx++]=1;
        }
        while(c--!=0){
            nums[idx++]=2;
        }
    }
}

快排模板

以及测试代码

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
37
38
39
40
41
@Test
public void qsTest(){
    int size=10;// 测试数组的规模
    for (int i = 0; i < 50; i++) {
        int[]arr=generateArray(size);
        int[]nums=Arrays.copyOf(arr,arr.length);
        Arrays.sort(arr);
        quickSort(0,nums.length-1,nums);
        System.out.println(Arrays.equals(arr,nums));
    }
}
public int[] generateArray(int size){
    int[]nums=new int[size];
    for (int i = 0; i < size; i++) {
        nums[i]=(int)(Math.random()*1000);
    }
    return nums;
}

void quickSort(int i,int j,int []nums){//qs i j 表示需要排序的区间
    if(i>j) return ;
    int l=i,r=j;
    int pivot=nums[i];
    while(l<r){ // 哨兵就位
        while(l<r&&nums[r]>=pivot){
            r--;
        }
        while(l<r&&nums[l]<=pivot){
            l++;
        }
        if(l<r){ //当哨兵i和哨兵j没有相遇时
            int tmp=nums[l];
            nums[l]=nums[r];
            nums[r]=tmp;
        }
    }
    nums[i]=nums[l]; // 将left位置的数字变为基准数
    nums[l]=pivot;   //基准数字归位
    quickSort(i,l-1,nums);
    quickSort(l+1,j,nums);
}

遗留问题

快排为啥要从右边开始遍历?

简单的举个例子即可

快排为什么必须先从右往左查找（排升序）_lucy-bit的博客-CSDN博客

1
2
3
4
5
6
while(l<r&&nums[l]<=base){
    l++;
}
while(l<r&&nums[r]>=base){
    r--;
}

​

例如int[] arr = {6,1,2,7,9,8,4,5,10};

先以6 为基准数,

加入我们是 i 先遍历, i => 7
然后从右向左遍历 j=> 5 arr : {6,1,2,5,9,8,4,7,10}

i++ j--

此时i => 9 , j=> 4

那么 此时条件都满足 i<j

再次交换, 得到arr : {6,1,2,5,4,8,9,7,10}

j-- , 此时i, j相遇, 退出循环

交换基准数, 得到 arr : {8 1 2 5 4 6 9 7 10 }

此时我们可以发现, 6 的左边依然存在 大于6 的数字

而正确的结果应该是 4 1 2 5 6 8 9 7 10

图解

48. 旋转图像

难度中等1423

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在** 原地** 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

自外向内, 循环旋转矩阵

自外向内一共有不超过 n/2层（单个中心元素不算一层）矩形框。对于第 times层矩形框，其框边长len=nums−(times∗2)，

将其顺时针分为 4 份 len-1 的边，对四条边进行元素的循环交换即可。

注意循环的边界问题即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public void rotate(int[][] matrix) { // 两层for 循环  ,旋转结束
        for (int i = 0; i < matrix.length/2; i++) {
            for (int j = 0; j < (matrix.length+1)/2; j++) {
                /*
                对于n为奇数, 先加一再除二 与先除二再加一没区别
                读音n为偶数, 必须要先加一 再除二, 向下取整,否则会多除一次
                */
                int temp =matrix[i][j];
                matrix[i][j]=matrix[matrix.length-j-1][i];
                matrix[matrix.length-j-1][i]=matrix[matrix.length-i-1][matrix.length-j-1];
                matrix[matrix.length-i-1][matrix.length-j-1]=matrix[j][matrix.length-i-1];
                matrix[j][matrix.length-i-1]=temp;
            }
        }
    }
}

240. 搜索二维矩阵 II

难度中等1127

编写一个高效的算法来搜索 *m* x *n* 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

  • 每行的元素从左到右升序排列。
  • 每列的元素从上到下升序排列。

倒序遍历矩阵, 利用题目给的矩阵是升序的特性, 免去不必要的计算,

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
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        // if(matrix.length==1){ // 特殊情况判定 实际上不需要
        //     for (int i = 0; i < matrix[0].length; i++) {
        //         if(matrix[0][i]==target)
        //             return true;
        //     }
        //     return false;
        // }
        for (int i = matrix.length - 1; i >= 0; i--) {
            if(matrix[i][0]>target||matrix[i][matrix[0].length-1]<target){
                // 当前行的第一个元素就大于target (或者最后一个元素就小于target) ,只能去上面的行找
                continue;
            }else{ // target可能存在于这一行
                int l=0,r=matrix[0].length;
                while(l<r){ // 二分查找
                    int mid=(l+r)/2;
                    int cur=matrix[i][mid];
                    if(target<cur){
                        r=mid;
                    }else if(target>cur){
                        l=mid+1;
                    }else{
                        return true;
                    }
                }
            }
        }
        return false;
    }
}

74. 搜索二维矩阵

难度中等715

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

  • 每行中的整数从左到右按升序排列。
  • 每行的第一个整数大于前一行的最后一个整数。

思路与上一题相同

代码如下

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
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if(target>matrix[matrix.length-1][matrix[0].length-1]||target<matrix[0][0]) //比最大值还大 , 比最小值还小
            return false;
        int line=-1;
        for (int i = 0; i < matrix.length; i++) {
            if(matrix[i][0]>target){
                line=i;
                break;
            }else if(matrix[i][0]==target)  return true;
        }
        int []nums;
        if(line==-1) nums=matrix[matrix.length-1];
        else nums=line==0?matrix[0]:matrix[line-1];
        return binarySearch(nums,target);
    }
    boolean binarySearch(int[]nums,int target){
        int l=0,r=nums.length;
        while(l<r){
            int mid=l+ (r-l)/2;
            if(target>nums[mid])
                l=mid+1;
            else if(target<nums[mid])
                r=mid;
            else return true;
        }
        return false;
    }
}

54. 螺旋矩阵

难度中等1212

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

本题是顺时针遍历矩阵

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
class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        int l = 0, r = matrix[0].length-1, top = 0, bot = matrix.length-1;
        while (true) {
            // l to r
            for (int i = l; i <= r; i++) {
                res.add(matrix[top][i]);
            } // 遍历完了一行, 那么需要 top++
            if (++top > bot)
                break;
            for (int i = top; i <= bot; i++) {
                res.add(matrix[i][r]);
            }
            if (--r < l)
                break;
            for (int i = r; i >= l; i--) { //右到左
                res.add(matrix[bot][i]);
            }
            if (--bot < top)
                break;
            for (int i = bot; i >= top; i--) {// 下到上
                res.add(matrix[i][l]);
            }
            if (++l > r)
                break;
        }
        return res;
    }
}

59. 螺旋矩阵 II

难度中等822

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

本题是构造矩阵

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
class Solution {
    public int[][] generateMatrix(int n) {
        int[][]matrix=new int[n][n];
        int[]nums=new int[n*n]; // 提前存储元素, 方便后面遍历
        for (int i = 1; i <=n*n; i++) {
            nums[i-1]=i;
        }
        int top=0,bot=n-1,l=0,r=n-1,idx=0;
        while(true){
            for (int i = l; i <= r; i++) {// 行 : top
                matrix[top][i]=nums[idx++];
            }
            if(++top>bot) break;
            for (int i = top; i <= bot; i++) {// 列 : r
                matrix[i][r]=nums[idx++];
            }
            if(--r<l) break;
            for (int i = r; i >=l ; i--) {// 行 : top
                matrix[bot][i]=nums[idx++];
            }
            if(--bot<top) break;
            for (int i = bot; i >= top; i--) {// 列 : r
                matrix[i][l]=nums[idx++];
            }
            if(++l>r) break;
        }
        return matrix;
    }
}

总结

  1. 以上两道题的关键点在与遍历的方式, 定义四个遍历

    分别负责上下左右行列的遍历, 注意好边界问题即可

238. 除自身以外数组的乘积

难度中等1267

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

请**不要使用除法，**且在 O(*n*) 时间复杂度内完成此题。

对于 下标为 i的 数组中的元素numsp[i] ,

我们以i为中心, 分别求出他左右两边的元素的累乘的结果

这种思路如果不使用任何技巧, 实现如下

1
2
3
4
5
6
7
8
9
10
int[]res=new int[nums.length];
for (int i = 0; i < nums.length; i++) {
    res[i]=nums[i];
    for (int j = 0; j < i; j++) {
        res[i]*=nums[j];
    }
    for (int k = i+1; k < nums.length; k++) {
        res[i]*=nums[k];
    }
}

时间复杂度为O(n2) ,

果不其然TLE

可以发现, 在这个过程中, 我们做了许多的重复计算

解决的方法是用数组提前存储前某项累乘的乘积

那么便有了下边的写法,

我们使用res[]' 先遍历 nums, 提前在 nums[i] 对应的i下标, 存储下前i项的乘积(注意这里不能乘以nums[i]),

然后我们倒序遍历, 从后面求右半部分的累乘的乘积

然后左右两边相乘, 即可得到除了当前位置元素的乘积

初始化 res

res[i]=res[i-1]*a[i-1];

后半部分累乘 倒数遍历

tmp*=a[i+1];

随后左右两边相乘, 赋值给res[i] , 最后返回res即可

计算过程

完整代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int[] productExceptSelf(int[]a){
        int n =a.length;
        if(n==0) return new int[0];
        int[]res=new int[n]; // 我们使用 res数组来存储累乘的结果
        res[0]=1; // 注意 最后一个元素我们不需要计算 (也就是 res[n-2]不需要 * a[n-1])
        int tmp=1;
        for (int i = 1; i < res.length; i++) { // 注意res在计算的时候不会乘以本身
            res[i]=res[i-1]*a[i-1];
        }
        for (int i = n - 2; i >= 0; i--) { // 由于 a[n] 不需要乘以他本身, 因此 少循环一次, --> i=len-2;
            tmp*=nums[i+1]; //tmp表示以当前元素为中心, 将数组分成两部分, tmp即为右边的那一部分的累乘结果
            res[i]*=tmp;
        }
        return res;
    }
}

435. 无重叠区间

难度中等804

给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

​

本题与56. 合并区间 类似, 都是区间类问题

1

334. 递增的三元子序列

难度中等612

给你一个整数数组 nums ，判断这个数组中是否存在长度为 3 的递增子序列。

如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ，使得 nums[i] < nums[j] < nums[k] ，返回 true ；否则，返回 false 。

看到本题首先想到了DP做法

做法与300. 最长递增子序列 : DP类似

但是TLE了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public boolean increasingTriplet(int[] nums) {
        // if(nums.length==1) return 1;
        int res=0;
        int[]dp=new int[nums.length]; //dp[i]表示 以nums[i]结尾的最长的递增的子序列的长度
        Arrays.fill(dp,1);
        dp[0]=1;
        /// 对于每个nums[i] 都遍历他之前的元素, (倒序遍历), 如果遍历到的元素比当前的元素小, 那么就dp[i]=Math.max(dp[i].dp[j]+1);
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j <i; j++) {
                if(nums[i]>nums[j]){
                    dp[i]=Math.max(dp[i],dp[j]+1);
                }
                res=Math.max(res,dp[i]);
            }
        }
        return res>=3;
    }
}

LCP 64. 二叉树灯饰

难度中等3

「力扣嘉年华」的中心广场放置了一个巨型的二叉树形状的装饰树。每个节点上均有一盏灯和三个开关。节点值为 0 表示灯处于「关闭」状态，节点值为 1 表示灯处于「开启」状态。每个节点上的三个开关各自功能如下：

  • 开关 1：切换当前节点的灯的状态；
  • 开关 2：切换 以当前节点为根 的子树中，所有节点上的灯的状态，；
  • 开关 3：切换 当前节点及其左右子节点（若存在的话） 上的灯的状态；

给定该装饰的初始状态 root，请返回最少需要操作多少次开关，可以关闭所有节点的灯。

输入：root = [1,1,0,null,null,null,1]

输出：2

解释：以下是最佳的方案之一，如图所示

树形DP

树形DP准确的说是一种DP的思想，将DP建立在树状结构的基础上。整体的思路大致就是用树形的结构存储数据。

方法:
vector dp(TreeNode *root)返回 以root为根的数的对应的四种情况需要的操作数
vec[0] 全关 vec[1]只有根开 vec[2] 除根开 vec[3]全开

方法执行步骤:
首先dp左右孩子, 获取以左右孩子为根节点对应的变为四种情况需要的最小的操作数

然后枚举以子节点为根的子树的状态
a 表示子节点的状态
b 表示除了子节点之外其他节点的状态(这里的其他节点指的是 子节点下面的节点(以子节点为根节点))
每种操作最多做一次，因此用二进制枚举做了哪些操作

x 表示 操作1 (改变当前节点) y表示操作2 (改变所有节点上的灯的状态) z表示操作3 (改变左右子树)
// i 000 001 010 011 100 101 110 111
// x 000 001 000 001 000 001 000 001
// y 000 000 001 001 000 000 001 001
// z 000 000 000 000 100 001 001 001
// 全关 x y x y z x z y z 全开
aa表示子节点
bb表示除了子节点的其他节点
cc 表示当前节点

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Solution
{
    struct TreeNode
    {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };
    const int INF = (int)1e9;

    vector<int> dp(TreeNode *node)
    // 统计每个节点 全关, 只有根开,除根开，全开 分别对应的操作数 , 返账数组
    {
        if (node == nullptr)
            return {0, 0, 0, 0};
        vector<int> L = dp(node->left), R = dp(node->right);// 先dp 获得左右子树四种情况对于的操作次数
        vector<int> vec = {INF, INF, INF, INF}; // 当前节点每种操作对应的操作数
        // 0 1 2 3
        //  [全关，只有根开，除根开，全开]
        // 枚举以子节点为根的子树的状态，a 表示子节点的状态，b 表示除子节点外的其它节点的状态
        for (int a = 0; a < 2; a++) // 当前节点的状态: 亮or灭
            for (int b = 0; b < 2; b++)
            {
                int from = b * 2 + a;
                int c = node->val;
                // 每种操作最多做一次，因此用二进制枚举做了哪些操作
                for (int i = 0; i < 8; i++)
                // i  000  001  010  011  100 101  110  111
                // x  000  001  000  001  000 001  000  001
                // y  000  000  001  001  000 000  001  001
                // z  000  000  000  000  100 001  001  001
                //    全关  x    y   x y   z  x z   y z 全开
                {
                    int x = i & 1, y = i >> 1 & 1, z = i >> 2 & 1; // 分别对应三种操作数的次数
                    // 子节点只受操作 2 和 3 的影响
                    int aa = (y ^ z ? 1 - a : a);// 如果2, 3 操作的次数总和是偶数次, 那么子节点的亮灭不变
                    // 除子节点外的其它节点只受操作 2 的影响
                    int bb = (y ? 1 - b : b);
                    // 当前节点受所有操作影响
                    int cc = (x ^ y ^ z ? 1 - c : c);
                    
                    // 除根外的节点要保持一致，否则后续没有操作能让它们一致
                    if (aa != bb)
                        continue;
                    vec[aa * 2 + cc] = min(vec[aa * 2 + cc], L[from] + R[from] + x + y + z);
                }
            }
        return vec;
    }

public:
    int closeLampInTree(TreeNode *root)
    {
        return dp(root)[0]; // 返回根节点全关的次数
    }
};

  1. 如果当前节点的灯是开的，我们可以：(1) 操作一次开关1；(2) 操作一次开关2；(3) 操作一次开关3；(4) 操作开关123。

    即操作最小奇数次开关让当前节点的灯关掉。

  2. 如果当前节点的灯是关的，我们需要保持当前的状态，我们可以：(1) 不动开关；(2) 操作一次开关1+操作一次开关2；(3) 操作一次开关1+操作一次开关3；(4) 操作一次开关2+操作一次开关3。

    即操作最小偶数次开关，使得对于当前节点而言，你操作了等于没操作，当前节点的灯还是关的。

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Solution {
    /**
1.根结点+子树全部亮

2.根不亮+子树全部亮

3.根亮+子树全部不亮

4.根结点+子树全部不亮 
*/
    int[][] sz = new int[100010][2];
    int[][] dp = new int[100010][4];
    int idx = 0;
    int dfs1(TreeNode p){
        if(p == null) return 0;
        int rt = ++idx;
        sz[rt][p.val] = 1;
        int l = dfs1(p.left),r = dfs1(p.right);
        sz[rt][0] += sz[l][0] + sz[r][0];
        sz[rt][1] += sz[l][1] + sz[r][1];
        dp[rt][0] = sz[rt][0];//全部亮
        dp[rt][3] = sz[rt][1];//全部不亮
        dp[rt][1] = sz[l][0] + sz[r][0] + p.val;//根不亮，子树全部亮
        dp[rt][2] = sz[l][1] + sz[r][1] + 1 - p.val;//根亮，子树不亮
        if(l == 0&&r == 0) return rt;//叶结点
        int x = p.val;//期望rt不亮 
        int y = 1 - p.val;//期望rt亮
        dp[rt][1] = Math.min(dp[rt][1],dp[l][0] + dp[r][0] + x);//op1
        dp[rt][1] = Math.min(dp[rt][1],dp[l][3] + dp[r][3] + 1 + y);//op2
        dp[rt][1] = Math.min(dp[rt][1],dp[l][1] + dp[r][1] + 1 + y);//op3

        dp[rt][2] = Math.min(dp[rt][2],dp[rt][1] + 1);
        dp[rt][2] = Math.min(dp[rt][2],dp[l][3] + dp[r][3] + y);//op1
        dp[rt][2] = Math.min(dp[rt][2],dp[l][0] + dp[r][0] + 1 + x);//op2
        dp[rt][2] = Math.min(dp[rt][2],dp[l][2] + dp[r][2] + 1 + x);//op3

        dp[rt][0] = Math.min(dp[rt][0],dp[rt][1] + 1);
        dp[rt][0] = Math.min(dp[rt][0],dp[l][0] + dp[r][0] + y);//op1
        dp[rt][0] = Math.min(dp[rt][0],dp[l][3] + dp[r][3] + 1 + x);//op2
        dp[rt][0] = Math.min(dp[rt][0],dp[l][1] + dp[r][1] + 1 + x);//op3

        dp[rt][3] = Math.min(dp[rt][3],dp[rt][0] + 1);
        dp[rt][3] = Math.min(dp[rt][3],dp[l][3] + dp[r][3] + x);//op1
        dp[rt][3] = Math.min(dp[rt][3],dp[l][0] + dp[r][0] + 1 + y);//op2
        dp[rt][3] = Math.min(dp[rt][3],dp[l][2] + dp[r][2] + 1 + y);//op3
        
        dp[rt][0] = Math.min(dp[rt][0],dp[rt][3] + 1);
        dp[rt][1] = Math.min(dp[rt][1],dp[rt][2] + 1);
    
        return rt;
    }
    public int closeLampInTree(TreeNode root) {
        dfs1(root);
        return dp[1][3];
    }
}