LeetCode刷题的一些心得

记录一下在刷题的时候的一些小trick以及踩的一些坑。

滑动窗口

滑动窗口就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。它通常用于字符串或者数组特定长度下内容是否相同，也可以查找在内容相同情况下的最短长度(一般来说需要查找的数组或者字符串是连续的)。

next_permutation 全排列

next_permutation是 C++ 标准库中的一个函数， 它用于生成给定范围内的下一个字典序排列。如果可以生成这样的排列，函数返回 true；如果这个排列已经是最大的字典序排列，则函数将范围内的元素重排为最小的字典序排列（通常是升序排列）并返回 false。

这个函数非常适合于生成一个序列的全排列，或者在不需要考虑所有排列的情况下，寻找满足特定条件的下一个排列。

使用 next_permutation 的基本步骤如下：

1. 包含头文件：首先需要包含算法头文件 #include <algorithm>。
2. 初始化序列：你需要有一个序列（如数组或向量）。
3. 调用函数：使用 std::next_permutation 对序列进行操作。通常在一个循环中调用，直到函数返回 false。

#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> vec = {1, 2, 3};

    // 输出初始排列
    do {
        for (int num : vec) {
            std::cout << num << " ";
        }
        std::cout << std::endl;
    } while (std::next_permutation(vec.begin(), vec.end()));

    return 0;
}

这个示例会打印出数组 {1, 2, 3} 的所有排列。

需要注意的是，为了让 next_permutation 正确工作，初始序列应该是按照字典序最小排列的，也就是说，最好是升序排列。如果序列是降序排列，第一次调用 next_permutation 将直接将其重排为最小字典序排列。

时间复杂度（Master公式）

若有\(T(N)=a * T(\frac{N}{b}) +O(N^d)\)，则说明这个算法满足Master公式。也就是说只要是满足子问题等规模的递归都可以用Master公式。a，b，d的值可能会有三种情况。

1. \(\log_b a < d\),则算法时间复杂度为\(O(N^d)\)。
2. \(\log_b a > d\),则算法时间复杂度为\(O(N^{\log_b a})\)。
3. \(\log_b a = d\),则算法时间复杂度为\(O(N^d * \log n)\)。

链表

重要技巧

额外数据结构记录（哈希表等）

此技巧一般只适用于笔试做题，面试一般不适用。

设置额外的数据结构，比如数组、哈希表或者栈等来辅助做题。

快慢指针

有一些问题诸如寻找链表的中点，最简单暴力的方法是遍历一遍链表然后得到链表长度，然后根据长度得到其最中间的节点。这样做有一个问题，就是需要遍历一遍半的链表。而使用快慢指针就可以少遍历一遍链表。

它的思想是设置一个fast节点和一个slow节点，每次fast节点往后走两步，而slow节点往后走一步。这样当fast节点走完整个链表的时候，slow节点就在链表的中间。

代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
 
 // 奇数长度返回中点。偶数长度返回上中点
ListNode *fast = head, slow = head;
while(fast != nullptr)
{
      fast = fast -> next;
      if(fast && fast->next != nullptr)
            fast = fast -> next;
      else
            break;
      slow = slow -> next;   
}

需要特别注意的是，不要死记这代码，实际上在做题或者应用中的不同情况是是有很多细微的差别的，比如若链表长度是偶数，有的时候需要中间靠前的节点，有的时候需要中间靠后的节点，还有的时候需要中间靠前节点的前驱节点，不同情况要做对应的调整，同时还要注意边界条件，比如节点为空或者只有一个节点的情况。

链表长度为偶数情况下，寻找中间靠后的那个节点:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
 
 // 奇数长度返回中点，偶数长度返回下中点
ListNode *fast = head, slow = head;
while(fast != nullptr)
{
      fast = fast -> next;
      if(fast == nullptr)
            break;
      slow = slow -> next;   
      fast = fast -> next;
}

同余

两个数 x 和 y,如果(x - y) mod m = 0,则称x和y模m同余，记作x ≡ y (mod m)。

例如 42 ≡ 12 (mod 10), -17 ≡ 3 (mod 10)。

如果x和y均非负，则x ≡ y (mod m)相当于x mod m = y mod m。

如果x < 0,y > 0，则x ≡ y (mod m)相当于x mod m + m = y mod m。

这样无论 x 是否为负数，运算结果都会落在区间 [0,m) 中。

性质

若x ≡ y (mod m)，则x必然可以通过加/减若干次m得到y。

面试时链表解题方法论

1. 对于笔试，不用太在乎空间复杂度，一切为了时间复杂度。比如可以直接把链表copy到数组。
2. 对于面试，时间复杂度仍然放在第一位，但是要找到空间复杂度最省的方法。

__builtin_popcount函数

在C++中，__builtin_popcount 函数是GCC编译器提供的内建函数，用于计算一个无符号整数中置位（值为1的位）的数量。这通常被称为"population count"。

例如：

#include <iostream>

int main() {
    unsigned int x = 23; // 二进制表示为 10111，有4个置位
    std::cout << __builtin_popcount(x) << std::endl;
    return 0;
}

上面的代码会输出 4，因为数字 23 的二进制表示中有四个 1。

使用这个内建函数通常比手动计算一个数的置位要快，因为它被优化为使用CPU指令来计算置位的数量。但是，需要注意的是，__builtin_popcount 函数是GCC特有的，不是标准C++库的一部分，因此在非GCC编译器中可能不可用或者有不同的函数名。在写可移植代码时要特别注意这一点。

打表法

在刷题过程中经常会遇到一类题，这类题的特点是：输入简单，可能是一个或几个数或数组，输出也简单，可能只让你返回一个整形的结果。当然，一般的方法是根据题目的要求编写对应的算法求解。但是有时候这种方法并不那么容易实现或者并不那么容易想，这个时候可以考虑一种比较取巧的方法：打表法。

打表法就是用暴力方法先求出前面几十个或一百个解，从中找出其规律，然后根据规律直接编写对应方法求解。