学习笔记

好用的小操作

求数位之和

int dig(int x)
{ 
    return (x + 8) % 9 + 1; 
    // 输入123 返回6
} 

原理：

任意一个数字 x 可以写成它的各位数字的加权和，形式如下：

x = a_k * 10^k + a_(k-1) * 10^(k-1) + ... + a_1 * 10 + a_0

其中 a_k, a_(k-1), ..., a_0 是 x 的各个数位的数字。

关键性质：

我们知道，对于任何整数 n，有以下等式成立：

10 ≡ 1 (mod 9)

这意味着，10 对 9 取模的余数是 1。由此可以推出：

10^k ≡ 1^k = 1 (mod 9) 对于任意整数 k

应用到数字表达式： 现在来看数字 x 对 9 的余数，也就是 x % 9：

x (mod 9) = (a_k * 10^k + a_(k-1) * 10^(k-1) + ... + a_1 * 10 + a_0) (mod 9)

由于 10^k ≡ 1 (mod 9)，我们可以将每个项中的 10^k 替换为 1：

x (mod 9) = (a_k + a_(k-1) + ... + a_1 + a_0) (mod 9)

也就是说，x 对 9 取模的结果，实际上等于 x 各位数字之和对 9 的余数。

向上取整

// 我们需要计算 x / y 向上取整
 
int new_num = (x + y - 1) / y;

在环形区间内移动 凯撒密码

ch = (ch - base + shift) % 26 + base;

• shift 是凯撒密码中的“位移”量，也就是你想要将字母平移的位数。举个例子，shift = 3 就意味着每个字母会向右移动3个位置。
• base 是字母的起始点（基准字符），用于确保加密和解密的计算只在字母范围内循环。例如：
  • 如果字母是小写字母（如 'a'），则 base = 'a'。
  • 如果字母是大写字母（如 'A'），则 base = 'A'。

详细解释：

1. ch - base：
   • 这个操作将字符 ch 转换为一个相对 base 的位置。例如，如果 ch 是 'c'，且 base 是 'a'，那么 'c' - 'a' 结果为 2，因为 'a' 的 ASCII 值是 97，'c' 是 99，所以 99 - 97 = 2。
2. (ch - base + shift)：
   • 这个操作将字符向右移动 shift 位。比如，如果你想对字母 'c' 进行加密，shift = 3，那么 (2 + 3) 就是 5。
3. % 26：
   • 由于字母表有 26 个字母，这个操作确保结果循环在 26 个字母内。例如，如果位移后的结果大于 'z'，它会回绕到字母表的开始部分。如果 ch 是 'z'，并且 shift = 1，'z' 经过加密会变成 'a'，而不是 '{'。
4. + base：
   • 最后，加上 base 就是将数字转换回字母字符。例如，5 + 'a' 就会变成 'f'，即将 5 映射回字符。

字符串 子串处理与替换

1. replace：

replace 用于替换字符串中的部分内容，可以替换从某个位置开始的指定长度的字符。

基本语法：

string& replace (size_t pos, size_t len, const string& str);
string& replace (size_t pos, size_t len, const string& str, size_t subpos, size_t sublen);

• pos: 要替换的起始位置。
• len: 要替换的字符数。
• str: 替换的内容。

2. substr：

substr 用于获取字符串的子字符串。

基本语法：

string substr (size_t pos = 0, size_t len = npos) const;

• pos: 子字符串的起始位置。
• len: 要提取的子字符串的长度（默认为 npos，表示从 pos 到字符串的末尾）。

快速转换进制

vector<char> lettermap = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 
                          'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 
                          'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 
                          'u', 'v', 'w', 'x', 'y', 'z'};
 
signed main()
{
    int num, base;
    cin >> num >> base;
    
    string s = "";
 
    // 将数字转换为指定进制
    while (num)
    {
        s = lettermap[num % base] + s;  // 从高位到低位构建， 这样不需要
        num /= base;
    }
 
    cout << s << ' ';
}

异或

异或的性质

1. 实质是二进制无进位加法 例如 1011 + 1101 = 0110

2. 异或运算满足交换律、结合律，也就是同一批数字，不管异或顺序是什么，最终的结果都是一个

3. n ^ 0 = n, n ^ n = 0 可以结合第一个加法来理解

4. 整体异或和如果是x,整体中某个部分的异或和如果是y,那么剩下部分的异或和是 x ^ y 可以结合2的结合律，交换律来理解

这些结论最重要的就是1结论，所有其他结论都可以由这个结论推论得到 其中第4相关的题目最多，利用区间上异或和的性质

区间异或和的性质 计算从 0 到 x 的异或和：

• 通过观察，可以发现异或的规律每四个数重复一次：
• 如果 x % 4 == 0，则 xor(0, x) = x
• 如果 x % 4 == 1，则 xor(0, x) = 1
• 如果 x % 4 == 2，则 xor(0, x) = x + 1
• 如果 x % 4 == 3，则 xor(0, x) = 0

计算区间 [l, r] 的异或和： 假设我们可以计算出 xor(0, r) 和 xor(0, l-1) ，那么： xor(l, r) = xor(0, r) ^ xor(0, l-1)

异或的骚操作

1. 交换两个数

int a = 1, b = 2;
a = a ^ b;
b = a ^ b;
a = a ^ b;
// as a result a equals 2 and b equals 1

具体过程：

• 第一步：a = a ^ b; 之后，a 保存的是 a 和 b 异或的结果，即 a 和 b 的混合信息。
• 第二步：b = a ^ b; 在这一步中，a 已经存储了 a ^ b，所以 b = (a ^ b) ^ b。根据自反性，b 变成了原来的 a。
• 第三步：a = a ^ b; 最后，a = (a ^ b) ^ a，根据自反性，a 变成了原来的 b。

所以，通过这三步异或操作，我们完成了 a 和 b 的交换，而无需使用额外的临时变量。这种方法是非常高效且空间优化的，尤其是在内存受限的情况下。

2. 找到缺失的数字

// 在1~10中随便挖掉一个 让快速找出
 
// 原理： 缺失的数字 = 所有数异或和 - 剩下数字的异或和
 
vector<int> v = {1, 2, 3, 4, 6, 7, 8, 9};
 
// 计算1 ~ 10 的异或和 也就是 xor(0, 10) ^ xor(0, 0) 而xor(0, 0) = 0
 
int xor_1_to_10 = 10 + 1 = 11;
 
// 计算v中数字的异或和 应当从0开始
 
int xor_v = 0;
for (int i = 0; i < v.size(); i++) xor_v ^= v[i];
 
// 计算剩下的数字
 
int result = xor_1_to_10 ^ xor_v;
 

例：

leetcode268

可以说是异或很好的板子题

ac codes are as follows:

class Solution
{
public:
    int xor_(int x)
    {
        if (x % 4 == 0)
        {
            return x;
        }
        if (x % 4 == 1)
        {
            return 1;
        }
        if (x % 4 == 2)
        {
            return x + 1;
        }
        return 0;
    }
 
    int missingNumber(vector<int> &nums)
    {
        int n = nums.size();
 
        // calculate xor from 0 to n
 
        int xor_1_to_n = xor_(n);
 
        // calculate xor from array
        int temp = 0;
        for (auto &&i : nums)
        {
            temp ^= i;
        }
 
        return xor_1_to_n ^ temp;
    }
};

3. 数组中1种数出现了奇数次，其他的数都出现了偶数次，返回出现了奇数次的数

   用到的是性质2 可以往上看一眼

   vector<int> v = {1, 1, 1, 1, 2, 2, 3};
   int res = 0;
   for (auto && i : v) res ^= i;
   return res; 
   // as a result res equals 3

例：

leetcode136

ac codes are as follows:

class Solution
{
public:
    int singleNumber(vector<int> &nums)
    {
        int ans = 0;
        for (auto &&i : nums)
        {
            ans ^= i;
        }
        return ans;
    }
};

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

其实就是lowbit 将在树状数组中反复使用

对一个正数x取反 得到x ^ 0

对其结果 + 1 得到 ~x + 1 其实就是相反数-x

最后做与运算 则有

int lowbit(x)
{
    return x & (-x);
}

最后得到的结果在二进制下将至多只有一个1

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

原理：设结果a, b 使得 a != b 那么一定有 a 和 b 在二进制的某一位不相同 那么原数组中一定可以分成两种数字： 第一种在那一位是0 第二种在那一位是1 我们只需要分别对这两种数字进行异或和 就能筛选出唯一的数字 思考：二进制下有多少位不相同 有影响吗？ ans：没有影响 我们要做的只是筛选工作 选出来即可

code：

vector<int> v = {1, 1, 2, 3, 3, 4};
 
int temp = 0;
for (auto &&i : v) temp ^= i;
int lowbit_num = temp & (-temp);
 
// 得到了这个唯一的"1" 我们如何继续操作？
// 我们继续用到与运算：如果num 在 lowbit_num的对应位数上是1 那么结果就是num 如果是0 那么结果就是00000000 也就是0
 
int ans1 = 0;
for (auto &&i : v) if (i & lowbit_num) ans1 ^= i;
ans2 = ans1 ^ lowbit_num;
// 用到了性质4 部分和 = 全体和 ^ 另一部分和

例:

leetcode260

ac codes are as follows:

class Solution
{
public:
    vector<int> singleNumber(vector<int> &nums)
    {
        unsigned xor_nums = 0;
        for (auto &&i : nums)
        {
            xor_nums ^= i;
        }
 
        int lowbit = xor_nums & (-xor_nums);
 
        int res1 = 0;
        for (auto &&i : nums)
        {
            if (lowbit & i)
            {
                res1 ^= i;
            }
        }
        return {res1, res1 ^ (int)xor_nums};
    }
};
 

IMPORTANT

为什么使用 unsigned 类型来避免溢出

1. 补码表示和溢出问题：
   • 在 C++ 中，整数是以补码的形式存储的。
   • 对于 int 类型，取负数的操作涉及到补码的反转，当 xor_nums 等于 INT_MIN（即 -2147483648）时，-INT_MIN 会导致溢出。因为 INT_MIN 是 -2147483648，其补码表示超出了 int 类型的范围，因此无法表示其取反的结果，导致未定义的行为。
2. 使用 unsigned 类型：
   • unsigned 类型在存储负数时表现不同，因为它不使用补码。无符号整数的范围是 [0, 2^n - 1]，它不涉及负数，因此在进行负数取反时不会出现溢出问题。
   • 当你将 xor_nums 声明为 unsigned 类型时，它将不会出现负数，因此 -xor_nums 会按照无符号整数的规则进行计算，不会发生溢出。

我们可以在以下场景尝试使用unsigned：

位运算中出现了负数

如果你需要执行位操作时，运算符会作用于负数，例如 a & b、a ^ b 或 a | b，而某些操作可能涉及到负数的补码表示。这时，使用 unsigned 类型可以避免这些负数影响结果，因为无符号整数的操作不会引发负数的补码计算。

进行最低位 1 查找（x & (-x)）时

在诸如 x & (-x) 的操作中，目标是找到二进制表示中最低的 1。如果 x 是负数（例如 -2147483648），在 int 类型中执行 -x 可能导致溢出，因为补码表示不能正确处理 INT_MIN。而如果使用 unsigned 类型， x 会被视为无符号数，取负时不会引发溢出问题。

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

to be continued…

今天的题目基本上都可以用map去重做， 这里是为了更好的熟悉异或运算

Important

重要提示

    void solve()
    {
        int l, r;
        cin >> l >> r;
 
        // int left = xor_(l - 1);
        // int right = xor_(r);
        // cout << (left ^ right);
 
        cout << xor_(l - 1) ^ xor_(r);
    }

注释部分不会报错 而第十行会报错 是因为cout需要一个可以明确的返回值类型而异或操作给不出, 笔者也没有想明白这是为什么)

总而言之 在异或操作的外面加一个括号可以完美避免这个问题

二分

TO START WITH

今天的内容侧重于我自己对代码流程的理解和思考 建议初步了解二分思想 想要规范书写流程 培养思维逻辑的读者

不建议对二分思想毫无了解的读者阅读 你会一头雾水的！（确信

二分搜索

1. 在有序数组中确定target存在还是不存在

Important

为什么一定要是有序的？

二分的思想一定程度上依赖于单调性 无序的数组不存在单调性 无法应用二分

bool isExist(vector<int> &nums, int target)
{
    if (nums.empty()) return 0;
    
    int l = 0, r = nums.size() - 1, mid;
    
    while (l <= r)
    {
        mid = l + ((r - l) >> 1);
        // 为什么不直接(r + l) / 2 ? 两个很大的数字相加有可能会超出int 而line9可以保证计算的过程始终讴歌处于[l, r]
        
        if (nums[mid] == target) return 1;
        else if (nums[mid] < target) /* 缩短左边界 */ l = mid + 1;
        else /* 缩短右边界 */ r = mid - 1;
    }
    //进行到这里还没return 就说明没找到
    return 0;
}

2. 在有序数组中找>=target的最左位置

Important

可以被*upper_bound 替代

int findleft(vector<int> &nums, int target)
{
    int l = 0, r = nums.size() - 1, mid;
    int ans = -1;
    
    while (l <= r)
    {
        mid = l + ((r - l) >> 1);
        if (nums[mid] >= target) // 满足条件 更新ans 并继续缩小范围
        {
            ans = mid;
            // 如何缩小范围? 这是一个单调的 现在发现数字大了 那么应该缩小右边界
            r = mid - 1;
        }
        else /* 当前数字太小了 那么应该找更大的 缩小左边界 */ l = mid + 1;
    }
    return ans; // 如果没有找到结果 将会返回-1
}

Important

思考：如果是 >target的最左位置 应该如何思考？

事实上 我们只需要把line9的 >= 变成 > 即可

3. 在有序数组中找⇐target的最右位置

那么 ⇐target 的最右位置 应该怎么做呢

int findright(vector<int> &nums, int target)
{
	int l = 0, r = nums.size() - 1, mid;
	int ans = -1;
	
	while (l <= r)
	{
		mid = l + (r - l) / 2; // 见识过位运算的骚操作之后还是觉得这样写方便一点 少打一个括号
		if (nums[mid] <= target) // 这是符合要求的 可以更新边界 更新ans
		{
			ans = mid;
			// 如何更新边界呢？找找有没有更大的数满足条件 缩短左边界
			l = mid + 1;
		}
		else r = mid - 1;
	}
	return ans; // 没找到返回-1
}

我们的思考重心应该放在 根据 nums[mid] 和 target 的对应关系 在满足条件的时候更新ans 缩短边界

4. 二分搜索不一定发生在有序数组上（比如寻找峰值问题）

板子题 leetcode162

ac codes are as follows:

class Solution
{
public:
    int findPeakElement(vector<int> &nums)
    {
        auto n = nums.size();
 
        if (n == 1) // 只有一个元素 那么这个就是极值点
        {
            return 0; // 特
        }
		// 首先检查nums.front() 和 nums.back()
        if (nums[0] > nums[1])
        {
            return 0;
        }
        if (nums[n - 1] > nums[n - 2])
        {
            return n - 1;
        }
 
        // 现在已经确定 [1, n - 2] 中一定有极值点 可以开始二分搜索
 
        int l = 1, r = n - 2, mid;
 
        while(l <= r)
        {
            mid = l + (l - l) / 2;
 
            // 判断是不是极值点 要看nums[mid]和相邻左右的关系
 
            if (nums[mid] > nums[mid - 1] and nums[mid] > nums[mid + 1])
            {
                return mid;
            }
            else
            {
                if (nums[mid] < nums[mid - 1])
                {
                    // 左边呈上升趋势 缩短右边界 在左边查找
                    r = mid - 1;
                }
                else
                {
                    // 缩短左边界 在右边查找
                    l = mid + 1;
                }
            }
        }
        return mid;
    }
};

二分搜索 with STL

在 stl 中 我们有 ranges::upper_bound 和 ranges::lower_bound

vector<int> v = {1, 2, 3, 4, 5};
 
auto it1 = ranges::upper_bound(v, 2);
// 返回指向 v[2] = 3 的迭代器
auto it2 = ranges::lower_bound(v, 2);
// 返回指向 v[1] = 2 的迭代器

分析实质

ranges::upper_bound 返回的it1 满足 *it1 > 2*, 而 ranges::lower_bound 返回的 it2 满足 it2 >= 2

并且他们都是首个满足条件的元素

所以我们分析可以得到：

问 >= x 的最小值 可以int it = *ranges::lower_bound(v, x)

问 > x 的最小值 可以 int it = *ranges::upper_bound(v, x)

问 < x 的 最大值 其实就是 >= x 的前一个值

例如 问 < 3 的最小值 其实就是 >= 3 的前一个值 也就是2

那我们可以写 int it = *(ranges::lower_bound(v, x) - 1)

同理：问 <= x 的 最大值 其实就是 > x 的 前一个值

也就是 int it = *(ranges::upper_bound(v, x) - 1)

总结 and 板子

Important

总结一下吧：

问更大的有现成函数

问更小的就 计算目标范围的补集（例如问 <= 那么就求>) 把求出来的结果-1 即可

最后的判断标准：

问大就判断是否超出右侧区间；

问小就判断是否超出左侧区间；

若询问相等 就额外判等

void find(vector<int> &nums, int target)
{
    int n = nums.size();
    
	// 求出首个使得num == target 的num的位置 (不存在返回-1)
	int it1 = ranges::lower_bound(nums, target) - nums.begin();
    cout << ((it1 == n or nums[it1] != target) ? -1 : it1) << endl;
    
    // 求出首个使得num >= target 的num的位置 (不存在返回-1)
	int it2 = ranges::lower_bound(nums, target) - nums.begin();
    cout << (it2 == n ? -1 : it2) << endl;
    
    // 求出首个使得num > target 的num的位置 (不存在返回-1)
    int it3 = ranges::upper_bound(nums, target) - nums.begin();
    cout << (it3 == n ? -1 : it3) << endl;
    
    // 求出首个使得num <= target 的num的位置 (不存在返回-1)
    int it4 = ranges::upper_bound(nums, target) - nums.begin() - 1; // 其实就是it3 - 1!!!!
    cout << (it4 < 0 ? -1 : it4) << endl;
    
    // 求出首个使得num < target 的num的位置 (不存在返回-1)
    int it5 = ranges::lower_bound(nums, target) - nums.begin() - 1; // 其实就是it2 - 1!!!!
    cout << (it5 < 0 ? -1 : it5) << endl;
}

例题

leetcode34

第一个位置就是 >= x 的第一个元素

最后一个位置就是 > x 的前一个元素

思路：

// 首先 lower出 >= x 的 第一个元素 判断是否与目标值相等 或者是否来到边界(来到边界意味着数组中没有不小于target的元素)
int num1 = ranges::lower_bound(nums, target) - nums.begin();
 
if (num1 == nums.size() or nums[num1] != target)
{
	return {-1, -1};
}
else
{
    // 数组中起码有一个 我们就可以upper了
    int num2 = ranges::upper_bound(nums, target) - nums.begin() - 1;
    // remember that 直接与begin()相减 求出来的就是下标
    return {num1, num2};
}    

另外：

我们也可以利用cpp20的 equal_range 函数 来快速获得范围

{0, 1, 1, 1, 2}

auto [start, end] = ranges::equal_range(nums, 1); // 此处的auto应该是pair<iterator, iterator>类型
// start指向nums[1], end指向nums[3]的下一个 也就是 [start, end) 这样一个半开区间
if (start == end) return {-1, -1};
return {start - nums.begin(), end - 1 - nums.begin()};
// 如果问长度那么直接end - start即可

leetcode35

直接返回 >= target 的第一个元素位置即可

return ranges::lower_bound(nums, target) - nums.begin();

leetcode704

跟上面大差不差 搜索到lower之后比较是否相等即可

auto num = ranges::lower_bound(nums, target) - nums.begin();
return (num != nums.size() and nums[num] == target ? num : -1);

Important

当我们需要使用迭代器的时候 要注意有可能返回 nums.emd() 导致 num = n

这样的情况下nums[num] 是 越界的

因此 我们应该加上 num == nums.size() 的判断

leetcode744

判断 upper是否 == letters.end() 即可

auto it = ranges::upper_bound(letters, target) - letters.begin();
return (it == letters.size() ? letters.front() : letters[it]);

leetcode2529

什么是数目？

我们不妨做个测试

{-1, 0, 1}

lower(0) - begin() 会返回第一个非负数的下标 记为 it 显然 it - 1就是最后一个负数的下标 本例中为0 那么个数就是最后一个下标 0 + 1 也恰好就是 lower(0) - begin()

lower(1) - begin() 返回第一个正数的下标 本例中为2 个数应为 size() - it其实就是 end() - lower(1)

int a = ranges::lower_bound(nums, 0) - nums.begin();
int b = nums.end() - ranges::upper_bound(nums, 0);
return max(a, b);

二分答案

解题步骤

1. 估计最终答案可能的范围是什么 经验之谈：为什么叫做二分答案呢？因为二分的就是答案——问什么就二分什么
2. 分析问题的答案和给定条件之间的单调性，大部分时候只需要用到自然智慧
3. 建立一个f函数，当答案固定的情况下，判断给定的条件是否达标
4. 在最终答案可能的范围上不断二分搜索，每次用f函数判断，直到二分结束，找到最合适的答案

核心点：分析单调性、建立f函数

注意：这个技巧常用且重要，一定要引起重视

这么说出来可能过于抽象 我们结合例题理解

二分答案：求最小

leetcode1283

问什么就对什么二分， 我们对除数二分

除数的上下界怎么找？ 下界应该是1 这样可以让sum最大 上界可以选择ranges::max(nums) 这样可以让sum最小

那我们就确定下来：

// 对除数二分
// 除数的范围应该在[1, ranges::max(num)]
 
int l = 1, r = ranges::max(nums), m, ans;

随后二分开始

while (l <= r)
{
    m = l + (r - l) / 2;
    // m 是 除数
    if (f(m, nums, int threshold)) // 满足条件 记录答案 找更小的
    {
        ans = m;
        r = m - 1;
    }
    else // 不满足条件 找更大的
    {
        l = m + 1;
    }
    return ans;
}

f函数如下：

bool f(int m, vector<int> &nums, int target)
{
    int ans = 0;
    for (auto &&i: nums)
    {
        ans += (i + m - 1) / m; // 上取整 注意能不用ceil就不用ceil 可能造成精度丢失
        if (ans > target) 
        {
            return 0;
        }
    }
    return 1;
}

leetcode2187

问时间 我们尝试对时间进行二分

最快时间应该是 ranges::min(time) 此时 totalTrips = 1

最慢时间应该是 ranges::min(time) * totalTrips

不难写出如下代码

long long minimumTime(vector<int> &time, int totalTrips)
{
    // 二分时间
    long long l = ranges::min(time), r = l * totalTrips, m, ans;
    while (l <= r)
    {
        m = l + (r - l) / 2;
 
        if (f(m, time, totalTrips)) ans = m, r = m - 1;
        else l = m + 1;
    }
    return ans;
}

f函数也就是常规的加一遍：

bool f(long long m, vector<int>& time, int target)
{
    int ans = 0;
    for (auto &&t : time)
    {
        ans += m / t;
        if (ans >= target)
        {
            return 1;
        }
    }
    return 0;
}

难而杂的例题

leetcode875

Important

思考：有没有可能速度为0?

当且仅当数组全部都是0的时候 每小时0根也肯定可以吃完

题目中说到香蕉数量>= 1 那么不可能是0

因此 最慢速度就是1

思考：最快速度是多少

应当为 数组中的最大元素 （一堆最多的香蕉）

思考：速度再快有意义吗？

没有了 我们需要用到二分法 那么初始的范围小 对我们的二分是有益的

经过分析 我们可以得出 速度的取值应当在 [1, *max_element(piles.begin(), piles.end())]

不难发现：随着速度的增大 吃掉所有香蕉用掉的小时数 只可能不严格单调递减 速度变大反而耗时变多的情况是不存在的

那我们就可以对速度进行二分 进而求出小时数

ac codes are as follows:

class Solution
{
public:
    int minEatingSpeed(vector<int> &piles, int h)
    {
        int l = 1, r = *max_element(piles.begin(), piles.end());
 
        int ans = 0;
        int mid = 0;
        while (l <= r)
        {
            mid = l + (r - l) / 2;
            /*
            这个mid是什么？是速度
            我们要求什么？求时间
            因此我们应该遍历整个香蕉数组， 把用时求出来 和 h 进行比较
            */
            long long h1 = 0; // h1 就是 用时 实际比赛的时候我们其实可以#define int long long
            for (auto &&pile : piles)
            {
                /*
                是熟悉的区间分割诶！
                我的拙劣的讲解视频 BV15QcAefE5j
                区间是 mid
                要划分的变量是 pile
                用时就是 (pile - 1) / mid + 1
                我们其实也可以写成
                (pile + mid - 1) / mid
                
                by the way 他的本质其实是 pile / mid 结果向上取整
                */
 
                h1 += (pile - 1) / mid + 1;
            }
 
            if (h1 <= h) // 当前用时达标！更新答案 放慢速度
            {
                ans = mid;
                r = mid - 1;
            }
            else // 未达标！增加速度
            {
                l = mid + 1;
            }
        }
        return ans;
    }
};

这里有一个很实用的技巧 就是把 速度 → 时间 的变化作为函数封装起来

具体来说我们有

int f(vector<int> &piles, int k)
{
    int ans = 0;
    
    for (auto&& p: piles) ans += (p + k - 1) / k;
    
    return ans;
}

此处被 return 的 ans 将作为 h1 与 h 进行比较

这也就是我第3步说的 建立f函数

leetcode410

看到「最大化最小值」或者「最小化最大值」就要想到二分答案，这是一个固定的套路。

为什么？「元素和的最大值」越小，需要划分出的段数就越多，反之越少。例如示例 1 的 nums = [7,2,5,10,8]，在最大和为 15 时，至少要划分 3 段，比如 [7,2,5],[10],[8]。而在最大和为 18 时，只需要划分 2 段，比如 [7,2,5],[10,8]。

一般地，二分的值越小，越不能/能满足要求；二分的值越大，越能/不能满足要求。有单调性的保证，就可以二分答案了。

Important

思考：如何保证二分结果一定能划分成 k 段？如果小于 k 段呢？

题目要求划分成 k 段，但其实如果能划分成小于 k 段，也可以划分成 k 段。比如划分成 k−1 段，那么把其中的一个长度至少为 2 的段分成两段，这两段的元素和都比原来的一段小，也满足要求。所以题目相当于：把数组划分成至多 k 段，分别计算每一段的元素和，最小化元素和的最大值。

应当注意的是， k的取值是 1 <= k <= min(50, nums.length) 这意味着k不会取一个天花乱坠的数字 我们能保证大部分情况下k <= nums.size() 这就够了

题目问我们最大值 我们就尝试二分最大值

最大的最大值是多少？k = 1 时数组和的最大值最大 就是accumulate(nums.begin(), nums.end())

最小的最大值是多少？k = nums.size() 时数组和的最大值最小 是 max_element(nums.begin(), nums.end())

如何把最大值 跟 k 联系起来？

f函数参考如下：

int f(vector<int> nums, int m)
    {
        int ans = 1, sum = 0; // 一开始只需要分一段
 
        for (auto &&i : nums)
        {
            if (sum + i <= m) // 如果最大值没超过 那么最大值可以继续增加
            {
                sum += i;
            }
            else // 超过了就需要增加一段了 与此同时 sum 更新为新的一段
            {
                ans++;
                sum = i;
            }
        }
        return ans;
    }

有了这个函数 我们就找到了最大值和段数的关系 那么我们只需要不断二分最大值 让段数逐渐接近k就行

ac codes are as follows:

int splitArray(vector<int> &nums, int k)
    {
        long long sum = accumulate(nums.begin(), nums.end(), 0ll);
        // 二分的是最大值 要求的答案是k
        // k 可以尽可能小 因为小于k段却满足条件 我们大可以把其中的一些段分开 也不会影响答案
        long long ans = 0;
 
        long long l = *max_element(nums.begin(), nums.end()), r = sum, mid, need;
        while (l <= r)
        {
            // 必须让每一部分的累加和 <= mid， 请问划分成几个部分才够？
 
            mid = l + (r - l) / 2;
 
            need = f(nums, mid); // need 是最大值为 mid 所需要的段数
 
            if (need <= k) // 达标 更新答案 缩小右区间 找更小的最大值
            {
                ans = mid;
                r = mid - 1;
            }
            else // 未达标 缩小左区间 找更大的最大值
            {
                l = mid + 1;
            }
        }
        return ans;
    }

Important

在f函数中 我们就可以适当的暴力一点 因为f是为二分服务的 而二分本身复杂度就已经很低了

看完这两题是不是有一点体会了？有的兄弟有的，这样的例题还有一堆

现在是 20250114 00：01：32

牛客 机器人跳跃问题

看到问能量值 那我们尝试二分能量值

首先要确定能量值的边界

我们来分析题目：能量值比楼房的高度小 反而要减少 比楼房的高度高 反而要增大

那我们只需要让他的高度比所有的楼房都要高 不就一定能通过吗

因此 r = *max_element(v.begin(), v.end())

那么我们最起码要让他安然无恙的通过最矮的楼房 否则就必定无法通过

因此 l = *min_element(v.begin(), v.end())

Important

最大值最小值的写法在cpp20中已经得到了进一步优化

我们可以使用 ranges::max(v) 和 ranges::min(v) 来快速求数组的最大 最小值

那我们写f函数的目的也就随之确定下来， 即：

给定一个能量值 判断这个能量值是否可以通过所有楼房

bool f(vector<int> v /* 所有楼房高度 */, int e /* 能量 */, int max_ /* 最大建筑高度 */)
{
    for (auto &&i: v)
    {
        if (e > i) e += (e - i);
        else e -= (i - e);
        
        // 判断是否达到上边界
        if (e >= max) return 1;
        // 判断是否变成负数
        if (e < 0) return 0;
    }
    return 1;
}

有了f函数 我们就可以写出二分答案的流程

void solve()
{
	int n;
    cin >> n;
    vector<int> v(n);
    for (auto &&i: v) cin >> i;
    
    auto l = ranges::min(v), r = ranges::max(v);
    auto max_ = r;
    
    int mid, ans;
    
    while (l <= r)
    {
        mid = l + (r - l) / 2; // 时刻牢记 mid 是初始能量
        
        // 给定能量 用f来验证是否满足题意
        if (f(v, mid, max_)) // 满足条件 找更小的
        {
            ans = mid;
            r = mid - 1;
        }
        else // 不满足条件 找更大的
        {
            l = mid + 1;
        }
    }
    cout << ans;
}

leetcode719

ac codes are as follows:

class Solution
{
public:
    int f(vector<int> nums, int lim)
    {
        int ans = 0;
        int r = 0;
        for (int l = 0; l < nums.size(); l++)
        {
            while (r < nums.size() and nums[r] - nums[l] <= lim)
            {
                r++;
            }
            ans += r - l - 1;
        }
        return ans;
    }
 
    int smallestDistancePair(vector<int> &nums, int k)
    {
        ranges::sort(nums);
 
        long long l = 0, r = nums.back() - nums.front();
 
        long long mid, ans, cur;
 
        while (l <= r)
        {
            // 我们再对数字差作二分
            mid = l + (r - l) / 2;
            // 要验证是否是第k小 只需要遍历看看 差值 <= mid 的 是否有k个
            if (f(nums, mid) >= k) // 有可能有更小的 因为 f里面提到 差值 <= mid 即可
            {
                ans = mid;
                r = mid - 1;
            }
            else
            {
                l = mid + 1;
            }
        }
        return ans;
    }
};

f函数的构造比较复杂 值得细品…

leetcode2141

并查集

并查集解决的是怎样的问题呢？就是对集合的 合并 查询

要想比较高效的完成合并查询工作 我们需要两个数组：father 和 sz， 一个模拟递归的栈stk

板子：

初始化：

vector<int> father, siz;
stack<int> stk;
 
void init(int n) {
    father.resize(n);
    siz.resize(n, 1);
    ranges::iota(father, 0ll);  // father[i] 初始时指向自己
}

完全体：

// 查找父节点，路径压缩
int ffind(int i) {
    while (father[i] != i) {
        // 递归查找并压缩路径, 使用栈优化递归
        stk.push(i);
        i = father[i];
    }
    while (!stk.empty())
    {
        father[stk.top()] = i; // 将栈中的节点都指向根节点
        stk.pop();
    }
    return father[i];
}
 
// 合并两个集合，按秩合并
void union(int i, int j) {
    int rootI = ffind(i);
    int rootJ = ffind(j);
 
    if (rootI != rootJ) {
        // 按树的大小（秩）合并
        if (siz[rootI] < siz[rootJ]) {
            swap(rootI, rootJ);  // 确保 rootI 永远是较大的树
        }
        father[rootJ] = rootI;  // 将 rootJ 的根节点指向 rootI
        siz[rootI] += siz[rootJ];  // 更新 rootI 的大小
    }
}
 
bool issame(int i, int j)
{
	return ffind(i) == ffind(j);
}

精简化写法：

int ffind(int n)
{
    if (n != father[n])
    {
        father[n] = ffind(father[n]);
    }
    return father[n];
}
 
void funion(int i, int j)
{
	father[i] = j;
}
 
bool issame(int i, int j)
{
    return ffind(i) == ffind(j);
}

luoguP3367

void solve()
{
    int n, m;
    cin >> n >> m;
    // FU begin
    vector<int> father;
    auto init = [&](int n)
    {
        father.resize(n);
        iota(all(father), 0);
    };
 
    function<int(int)> ffind = [&](int i)
    {
        return i == father[i] ? i : father[i] = ffind(father[i]);
    };
 
    auto funion = [&](int i, int j)
    {
        auto ri = ffind(i), rj = ffind(j);
        if (ri != rj)
        {
            father[ri] = rj;
        }
    };
 
    auto issame = [&](int i, int j)
    {
        return ffind(i) == ffind(j);
    };
 
    // FU end
    init(n);
    int a, b, c;
    while (m--)
    {
        cin >> a >> b >> c;
        b--, c--; // 0 based
        if (a == 1)
        {
            funion(b, c);
        }
        else
        {
            cout << (issame(b, c) ? 'Y' : 'N') << endl;
        }
    }
}

DFS

板子：

vector<pair<int, int>> d = {{1, 0}, {0, 1}{-1, 0}, {0, -1}};
 
void dfs(int i, int j, vector<vector<int>> grid)
{
    if (i < 0 or i == grid.size() or j < 0 or j == grid[0].size() or grid[i][j] != 0)
    {
        return;
    }
    
    grid[i][j] = 2; // 与原先不同的标记
    
    for (auto &&[x, y]: d)
    {
        dfs(i + x, j + y, grid);
    }
}

图

图的表示

邻接表

unordered_map<int, unordered_map<int, int>> adj; // v1, v2, val

邻接矩阵

图的遍历

dfs

bfs

图算法

最小生成树 （MST，Minimum Spanning Tree）

什么是最小生成树？ 最小生成树是所有节点的最小联通子图， 即：用最小的成本（边的权值）将所有的节点连接到一起

假如存在 n 个节点 那么必定可以用 n - 1 条边将他们连接到一起， 如何选择这 n - 1 条边就是任务所在

prim

Important

1. 解锁的点的放入 set、解锁的边的集合叫 heap（小根堆）。一开始 set 和 heap 都为空。
2. 可从任意点开始，开始点加入到 set，开始点的所有边加入到 heap
3. 从 heap 中弹出权值最小的边 e，查看边 e 所去往的点 x
   • 如果 x 已经在 set 中，边 e舍弃，重复步骤3
   • 如果 x不在 set 中，边 e 属于最小生成树，把 x 加入 set ，重复步骤3
4. 当 heap 为空，最小生成树也就得到了

luoguP3366

void solve()
{
    int n, m; // n为顶点数，m为边数
    cin >> n >> m;
    // prim
    set<int> nodes; // 存储已访问的节点
 
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq; // 小顶堆，存储边{权重,目标顶点}
 
    int MSTweight = 0; // 最小生成树的总权重
 
    int v1, v2, val; // v1,v2为边的两个顶点，val为边的权重
 
    vector<vector<pair<int, int>>> adj(n + 1); // 邻接表存储图，adj[u]存储u的所有邻边{顶点,权重}
    while (m--)
    {
        cin >> v1 >> v2 >> val;
        // 无向图需要添加两条边
        adj[v1].emplace_back(v2, val);
        adj[v2].emplace_back(v1, val);
    }
 
    pq.push({0, 1}); // 从顶点1开始，初始权重为0
 
    while (pq.size())
    {
        auto [curw, cur] = pq.top(); // curw为当前边的权重，cur为当前顶点
        pq.pop();
 
        if (nodes.count(cur)) // 如果当前顶点已访问，跳过
        {
            continue;
        }
 
        nodes.insert(cur); // 将当前顶点标记为已访问
        MSTweight += curw; // 将当前边的权重加入最小生成树的总权重
 
        // 遍历当前顶点的所有邻边
        for (auto &&[next, nextw] : adj[cur]) // next为邻接顶点，nextw为边权重
        {
            if (!nodes.count(next)) // 如果邻接顶点未访问
            {
                pq.push({nextw, next}); // 将边加入优先队列
            }
        }
    }
    if (nodes.size() != n) // 如果访问的顶点数不等于总顶点数，说明图不连通
    {
        cout << "orz"; // 输出无解
    }
    else
    {
        cout << MSTweight; // 输出最小生成树的总权重
    }
}

kruskal

Important

1. 把所有的边，根据权值从小到大排序，从权值小的边开始考虑
2. 如果连接当前的边不会形成环，就选择当前的边
3. 如果连接当前的边会形成环，就不要当前的边
4. 考察完所有边之后，最小生成树也就得到了

luoguP3366

void solve()
{
    int n, m, v1, v2, val;
    cin >> n >> m;
 
    struct Data
    {
        int v1, v2, val;
    };
    vector<Data> datas;
    while (m--)
    {
        cin >> v1 >> v2 >> val;
        v1--, v2--;
        if (v1 != v2)
        {
            datas.push_back({v1, v2, val});
        }
    }
 
    // kruskal
 
    // FU begin
    vector<int> father;
    auto init = [&](int n)
    {
        father.resize(n);
        iota(all(father), 0);
    };
 
    function<int(int)> ffind = [&](int i)
    {
        return i == father[i] ? i : father[i] = ffind(father[i]);
    };
 
    auto funion = [&](int i, int j)
    {
        auto ri = ffind(i), rj = ffind(j);
        if (ri - rj)
        {
            father[ri] = rj;
        }
    };
 
    auto issame = [&](int i, int j) -> bool
    {
        return ffind(i) == ffind(j);
    };
 
    // FU end
 
    ranges::sort(datas, [](Data &a, Data &b)
                 { return a.val < b.val; });
 
    init(5001);
    int ans = 0, count = 0;
 
    vector<bool> visited(n, 0);
    for (auto &&[v1, v2, val] : datas)
    {
        if (!issame(v1, v2))
        {
            visited[v1] = visited[v2] = 1;
            ans += val;
            funion(v1, v2);
            count++;
        }
    }
 
    if (count == n - 1)
    {
        cout << ans;
    }
    else
    {
        cout << "orz";
    }
}

拓扑排序

luoguB3644

void solve()
{
    int n;
    cin >> n;
    int num;
 
    // 没有边权的邻接表
    unordered_map<int, vector<int>> adj;
    // 入度
    vector<int> indegree(n + 1, 0); // 1 based
    vector<int> result;
 
    for (int i = 1; i <= n; i++)
    {
        adj[i];
        while (cin >> num)
        {
            if (num == 0)
            {
                break;
            }
            adj[i].push_back(num);
            indegree[num]++; // 入度， 入度！
        }
    }
 
    // 拓扑
    queue<int> que;
    for (int i = 1; i <= n; i++)
    {
        // 入度为0 可以作为开头 假如队列
        if (indegree[i] == 0)
        {
            que.push(i);
        }
    }
 
    while (que.size())
    {
        auto cur = que.front();
        que.pop();
        result.push_back(cur);
 
        if (adj[cur].size())
        {
            for (auto &&i : adj[cur])
            {
                indegree[i]--;
                if (indegree[i] == 0)
                {
                    que.push(i);
                }
            }
        }
    }
    for (auto &&i : result)
    {
        cout << i << ' ';
    }
}

KMP

vector<int> getnext(string s)
{
	int n = s.size();
	vector<int> v(n, 0);
	int j = 0; // 前缀长度
	for (int i = 1; i < n; i++)
	{
		while (j and s[i] != s[j])
		{
			j = v[j - 1];
		}
		if (s[i] == s[j])
		{
			j++;
		}
		v[i] = j;
	}
	return v;
}