因为各种各样的原因，我需要开始进行一定的算法训练，在此记下过程中的一些心得体会和文章摘抄。刷的题目集是代码随想录。

置顶

202. 快乐数

很难崩

TODO用DP做一下

TODO

TODO

TODO，区间思想做一下

每日一题

2024.5.1 Medium 2462. 雇佣 K 位工人的总代价

这个比较有意思。其中一个c++写法需要注意：

struct element {
    int index;
    int val;
};

struct Compare {
    bool operator()(const element &a, const element &b) const {
        // 首先比较 val 值
        if (a.val != b.val) {
            return a.val > b.val; // 小顶堆：较小的 val 在堆顶
        }
        // 如果 val 值相同，则比较 index 值
        return a.index > b.index; // 小顶堆：较小的 index 在堆顶
    }
};
std::priority_queue<element, std::vector<element>, Compare> heap;

可以直接写成：

1 2	// pair第一位对应val，第二位对应index priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;

很直观，pair的greater逻辑应该就是先比第一个再比第二个，学到了。

24.5.10 2960. 统计已测试设备

居然无师自通了差分，不过差分居然可以视为前缀和，对这个思想感到非常巧妙。当然更复杂的树差分这里暂且只先了解一下概念了。。。

https://leetcode.cn/problems/find-the-longest-equal-subarray/description/?envType=daily-question&envId=2024-05-23

这题有时间仔细想想。。其实我已经有一个近似解了，只不过问题出在需要枚举左区间，这种情况下理应想到滑动窗口的

基础

数学

69. x 的平方根牛顿迭代

1017. 负二进制转换是我最讨厌的数学种类之一……

数组

209. 长度最小的子数组 TODO

59. 螺旋矩阵 II

二分查找

二分查找涉及的很多的边界条件，逻辑比较简单，但就是写不好。例如到底是 while(left < right) 还是 while(left <= right)，到底是right = middle呢，还是要right = middle - 1呢？

大家写二分法经常写乱，主要是因为对区间的定义没有想清楚，区间的定义就是不变量。要在二分查找的过程中，保持不变量，就是在while寻找中每一次边界的处理都要坚持根据区间的定义来操作，这就是循环不变量规则。

写二分法，区间的定义一般为两种，**左闭右闭即[left, right]，或者左闭右开即[left, right)**。

第一种写法，我们定义 target 是在一个在左闭右闭的区间里，也就是[left, right] （这个很重要非常重要）。

区间的定义这就决定了二分法的代码应该如何写，因为定义target在[left, right]区间，所以有如下两点：

while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=

if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle - 1

第二种写法，如果说定义 target 是在一个在左闭右开的区间里，也就是[left, right) ，那么二分法的边界处理方式则截然不同。

有如下两点：

while (left < right)，这里使用 < ,因为left == right在区间[left, right)是没有意义的

if (nums[middle] > target) right 更新为 middle，因为当前nums[middle]不等于target，去左区间继续寻找，而寻找区间是左闭右开区间，所以right更新为middle，即：下一个查询区间不会去比较nums[middle]

35.搜索插入位置

34. 在排序数组中查找元素的第一个和最后一个位置

做了这么多二分下来，感觉二分最核心的还是脑补出这样一个结构：left和right一左一右紧挨着，此时，

left指向target
1. middle=left
  
  直接return，此时target = left = right - 1 = middle
2. middle=right
  1. 开区间：不可能出现该情况。
  2. 闭区间：right紧缩。下一轮return，target = left = right = middle
right指向target
1. middle=left
  
  left紧缩。
  1. 开区间：下一轮left = right退出循环，target = left = right = middle + 1
  2. 闭区间：下一轮return，target = left = right = middle
2. middle=right
  1. 开区间：不可能出现该情况。
  2. 闭区间：直接，此时target = right = left + 1 = middle

所以总结：

对于开区间来说，middle != right恒成立，这点也很直观。
传统的二分查找开闭区间都是在内层return middle，外层return -1。

想要解决区间问题，最重要的就是想清楚这四点……

还有二分枚举：

69. x 的平方根

双指针

977. 有序数组的平方

6666，我用的是方法二，也即找到零点分界线再左右遍历，它这个思路三比我高超

15. 三数之和见哈希表一节

滑动窗口

209. 长度最小的子数组

算是简单的滑动窗口了。right bound负责遍历拓展视野，left bound负责在区间的底线反复横跳。

各种遍历顺序

1329. 将矩阵按对角线排序

因为矩阵的下标不能为负数。同一“对角线”上的点，i-j的值相等，但是，可能是负数，所以我们，把那部分负数的值，变换到都大于等于0。考虑到，i最小为0，j最大为m-1 时，（i-j）最小为：0-(m-1) = 1-m，故i-j+m，就把原来可能为负的区间，向右平移，变成最小值为1的区间。

因此，我们就可以将每条对角线映射到<i-j+m, array>这样的映射中了。

TopK

347. 前 K 个高频元素

这个On做法亮瞎我了。。。

链表

203. 移除链表元素

学到了一个很有意思的写法：dummyHead

ListNode* removeElements(ListNode* head, int val) {
    auto dummyHead = std::make_shared<ListNode>(0, head);
    auto tmp = dummyHead.get();
    while (tmp->next) {
        if (tmp->next->val == val) {
            tmp->next = tmp->next->next;
        } else {
            tmp = tmp->next;
        }
    }
    return dummyHead->next;
}

还有递归写法也值得一看：

ListNode* removeElements(ListNode* head, int val) {
    if (!head)  return head;
    head->next = removeElements(head->next, val);
    return head->val == val ? head->next : head;
}

206. 反转链表

可以很好地练一下递归写法

24. 两两交换链表中的节点

还有这题递归写法也很经典

面试题 02.07. 链表相交 142. 环形链表 II

经典指针

LCR 027. 回文链表

这题的递归写法思路很有意思

哈希表

1. 两数之和

一次遍历的做法值得注意

454. 四数相加 II 经典老题，不过这次真是水平提升了居然很快想出一两年前觉得很难的正解hhh

15. 三数之和这题其实最难的是去重。

我的思路是两重循环建立哈希表，然后一重循环找元组。

对于去重，需要做以下几件事：

保证i<j<k
排序

这个很重要。。。。也是我绞尽脑汁好久没想出来的。有了这个，才能让重复元素连续出现，确保i<j<k的情况不会重复
两重循环建立哈希表的时候，保证i和j不重复

具体来说，对于连续的重复元素，都只取第一个作为i、j，后面的都跳过。
一重循环找元组的时候，保证k不重复

k就不能像3一样简单粗暴地取第一个然后跳过了，因为有可能第一个不满足i<j<k但是第二个满足。

所以我们要做的，就是把那些满足的加入res之后，赶紧把它给erase了，这样一来就能防止重复了。

还有这题的双指针解法也很需要注意。

我一直没怎么考虑到数组已排序的条件，所以在想怎么用双指针做时一直没想到这点。。。实在是很巧妙。再加上理解为太大了小一点（紧缩有边界），太小了大一点（紧缩左边界），也是挺有意思。

18. 四数之和

跟三数之和解法一模一样。值得注意的是，需要注意这里的隐式类型转换坑。

1	for (int m = 0; m < nums.size() - 3; m ++)

当m=0，num.size() = 2,此时居然会得到m < nums.size() - 3为true，解释一下这个现象

在表达式 m < nums.size() - 3 中，如果 nums.size() = 2，那么 nums.size() - 3 的计算结果为 2 - 3 = -1。这个结果是一个 int 类型的常量 -1，但由于 nums.size() 的返回类型是 size_t，它是一个无符号整数类型。

在 C++ 中，当无符号整数和有符号整数进行运算时，有符号整数会转换为无符号整数类型。这意味着在计算 nums.size() - 3 时，-1 会被转换为无符号整数。

具体来说，-1 在无符号整数 size_t 中表示为一个非常大的数，因为在无符号整数中，负数表示为最大的正数减去对应的绝对值。例如，在一个 32 位无符号整数中，-1 会被解释为 4294967295。

因此，当 m 为 0 时，表达式 m < nums.size() - 3 变成了 0 < -1（解释为一个非常大的正数），结果是 true。这是因为 0 小于非常大的正数，因此得到 true 结果。

这说明在 C++ 中的类型转换时，要特别注意有符号整数和无符号整数之间的转换，因为它们可能导致意外的结果。在这种情况下，您可能需要确保变量和表达式类型匹配，以避免未预期的行为。