左神学习笔记1

2025.11.22开始学习

2025.11.22 - 2025.11.24

位运算

1）二进制和位的概念 2）正数怎么用二进制表达 3）负数怎么用二进制表达 4）打印二进制；直接定义二进制、十六进制的变量 5）常见的位运算（|、&、^、~、<<、>>、>>>） 6）解释打印二进制的函数 7）注意|、&是位运算或、位运算与；||、&&是逻辑或、逻辑与，两者是有区别的 8）相反数 9）整数最小值的特殊性(取绝对值还是自己) 10）为什么这么设计二进制（为了加法的逻辑是一套逻辑，没有条件转移），那么为啥加法逻辑如此重要呢？ 11）关于溢出（自己确保自己的调用所得到的结果不会溢出，一定是自己确保的，计算机不会给你做检查） 12）位运算玩法很多很多，特别是异或运算（后面的课会详细讲述）、如何用位运算实现加减乘除（后面的课会详细讲述）

最小的负整数无相反数例如：INT_MIN的相反数还是自己

求相反数 (b和c都是a的相反数)：

c++

int a = 10;
int b = -a;
int c = ~a + 1;

对数器

c++

1，你想要测的方法a（最优解）
2，实现复杂度不好但是容易实现的方法b（暴力解）
3，实现一个随机样本产生器（长度也随机、值也随机）
4，把方法a和方法b跑相同的输入样本，看看得到的结果是否一样
5，如果有一个随机样本使得比对结果不一致，打印这个出错的样本进行人工干预，改对方法a和方法b
6，当样本数量很多时比对测试依然正确，可以确定方法a（最优解）已经正确。 

关键是第5步，找到一个数据量小的错误样本，便于你去带入debug
然后把错误例子带入代码一步一步排查
Print大法、断点技术都可以
对数器的门槛其实是比较高的，因为往往需要在两种不同思路下实现功能相同的两个方法，暴力一个、想象中的最优解是另一个。
以后的很多题目都会用到对数器，几乎可以验证任何方法，尤其在验证贪心、观察规律方面很有用
到时候会丰富很多对数器的实战用法，这里只是一个简单易懂的示例

二分搜索

1）在有序数组中确定num存在还是不存在 2）在有序数组中找>=num的最左位置 3）在有序数组中找<=num的最右位置 4）二分搜索不一定发生在有序数组上（比如寻找峰值问题） 5）“二分答案法”这个非常重要的算法，很秀很厉害，将在【必备】课程里继续如果数组长度为n，那么二分搜索搜索次数是log n次，以2为底

Lower_bound和upper_bound

https://labuladong.online/algo/essential-technique/binary-search-framework/

时间复杂度

1，常数操作，固定时间的操作，执行时间和数据量无关

2，时间复杂度，一个和数据量有关、只要高阶项、不要低阶项、不要常数项的操作次数表达式举例：选择、冒泡、插入

3，严格固定流程的算法，一定强调最差情况！比如插入排序

4，算法流程上利用随机行为作为重要部分的，要看平均或者期望的时间复杂度，因为最差的时间复杂度无意义（用生成相邻值不同的数组来说明）

5，算法流程上利用随机行为作为重要部分的，还有随机快速排序（【必备】课）、跳表（【扩展】课），也只在乎平均或者期望的时间复杂度，因为最差的时间复杂度无意义

6，时间复杂度的内涵：描述算法运行时间和数据量大小的关系，而且当数据量很大很大时，这种关系相当的本质，并且排除了低阶项、常数时间的干扰

7，空间复杂度，强调额外空间；常数项时间，放弃理论分析、选择用实验来确定，因为不同常数操作的时间不同

8，什么叫最优解，先满足时间复杂度最优，然后尽量少用空间的解

9，时间复杂度的均摊，用动态数组的扩容来说明（等比数列、均摊的意义）

并查集、单调队列、单调栈、哈希表等结构，均有这个概念。这些内容【必备】课都会讲

12，时间复杂度只能是对算法流程充分理解才能分析出来，而不是简单的看代码结构！这是一个常见的错误！

甚至有些算法的实现用了多层循环嵌套，但时间复杂度是O(N)的。在【必备】课程里会经常见到

13，常见复杂度一览：

c++

O(1) O(logN) O(N) O(N*logN) O(N^2) … O(N^k) O(2^N) … O(k^N) … O(N!)

14，时间复杂度非常重要，可以直接判断某个方法能不能通过一个题目，根据数据量猜解法，【必备】课都会讲

15，整套课会讲很多算法和数据结构，也会见到很多的时间复杂度的表达，持续看课即可

算法和数据结构简介

算法可分为：硬计算类算法、软计算类算法注意：这两个名词都不是计算机科学或算法中的标准术语那为啥要提这个呢？因为很有现实意义。

硬计算类算法：精确求解。但是某些问题使用硬计算类的算法，可能会让计算的复杂度较高。大厂算法和数据结构笔试、面试题、acm比赛或者和acm形式类似的比赛，考察的都是硬计算类算法。软计算类算法：更注重逼近解决问题，而不是精确求解。计算时间可控比如：模糊逻辑、神经网络、进化计算、概率理论、混沌理论、支持向量机、群体智能

硬计算类算法是所有程序员岗位都会考、任何写代码的工作都会用到的。前端、后端、架构、算法所有岗位都要用到。但是算法工程师除了掌握硬计算类的算法之外，还需要掌握软计算类的算法。

宏观的数据结构分类：连续结构、跳转结构任何数据结构都一定是这两个结构拼出来的！没有例外！

2025.11.25

015 最小栈

（1）题目

来源	题目/题单	说明
leetcode	https://leetcode.cn/problems/min-stack/description/	155. 最小栈
牛客	https://www.nowcoder.com/practice/a4d17eb2e9884359839f8ec559043761	最小栈
洛谷	https://www.luogu.com.cn/problem/T635562	T635562 最小栈
洛谷	https://www.luogu.com.cn/problem/T324020	T324020 最小栈

leetcode: https://leetcode.cn/problems/min-stack/description/

牛客：https://www.nowcoder.com/practice/a4d17eb2e9884359839f8ec559043761

洛谷： https://www.luogu.com.cn/problem/T635562

https://www.luogu.com.cn/problem/T324020

（2）洛谷题代码实现

cpp

#include <iostream>
using namespace std;
class minStack {
 public:
  static constexpr int N = 1e5 + 5;
  int a[N], b[N];
  int sz;
  minStack() { sz = 0; }
  bool pop() {
    if (sz) {
      sz--;
      return true;
    } else {
      return false;
    }
  }
  void push(int x) {
    a[sz] = x;
    if (sz == 0) {
      b[sz] = x;
    } else {
      b[sz] = min(x, b[sz - 1]);
    }
    sz++;
  }
  int top() {
    if (sz == 0) { return -1; }
    return a[sz - 1];
  }
  int get_min() {
    if (sz == 0) { return -1; }
    return b[sz - 1];
  }
};
int main() {
  minStack stk = minStack();
  int n, x;
  string s;
  scanf("%d", &n);
  while (n--) {
    cin >> s;
    if (s == "top") {
      int t = stk.top();
      if (t == -1) {
        printf("error\n");
      } else {
        printf("%d\n", t);
      }
    } else if (s == "push") {
      scanf("%d", &x);
      stk.push(x);
    } else if (s == "pop") {
      if (!stk.pop()) { printf("error\n"); }
    } else if (s == "get_min") {
      int t = stk.get_min();
      if (t == -1) {
        printf("error\n");
      } else {
        printf("%d\n", t);
      }
    }
  }
  return 0;
}

016 双端队列

（1）题目

牛客：

【模板】循环队列 https://www.nowcoder.com/practice/0a3a216e50004d8bb5da43ad38bcfcbf

双端队列设计https://www.nowcoder.com/practice/54ebef63058242459194a2bd1e04a908

leetcode: 641设计循环双端队列 https://leetcode.cn/problems/design-circular-deque/

洛谷： B3656 【模板】双端队列 1 https://www.luogu.com.cn/problem/B3656

T627198 【模板】双端队列 https://www.luogu.com.cn/problem/T627198

U546596 【模板】双端队列 https://www.luogu.com.cn/problem/U546596

T427220 【模板】双端队列 https://www.luogu.com.cn/problem/T427220

（2）代码：

数组实现双端队列：

cpp

class MyCircularDeque {
public:
    static constexpr int N = 1e3 + 5;
    int doubleEndQueue[N];
    int sz, limits, l, r;
    MyCircularDeque(int k) { l = r = sz = 0, limits = k; }

    bool insertFront(int value) {
        if (isEmpty()) {
            l = r = 0;
            doubleEndQueue[l] = value;
        } else {
            if (isFull()) {
                return false;
            }
            l = (l - 1 + limits) % limits;
            doubleEndQueue[l] = value;
        }
        sz++;
        return true;
    }

    bool insertLast(int value) {
        if (isEmpty()) {
            l = r = 0;
            doubleEndQueue[r] = value;
        } else {
            if (isFull()) {
                return false;
            }
            r = (r + 1) % limits;
            doubleEndQueue[r] = value;
        }
        sz++;
        return true;
    }

    bool deleteFront() {
        if (isEmpty()) {
            return false;
        }
        l = (l + 1) % limits;
        sz--;
        return true;
    }

    bool deleteLast() {
        if (isEmpty()) {
            return false;
        }
        r = (r - 1 + limits) % limits;
        sz--;
        return true;
    }

    int getFront() {
        if (isEmpty()) {
            return -1;
        }
        return doubleEndQueue[l];
    }

    int getRear() {
        if (isEmpty()) {
            return -1;
        }
        return doubleEndQueue[r];
    }

    bool isEmpty() { return sz == 0; }

    bool isFull() { return sz == limits; }
};

2025.11.26

算法讲解017【入门】二叉树及其三种序的递归实现

1）二叉树的节点

2）二叉树的先序、中序、后序

3）递归序加工出三种序的遍历

4）时间复杂度O(n)，额外空间复杂度O(h)，h是二叉树的高度

算法讲解018【入门】二叉树遍历的非递归实现和复杂度分析

1）用栈实现二叉树先序遍历

2）用栈实现二叉树中序遍历

3）用两个栈实现二叉树后序遍历，好写但是不推荐，因为需要收集所有节点，最后逆序弹出，额外空间复杂度为O(n)

4）用一个栈实现二叉树后序遍历

5）遍历二叉树复杂度分析：

3、存在时间复杂度O(n)，额外空间复杂度O(1)的遍历方式：Morris遍历

4、Morris遍历比较难，也比较冷门，会在【扩展】课程里讲述

#38aaa3

用一个栈实现二叉树后序遍历

cpp

#include <iostream>
#include <stack>

using namespace std;

// 假设 TreeNode 定义如下（与前文一致）
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

void posOrderOneStack(TreeNode* h) {
    if (h != nullptr) {
        stack<TreeNode*> stk;
        stk.push(h);
        // h 的含义：上一次打印的节点（初始为根节点）
        while (!stk.empty()) {
            TreeNode* cur = stk.top();
            // 如果有左子树，且左子树既不是刚打印的节点，也不是右子树（即未处理过）
            if (cur->left != nullptr && h != cur->left && h != cur->right) {
                stk.push(cur->left);
            }
            // 如果有右子树，且右子树不是刚打印的节点（即未处理过）
            else if (cur->right != nullptr && h != cur->right) {
                stk.push(cur->right);
            }
            // 左右子树都为空，或都已经处理过
            else {
                cout << cur->val << " ";
                h = stk.top();  // 记录刚刚打印的节点
                stk.pop();
            }
        }
        cout << endl;
    }
}

// 示例测试
int main() {
    // 构建测试树:
    //       1
    //      / \
    //     2   3
    //    / \ / \
    //   4  5 6 7
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->left = new TreeNode(6);
    root->right->right = new TreeNode(7);

    cout << "后序遍历（单栈非递归）: ";
    posOrderOneStack(root);

    // 简单内存释放（实际项目中建议用智能指针或封装析构）
    // 这里为简洁略去完整释放逻辑

    return 0;
}

算法讲解019【必备】算法笔试中处理输入和输出

Java语言： 1）填函数风格 2）acm风格（笔试、比赛最常见） a. 规定数据量(BufferedReader、StreamTokenizer、PrintWriter)，其他语言有对等的写法 b. 按行读(BufferedReader、PrintWriter)，其他语言有对等的写法 c. 不要用Scanner、System.out，IO效率慢 3）不推荐：临时动态空间 4）推荐：全局静态空间

算法讲解020【必备】递归和master公式

1）从思想上理解递归：对于新手来说，递归去画调用图是非常重要的，有利于分析递归

2）从实际上理解递归：递归不是玄学，底层是利用系统栈来实现的

3）任何递归函数都一定可以改成非递归，不用系统帮你压栈（系统栈空间），自己压栈呗（内存空间）

4）递归改成非递归的必要性：

a. 工程上几乎一定要改，除非确定数据量再大递归也一定不深，归并排序、快速排序、线段树、很多的平衡树等，后面都讲

b. 算法笔试或者比赛中（能通过就不改）

5）master公式

a. 所有子问题规模相同的递归才能用master公式：

b. 如果log(b,a) < c，复杂度为：O(n^c)

c. 如果log(b,a) > c，复杂度为：O(n^log(b,a))

d. 如果log(b,a) == c，复杂度为：O(n^c * logn)

注意：子问题的时间复杂度必须一样

6）一个补充

T(n) = 2T(n/2) + O(nlogn)，时间复杂度是 $O (n \cdot (\log n)^{2})$ [O(n * ((logn)^2))] ，证明过程比较复杂，记住即可

算法讲解021【必备】归并排序

前置知识：讲解019-算法笔试中处理输入和输出、讲解020-递归和master公式

1）左部分排好序、右部分排好序、利用merge过程让左右整体有序 2）merge过程：谁小拷贝谁，直到左右两部分所有的数字耗尽，拷贝回原数组 3）递归实现和非递归实现 4）时间复杂度O(n * logn) 5）需要辅助数组，所以额外空间复杂度O(n) 6）归并排序为什么比O(n^2)的排序快？因为比较行为没有浪费！ 7）利用归并排序的便利性可以解决很多问题 - 归并分治 - 下节课注意：有些资料说可以用原地归并排序，把额外空间复杂度变成O(1)，不要浪费时间去学因为原地归并排序确实可以省空间，但是会让复杂度变成O(n^2) 有关排序更多的概念、注意点、闭坑指南，将在后续课程继续

（1）题目

牛客： https://www.nowcoder.com/practice/bc25055fb97e4a0bb564cb4b214ffa92

洛谷： U232725 【模板】归并排序 https://www.luogu.com.cn/problem/U232725

U175650 【模板】归并排序 https://www.luogu.com.cn/problem/U175650

T323776 归并 https://www.luogu.com.cn/problem/T323776

T345322 【1-4例题A】归并 https://www.luogu.com.cn/problem/T345322

U223709 归并排序 https://www.luogu.com.cn/problem/U223709

T588262 归并排序 https://www.luogu.com.cn/problem/T588262

（2）代码

cpp

#include <iostream>
#include <algorithm>  // 用于 std::min
using namespace std;

const int N = 1e3 + 5;   // 最大数组长度（可根据需要调整）
int nums[N];             // 存储待排序的数据
int temp[N];             // 辅助数组，用于合并过程

/**
 * 合并两个已排序的子数组 [l, m] 和 [m+1, r]
 * 前提：nums[l..m] 和 nums[m+1..r] 都是有序的
 */
void merge(int l, int m, int r) {
    int i = l;           // 左子数组起始索引
    int j = m + 1;       // 右子数组起始索引
    int k = 0;           // temp 数组的写入位置

    // 比较左右两部分元素，按升序填入 temp
    while (i <= m && j <= r) {
        if (nums[i] <= nums[j]) {
            temp[k++] = nums[i++];
        } else {
            temp[k++] = nums[j++];
        }
    }

    // 复制左子数组剩余元素（如果有）
    while (i <= m) {
        temp[k++] = nums[i++];
    }

    // 复制右子数组剩余元素（如果有）
    while (j <= r) {
        temp[k++] = nums[j++];
    }

    // 将合并后的结果从 temp 写回原数组 nums 的 [l, r] 区间
    for (int idx = 0; idx < k; ++idx) {
        nums[l + idx] = temp[idx];
    }
}

/**
 * 递归版归并排序（自顶向下）
 * 对区间 [l, r] 进行排序
 */
void mergeSort1(int l, int r) {
    if (l >= r) return;                     // 基线条件：单个元素或无效区间

    int m = l + ((r - l) >> 1);             // 等价于 (l + r) / 2，但避免溢出

    mergeSort1(l, m);                       // 排序左半部分
    mergeSort1(m + 1, r);                   // 排序右半部分
    merge(l, m, r);                         // 合并两个有序部分
}

/**
 * 迭代版归并排序（自底向上）
 * 对区间 [start, end] 进行排序，无需递归
 */
void mergeSort2(int start, int end) {
    int n = end - start + 1;                // 待排序元素总数

    // step 表示当前每个子数组的长度，从 1 开始，每次翻倍
    for (int step = 1; step < n; step <<= 1) {
        int l = start;                      // 当前处理区间的左端点

        // 遍历整个数组，每次合并相邻的两个长度为 step 的块
        while (l <= end) {
            int m = l + step - 1;           // 第一个子块的右端点
            if (m + 1 > end) break;         // 若没有第二个子块，则跳过

            int r = min(l + (step << 1) - 1, end); // 第二个子块的右端点（可能不足 step）

            merge(l, m, r);                 // 合并 [l, m] 与 [m+1, r]

            l = r + 1;                      // 移动到下一组合并起点
        }
    }
}

/**
 * 主函数：读入数据，调用排序，输出结果
 */
int main() {
    int n;
    scanf("%d", &n);                        // 输入数组长度

    for (int i = 0; i < n; ++i) {
        scanf("%d", &nums[i]);              // 输入数组元素
    }

    // 选择一种排序方式（取消对应注释即可切换）：
    // mergeSort1(0, n - 1);                // 递归版（自顶向下）
    mergeSort2(0, n - 1);                   // 迭代版（自底向上）← 当前启用

    // 输出排序后的结果
    for (int i = 0; i < n; ++i) {
        printf("%d ", nums[i]);
    }
    printf("\n");

    return 0;
}

2025.11.27 16:26

算法讲解022【必备】归并分治

原理：

补充： 1）一些用归并分治解决的问题，往往也可以用线段树、树状数组等解法。时间复杂度也都是最优解，这些数据结构都会在【必备】或者【扩展】课程阶段讲到 2）本节讲述的题目都是归并分治的常规题，难度不大。归并分治不仅可以解决简单问题，还可以解决很多较难的问题，只要符合上面说的特征。比如二维空间里任何两点间的最短距离问题，这个内容会在【挺难】课程阶段里讲述。顶级公司考这个问题的也很少，因为很难，但是这个问题本身并不冷门，来自《算法导论》原题 3）还有一个常考的算法：“整块分治”。会在【必备】课程阶段讲到

聊：精妙又美丽的思想传统

来源	题目/题单	说明
牛客	https://www.nowcoder.com/practice/edfe05a1d45c4ea89101d936cac32469	计算数组的小和
leetcode	https://leetcode.cn/problems/reverse-pairs	493.翻转对
洛谷	https://www.luogu.com.cn/problem/T696215	T696215 翻转对

计算数组的小和： https://www.nowcoder.com/practice/edfe05a1d45c4ea89101d936cac32469

代码实现：

cpp

#include <iostream>
using namespace std;
const int N = 1e5 + 5;
typedef long long LL;
int nums[N], temp[N];
LL merge(int l, int m, int r) {
  // 计算跨左右两侧的小和
  LL ans = 0, sum = 0;
  for (int i = l, j = m + 1; j <= r; j++) {
    while (i <= m && nums[i] <= nums[j]) { sum += nums[i++]; }
    ans += sum;
  }
  // 归并过程
  int k = 0, i, j;
  for (i = l, j = m + 1; i <= m && j <= r;) {
    temp[k++] = nums[i] <= nums[j] ? nums[i++] : nums[j++];
  }
  while (i <= m) { temp[k++] = nums[i++]; }
  while (j <= r) { temp[k++] = nums[j++]; }
  for (i = 0; i < k; i++) { nums[l + i] = temp[i]; }
  return ans;
}
LL smallSum(int l, int r) {
  if (l >= r) { return 0; }
  int m = l + ((r - l) >> 1);
  return smallSum(l, m) + smallSum(m + 1, r) + merge(l, m, r);
}
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) { scanf("%d", nums + i); }
  printf("%lld", smallSum(0, n - 1));
  return 0;
}

算法讲解023【必备】随机快速排序

（1）内容1：

前置知识：讲解007-时间复杂度和空间复杂度-分析随机行为的时间复杂度的部分

经典随机快速排序流程讲解

荷兰国旗问题优化随机快速排序流程讲解

荷兰国旗问题优化后的过程：

在当前范围上选择一个数字x，利用荷兰国旗问题进行数组的划分，<x =x >x

对<x范围重复这个过程，对>x范围重复这个过程

荷兰国旗问题的优化点：选出一个数字x，数组在划分时会搞定所有值是x的数字

（2）快速排序的时间和空间复杂度分析

核心点：怎么选择数字？

选择的数字是当前范围上的固定位置，比如范围上的最右数字，那么就是普通快速排序

选择的数字是当前范围上的随机位置，那么就是随机快速排序

普通快速排序，时间复杂度O(n^2)，额外空间复杂度O(n)

随机快速排序，时间复杂度O(n * logn)，额外空间复杂度O(logn)

关于复杂度的分析，进行定性的说明，定量证明略，因为证明较为复杂

来源	题目/题单	说明
牛客	https://www.nowcoder.com/practice/3385982ae71d4a1ca8bf3d03614c0325	快速排序
牛客	https://www.nowcoder.com/practice/34731183c31e4276b2d081590b2f3a4b	排序（快速排序）
洛谷	https://www.luogu.com.cn/problem/T588555	T588555 快速排序
洛谷	https://www.luogu.com.cn/problem/U223702	U223702 快速排序
洛谷	https://www.luogu.com.cn/problem/T292012	T292012 【模板】快速排序
洛谷	https://www.luogu.com.cn/problem/T588555	T588555 快速排序
洛谷	https://www.luogu.com.cn/problem/T318859	T318859 Quick Sort快排

代码实现：

c++

void quick_sort(int l,int r)
{
    if(l >= r) return;
    int i = l,j = r,k = l,x = q[l + r >> 1];
    while(k <= j)
    {
        if(q[k] < x) swap(q[i ++],q[k ++]);
        else if(q[k] == x) k ++;
        else  swap(q[k],q[j --]);
    }
    quick_sort(l,i - 1),quick_sort(j + 1,r);
}

2025.11.28 17:09

算法讲解024【必备】随机选择算法

前置知识：讲解023-随机快速排序

无序数组中寻找第K大的数给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

利用改写快排的方法，时间复杂度O(n)，额外空间复杂度O(1)

题目：

来源	题目/题单	说明
牛客	https://www.nowcoder.com/practice/e016ad9b7f0b45048c58a9f27ba618bf	寻找第K大
leetcode	LCR 076. 数组中的第 K 个最大元素 - 力扣（LeetCode）	LCR 076. 数组中的第 K 个最大元素
洛谷	https://www.luogu.com.cn/problem/T588557	T588557 第K大的数
洛谷	https://www.luogu.com.cn/problem/U528642	U528642 第k大数
洛谷	https://www.luogu.com.cn/problem/U493243	U493243 求第 k 大的数
洛谷	https://www.luogu.com.cn/problem/U532286	U532286 第k大的数
洛谷	https://www.luogu.com.cn/problem/U493776	U493776 第 k 大数
洛谷	https://www.luogu.com.cn/problem/U511193	U511193 第K个数
洛谷	https://www.luogu.com.cn/problem/T217491	T217491 第k小数

代码：

核心代码模式：

c++

// 如果arr排序的话，在i位置的数字是什么
// 借助三路归并排序实现
int randomizedSelect(vector<int>& nums, int i) {
    int ans = 0;
    for (int l = 0, r = nums.size() - 1; l <= r;) {
        int lt = l, gt = r, j = l, x = nums[l + rand() % (r - l + 1)];
        while (j <= gt) {
            if (nums[j] < x) {
                swap(nums[j++], nums[lt++]);
            } else if (nums[j] == x) {
                j++;
            } else {
                swap(nums[j], nums[gt--]);
            }
        }
        if (i < lt) {
            r = lt - 1;
        } else if (i > gt) {
            l = gt + 1;
        } else {
            ans = nums[lt];
            break;
        }
    }
    return ans;
}
// 返回数组中的第 K 个最大元素
int findKthLargest(vector<int>& nums, int k) {
    return randomizedSelect(nums, nums.size() - k);
}

ACM模式（ https://www.luogu.com.cn/problem/U528642 第K大的数）：

c++

#include <iostream>
using namespace std;
const int N = 1e7 + 5;
int nums[N];
int n, k;
int findKth(int k) {
  for (int l = 0, r = n - 1; l <= r;) {
    int lt = l, gt = r, x = nums[l + rand() % (r - l + 1)];
    for (int i = l; i <= gt;) {
      if (nums[i] < x) {
        swap(nums[i++], nums[lt++]);
      } else if (nums[i] == x) {
        i++;
      } else {
        swap(nums[i], nums[gt--]);
      }
    }
    if (k < lt) {
      r = lt - 1;
    } else if (k > gt) {
      l = gt + 1;
    } else {
      return nums[k];
    }
  }
  return -1;
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 0; i < n; i++) { scanf("%d", nums + i); }
  printf("%d", findKth(n - k));
  return 0;
}

2025.11.29 11:12

算法讲解025【必备】堆结构和堆排序

前置知识：无

堆结构完全二叉树和数组前缀范围来对应，大小，单独的变量size来控制 i的父亲节点：(i-1)/2，i的左孩子：i*2 + 1，i的右孩子：i*2 + 2 堆的定义（大根堆、小根堆），本节课讲解按照大根堆来讲解，小根堆是同理的。堆的调整：heapInsert（向上调整）、heapify（向下调整） heapInsert、heapify方法的单次调用，时间复杂度O(log n)，完全二叉树的结构决定的

堆排序 A. 从顶到底建堆，时间复杂度O(n * log n)，log1 + log2 + log3 + … + logn -> O(n*logn) 或者用增倍分析法：建堆的复杂度分析+子矩阵数量的复杂度分析 B. 从底到顶建堆，时间复杂度O(n)，总代价就是简单的等比数列关系，为啥会有差异？简单图解一下 C. 建好堆之后的调整阶段，从最大值到最小值依次归位，时间复杂度O(n * log n) 时间复杂度O(n * log n)，不管以什么方式建堆，调整阶段的时间复杂度都是这个，所以整体复杂度也是这个额外空间复杂度是O(1)，因为堆直接建立在了要排序的数组上，所以没有什么额外空间

注意：堆结构比堆排序有用的多，尤其是和比较器结合之后。后面几节课会重点讲述。

来源	题目/题单	说明
牛客	https://www.nowcoder.com/practice/ed8308a5f0f744fc936bdba78c15f810	排序（堆排序）
洛谷	https://www.luogu.com.cn/problem/U272509	U272509 堆排序
洛谷	https://www.luogu.com.cn/problem/U308067	U308067 堆排序
洛谷	https://www.luogu.com.cn/problem/T625390	T625390 堆排序
洛谷	https://www.luogu.com.cn/problem/U551901	U551901 堆排序
洛谷	https://www.luogu.com.cn/problem/U247189	U247189 堆排序
洛谷	https://www.luogu.com.cn/problem/U613162	U613162 堆排序
洛谷	https://www.luogu.com.cn/problem/T522102	T522102 使用堆排序
洛谷	https://www.luogu.com.cn/problem/U303835	U303835 堆排序
洛谷	https://www.luogu.com.cn/problem/U590353	U590353 堆排序
洛谷	https://www.luogu.com.cn/problem/T632596	T632596 堆排序
洛谷	https://www.luogu.com.cn/training/12191	堆
洛谷	https://www.luogu.com.cn/training/168012	堆
洛谷	https://www.luogu.com.cn/training/500218	堆排序

堆排序简介

堆排序是一种基于二叉堆数据结构的选择排序算法。它分为两个主要阶段：建立堆和排序过程。堆可以是最大堆或最小堆，这里我们讨论的是基于最大堆的堆排序算法。

基本概念

堆：堆是一种特殊的完全二叉树结构。

最大堆：对于每一个非叶子节点，其值都大于等于它的孩子节点的值。

最小堆：对于每一个非叶子节点，其值都小于等于它的孩子节点的值。

堆排序步骤

构造最大堆：将无序序列构造成一个最大堆。

排序：将堆顶元素与最后一个元素交换，然后调整剩余元素使其满足最大堆性质，重复此过程直到整个序列有序。

代码：

c++

#include <iostream>
using namespace std;
const int N = 1e5 + 5;  // 定义数组的最大大小
int nums[N];            // 存储输入数据的数组

// 上浮操作：用于维护大顶堆的性质
void up(int k) {
  // 当当前节点值大于其父节点值时进行交换
  while (k && nums[k] > nums[(k - 1) / 2]) {
    swap(nums[k], nums[(k - 1) / 2]);  // 交换当前节点与父节点
    k = (k - 1) / 2;                   // 更新当前节点为其父节点位置
  }
}

// 下沉操作：同样用于维护大顶堆的性质
void down(int k, int end) {
  int temp = nums[k];
  // 遍历子节点，寻找最大的子节点上浮
  for (int i = 2 * k + 1; i <= end; i = 2 * i + 1) {
    if (i < end && nums[i] < nums[i + 1]) {
      i++;
    }  // 如果右子节点存在且比左子节点大，则选择右子节点
    if (nums[i] <= temp) { break; }  // 如果找到的位置不大于temp，则停止下沉
    nums[k] = nums[i];               // 将较大的子节点上移
    k = i;                           // 更新当前位置为较大子节点位置
  }
  nums[k] = temp;  // 最后放置临时变量保存的值
}

// 自底向上建堆方法，时间复杂度O(nlogn)
void buildHeap1(int start, int end) {
  for (int i = start; i <= end; i++) { up(i); }  // 对每个元素执行上浮操作
}

// 自顶向下建堆方法，时间复杂度O(n)
void buildHeap2(int start, int end) {
  for (int i = (end - 1) / 2; i >= start; i--) {
    down(i, end);
  }  // 从最后一个非叶子节点开始执行下沉操作
}

// 堆排序函数
void HeapSort(int start, int end) {
  buildHeap2(start, end);  // 使用自顶向下方法构建堆
  for (int i = end; i > start;) {
    swap(nums[i--], nums[start]);  // 将堆顶元素与末尾元素交换
    down(start, i);                // 调整堆
  }
}

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) { scanf("%d", nums + i); }   // 输入数组元素
  HeapSort(0, n - 1);                                      // 执行堆排序
  for (int i = 0; i < n; i++) { printf("%d ", nums[i]); }  // 输出排序后的数组
  return 0;
}

算法讲解026【必备】哈希表、有序表和比较器的用法

前置知识：无提醒：讲解虽然用的java语言，但是任何语言都有对等的概念提醒：后续有专门的章节来详解哈希函数、有序表，这节课就是常规用法展示

哈希表的用法（认为是集合，根据值来做key 或者根据内存地址做key） HashSet和HashMap原理一样，有无伴随数据的区别增、删、改、查时间为O(1)，但是大常数所以当key的范围是固定的、可控的情况下，可以用数组结构替代哈希表结构注意： Java中通过自定义hashCode、equals等方法任何类都可以实现“根据值做key”或者“根据内存地址做key”的需求但是这里不再展开，因为在算法学习这个范畴内，这些并不重要，还有其他语言的同学也不关心这些笔试、面试、比赛也都不会用到，课上只说对算法学习重要的内容

有序表的用法（认为是集合，但是有序组织） TreeSet和TreeMap原理一样，有无伴随数据的区别增、删、改、查 + 很多和有序相关的操作(floor、ceilling等)，时间为O(log n) 有序表比较相同的东西会去重，如果不想去重就加入更多的比较策略（比较器定制）。堆不会去重。有序表在java里就是红黑树实现的 AVL树、SB树、替罪羊树、Treap、Splay、跳表等等很多结构都可实现同样功能后续的课程会涉及，这里不做展开，只讲解简单用法

比较器：定制比较策略。用在排序、堆、有序表等很多需要序的结构中都可使用定义类、直接Lamda表达式字典序的概念

2025.11.30 10:50

算法讲解027【必备】堆结构常见题

堆结构常见题：前置知识:讲解025-堆结构和堆排序、讲解026-比较器题目1：合并K个有序链表题目2：线段最多重合问题题目3：让数组整体累加和减半的最少操作次数

来源	题目/题单	说明
牛客	合并k个已排序的链表_牛客题霸_牛客网	合并k个已排序的链表
leetcode	23. 合并 K 个升序链表 - 力扣（LeetCode）	23. 合并 K 个升序链表
leetcode	LCR 078. 合并 K 个升序链表 - 力扣（LeetCode）	LCR 078. 合并 K 个升序链表

牛客	线段重合_牛客题霸_牛客网	线段重合
洛谷	https://www.luogu.com.cn/problem/U628908	U628908 最大线段重合数

leetcode	2208. 将数组和减半的最少操作次数 - 力扣（LeetCode）	2208. 将数组和减半的最少操作次数
洛谷	https://www.luogu.com.cn/problem/T525681	T525681 最少减半

	https://www.luogu.com.cn/problem/U518931	U518931 会议室
	https://www.luogu.com.cn/problem/U422228	U422228 会议室

算法讲解028【必备】基数排序

前置知识：无

（1）基于比较的排序：只需要定义好两个对象之间怎么比较即可，对象的数据特征并不关心，很通用

（2）不基于比较的排序：和比较无关的排序，对于对象的数据特征有要求，并不通用

计数排序，非常简单，但是数值范围比较大了就不行了

基数排序的实现细节，非常优雅的一个实现

关键点：前缀数量分区的技巧、数字提取某一位的技巧
时间复杂度O(n)，额外空间复杂度O(m)，需要辅助空间做类似桶的作用，来不停的装入、弹出数字

一般来讲，计数排序要求，样本是整数，且范围比较窄

一般来讲，基数排序要求，样本是10进制的非负整数

如果不是就需要转化，代码里做了转化，并且代码里可以设置任何进制来进行排序

一旦比较的对象不再是常规数字，那么改写代价的增加是显而易见的，所以不基于比较的排序并不通用

来源	题目/题单	说明
牛客	排序（基数排序）_牛客题霸_牛客网	排序（基数排序）
洛谷	https://www.luogu.com.cn/problem/T436777	T436777 基数排序的过程
洛谷	https://www.luogu.com.cn/problem/U379590	U379590 基数排序的过程
洛谷	https://www.luogu.com.cn/problem/T110310	T110310 基数排序的过程

当然可以！以下是根据你提供的 C++ 基数排序代码，整理出的一份结构清晰、注释详尽、适合在 Typora 中渲染的 Markdown 笔记。该笔记涵盖了基数排序的基本原理、算法步骤、代码详解与注意事项。

基数排序（Radix Sort）详解

适用场景：对非负整数（或可转化为非负整数）进行线性时间排序 时间复杂度： $O (d \cdot (n + k))$ ，其中 $d$ 是最大数的位数， $k$ 是进制（通常为 10） 空间复杂度： $O (n + k)$ 稳定性：稳定排序

一、基本思想

基数排序是一种非比较型整数排序算法，其核心思想是：

将整数按位数（个位、十位、百位……）依次进行排序；
每一位使用**计数排序（Counting Sort）**作为子过程；
从最低位（Least Significant Digit, LSD）开始，逐位向高位处理；
由于计数排序是稳定的，因此最终结果保持整体有序。

⚠️ 注意：标准的基数排序要求输入数据为非负整数。若存在负数，需特殊处理（如偏移法）。

二、算法流程

找出数组中的最大值，确定最大位数 d；
对每一位（从个位到最高位）使用计数排序对该位进行排序；
排序完成后，数组即为升序排列。

三、C++ 实现（含详细注释）

cpp

#include <algorithm>  // for min, max
#include <iostream>
using namespace std;

const int BASE = 10;    // 进制（十进制）
const int N = 1e5 + 5;  // 最大元素数量
int nums[N], temp[N];   // 原数组与临时数组
int cnt[BASE];          // 计数数组，用于计数排序
int n;                  // 数组长度

// 辅助函数：计算一个非负整数 x 在 BASE 进制下的位数
int getBits(int x) {
  if (x == 0) return 1;  // 特殊处理 0
  int ans = 0;
  while (x) {
    x /= BASE;
    ans++;
  }
  return ans;
}

/**
 * 基数排序核心函数（LSD 版本）
 * @param bits: 最大数在 BASE 进制下的位数
 * @note 要求 nums 中所有元素已转换为非负整数
 */
void radixSort(int bits) {
  // offset 表示当前处理的是哪一位（1=个位, 10=十位, 100=百位...）
  for (int offset = 1; bits > 0; offset *= BASE, bits--) {
    // 1. 清空计数数组
    fill(cnt, cnt + BASE, 0);

    // 2. 统计当前位上各数字（0~9）的出现次数
    for (int i = 0; i < n; i++) {
      int digit = (nums[i] / offset) % BASE;
      cnt[digit]++;
    }

    // 3. 将计数数组转换为前缀和（得到每个数字在 temp 中的结束位置）
    for (int i = 1; i < BASE; i++) { cnt[i] += cnt[i - 1]; }

    // 4. 从后往前遍历原数组（保证稳定性），将元素放入 temp
    for (int i = n - 1; i >= 0; i--) {
      int digit = (nums[i] / offset) % BASE;
      temp[--cnt[digit]] = nums[i];
    }

    // 5. 将 temp 复制回 nums，完成当前位排序
    for (int i = 0; i < n; i++) { nums[i] = temp[i]; }
  }
}

/**
 * 外部接口：支持包含负数的数组排序
 * 方法：先整体偏移，使所有数变为非负；排序后再还原
 */
void RadixSort() {
  // 1. 找最小值（用于偏移）
  int minVal = nums[0];
  for (int i = 1; i < n; i++) { minVal = min(nums[i], minVal); }

  // 2. 偏移：所有元素减去 minVal，确保非负
  for (int i = 0; i < n; i++) { nums[i] -= minVal; }

  // 3. 找最大值（用于确定位数）
  int maxVal = 0;
  for (int i = 0; i < n; i++) { maxVal = max(maxVal, nums[i]); }

  // 4. 执行基数排序
  radixSort(getBits(maxVal));

  // 5. 还原原始数值（加回偏移量）
  for (int i = 0; i < n; i++) { nums[i] += minVal; }
}

// 主函数：读入、排序、输出
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++) { scanf("%d", nums + i); }
  RadixSort();
  for (int i = 0; i < n; i++) { printf("%d ", nums[i]); }
  return 0;
}

四、关键点解析

✅ 为什么从低位开始？

LSD（Least Significant Digit）方式允许我们逐步构建有序序列；
每次排序只关注当前位，但依赖之前低位已排好序（稳定性保障）。

✅ 为什么需要 temp 数组？

计数排序需要一个临时输出数组来存放排序后的结果；
直接在原数组操作会覆盖未处理的数据。

✅ 如何处理负数？

通过整体偏移（减去最小值）将所有数转为非负；
排序后再加回偏移量，恢复原始值；
此方法适用于整数范围不太大的情况（避免溢出）。

✅ 时间复杂度分析

设最大数有 d 位，每次计数排序耗时 $O (n + B A S E)$ ；
总时间： $O (d \cdot (n + B A S E))$ ；
当 d 为常数（如 32 位整数最多 10 位十进制数），可视为 线性时间。

五、优缺点总结

优点	缺点
✅ 线性时间复杂度（特定条件下）	❌ 仅适用于整数或可映射为整数的数据
✅ 稳定排序	❌ 需额外空间（O(n + k)）
✅ 实际性能优秀（缓存友好）	❌ 负数需特殊处理

六、应用场景

对大量整数进行排序（如学号、ID、电话号码等）；
作为其他算法的子过程（如字符串排序中按字符位处理）；
在已知数据范围且无浮点数时，可替代快速排序获得更优性能。

算法讲解029【必备】重要排序算法的总结

1、排序算法的稳定性

稳定性：若待排序序列中存在多个相等元素，排序后它们的相对次序保持不变，则该排序算法是稳定的。

对基础类型（如 int、float）：稳定性无实际意义，因为值相同即视为完全等价。
对非基础类型对象（如学生记录、订单等）：稳定性很重要，可保留原始数据中的逻辑顺序（例如：先按姓名排序，再按年龄排序时，同龄人仍保持姓名排序的次序）。

2、主流排序算法对比表

算法名称	时间复杂度	空间复杂度	稳定性
选择排序 (SelectionSort)	O(N²)	O(1)	❌ 不稳定
冒泡排序 (BubbleSort)	O(N²)	O(1)	✅ 稳定
插入排序 (InsertionSort)	O(N²)	O(1)	✅ 稳定
归并排序 (MergeSort)	O(N log N)	O(N)	✅ 稳定
快速排序 (QuickSort)	O(N log N)（期望）	O(log N)（递归栈）	❌ 不稳定
堆排序 (HeapSort)	O(N log N)	O(1)	❌ 不稳定
计数排序 (CountSort)	O(N)	O(M)（M为值域大小）	✅ 稳定
基数排序 (RadixSort)	O(N)	O(M)（每轮桶空间）	✅ 稳定

注：
随机化快速排序的时间复杂度应以期望时间复杂度 O(N log N) 为准，最坏情况 O(N²) 在随机化下概率极低，不应作为主要评估依据。
M 表示数据的值域范围（如最大值 - 最小值 + 1），适用于非比较类排序。

3、理论边界与补充说明

（1）基于比较的排序算法限制

下界：任何基于元素比较的排序算法，其最坏或平均时间复杂度下限为 O(N log N)。
不可能三角：目前不存在同时满足以下三个条件的基于比较的排序算法：
- 时间复杂度 O(N log N)
- 空间复杂度 低于 O(N)（即 O(1) 或 O(log N)）
- 稳定

即使是实际中表现优异的 TimSort（Python 和 Java 默认排序）：
虽在多数场景空间占用较小，
但其最坏空间复杂度仍为 O(N)，
且在算法竞赛、面试中极少要求实现或使用。

（2）其他算法简述

希尔排序 (ShellSort)：是插入排序的改进版，通过引入“步长”进行分组插入排序。虽有时性能不错，但不稳定，且理论分析复杂，不常用于标准考察。

4、实际应用选型建议

根据具体需求选择合适的排序算法：

场景需求	推荐算法	理由
数据量极小（如 N < 50）	插入排序	常数小、实现简单、缓存友好，实际运行快
追求高性能 + 实现简单 + 不要求稳定	随机快速排序	平均性能最优，原地排序，广泛用于标准库
要求稳定 + 高性能 + 可接受额外空间	归并排序	稳定、时间复杂度稳定 O(N log N)，适合链表或外部排序
要求 O(1) 额外空间 + 高性能 + 不要求稳定	堆排序	原地排序，最坏情况仍为 O(N log N)，但常数较大
整数/有限范围数据 + 极致线性时间	计数排序 / 基数排序	非比较排序，O(N) 时间，但需值域不太大

5、总结

没有“最好”的排序算法，只有“最合适”的排序算法。 选择时需综合考虑：
数据规模（N 大小）
数据分布（是否近似有序、值域范围）
稳定性要求
空间限制
实现复杂度与工程维护性

掌握各类排序的本质特性，才能在算法设计与系统优化中做出合理决策。

2025.12.01 22:35

白天在完善github首页。

完善学习算法讲解030【必备】异或运算的骚操作了一半，后半部分太晚了没学

2025.12.02 10:44

算法讲解030【必备】异或运算的骚操作

异或运算性质

(1) 异或运算就是无进位相加(2) 异或运算满足交换律、结合律，也就是同一批数字，不管异或顺序是什么，最终的结果都是一个(3) 0^n=n，n^n=0(4) 整体异或和如果是x，整体中某个部分的异或和如果是y，那么剩下部分的异或和是x^y

这些结论最重要的就是 (1) 结论，所有其他结论都可以由这个结论推论得到

其中第 (4) 相关的题目最多，利用区间上异或和的性质

Nim博弈也是和异或运算相关的算法，将在后续【必备】课程里讲到

题目：

题目1 交换两个数

题目2 不用任何判断语句和比较操作，返回两个数的最大值

题目3 找到缺失的数字

题目4 数组中1种数出现了奇数次，其他的数都出现了偶数次，返回出现了奇数次的数

Brian Kernighan算法 - 提取出二进制状态中最右侧的1

题目5 数组中有2种数出现了奇数次，其他的数都出现了偶数次，返回这2种出现了奇数次的数

题目6 数组中只有1种数出现次数少于m次，其他数都出现了m次，返回出现次数小于m次的那种数

交换两个数：

c++

void swap(int& a, int& b){
    a ^= b;
    b ^= a;
    a ^= b;
}

返回两个数的最大值：

c++

#include <climits>
#include <iostream>

using namespace std;

// 必须保证 n 是 0 或 1
// 0 变 1，1 变 0
int flip(int n) { return n ^ 1; }

// 非负数返回 1，负数返回 0
int sign(int n) {
  // 在 C++ 中，右移负数是实现定义的（通常是算术右移）
  // 所以不能直接用 n >> 31
  // 我们通过将 n 转为 unsigned int 来逻辑右移
  return flip(static_cast<int>((static_cast<unsigned int>(n) >> 31)));
}


// 安全实现（无溢出问题）
int getMax(int a, int b) {
  int c = a - b;  // 可能溢出，但我们不会直接依赖它的符号当 a、b 异号时
  int sa = sign(a);
  int sb = sign(b);
  int sc = sign(c);

  int diffAB = sa ^ sb;       // 符号不同则为 1
  int sameAB = flip(diffAB);  // 符号相同则为 1

  // 如果符号不同：选正数（sa == 1 则 a 是非负，即更大）
  // 如果符号相同：看 c 的符号（即 a - b 是否非负）
  int returnA = diffAB * sa + sameAB * sc;
  int returnB = flip(returnA);
  return a * returnA + b * returnB;
}

int main() {
  int a = 10;
  int b = 4;

  // getMax 始终正确
  cout << getMax(a, b) << endl;

  return 0;
}

来源	题目/题单	说明
牛客	获取最大值_牛客题霸_牛客网	获取最大值
leetcode	268. 丢失的数字 - 力扣（LeetCode）	268. 丢失的数字
洛谷	https://www.luogu.com.cn/problem/T454753	T454753 寻找丢失的数字
洛谷	https://www.luogu.com.cn/problem/T311157	T311157 丢失的数字
洛谷	https://www.luogu.com.cn/problem/U631225	U631225 丢失的数字
洛谷	https://www.luogu.com.cn/problem/U482390	U482390 丢失的数字

leetcode	136. 只出现一次的数字 - 力扣（LeetCode）	136. 只出现一次的数字

leetcode	260. 只出现一次的数字 III - 力扣（LeetCode）	260. 只出现一次的数字 III

leetcode	137. 只出现一次的数字 II - 力扣（LeetCode）	137. 只出现一次的数字 II

算法讲解031【必备】位运算的骚操作

前置知识：讲解003-二进制和位运算、讲解030-异或运算的骚操作特别提醒：Python的同学实现位运算的题目需要特别注意，需要自己去手动处理溢出和符号扩展等问题比如：(n << shift_amount) & 0xFFFFFFFF

位运算有很多奇技淫巧，位运算的速度非常快，仅次于赋值操作，常数时间极好！

这节课展示一下先贤的功力！骚就完了！

关于位运算还有非常重要的内容： N皇后问题用位运算实现，将在【必备】课程里讲到状态压缩的动态规划，将在【扩展】课程里讲到

题目1 判断一个整数是不是2的幂

题目2 判断一个整数是不是3的幂

题目3 返回大于等于n的最小的2的幂

题目4 区间[left, right]内所有数字 & 的结果

题目5 反转一个二进制的状态，不是0变1、1变0，是逆序。超自然版

题目6 返回一个数二进制中有几个1。超自然版，看完佩服大牛的脑洞，能爽一整天

题目5和题目6代码看着跟脑子有大病一样，承认很强但似乎有点太嘚瑟了，是这样吗？

不是的，条件判断相比于赋值、位运算、算术运算是稍慢的，所以其实有现实意义

但是不需要追求在练算法过程中尽量少写条件判断，

那样会带来很多不必要的困扰，还是要写尽量直白、尤其是自己能理解的代码最好

大牛的实现欣赏完理解就好，下次当模版直接用

来源	题目/题单	说明
leetcode	201. 数字范围按位与 - 力扣（LeetCode）	201. 数字范围按位与
leetcode	190. 颠倒二进制位 - 力扣（LeetCode）	190. 颠倒二进制位
leetcode	461. 汉明距离 - 力扣（LeetCode）	461. 汉明距离

3、返回大于等于n的最小的2的幂

c++

#include <iostream>
using namespace std;

// 定义常量 N（虽然本题中未使用，但保留原样）
const int N = 1e4 + 5;

/**
 * 返回大于等于 n 的最小的 2 的幂。
 * 原理：通过位运算将 n-1 的二进制表示“填满”为全 1，
 * 然后加 1 得到下一个 2 的幂。
 * 
 * 例如：
 *   n = 5 -> n-1 = 4 (100)
 *   经过一系列右移和或操作后变为 111 (即 7)
 *   返回 7 + 1 = 8，即 >=5 的最小 2 的幂。
 * 
 * 注意：该函数假设 n > 0，且结果不会溢出 int 范围。
 */
int getNear2power(int n) {
    // 特殊情况：如果 n <= 1，直接返回 1（因为 2^0 = 1）
    if (n <= 1) return 1;
    n--;  // 先减 1，是为了处理 n 本身已经是 2 的幂的情况
    // 将最高位的 1 复制到其右边所有低位，最终使 n 变成形如 00...0111...1 的形式
    n |= n >> 1;   // 将最高位的 1 复制到次高位
    n |= n >> 2;   // 每次扩大覆盖范围：2 位 → 4 位 → 8 位...
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;  // 对于 32 位整数，最多需要右移 16 位即可覆盖全部低位

    // 此时 n 是小于目标值的最大“全 1”数，加 1 即得最小的 ≥ 原 n 的 2 的幂
    return n + 1;
}

int main() {
    int n;
    scanf("%d", &n);
    printf("%d", getNear2power(n));
    return 0;
}

2025.12.03 21:12

算法讲解031【必备】位运算的骚操作尚同

2025.12.04 10:54

算法讲解031【必备】位运算的骚操作尚同

算法讲解032【必备】位图

前置知识：讲解003-二进制和位运算、讲解005-对数器

特别提醒：Python的同学实现位运算的题目需要特别注意，需要自己去手动处理溢出和符号扩展等问题比如：(n << shift_amount) & 0xFFFFFFFF

（1）位图原理

其实就是用bit组成的数组来存放值，用bit状态1、0代表存在、不存在，取值和存值操作都用位运算。限制是必须为连续范围且不能过大。好处是极大的节省空间，因为1个数字只占用1个bit的空间

（2）位图的实现 Bitset(int n)：初始化位图的大小，只支持0~n-1所有数字的增删改查

void add(int num)：把num加入到位图

void remove(int num)：把num从位图中删除

void reverse(int num)：如果位图里没有num，就加入；如果位图里有num，就删除

boolean contains(int num)：查询num是否在位图中

将采用对数器验证，当你找不到测试链接的时候就用对数器验证，而且对数器验证更稳妥、更能练习debug能力

c++

#include <cstdlib>  // 用于 rand() 和 srand()
#include <ctime>    // 用于 time()
#include <iostream>
#include <unordered_set>

using namespace std;

// 位图的实现
class Bitset {
 public:
  // 使用 vector 替代 int[]，自动管理内存
  int* set;

  // n个数字 : 0~n-1
  Bitset(int n) {
    // (n + 31) / 32 是向上取整的写法，确保空间足够
    // vector 构造时会自动将所有元素初始化为 0
    set = new int[(n + 31) / 32];
  }

  void add(int num) { set[num / 32] |= (1 << (num % 32)); }

  void remove(int num) { set[num / 32] &= ~(1 << (num % 32)); }

  void reverse(int num) { set[num / 32] ^= (1 << (num % 32)); }

  bool contains(int num) { return ((set[num / 32] >> (num % 32)) & 1) == 1; }
 
};

int main() {
  // 初始化随机数种子，类似 Java 的随机环境
  srand((unsigned int)time(0));
  string s;

  int n = 1000;
  int testTimes = 10000;
  cout << "测试开始" << endl;

  // 实现的位图结构
  Bitset bitSet(n);

  // 直接用 unordered_set 做对比测试 (C++ 中的 HashSet)
  unordered_set<int> hashSet;

  cout << "调用阶段开始" << endl;
  for (int i = 0; i < testTimes; i++) {
    // 生成 [0, 1) 之间的随机小数
    double decide = (double)rand() / RAND_MAX;
    // number -> 0 ~ n-1
    int number = rand() % n;

    if (decide < 0.333) {
      bitSet.add(number);
      hashSet.emplace(number);
    } else if (decide < 0.666) {
      bitSet.remove(number);
      hashSet.erase(number);
    } else {
      bitSet.reverse(number);
      // hashSet.count 返回 1 表示存在，0 表示不存在
      if (hashSet.count(number)) {
        hashSet.erase(number);
      } else {
        hashSet.insert(number);
      }
    }
  }
  printf("调用阶段结束\n");

  printf("验证阶段开始\n");
  for (int i = 0; i < n; i++) {
    bool bitSetHas = bitSet.contains(i);
    bool hashSetHas = hashSet.count(i);  // count > 0 即为 true

    if (bitSetHas != hashSetHas) { cout << "出错了!" << endl; }
  }
  printf("验证阶段结束\n");
  printf("测试结束\n");

  return 0;
}

找到了一个相关测试：https://leetcode-cn.com/problems/design-bitset/

Bitset是一种能以紧凑形式存储位的数据结构

Bitset(int n) : 初始化n个位，所有位都是0

void fix(int i) : 将下标i的位上的值更新为1

void unfix(int i) : 将下标i的位上的值更新为0

void flip() : 翻转所有位的值

boolean all() : 是否所有位都是1

boolean one() : 是否至少有一位是1

int count() : 返回所有位中1的数量

String toString() : 返回所有位的状态

位图的后续扩展，将在【扩展】课程里进一步讲述

算法讲解033【必备】位运算实现加减乘除

前置知识：讲解003-二进制和位运算特别提醒：Python的同学实现位运算的题目需要特别注意，需要自己去手动处理溢出和符号扩展等问题比如：(n << shift_amount) & 0xFFFFFFFF

位运算实现加减乘除，过程中不能出现任何算术运算符

加法：利用每一步无进位相加的结果 + 进位的结果不停计算，直到进位消失减法：利用加法，和一个数字x相反数就是(~x)+1 乘法：回想小学时候怎么学的乘法，除此之外没别的了除法：为了防止溢出，让被除数右移，而不是除数左移。从高位尝试到低位。

29. 两数相除 - 力扣（LeetCode）

代码实现：

c++

#include <climits>
#include <cstdlib>
#include <ctime>
#include <iostream>
using namespace std;

int add(int a, int b) {
  while (b != 0) {
    int sum = a ^ b;
    b = (a & b) << 1;
    a = sum;
  }
  return a;
}

int neg(int a) { return add(~a, 1); }

int SelfMinus(int a, int b) { return add(a, neg(b)); }

int multiply(int a, int b) {
  int ans = 0;
  while (b != 0) {
    if ((b & 1) != 0) { ans = add(ans, a); }
    a = static_cast<int>(static_cast<unsigned int>(a) << 1);
    b = static_cast<int>(static_cast<unsigned int>(b) >> 1);
  }
  return ans;
}

int SelfDiv(int a, int b) {
  int x = a < 0 ? neg(a) : a;
  int y = b < 0 ? neg(b) : b;
  int ans = 0;
  for (int i = 30; i >= 0; i = SelfMinus(i, 1)) {
    if ((static_cast<unsigned int>(x) >> i) >= y) {
      ans |= (1 << i);
      x = SelfMinus(x, y << i);
    }
  }
  return (a < 0) ^ (b < 0) ? neg(ans) : ans;
}

int divide(int a, int b) {
  if (a == INT_MIN && b == INT_MIN) return 1;
  if (a != INT_MIN && b != INT_MIN) return SelfDiv(a, b);
  if (b == INT_MIN) return 0;
  if (b == -1) return INT_MAX;

  // a == INT_MIN, b != INT_MIN and b != -1
  a = add(a, b > 0 ? b : neg(b));  // a = INT_MIN + |b|
  a = SelfDiv(a, b);
  int offset = b > 0 ? neg(1) : 1;
  return add(a, offset);
}

// ===== 对数器验证 =====
int main() {
  srand(time(0));
  const int TESTS = 100000;
  for (int t = 0; t < TESTS; ++t) {
    int a = rand() % 2000000001 - 1000000000;  // [-1e9, 1e9]
    int b = rand() % 2000000001 - 1000000000;
    if (b == 0) continue;  // skip division by zero

    // 避免 INT_MIN / -1 溢出（标准除法也 undefined，但 LeetCode 特殊处理）
    if (a == INT_MIN && b == -1) {
      if (divide(a, b) != INT_MAX) {
        cout << "FAIL at INT_MIN / -1" << endl;
        return 1;
      }
      continue;
    }

    // 测试加法
    if (add(a, b) != a + b) {
      cout << "Add failed: " << a << " + " << b << endl;
      return 1;
    }

    // 测试减法
    if (SelfMinus(a, b) != a - b) {
      cout << "Minus failed: " << a << " - " << b << endl;
      return 1;
    }

    // 测试乘法（注意溢出可能，但位运算乘法与标准乘法在溢出时行为一致）
    if (multiply(a, b) != a * b) {
      cout << "Multiply failed: " << a << " * " << b << endl;
      return 1;
    }

    // 测试除法（仅当 a,b 都不是 INT_MIN 时 SelfDiv 有效）
    if (a != INT_MIN && b != INT_MIN) {
      int expected = a / b;
      int actual = SelfDiv(a, b);
      if (actual != expected) {
        cout << "SelfDiv failed: " << a << " / " << b << " = " << actual
             << ", expected " << expected << endl;
        return 1;
      }
    }

    // 测试完整 divide（符合 LeetCode 规则）
    int expected_div = (a == INT_MIN && b == -1) ? INT_MAX : a / b;
    int actual_div = divide(a, b);
    if (actual_div != expected_div) {
      cout << "Divide failed: " << a << " / " << b << " = " << actual_div
           << ", expected " << expected_div << endl;
      return 1;
    }
  }
  cout << "All " << TESTS << " tests passed!" << endl;
  return 0;
}

来源	题目/题单	说明
洛谷	https://www.luogu.com.cn/training/450542	位运算（题单）
洛谷	https://www.luogu.com.cn/training/3071	位运算（题单）
洛谷	https://www.luogu.com.cn/training/406978	位运算（题单）
洛谷	https://www.luogu.com.cn/training/463970	位运算题单（题单）

算法讲解034【必备】链表高频题目和必备技巧

前置知识：讲解009~012-链表入门内容、讲解021-归并排序讲解026-哈希表的使用、讲解029-排序算法的稳定性

链表类题目注意点： 1，如果笔试中空间要求不严格，直接使用容器来解决链表问题 2，如果笔试中空间要求严格、或者在面试中面试官强调空间的优化，需要使用额外空间复杂度O(1)的方法 3，最常用的技巧-快慢指针 4，链表类题目往往都是很简单的算法问题，核心考察点也并不是算法设计，是coding能力 5，这一类问题除了多写多练没有别的应对方法

个人建议：链表类问题既然练的就是coding，那么不要采取空间上讨巧的方式来练习

注意：链表相关的比较难的问题是约瑟夫环问题，会在【扩展】阶段讲解，变形很多会单独出一期视频讲解

题目1 : 返回两个无环链表相交的第一个节点

题目2 : 每k个节点一组翻转链表

题目3 : 复制带随机指针的链表

题目4 : 判断链表是否是回文结构。这个题的流程设计甚至是考研常用。快慢指针找中点。

题目5 : 返回链表的第一个入环节点。快慢指针找中点。

题目6 : 在链表上排序。要求时间复杂度O(n * log n)，额外空间复杂度O(1)，还要求排序有稳定性。

注意：这些题目往往难度标为“简单”，是因为用容器解决真的很简单但是不用容器、实现额外空间复杂度O(1)的方法并不轻松，包括很多提交的答案也都没有符合要求

来源	题目/题单	说明
leetcode	160. 相交链表 - 力扣（LeetCode）	160. 相交链表
leetcode	25. K 个一组翻转链表 - 力扣（LeetCode）	25. K 个一组翻转链表
牛客	链表中的节点每k个一组翻转_牛客题霸_牛客网	链表中的节点每k个一组翻转
leetcode	138. 随机链表的复制 - 力扣（LeetCode）	138. 随机链表的复制
leetcode	234. 回文链表 - 力扣（LeetCode）	234. 回文链表
leetcode	142. 环形链表 II - 力扣（LeetCode）	142. 环形链表 II
leetcode	148. 排序链表 - 力扣（LeetCode）	148. 排序链表
牛客	单链表的排序_牛客题霸_牛客网	单链表的排序

2025.12.05 19:24

算法讲解035【必备】数据结构设计高频题

前置知识：
讲解007-动态数组和扩容分析、讲解009~012-链表入门内容
讲解025-堆结构、讲解026-哈希表、有序表、比较器的使用

注意：
本节以数据结构设计高频题为主，并不涉及太难的数据结构设计题目
数据结构设计的更难题目，需要学习更多数据结构之后才能解决，如前缀树、并查集、线段树等
后续会更新【必备】、【扩展】、【挺难】视频，包含大量基础和高级数据结构最好懂的原理详解
更多更难的算法、数据结构题目会在“好题解析”系列进行讲解，这个系列将在原理详解系列结束后开始

欢迎持续关注、转发


题目1 : setAll功能的哈希表
https://www.nowcoder.com/practice/7c4559f138e74ceb9ba57d76fd169967

题目2 : 实现LRU结构
https://leetcode.cn/problems/lru-cache/
https://www.nowcoder.com/practice/5dfded165916435d9defb053c63f1e84

题目3 : 插入、删除和获取随机元素O(1)时间的结构
https://leetcode.cn/problems/insert-delete-getrandom-o1/description/

题目4 : 插入、删除和获取随机元素O(1)时间且允许有重复数字的结构
https://leetcode.cn/problems/insert-delete-getrandom-o1-duplicates-allowed/


题目5 : 快速获得数据流的中位数的结构
https://leetcode.cn/problems/find-median-from-data-stream/
https://www.nowcoder.com/practice/9be0172896bd43948f8a32fb954e1be1

题目6 : 最大频率栈
https://leetcode.cn/problems/maximum-frequency-stack/description/

题目7 : 全O(1)的数据结构
https://leetcode.cn/problems/all-oone-data-structure/

2025.12.06 11:25

尚同

2025.12.08 16:04

二叉树高频题目-上-不含树型dp




前置知识：
讲解013-队列用数组实现、讲解017~018-二叉树入门内容

特别说明：
这一期和下一期视频，会讲解二叉树高频题目，但是不含树型dp的题目
树型dp问题，会放在【必备】课程的动态规划大章节部分讲述
树型dp中的换根dp问题，会放在【扩展】课程的动态规划大章节部分讲述
AVL树的实现，树的左旋、右旋，这些内容也会在【扩展】课程里讲述


题目1 : 二叉树的层序遍历
https://leetcode.cn/problems/binary-tree-level-order-traversal/description/
https://www.nowcoder.com/practice/04a5560e43e24e9db4595865dc9c63a3


题目2 : 二叉树的锯齿形层序遍历
https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/
https://www.nowcoder.com/practice/91b69814117f4e8097390d107d2efbe0

题目3 : 二叉树的最大特殊宽度
https://leetcode.cn/problems/maximum-width-of-binary-tree/description/

题目4 : 求二叉树的最大深度、求二叉树的最小深度
https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/
https://leetcode.cn/problems/minimum-depth-of-binary-tree/description/
https://www.nowcoder.com/practice/8a2b2bf6c19b4f23a9bdb9b233eefa73
https://www.nowcoder.com/practice/e08819cfdeb34985a8de9c4e6562e724


题目5 : 二叉树先序序列化和反序列化
题目6 : 二叉树按层序列化和反序列化
https://leetcode.cn/problems/serialize-and-deserialize-binary-tree
https://www.nowcoder.com/practice/cf7e25aa97c04cc1a68c8f040e71fb84


题目7 : 利用先序与中序遍历序列构造二叉树
https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/

题目8 : 验证完全二叉树
https://leetcode.cn/problems/check-completeness-of-a-binary-tree

题目9 : 求完全二叉树的节点个数，要求时间复杂度低于O(n)
https://leetcode.cn/problems/count-complete-tree-nodes/
https://www.nowcoder.com/practice/512688d2ecf54414826f52df4e4b5693


注意：中序遍历无法完成二叉树的序列化和反序列化，代码中给出了说明。后序遍历可以但不再详述。

2025.12.09 16:08

二叉树高频题目-下-不含树型dp

前置知识：
讲解013-队列用数组实现、讲解017~018-二叉树入门内容

特别说明：
这一期和上一期视频，会讲解二叉树高频题目，但是不含树型dp的题目
树型dp问题，会放在【必备】课程的动态规划大章节部分讲述
树型dp中的换根dp问题，会放在【扩展】课程的动态规划大章节部分讲述
AVL树的实现，树的左旋、右旋，这些内容也会在【扩展】课程里讲述


题目1 : 普通二叉树上寻找两个节点的最近公共祖先
https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/

题目2 : 搜索二叉树上寻找两个节点的最近公共祖先
https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/description/

题目3 : 收集累加和等于aim的所有路径(递归恢复现场)
https://leetcode.cn/problems/path-sum-ii/description/

题目4 : 验证平衡二叉树(树型dp沾边)
https://leetcode.cn/problems/balanced-binary-tree/description/

题目5 : 验证搜索二叉树(树型dp沾边)
https://leetcode.cn/problems/validate-binary-search-tree/description/

题目6 : 修剪搜索二叉树


题目7 : 二叉树打家劫舍问题(树型dp沾边)

注意 : 问题1又叫lca问题，非常重要的问题！
      Tarjan算法解决lca的批量查询、树链剖分算法解决lca的在线查询，会在【扩展】课程讲述
注意 : 数组的打家劫舍问题变形很多，会在【必备】课程的动态规划大章节部分讲述
注意 : 再次强调树型dp的整体讲解，会在【必备】课程的动态规划大章节部分讲述

2025.12.10 15:53

算法讲解038【必备】常见经典递归过程解析

前置知识：
讲解017、020、021、023、036、037
这些章节都分析过递归，不熟悉的同学可以先熟悉一下

带路径的递归 vs 不带路径的递归(大部分dp，状态压缩dp认为是路径简化了结构，dp专题后续讲述)
任何递归都是dfs且非常灵活。回溯这个术语并不重要。

题目1 : 返回字符串全部子序列，子序列要求去重。时间复杂度O(2^n * n)
https://www.nowcoder.com/practice/92e6247998294f2c933906fdedbc6e6a

题目2 : 返回数组的所有组合，可以无视元素顺序。时间复杂度O(2^n * n)
https://leetcode.cn/problems/subsets-ii/description/

题目3 : 返回没有重复值数组的全部排列。时间复杂度O(n! * n)
https://leetcode.cn/problems/permutations/

题目4 : 返回可能有重复值数组的全部排列，排列要求去重。时间复杂度O(n! * n)
https://leetcode.cn/problems/permutations-ii/description/


题目5 : 用递归逆序一个栈。时间复杂度O(n^2)


题目6 : 用递归排序一个栈。时间复杂度O(n^2)


题目7 : 打印n层汉诺塔问题的最优移动轨迹。时间复杂度O(2^n)
https://www.nowcoder.com/practice/7d6cab7d435048c4b05251bf44e9f185

2025.12.11 16:13

尚同

2025.12.15 18:15

算法讲解039【必备】嵌套类问题的递归解题套路

前置知识：
讲解017、020、021、023、036、037、038
这些章节都分析过递归，尤其讲解038，不熟悉的同学可以先熟悉一下

嵌套类问题的解题套路
大概过程: 
定义全局变量 int where
递归函数f(i) : s[i..]，从i位置出发开始解析，遇到 字符串终止 或 嵌套条件终止 就返回
返回值是f(i)负责这一段的结果
f(i)在返回前更新全局变量where，让上级函数通过where知道解析到了什么位置，进而继续

执行细节:
如果f(i)遇到 嵌套条件开始，就调用下级递归去处理嵌套，下级会负责嵌套部分的计算结果
f(i)下级处理完成后，f(i)可以根据下级更新的全局变量where，知道该从什么位置继续解析


实战一下

题目1 : 含有嵌套的表达式求值。时间复杂度O(n)
https://www.nowcoder.com/practice/c215ba61c8b1443b996351df929dc4d4

题目2 : 含有嵌套的字符串解码。时间复杂度O(n)
https://leetcode.cn/problems/decode-string/

题目3 : 含有嵌套的分子式求原子数量。时间复杂度O(n)
https://leetcode.cn/problems/number-of-atoms/

算法讲解040【必备】N皇后问题-重点是位运算的版本

https://www.nowcoder.com/practice/c76408782512486d91eea181107293b6

https://www.nowcoder.com/practice/c77ac599d0764433a5946610a7626768

https://leetcode.cn/problems/n-queens-ii/description/

前置知识
递归相关 : 讲解038
位运算相关 : 讲解003、030、031、032、033

解决N皇后问题的时间复杂度是O(n!)，好的方法可以大量剪枝，大量优化常数时间

用数组表示路径的方法（经典、常数时间慢，不推荐）
记录之前每一行的皇后放在了什么列
来到第i行的时候，可以根据0..i-1行皇后的位置，判断能放哪些列
把能放的列都尝试一遍，每次尝试修改路径数组表示当前的决策，后续返回的答案都累加返回

用位运算的方法（巧妙、常数时间快，推荐）
int col   : 0..i-1行皇后放置的位置因为正下方向延伸的原因，哪些列不能再放皇后
int left  : 0..i-1行皇后放置的位置因为左下方向延伸的原因，哪些列不能再放皇后
int right : 0..i-1行皇后放置的位置因为右下方向延伸的原因，哪些列不能再放皇后
根据col、left、right，用位运算快速判断能放哪些列
把能放的列都尝试一遍，每次尝试修改3个数字表示当前的决策，后续返回的答案都累加返回

代码实现：

c++

/**
 * N 皇后问题的位运算优化解法（回溯 + 位压缩）
 *
 * 本程序使用位运算高效地求解 N 皇后问题的所有合法摆放方案。
 * 对于输入的 n（棋盘大小），输出每一行皇后所在的列号（从 1 开始）。
 * 特别地：当 n = 2 或 n = 3 时，无解，直接输出 -1。
 *
 * 算法核心思想：
 *   - 使用三个整数 col、left、right 分别表示当前行中：
 *       col:   已被占据的列（纵向冲突）
 *       left:  左对角线（从左上到右下）的冲突位置
 *       right: 右对角线（从右上到左下）的冲突位置
 *   - 每次递归处理一行，通过位运算快速找出当前行可放置的位置。
 *   - 利用 lowbit 技巧（x & -x）逐个枚举可行位置。
 *
 * 时间复杂度：O(N!)，但由于位运算剪枝，实际运行非常快。
 * 空间复杂度：O(N)，仅用于存储当前路径。
 */

#include <iostream>
#include <cstdio>  // 使用 printf/scanf 更高效（尤其在大量输出时）
using namespace std;

// 类型别名：UI 表示无符号整数（通常为 32 位）
typedef unsigned int UI;

// 最大支持的皇后数量（受限于 unsigned int 的位宽，最多 32）
const UI N = 15;
UI nums[N];    // 记录当前已放置皇后的列位置（从 1 开始编号）
UI sz = 0;     // 当前已放置的皇后数量（即当前递归深度）
UI n;          // 棋盘大小（输入）

/**
 * ctz_mask(x): 返回 x 的最低位 1 所在的位置（从 0 开始计数）
 * 例如：x = 0b1000 → 返回 3；x = 0b10100 → 返回 2
 * 若 x == 0，则返回 32（表示无效）
 */
UI ctz_mask(UI x) {
    for (UI i = 0; i < 32; i++) {
        if (x & (1U << i)) {
            return i;
        }
    }
    return 32;  // x == 0 时无有效位
}

/**
 * dfs(limits, col, left, right)
 * 
 * 参数说明：
 *   - limits: 一个掩码，低 n 位为 1，其余为 0，用于限制只在 [0, n-1] 列操作
 *   - col:    当前列已被占用的位置（按位表示）
 *   - left:   左对角线（\）方向的冲突位（每深入一行需右移一位）
 *   - right:  右对角线（/）方向的冲突位（每深入一行需左移一位）
 *
 * 算法流程：
 *   1. 如果已放置 n 个皇后（sz == n），输出当前解。
 *   2. 合并所有冲突位：col | left | right
 *   3. 取反并与 limits 相与，得到当前行可选位置 candidates。
 *   4. 用 lowbit 技巧（candidates & -candidates）逐个取出可选位置。
 *   5. 递归尝试每个位置，并更新状态。
 */
void dfs(UI limits, UI col, UI left, UI right) {
    // 终止条件：已成功放置 n 个皇后
    if (sz == n) {
        for (UI i = 0; i < sz; i++) {
            printf("%u ", nums[i]);  // 输出列号（从 1 开始）
            if (i == sz - 1) {
                printf("\n");
            }
        }
        return;
    }

    // 计算当前行不能放皇后的位置（冲突位）
    UI ban = limits & (col | left | right);
    // 可选位置 = 所有列 - 冲突列
    UI candidates = limits & (~ban);

    UI place = 0;
    // 枚举所有可选位置（利用 lowbit 技巧）
    while (candidates) {
        place = candidates & (-candidates);  // 取出最低位的 1（即一个可选列）
        // 记录该列（转换为 1-based 编号）
        nums[sz++] = ctz_mask(place) + 1;

        // 更新状态并递归下一行：
        // - col | place：标记该列为已占用
        // - (left | place) >> 1：左对角线下一行的冲突位（右移）
        // - (right | place) << 1：右对角线下一行的冲突位（左移）
        dfs(limits, col | place, (left | place) >> 1, (right | place) << 1);

        // 回溯：恢复状态
        sz--;
        candidates ^= place;  // 清除已处理的位置
    }
}

/**
 * 主函数：
 *   - 读入 n
 *   - 特判 n=2 或 n=3（无解）
 *   - 初始化 limits = (1 << n) - 1（低 n 位为 1）
 *   - 启动 DFS 搜索
 */
int main() {
    scanf("%u", &n);

    // N=2 和 N=3 时无解（数学上已证明）
    if (n == 2 || n == 3) {
        printf("-1\n");
        return 0;
    }

    // 构造掩码：只有低 n 位有效（例如 n=4 → limits = 0b1111 = 15）
    UI limits = (1U << n) - 1;

    // 从第 0 行开始搜索，初始无任何冲突
    dfs(limits, 0, 0, 0);

    return 0;
}

2025.12.16 12:59

尚同

算法讲解041【必备】最大公约数、同余原理


前置知识 : 无

求最大公约数
1) 欧几里得算法的过程 : 辗转相除法
2) 正确性的证明过程见代码注释部分，我润色的证明过程非常好懂，不过直接记忆过程即可
3) 求gcd(a,b)，其中a>b，时间复杂度为O((log a)的3次方)，时间复杂度证明略，这个复杂度足够好了
4) 简单转化就可以求最小公倍数
5) 更高效求最大公约数的Stein算法、由最大公约数扩展出的“裴蜀定理”，比赛同学有兴趣可以继续研究
6) 不比赛的同学，哪怕你的目标是最顶级的公司应聘、还是考研，掌握这个只有一行的函数已经足够！

同余原理
1) 介绍背景
2) 加法、乘法每一步计算完后直接取模，减法则为(a-b+m)%m
3) 要确保过程中不溢出，所以往往乘法运算的用long类型做中间变量
4) 除法的同余需要求逆元，会在【必备】课程里讲述，较难的题目才会涉及



求最大公约数相关的经典题目
一个正整数如果能被 a 或 b 整除，那么它是神奇的。
给定三个整数 n , a , b ，返回第 n 个神奇的数字。
因为答案可能很大，所以返回答案 对 10^9 + 7 取模 后的值。
注意：
本题用到“二分答案法”和“容斥原理”两个重要的算法，不过用的非常浅，之前没有接触过也能理解
“二分答案法”非常巧妙可以解决很多问题，整套内容会在后续的【必备】课程里做成专题视频讲述
“容斥原理”可以考的非常难，也会在后续的【扩展】课程里做成专题视频讲述

同余原理的测试
代码中用对数器进行了验证
你也可以设计实验用对数器随意验证

题目：

878. 第 N 个神奇数字 - 力扣（LeetCode）

2025.12.17 15:33

尚同

算法讲解042【必备】对数器打表找规律的技巧

前置知识 : 会基本递归即可，推荐去看讲解038-常见经典递归过程解析


对数器打表找规律的使用场景 : 输入参数是简单类型，返回值也是简单类型


对数器打表找规律的过程
1) 可以用最暴力的实现求入参不大情况下的答案，往往只需要最基本的递归能力
2) 打印入参不大情况下的答案，然后观察规律
3) 把规律变成代码，就是最优解了


题目1 : 使用规格8和规格6的袋子买苹果问题

题目2 : A和B轮流吃草最终谁会赢

题目3 : 判断一个数字是否是若干数量(数量>1)的连续正整数的和

题目4 : 要求只有一个长度>=2的回文子串，求所有长度为n的red字符串中好串的数量

算法讲解043【必备】根据数据量猜解法的技巧-天字第一号重要技巧

前置知识 : 讲解007-时间复杂度、讲解038-全排列递归代码的执行细节

一个基本事实
C/C++运行时间1s，java/python/go等其他语言运行时间1s~2s，
对应的常数指令操作量是 10^7 ~ 10^8，不管什么测试平台，不管什么cpu，都是这个数量级
所以可以根据这个基本事实，来猜测自己设计的算法最终有没有可能在规定时间内通过

运用 根据数据量猜解法技巧 的必要条件：
1，题目要给定各个入参的范围最大值，正式笔试、比赛的题目一定都会给，面试中要和面试官确认
2，对于自己设计的算法，时间复杂度要有准确的估计

这个技巧太重要了！既可以提前获知自己的方法能不能通过，也可以对题目的分析有引导作用！


问题规模和可用算法
                 logn      n      n*logn      n*根号n      n^2      2^n      n!
   
n <= 11          Yes      Yes      Yes         Yes        Yes      Yes      Yes
n <= 25          Yes      Yes      Yes         Yes        Yes      Yes      No
n <= 5000        Yes      Yes      Yes         Yes        Yes      No       No
n <= 10^5        Yes      Yes      Yes         Yes        No       No       No
n <= 10^6        Yes      Yes      Yes         No         No       No       No
n <= 10^7        Yes      Yes      No          No         No       No       No
n >= 10^8        Yes      No       No          No         No       No       No

上面每个复杂度，课上都讲过类似的过程了。
除了 n*根号n，这个复杂度常出现在“莫队算法”能解决的相关题目里，后续的【挺难】课程会有系统讲述
这张表其实作用有限
因为时间复杂度的估计很多时候并不是一个入参决定，可能是多个入参共同决定。比如O(n*m), O(n+m)等
所以最关键的就是记住常数指令操作量是 10^7 ~ 10^8，然后方法是什么复杂度就可以估计能否通过了

题目1 : 最优的技能释放顺序

现在有一个打怪类型的游戏，这个游戏是这样的，你有n个技能
每一个技能会有一个伤害，
同时若怪物小于等于一定的血量，则该技能可能造成双倍伤害
每一个技能最多只能释放一次，已知怪物有m点血量
现在想问你最少用几个技能能消灭掉他(血量小于等于0)
技能的数量是n，怪物的血量是m
i号技能的伤害是x[i]，i号技能触发双倍伤害的血量最小值是y[i]
1 <= n <= 10
1 <= m、x[i]、y[i] <= 10^6

题目：
https://www.nowcoder.com/practice/d88ef50f8dab4850be8cd4b95514bbbd


题目2 : 超级回文数的数目

如果一个正整数自身是回文数，而且它也是一个回文数的平方，那么我们称这个数为超级回文数。
现在，给定两个正整数 L 和 R （以字符串形式表示），
返回包含在范围 [L, R] 中的超级回文数的数目。
1 <= len(L) <= 18
1 <= len(R) <= 18
L 和 R 是表示 [1, 10^18) 范围的整数的字符串

题目：
https://leetcode.cn/problems/super-palindromes/description/

2025.12.18 19:25

尚同

2025.12.29 20:00 | 2026.1.4 17:01

算法讲解044【必备】前缀树原理和代码详解

前置知识 : 知道什么是树结构，比如二叉树。讲解008-数据结构分类，讲解017-二叉树基本概念知道为什么推荐静态数组的方式实现各种结构。讲解019-处理输入和输出-推荐静态空间的实现知道哈希表怎么用。讲解026-哈希表的使用

前缀树又叫字典树，英文名trie：每个样本都从头节点开始根据前缀字符或者前缀数字建出来的一棵大树，就是前缀树没有路就新建节点；已经有路了，就复用节点

前缀树的使用场景：需要根据前缀信息来查询的场景
前缀树的优点：根据前缀信息选择树上的分支，可以节省大量的时间
前缀树的缺点：比较浪费空间，和总字符数量有关，字符的种类有关
前缀树的定制：pass、end等信息

这节课是前缀树的原理和代码讲解。下节课是前缀树相关题目讲解，展示前缀树在解题时的常见用法。

实现前缀树 Trie 类：

Trie() 初始化前缀树对象。
void insert(String word) 将字符串 word 插入前缀树中。
int search(String word) 返回前缀树中字符串 word 的实例个数。
int prefixNumber(String prefix) 返回前缀树中以 prefix 为前缀的字符串个数
void delete(String word) 从前缀树中移除字符串 word 。

分别用类描述的方式、静态数组的方式实现

前缀树的实现方式：

1）类描述的实现方式（动态结构）。不推荐！虽然最常用。

路的可能性范围较小，用固定数组实现路
路的可能性范围较大，用哈希表实现路

2）静态数组的实现方式。推荐！不仅笔试，就连比赛也能保证使用。

  1. 一切都是静态数组来实现，提交准备好够用的空间
  2. 如果路的可能性范围较大，就用每一位的信息建树。下节课前缀树的题目里展示

类描述实现（C++智能指针实现）：

c++

#include <array>
#include <memory>
#include <string>
using namespace std;
class Trie {
 private:
  struct TrieNode {
    // pass 表示经过该节点的单词数量
    // end 表示以该节点结尾的单词数量
    int pass = 0;
    int end = 0;
    // nexts 存储指向子节点的指针
    array<unique_ptr<TrieNode>, 26> nexts;
  };
  unique_ptr<TrieNode> root;

 public:
  Trie() : root(make_unique<TrieNode>()) {}

  // 插入单词
  void insert(const string& word) {
    TrieNode* node = root.get();
    node->pass++;
    for (char c : word) {
      int idx = c - 'a';
      if (!node->nexts[idx]) { node->nexts[idx] = make_unique<TrieNode>(); }
      node = node->nexts[idx].get();
      node->pass++;
    }
    node->end++;
  }

  // 删除单词（如果存在）
  void erase(const string& word) {
    if (countWordsEqualTo(word) == 0) { return; }
    TrieNode* node = root.get();
    node->pass--;
    for (char c : word) {
      int idx = c - 'a';
      TrieNode* next = node->nexts[idx].get();
      if (--next->pass == 0) {
        node->nexts[idx].reset();  // 自动释放整棵子树
        return;
      }
      node = next;
    }
    node->end--;
  }

  // 查询单词出现次数
  int countWordsEqualTo(const string& word) const {
    const TrieNode* node = root.get();
    for (char c : word) {
      int idx = c - 'a';
      if (!node->nexts[idx]) { return 0; }
      node = node->nexts[idx].get();
    }
    return node->end;
  }

  // 查询以 pre 为前缀的单词数量
  int countWordsStartingWith(const string& pre) const {
    const TrieNode* node = root.get();
    for (char c : pre) {
      int idx = c - 'a';
      if (!node->nexts[idx]) { return 0; }
      node = node->nexts[idx].get();
    }
    return node->pass;
  }
};

静态数组实现：

c++

#include <cstring>
#include <iostream>
using namespace std;
const int N = 1e6 + 5;
// Trie 数组实现
// son[u][c] 表示节点 u 的子节点中，字符 c 所指向的节点编号
int son[N][26];
// ps 表示经过节点 i 的单词数量
// ed 表示以节点 i 结尾的单词数量
int ps[N], ed[N], idx = 1;

// 插入单词
void insert(const string& word) {
  int cur = 1;
  ps[cur]++;
  for (int i = 0; i < word.size(); i++) {
    int path = word[i] - 'a';
    if (!son[cur][path]) { son[cur][path] = ++idx; }
    cur = son[cur][path];
    ps[cur]++;
  }
  ed[cur]++;
}

// 查询单词出现次数
int countWordsEqualTo(const string& word) {
  int cur = 1;
  for (int i = 0; i < word.size(); i++) {
    int path = word[i] - 'a';
    if (!son[cur][path]) { return false; }
    cur = son[cur][path];
  }
  return ed[cur];
}

// 查询以 pre 为前缀的单词数量
int countWordsStartingWith(const string& word) {
  int cur = 1;
  for (int i = 0; i < word.size(); i++) {
    int path = word[i] - 'a';
    if (!son[cur][path]) { return 0; }
    cur = son[cur][path];
  }
  return ps[cur];
}

// 删除单词（如果存在）
void remove(const string& word) {
  if (countWordsEqualTo(word) > 0) {
    int cur = 1;
    ps[cur]--;
    for (int i = 0; i < word.size(); i++) {
      int path = word[i] - 'a';
      if (--ps[son[cur][path]] == 0) {
        son[cur][path] = 0;
        return;
      }
      cur = son[cur][path];
    }
    ed[cur]--;
  }
}

void reset() {
  memset(ps, 0, sizeof ps);
  memset(ed, 0, sizeof ed);
  memset(son, 0, sizeof son);
  idx = 1;
}
int main() {
  int m, op;
  string word;
  while (scanf("%d", &m) != EOF) {
    reset();
    while (m--) {
      scanf("%d", &op);
      cin >> word;
      switch (op) {
        case 1:
          insert(word);
          break;
        case 2:
          remove(word);
          break;
        case 3:
          if (countWordsEqualTo(word)) {
            printf("YES\n");
          } else {
            printf("NO\n");
          }
          break;
        case 4:
          printf("%d\n", countWordsStartingWith(word));
          break;
      }
    }
  }

  return 0;
}

题目：
https://www.nowcoder.com/practice/7f8a8553ddbf4eaab749ec988726702b
https://leetcode.cn/problems/implement-trie-prefix-tree/description/

前缀树将节点存放在边上，不是点上

算法讲解045【必备】前缀树的相关题目

前置知识 : 讲解044-前缀树原理和代码详解-静态空间的方式实现

题目1
https://www.nowcoder.com/practice/c552d3b4dfda49ccb883a6371d9a6932
接头密匙
牛牛和他的朋友们约定了一套接头密匙系统，用于确认彼此身份
密匙由一组数字序列表示，两个密匙被认为是一致的，如果满足以下条件：
密匙 b 的长度不超过密匙 a 的长度。
对于任意 0 <= i < length(b)，有b[i+1] - b[i] == a[i+1] - a[i]
现在给定了m个密匙 b 的数组，以及n个密匙 a 的数组
请你返回一个长度为 m 的结果数组 ans，表示每个密匙b都有多少一致的密匙
数组 a 和数组 b 中的元素个数均不超过 10^5
1 <= m, n <= 1000

用前缀树方法：
时间复杂度，O(a数组的数字个数 * 10) + O(b数组的数字个数 * 10)
空间复杂度，O(a数组的数字个数 * 10)，这是树上的节点数量





前置知识 : 讲解030-异或运算的骚操作、讲解044-前缀树原理和代码详解

题目2
https://leetcode.cn/problems/maximum-xor-of-two-numbers-in-an-array/description/
数组中两个数的最大异或值
给你一个整数数组 nums ，返回 nums[i] XOR nums[j] 的最大运算结果，其中 0<=i<=j<=n
1 <= nums.length <= 2 * 10^5
0 <= nums[i] <= 2^31 - 1


前缀树做法 & 哈希表做法
时间复杂度O(n * logV)，空间复杂度O(n * logV)，V是数值范围





前置知识 : 讲解038-常见经典递归过程解析、讲解044-前缀树原理和代码详解

题目3
https://leetcode.cn/problems/word-search-ii/description/
在二维字符数组中搜索可能的单词
给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words
返回所有二维网格上的单词。单词必须按照字母顺序，通过 相邻的单元格 内的字母构成
其中“相邻”单元格是那些水平相邻或垂直相邻的单元格
同一个单元格内的字母在一个单词中不允许被重复使用
1 <= m, n <= 12
1 <= words.length <= 3 * 10^4
1 <= words[i].length <= 10

时间复杂度，O(m * n * 4^10)
不管用不用前缀树都是这个复杂度，只不过前缀树可以大量剪枝，优化常数时间
空间复杂度，O(words中所有字符串的全部字符数量)

2026.1.5 13:37

尚同

算法讲解046【必备】构建前缀信息的技巧-解决子数组相关问题

前置知识 : 讲解026-哈希表的用法

解决如下问题，时间复杂度O(n)
题目1 : 构建 前缀和数组。快速解决子数组范围求和的问题
(https://leetcode.cn/problems/range-sum-query-immutable/)
题目2 : 构建 前缀和 最早出现的位置。返回 无序数组中 累加和为给定值的 最长子数组长度
(
https://www.nowcoder.com/practice/36fb0fd3c656480c92b569258a1223d5
https://www.nowcoder.com/practice/704c8388a82e42e58b7f5751ec943a11
)
题目3 : 构建 前缀和 出现的次数。返回 无序数组中 累加和为给定值的 子数组数
(https://leetcode.cn/problems/subarray-sum-equals-k/description/)
题目4 : 构建 前缀和 最早出现的位置。返回 无序数组中 正数和负数个数相等的 最长子数组长度
(https://www.nowcoder.com/practice/545544c060804eceaed0bb84fcd992fb)
题目5 : 构建 前缀和 最早出现的位置。表现良好的最长时间段问题
(https://leetcode.cn/problems/longest-well-performing-interval/)
题目6 : 构建 前缀和余数 最晚出现的位置。移除的最短子数组长度，使得剩余元素的累加和能被p整除
(https://leetcode.cn/problems/make-sum-divisible-by-p/description/)
题目7 : 构建 前缀奇偶状态 最早出现的位置。每个元音包含偶数次的 最长子串长度
(https://leetcode.cn/problems/find-the-longest-substring-containing-vowels-in-even-counts/)

构建某个前缀信息 最早出现、最晚出现、出现次数等，是很常见的技巧
除此之外，还有很多种类的前缀信息可以构建出来，解决很多子数组相关问题
更多题目会在 题目系列 里见到，欢迎持续关注、转发，下节见！

2026.1.6 11:46

算法讲解047【必备】一维差分与等差数列差分

前置知识 : 无，知道什么是数组就行

一维差分：太简单了，没有理解难度。不支持边操作、边查询。

等差数列差分问题描述：
一开始1~n范围上的数字都是0。接下来一共有m个操作。
每次操作：l~r范围上依次加上首项s、末项e、公差d的数列
最终1~n范围上的每个数字都要正确得到

等差数列差分的过程：
每个操作调用set方法
所有操作完成后在arr上生成两遍前缀和，即调用build方法
arr里就是最终1~n范围上的每个数字

注意：
等差数列差分在大厂笔试、面试中还不常见，是比赛必备技巧，但预计会流行
二维差分会在后续的【必备】课程里进一步讲述，支持边操作、边查询的结构会在【扩展】课程讲述

题目1
航班预订统计
这里有 n 个航班，它们分别从 1 到 n 进行编号。
有一份航班预订表 bookings ，
表中第 i 条预订记录 bookings[i] = [firsti, lasti, seatsi]
意味着在从 firsti 到 lasti 
包含 firsti 和 lasti ）的 每个航班 上预订了 seatsi 个座位。
请你返回一个长度为 n 的数组 answer，里面的元素是每个航班预定的座位总数。
(https://leetcode.cn/problems/corporate-flight-bookings/)


题目2
等差数列差分模版
一开始1~n范围上的数字都是0，一共有m个操作，每次操作为(l,r,s,e,d)
表示在l~r范围上依次加上首项为s、末项为e、公差为d的数列
M个操作做完之后，统计1~n范围上所有数字的最大值和异或和
1 <= n <= 10^7
1 <= m <= 3 * 10^5
1 <= l <= r <= n
(https://www.luogu.com.cn/problem/P4231)


题目3
等差数列差分经典题目
一群人落水后求每个位置的水位高度
问题描述比较复杂，见测试链接
测试链接 : https://www.luogu.com.cn/problem/P5026

注意：这道题OFFSET的设计，可以避免大量的边界讨论

等差数列差分模板：

c++

/*
一开始1~n范围上的数字都是0。接下来一共有m个操作。
每次操作：l~r范围上依次加上首项s、末项e、公差d的数列
最终1~n范围上的每个数字都要正确得到
*/

void set(int l, int r, int s, int e, int d) {
    arr[l] += s;
    arr[l + 1] += d - s;
    arr[r + 1] -= d + e;
    arr[r + 2] += e;
}
void build() {
    for (int i = 1; i <= n; i++) {
        arr[i] += arr[i - 1];
    }
    for (int i = 1; i <= n; i++) {
        arr[i] += arr[i - 1];
    }
}

算法讲解048【必备】二维前缀和、二维差分、离散化技巧

前置知识 : 讲解047-关于一维差分的内容

二维前缀和的原理、代码实现、相关题目

二维差分的原理、代码实现、相关题目

离散化技巧，用具体题目来说明

注意:
支持实时单点修改 + 实时查询的结构是二维树状数组，会在【扩展】课程里讲述

知识点：

二维前缀和

目的是预处理出一个结构，以后每次查询二维数组任何范围上的累加和都是O(1)的操作
1 根据原始状况，生成二维前缀和数组sum，
   sum[i][j]: 代表左上角(0,0)到右下角(i,j)这个范围的累加和
   sum[i][j] += sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1];
2 查询左上角(a,b)到右下角(c,d)这个范围的累加和
   sum[c][d] - sum[c][b-1] - sum[a-1][d] + sum[a-1][b-1];
3 实际过程中往往补第0行、第0列来减少很多条件判断。
  当然也可以不补。根据个人习惯决定。

二维差分

在二维数组中，如果经历如下的过程
1 批量的做如下的操作，每个操作都有独立的a、b、c、d、v
void add(a, b, c, d, v) : 左上角(a,b)到右下角(c,d)范围上，每个数字+v，怎么快速处理？
2 操作做完后，如何正确得到二维数组中每个位置的值？

这就是二维差分的主要工作，add时候快速处理，最后build得到每个位置的值，修改操作必须集中在一起，不能边修改边查询。
1）add方法实现，比较巧妙！
2）build方法实现，和处理前缀和类似
3）真实数据用一圈0包裹起来，可以减少很多边界讨论

c++

void add(int a, int b, int c, int d, int v) {
  diff[a][b] += v;
  diff[c + 1][b] -= v;
  diff[a][d + 1] -= v;
  diff[c + 1][d + 1] += v;
}

void build() {
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1];
    }
  }
}

题目：

题目1
二维前缀和模版
https://leetcode.cn/problems/range-sum-query-2d-immutable/

题目2
边框为1的最大正方形
给你一个由若干 0 和 1 组成的二维网格 grid
请你找出边界全部由 1 组成的最大 正方形 子网格
并返回该子网格中的元素数量。如果不存在，则返回 0。
测试链接 : https://leetcode.cn/problems/largest-1-bordered-square/


题目3
二维差分模版
https://www.nowcoder.com/practice/50e1a93989df42efb0b1dec386fb4ccc
https://www.luogu.com.cn/problem/P3397


题目4
用邮票贴满网格图
给你一个 m * n 的二进制矩阵 grid
每个格子要么为 0 （空）要么为 1 （被占据）
给你邮票的尺寸为 stampHeight * stampWidth
我们想将邮票贴进二进制矩阵中，且满足以下 限制 和 要求 ：
覆盖所有空格子，不覆盖任何被占据的格子
可以放入任意数目的邮票，邮票可以相互有重叠部分
邮票不允许旋转，邮票必须完全在矩阵内
如果在满足上述要求的前提下，可以放入邮票，请返回 true ，否则返回 false
测试链接 : https://leetcode.cn/problems/stamping-the-grid/




题目5
重要！包含离散化技巧！
最强祝福力场
小扣在探索丛林的过程中，无意间发现了传说中"落寞的黄金之都"
而在这片建筑废墟的地带中，小扣使用探测仪监测到了存在某种带有「祝福」效果的力场
经过不断的勘测记录，小扣将所有力场的分布都记录了下来
forceField[i] = [x,y,side] 
表示第 i 片力场将覆盖以坐标 (x,y) 为中心，边长为 side 的正方形区域。
若任意一点的 力场强度 等于覆盖该点的力场数量
请求出在这片地带中 力场强度 最强处的 力场强度
注意：力场范围的边缘同样被力场覆盖。
测试链接 : https://leetcode.cn/problems/xepqZ5/

在线Debug 时间限制（2s）

https://www.acwing.com/problem/content/4903/

https://github.com/SeanWong17/Image-Deduplicator

左神学习笔记1 ​

2025.11.22 - 2025.11.24 ​

位运算 ​

对数器 ​

二分搜索 ​

时间复杂度 ​

算法和数据结构简介 ​

2025.11.25 ​

015 最小栈 ​

016 双端队列 ​

2025.11.26 ​

算法讲解017【入门】二叉树及其三种序的递归实现 ​

算法讲解018【入门】二叉树遍历的非递归实现和复杂度分析 ​

用一个栈实现二叉树后序遍历 ​

算法讲解019【必备】算法笔试中处理输入和输出 ​

算法讲解020【必备】递归和master公式 ​

算法讲解021【必备】归并排序 ​

2025.11.27 16:26 ​

算法讲解022【必备】归并分治 ​

算法讲解023【必备】随机快速排序 ​

2025.11.28 17:09 ​

算法讲解024【必备】随机选择算法 ​

2025.11.29 11:12 ​

算法讲解025【必备】堆结构和堆排序 ​

算法讲解026【必备】哈希表、有序表和比较器的用法 ​

2025.11.30 10:50 ​

算法讲解027【必备】堆结构常见题 ​

算法讲解028【必备】基数排序 ​

基数排序（Radix Sort）详解 ​

一、基本思想 ​

二、算法流程 ​

三、C++ 实现（含详细注释） ​

四、关键点解析 ​

五、优缺点总结 ​

六、应用场景 ​

算法讲解029【必备】重要排序算法的总结 ​

1、排序算法的稳定性 ​

2、主流排序算法对比表 ​

3、理论边界与补充说明 ​

4、实际应用选型建议 ​

5、总结 ​

2025.12.01 22:35 ​

2025.12.02 10:44 ​

算法讲解030【必备】异或运算的骚操作 ​

算法讲解031【必备】位运算的骚操作 ​

2025.12.03 21:12 ​

2025.12.04 10:54 ​

算法讲解032【必备】位图 ​

算法讲解033【必备】位运算实现加减乘除 ​

算法讲解034【必备】链表高频题目和必备技巧 ​

2025.12.05 19:24 ​

算法讲解035【必备】数据结构设计高频题 ​

2025.12.06 11:25 ​

2025.12.08 16:04 ​

二叉树高频题目-上-不含树型dp ​

2025.12.09 16:08 ​

二叉树高频题目-下-不含树型dp ​

2025.12.10 15:53 ​

算法讲解038【必备】常见经典递归过程解析 ​

2025.12.11 16:13 ​

2025.12.15 18:15 ​

算法讲解039【必备】嵌套类问题的递归解题套路 ​

算法讲解040【必备】N皇后问题-重点是位运算的版本 ​

2025.12.16 12:59 ​

算法讲解041【必备】最大公约数、同余原理 ​

2025.12.17 15:33 ​

算法讲解042【必备】对数器打表找规律的技巧 ​

算法讲解043【必备】根据数据量猜解法的技巧-天字第一号重要技巧 ​

2025.12.18 19:25 ​

2025.12.29 20:00 | 2026.1.4 17:01 ​

算法讲解044【必备】前缀树原理和代码详解 ​

算法讲解045【必备】前缀树的相关题目 ​

2026.1.5 13:37 ​

算法讲解046【必备】构建前缀信息的技巧-解决子数组相关问题 ​

2026.1.6 11:46 ​

算法讲解047【必备】一维差分与等差数列差分 ​

算法讲解048【必备】二维前缀和、二维差分、离散化技巧 ​

左神学习笔记1

2025.11.22 - 2025.11.24

位运算

对数器

二分搜索

时间复杂度

算法和数据结构简介

2025.11.25

015 最小栈

016 双端队列

2025.11.26

算法讲解017【入门】二叉树及其三种序的递归实现

算法讲解018【入门】二叉树遍历的非递归实现和复杂度分析

用一个栈实现二叉树后序遍历

算法讲解019【必备】算法笔试中处理输入和输出

算法讲解020【必备】递归和master公式

算法讲解021【必备】归并排序

2025.11.27 16:26

算法讲解022【必备】归并分治

算法讲解023【必备】随机快速排序

2025.11.28 17:09

算法讲解024【必备】随机选择算法

2025.11.29 11:12

算法讲解025【必备】堆结构和堆排序

算法讲解026【必备】哈希表、有序表和比较器的用法

2025.11.30 10:50

算法讲解027【必备】堆结构常见题

算法讲解028【必备】基数排序

基数排序（Radix Sort）详解

一、基本思想

二、算法流程

三、C++ 实现（含详细注释）

四、关键点解析

五、优缺点总结

六、应用场景

算法讲解029【必备】重要排序算法的总结

1、排序算法的稳定性

2、主流排序算法对比表

3、理论边界与补充说明

4、实际应用选型建议

5、总结

2025.12.01 22:35

2025.12.02 10:44

算法讲解030【必备】异或运算的骚操作

算法讲解031【必备】位运算的骚操作

2025.12.03 21:12

2025.12.04 10:54

算法讲解032【必备】位图

算法讲解033【必备】位运算实现加减乘除

算法讲解034【必备】链表高频题目和必备技巧

2025.12.05 19:24

算法讲解035【必备】数据结构设计高频题

2025.12.06 11:25

2025.12.08 16:04

二叉树高频题目-上-不含树型dp

2025.12.09 16:08

二叉树高频题目-下-不含树型dp

2025.12.10 15:53

算法讲解038【必备】常见经典递归过程解析

2025.12.11 16:13

2025.12.15 18:15

算法讲解039【必备】嵌套类问题的递归解题套路

算法讲解040【必备】N皇后问题-重点是位运算的版本

2025.12.16 12:59

算法讲解041【必备】最大公约数、同余原理

2025.12.17 15:33

算法讲解042【必备】对数器打表找规律的技巧

算法讲解043【必备】根据数据量猜解法的技巧-天字第一号重要技巧

2025.12.18 19:25

2025.12.29 20:00 | 2026.1.4 17:01

算法讲解044【必备】前缀树原理和代码详解

算法讲解045【必备】前缀树的相关题目

2026.1.5 13:37

算法讲解046【必备】构建前缀信息的技巧-解决子数组相关问题

2026.1.6 11:46

算法讲解047【必备】一维差分与等差数列差分

算法讲解048【必备】二维前缀和、二维差分、离散化技巧