贪心算法理论基础

发表于2024-05-12更新于2024-05-15

贪心算法

什么是贪心

贪心的本质是选择每一阶段的局部最优，从而达到全局最优。

这么说有点抽象，来举一个例子：

例如，有一堆钞票，你可以拿走十张，如果想达到最大的金额，你要怎么拿？

指定每次拿最大的，最终结果就是拿走最大数额的钱。

每次拿最大的就是局部最优，最后拿走最大数额的钱就是推出全局最优。

再举一个例子如果是 有一堆盒子，你有一个背包体积为n，如何把背包尽可能装满，如果还每次选最大的盒子，就不行了。这时候就需要动态规划。动态规划的问题在下一个系列会详细讲解。

贪心的两个极端

很多同学做贪心的题目的时候，想不出来是贪心，想知道有没有什么套路可以一看就看出来是贪心。

说实话贪心算法并没有固定的套路。

所以唯一的难点就是如何通过局部最优，推出整体最优。

那么如何能看出局部最优是否能推出整体最优呢？有没有什么固定策略或者套路呢？

不好意思，也没有！ 靠自己手动模拟，如果模拟可行，就可以试一试贪心策略，如果不可行，可能需要动态规划。

有同学问了如何验证可不可以用贪心算法呢？

最好用的策略就是举反例，如果想不到反例，那么就试一试贪心吧。

可有有同学认为手动模拟，举例子得出的结论不靠谱，想要严格的数学证明。

一般数学证明有如下两种方法：

数学归纳法
反证法
看教课书上讲解贪心可以是一堆公式，估计大家连看都不想看，所以数学证明就不在我要讲解的范围内了，大家感兴趣可以自行查找资料。

面试中基本不会让面试者现场证明贪心的合理性，代码写出来跑过测试用例即可，或者自己能自圆其说理由就行了。

举一个不太恰当的例子：我要用一下1+1 = 2，但我要先证明1+1 为什么等于2。严谨是严谨了，但没必要。

虽然这个例子很极端，但可以表达这么个意思：刷题或者面试的时候，手动模拟一下感觉可以局部最优推出整体最优，而且想不到反例，那么就试一试贪心。

例如刚刚举的拿钞票的例子，就是模拟一下每次拿做大的，最后就能拿到最多的钱，这还要数学证明的话，其实就不在算法面试的范围内了，可以看看专业的数学书籍！

所以这也是为什么很多同学通过（accept）了贪心的题目，但都不知道自己用了贪心算法，因为贪心有时候就是常识性的推导，所以会认为本应该就这么做！

那么刷题的时候什么时候真的需要数学推导呢？

例如这道题目：链表：环找到了，那入口呢？ (opens new window)，这道题不用数学推导一下，就找不出环的起始位置，想试一下就不知道怎么试，这种题目确实需要数学简单推导一下。

贪心的套路

想到局部最优是什么，然后想不出来反例，就可以用贪心算法了。
看了卡哥视频，就是要多刷题，见过套路才会写，没见过套路的一些比较难的题目很难通过总结规律做出来，因为每道题的规律都不同。

题目：k次取反后最大化的数组和

https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/description/

图 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var largestSumAfterKNegations = function(nums, k) {
  // 这里必须是降序，因为前面的负数越大，越能减小和
  nums.sort((a,b)=>Math.abs(b)-Math.abs(a));
  let sum = 0
  for(let i=0;i<nums.length;i++){
    if (nums[i]<0 && k>0){
      nums[i] = -nums[i];
      k--
    }
    sum += nums[i];
  }
  if (k%2 === 1){
    sum -= 2*nums[nums.length - 1];   // 2到-2差是4，所以减去2倍最小值
  }
  return sum;
};
我整错了，我刚开始竟然升序对绝对值进行了排序，可恶了。

四数之和

发表于2024-05-10更新于2024-05-14

四数之和

https://leetcode.cn/problems/4sum/

思路

四数之和和三数之和的思路是一脉相承的，只不过三数之和是一层for循环，每次遍历一个数。四数之和可以用双层for循环。

剪枝的思路与三数之和有些不同呢，三数之和的目标值是0，而四数之和的目标值是不固定的，如果遇到负数情况会有所不同。num>target不能直接退出，如果后面加负数的话，target会变小。

  • （看整体动态的过程）这个逻辑不影响right和left的变化，因为right–，sum会减小是必然，left++sum会增大也是必然。
  • （看静态的遍历到num[i]的时候，左右指针还没动的时候）变化的点在于，num[i] > target,如果target是0，那么num[i]之后的数都必然大于0。 而当target<0时情况便有所不同了，num[i]>target,如果num[i+1]<0,num[i]+num[i+1]一定小于num[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
var fourSum = function(nums, target) {
  let res = [];
  nums.sort((a,b)=>a-b);
  for(let i=0;i<nums.length-3;i++){
    //去重
    if(i>0 && nums[i]===nums[i-1]) continue;
    //剪枝
    if(num[i]>0 && num[i] > target) continue;
    for(let j=i+1;j<nums.length-2;j++){
      //去重
      if(j>i+1 && nums[j]===nums[j-1]) continue;
      //剪枝
      if(nums[i]+nums[j]>0 && nums[i]+nums[j] > target) continue;
      let left = j+1;
      let right = nums.length-1;
      while(left<right){
        let sum = nums[i] + nums[j] + nums[left] + nums[right];
        if (sum > target) right--;
        if (sum < target) left++;
        if(sum === target){
          res.push([nums[i],nums[j],nums[left],nums[right]]);
          while(left<right && nums[left] === nums[left+1]) left++;
          while(left<right && nums[right] === nums[right-1]) right--;
          left++;
          right--;
        }
      }
    }
  }
  return res;
};

三数之和

发表于2024-05-09更新于2024-05-14

三数之和

https://leetcode.cn/problems/3sum/description/

双指针法

思路

图 0

1、拿这个nums数组来举例，首先将数组排序，然后有一层for循环，i从下标0的地方开始，同时定一个下标left 定义在i+1的位置上，定义下标right 在数组结尾的位置上。

2、依然还是在数组中找到 abc 使得a + b +c =0，我们这里相当于 a = nums[i]，b = nums[left]，c = nums[right]。

3、接下来如何移动left 和right呢， 如果nums[i] + nums[left] + nums[right] > 0 就说明 此时三数之和大了，因为数组是排序后了，所以right下标就应该向左移动，这样才能让三数之和小一些。

4、如果 nums[i] + nums[left] + nums[right] < 0 说明 此时 三数之和小了，left 就向右移动，才能让三数之和大一些，直到left与right相遇为止。

去重

  • a去重逻辑
    当前遍历元素和前一个元素重复是，跳过

  • b和c去重逻辑

    • 如果当前left元素和left++对一个的元素相同，left++跳过。同理right和right–元素对比。
    • 当然如果不相同，left++的同时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
var threeSum = function(nums) {
  let res = [];
  nums.sort((a,b)=>a-b);
  for(let i=0;i<nums.length-2;i++){
    //剪枝
    if (nums[i] > 0) return
    //a去重逻辑，如果当前元素和前一个元素相同，跳过
    if(i>0 && nums[i]===nums[i-1]) continue;
    let left = i+1;
    let right = nums.length-1;
    while(left<right){
      let sum = nums[i] + nums[left] + nums[right];
      if (sum > 0) right--;
      if (sum < 0) left++;
      if(sum === 0){
        res.push([nums[i],nums[left],nums[right]]);
        //bc去重逻辑,如果left和right的元素和前一个元素相同，跳过
        while(left<right && nums[left] === nums[left+1]) left++;
        while(left<right && nums[right] === nums[right-1]) right--;
        left++;
        right--;
      }
    }
  }
  return res;
};

回溯算法

我的初始想法是用回溯算法，但是这个方法在处理较长的数组时会超时。

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
// 回溯算法
var threeSum = function(nums) {
  let res = [];
  let path =[];
  nums = nums.sort((a,b)=>a-b);
  const  backTraking = (nums,startIndex)=>{
    if(path.length === 3){
      if(path[0]+path[1]+path[2] === 0){
        res.push([...path])
      }
      return;
    }
    // 剪枝
    if (path.length === 0 && nums[startIndex] > 0) return;
    if (path.length === 1 && nums[startIndex]+path[0] > 0) return;
    if (path.length === 2 && nums[startIndex]+path[0]+path[1]>0) return;
    for(let i=startIndex;i<nums.length;i++){
      if(i>startIndex && nums[i] === nums[i-1]){
        continue;
      }
      path.push(nums[i]);
      backTraking(nums,i+1);
      path.pop();
    }
  }
  backTraking(nums,0);
  return res
};

四数相加II

发表于2024-05-09更新于2024-05-14

四数相加II

https://leetcode.cn/problems/4sum-ii/description/

有四个数组，将前两个数组中的值相加a+b。将值存放在map中的key，出现次数为相应key的value，然后遍历后两个数组两两相加的值，如果0-nums3[i]-nums4[j]在map中，则count+= 出现次数

本题解题步骤：

  • 首先定义 一个unordered_map，key放a和b两数之和，value 放a和b两数之和出现的次数。
  • 遍历大A和大B数组，统计两个数组元素之和，和出现的次数，放到map中。
  • 定义int变量count，用来统计 a+b+c+d = 0 出现的次数。
  • 在遍历大C和大D数组，找到如果 0-(c+d) 在map中出现过的话，就用count把map中key对应的value也就是出现次数统计出来。
  • 最后返回统计值 count 就可以了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
var fourSumCount = function(nums1, nums2, nums3, nums4) {
  let map = new Map()
  //前两个数组中的数两两相加，所以是双层for循环。
  for(let i=0;i<nums1.length;i++){
    for(let j=0;j<nums2.length;j++){
      if (map.has(nums1[i]+nums2[j])){
        map.set(nums1[i]+nums2[j], map.get(nums1[i]+nums2[j])+1)
      }
      else{
        map.set(nums1[i]+nums2[j],1)   //注意这里是1
      }
    }
  }
  let count = 0
  for(let i=0 ;i<nums3.length;i++){
    for(let j=0;j<nums4.length;j++){
      if (map.has(-nums3[i]-nums4[j])){
        // 这里不是+1，而是要加这个数出现的次数。
        count += map.get(-nums3[i]-nums4[j])
      }
    }
  }
  return count
};

反转链表

发表于2024-05-02更新于2024-05-02

删除链表的倒数第N个结点

https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/

两次遍历(我的解决方案)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var removeNthFromEnd = function(head, n) {
  // 使用两次遍历，确定链表长度,然后找到被删除的位置
  let dummy = new ListNode(0, head);
  cur = dummy
  let len = 0;
  while(cur.next){
    len++;
    cur = cur.next;
  }
  cur = dummy;
  for(let i=0;i<len-n;i++){
    cur = cur.next;
  }
  cur.next = cur.next.next;
  return dummy.next;
};

只使用一次遍历

  • 首先使用虚拟结点，方便处理实际的头结点逻辑，也就是说包括头结点在内的所有结点，处理逻辑是一致的。

  • 定义快慢指针，fast和slow
    图 0

  • fast比slow先走n+1步，这样当fast走到最后节点的下一个结点null的时候，slow正好指向将被删除结点的上一个结点。
    图 1

  • fast和slow同时移动指向末尾
    图 2

  • 删除slow指向的下一个结点
    图 3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var removeNthFromEnd = function(head, n) {
  // 一次遍历
  let dummy = new ListNode(0, head);
  let slow = dummy;
  let fast = dummy;
  while(fast){
    if(n+1>0){
      fast = fast.next
      n--
    }
    else{
      fast = fast.next
      slow = slow.next
    }
  }
  slow.next = slow.next.next
  return dummy.next
};

环形链表II

发表于2024-05-02更新于2024-05-02

环形链表II

逻辑

快慢指针可以找到环形链表的原因

快慢指针是一种常用的解决链表问题的方法，特别是对于环形链表的问题。这种方法的基本思想是使用两个指针，一个快指针和一个慢指针，同时从链表的头部开始遍历。快指针每次移动两个节点，而慢指针每次移动一个节点。

如果链表中存在环，那么快指针和慢指针最终会在环中的某个位置相遇。这是因为快指针移动的速度是慢指针的两倍，所以即使快指针进入环后，慢指针还没有进入环，快指针也会在环中继续移动，最终追上慢指针。

图 0

假设链表的头部到环的入口的距离为x，环的入口到快慢指针相遇点的距离为y，相遇点到环的入口的距离为z。

当快慢指针相遇时，慢指针走过的距离是x+y，快指针走过的距离是x+y+n(z+y)。因为快指针的速度是慢指针的两倍，所以2*(x+y) = x+y+n(z+y)，先拿n为1的情况来举例，意味着fast指针在环形里转了一圈之后，就遇到了 slow指针了。当 n为1的时候解这个等式可以得到x=z。

这就意味着，从链表的头部到环的入口的距离等于从快慢指针相遇点到环的入口的距离。所以，当快慢指针相遇后，我们可以将一个指针移动到链表的头部，然后两个指针同时移动，当它们再次相遇时，就是环的入口。

这就是使用快慢指针可以找到环形链表的数学原理。

图 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var detectCycle = function(head) {
    let slow = head, fast = head;
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow === fast) {
            let ptr = head;
            while (ptr !== slow) {
                ptr = ptr.next;
                slow = slow.next;
            }
            return ptr;
        }
    }
    return null;
};

链表相交

发表于2024-05-02更新于2024-05-06

链表相交

好神奇的方法

这段代码是用来找出两个链表的交点的。它使用了两个指针 pA 和 pB，分别从链表 headA 和 headB 的头部开始遍历。

在每一步，pA 和 pB 都会向前移动一步。如果 pA 到达了链表 headA 的末尾，那么将它重置到链表 headB 的头部；同样，如果 pB 到达了链表 headB 的末尾，那么将它重置到链表 headA 的头部。

这样，pA 和 pB 就会同时遍历两个链表。如果两个链表有交点，那么 pA 和 pB 就会在交点处相遇，此时 pA === pB，循环结束，返回 pA（或 pB）即可。如果两个链表没有交点，那么 pA 和 pB 就会同时到达两个链表的末尾，此时 pA === pB === null，循环结束，返回 pA（或 pB，此时为 null）。

这个算法的时间复杂度是 O(N)，空间复杂度是 O(1)，其中 N 是两个链表的总长度。

这个规律的关键在于，当两个链表的长度不同时，通过将指针在到达链表末尾后切换到另一个链表的头部，可以消除长度差异。

假设链表A的长度为a+c，链表B的长度为b+c，其中c是两个链表共享的部分的长度。当我们从链表A的头部和链表B的头部同时开始遍历，到达各自链表末尾时，我们已经遍历了a+c和b+c个节点。此时，如果我们将指针切换到另一个链表的头部继续遍历，那么当两个指针相遇时，它们都已经遍历了a+b+c个节点。

因此，无论两个链表的长度如何，当两个指针相遇时，它们都已经遍历了相同数量的节点。如果两个链表有交点，那么这个交点就是两个指针的相遇点；如果两个链表没有交点，那么两个指针就会在遍历了a+b+c个节点后同时到达链表的末尾，此时pA和pB都为null，循环结束。

这就是为什么这个规律可以找出两个链表的交点，或者确定两个链表没有交点的原因

1
2
3
4
5
6
7
8
var getIntersectionNode = function(headA, headB) {
  let pA = headA, pB = headB;
  while(pA !== pB){
    pA = pA === null ? headB : pA.next;
    pB = pB === null ? headA : pB.next;
  }
  return pA;
};

复杂度更高的方法

  • 首先确定两个链表的长度

  • 对齐：这个过程用图片示意如下；较短的那个位置是关键。
    图 0

  • 找到相同的结点返回即可

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
var getIntersectionNode = function(headA, headB) {
  var getListLen = (head) => {
    let len = 0;
    while (head) {
      head = head.next;
      len++;
  }
  return len;
  }
  let lenA = getListLen(headA);
  let lenB = getListLen(headB);
  if(lenA>lenB){
    for(let i = 0; i < lenA-lenB; i++){
      headA = headA.next;
    }
  }
  else{
    for(let i = 0; i < lenB-lenA; i++){
      headB = headB.next;
    }
  }
  while(headA){
    if(headA === headB){
      return headA;
    }
    headA = headA.next;
    headB = headB.next;
};
  return null;
}

两两交换链表中的结点

发表于2024-04-29更新于2024-05-02

两两交换链表的结点

https://leetcode.cn/problems/swap-nodes-in-pairs/description/

图 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var swapPairs = function(head) {
  // 创建虚拟结点，从虚拟结点开始，每次处理下面的两个结点。然后向后跳转两个结点。
  let dummy = new ListNode(0)
  dummy.next = head
  //prev是当前结点
  let prev = dummy
  while(prev.next && prev.next.next){
    let node1 = prev.next
    let node2 = prev.next.next
    //整个交换逻辑在这里
    prev.next = node2
    node1.next = node2.next
    node2.next = node1
    prev = node1
  }
  return dummy.next
};

反转链表

发表于2024-04-29更新于2024-04-28

反转链表

比较验单，理清逻辑注意细节

图 0

1
2
3
4
5
6
7
8
9
10
11
12
var reverseList = function(head) {
  let prev = null
  let cur = head
  while(cur){
    // 这一步我忘记了，没有把next的值保存下来，直接给cur.next赋值了
    const next = cur.next
    cur.next = prev
    prev = cur
    cur = next
  }
  return prev
};

移除链表元素

发表于2024-04-29更新于2024-04-28

移除链表元素

https://leetcode.cn/problems/remove-linked-list-elements/description/

逻辑：分情况讨论
  • 情况1：链表头部元素和val相同
  • 情况2：链表非头部元素和val相同
两种情况统一的方法：在链表头部加一个虚拟节点，从虚拟节点开始，每次对当前节点的 next 元素进行判断。即可统一两种情况

如果cur.next.val == val 让cur的next指向cur.next.next 否则cur = cur.next 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var removeElements = function(head, val) {
  //虚拟节点，虚拟节点的next指向传入链表的头
  const dummy = new ListNode(0);
  dummy.next = head;
  // dummy用于返回最终结果的头部，因此不能改动。只需将其赋值给另一个变量
  let cur = dummy;
  while(cur.next){
    if(cur.next.val == val){
      cur.next =cur.next.next;
    }
    else{
      cur = cur.next;
    }
  }
  return dummy.next;
};

我抽象的将这个过程想象为一个继承的过程，如果cur.next.val == val,那么它没有继承cur的资格，直接找cur.next.next过来进行资格审查。如果通过继承cur。每一代cur都要找继承人，直到最后没人可选。