LeetCode解题技巧

大数溢出取余方法

加法取余运算规则

两个大数相加如果超过其类型可以表示的大小范围很容易导致溢出，所以使用加法取余运算规则:

\[(x + y) \odot p = (x \odot p + y \odot p) \odot p\]

在循环计算大数时，只要涉及的是加减法，且题干要求取余时，可以在每一步都进行取余，这样最后的结果仍然正确

乘法取余运算规则

当遇到大数相乘时，同样容易溢出，有乘法取余运算规则:

\[(xy) \odot p = [(x \odot p)(y \odot p)] \odot p\]

对于LeetCode常碰到的连续幂问题$y=x^a$，题干要求取模时可以对其进行分解，分为循环取余方法和快速幂取余方法

循环取余法

按公式(1-1)的方法啊对连续幂进行分解，在连续相乘过程中自下而上地不断对$x^1,x^2,\dots,x^{a-1},x^a$等计算其对$p$的余数
\[\begin{aligned} y = x^a \odot p & = [(x^{a-1} \odot p)(x \odot p)] \odot p \\ & \xlongequal[x \odot p = x]{x < p} [(x^{a-1} \odot p)x] \odot p \end{aligned} \tag{1-1}\]
```
//循环取余
int remainder(int x, int a, int p){
    int rem = 1;
    for(int i = 0;i < a;i++)
        rem = (rem * x) % p;
    return rem;
}
```
快速幂取余法

按公式(1-2)的方法，利用快速幂，只需循环$O(\log{N})$次，自上而下地对$x^a$求$(x^2 \odot p)^{a//2}$对$p$的余数即可
\[\begin{aligned} y & = x^a \odot p = (x^{2})^{\frac{a}{2}} \odot p = (x^2 \odot p)^{\frac{a}{2}} \odot p \\ & = \left\{ \begin{array}{l c r} (x^2 \odot p)^{a//2} \odot p, & & a\textrm{为偶数} \\[5px] [(x \odot p)(x^{a-1} \odot p)] \odot p \xlongequal[x \odot p = x]{x < p} [x(x^2 \odot p)^{a//2}] \odot p, & & a\textrm{为奇数} \end{array} \right . \end{aligned} \tag{1-2}\]
```
// 快速幂取余
int remainder(int x, int a, int p){
    int rem = 1;
    while(a > 0){
        if(a % 2 != 0)            // 指数为奇数时
            rem = (rem * x) % p;
        x = x * x % p;            // 底数为 x^2 \odot p
        a /= 2;
    }
    return rem;
}
```

位运算魔法技巧

快速判断二进制表示中从右边起始第一个1的二进制位

对于一个整数$n$，对其进行-1的操作，其二进制表示下便是最右边的1被变成了0，同时将该二进制位右边的其他0全部变成1

将$n-1$与$n$相与，显然会将自$(n)_b$最右边的1及其右边的所有进制位置0，这样不断反复的操作便可以清空原$n$的二进制表示中所有的1，操作次数便是1的个数

int nums_of_1_in_binary(int n) {
    int count = 0;
    while (n) {
        count++;
        n = (n - 1) & n;
    }
    return count;
}

链表技巧

妙用哨兵Sentinel

对于单向链表而言，如果断链、反转等操作可能会影响到整个链表的头节点时，建议引入哨兵作为固定的头节点

这样对原来的链表头节点进行操作时，不需要考虑其前一个节点为空的问题，比如LeetCode#92 反转链表2:

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

当left为1，也就是反转区域包括头节点时，因为需要返回反转后的链表头节点，如果不设置sentinel就需要在循环里添加额外的条件以处理待反转区域的前一个节点为NULL的情况，同时还需要不断更新头节点的指向，很麻烦

/**
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        // 由于要采用头插，一般可以设定一个哨兵插入整个链表的头部之前
        // 否则如果头部节点也要被断链就很麻烦
        ListNode *sentinel = new ListNode(-1);
        sentinel->next = head;
        // pre指向left所在节点的上一个节点(反转链表区域的前1个节点)
        ListNode *pre = sentinel;
        for (int i = 1; i < left; i++)  // 先遍历到要反转的第1个节点位置(从下标1开始而不是0)
            pre = pre->next;            // 最后pre指向第1个节点的前1个节点
        ListNode *cur = pre->next;      // 从反转区域的第1个节点开始
        ListNode *succ;                 // 保存当前节点指向的下一个节点successor
        // 每次反转是将succ头插到反转区域最前面(pre后面)
        for(int i = left + 1;i <= right; i++) {
            succ = cur->next;           // succ指向当前节点的下一个节点
            cur->next = succ->next;     // 断开succ指向当前节点的下下个节点的链
            succ->next = pre->next;     // pre后面插入succ(头插到待反转区域头部)
            pre->next = succ;           // 更新反转区域头
        }
        return sentinel->next;
    }
};

[LeetCode]其他解题技巧汇总

刷题时常用的技巧记录