LYL's Blog
0%

leetcode刷题系列之小知识点

发表于 分类于
本文字数： 4k 阅读时长 ≈ 4 分钟

这篇文章是leetcode刷题系列的番外篇——刷题小知识点。主要是编程题中的一些冷知识、小技巧。

leetcode刷题系列其它文章组织如下：

1. 数组

2. 链表

3. 字符串

4. 二叉树

5. 队列和栈

6. 动态规划

7. 数据结构设计

8. 刷题小知识点

数字和字符串互转

数字转字符串使用std::to_string函数。比如可以用来快速得到数字的位数。字符串转数字有std::stoi，std::stol等。

对于字符串变量使用流stringstream

对于需要将字符串中的子串按照一定的分隔符依次读取，可以这么做

1
2
3
4
5
6
7
stringstream ss(str);
string substr;
// 分隔符视具体情况而定, 如'/', ' ', '.'
while(getline(ss, substr, ',')) {
    // 依次处理 substr
    ...
}

数字0-9和单个字符互转

1
2
3
4
5
6
7
8
9
// '0' 的 ASCII 码值为 48 (十进制)
// 'A' 的 ASCII 码值为 65
// 'a' 的 ASCII 码值为 97

int i = 6;
char c = i + '0';

char c = '6';
int i = c - '0';

单个字符转为字符串

  • string(1, c)
  • string().append(1, c)

数字转为字符串

  • std::to_string()

将迭代器前进和后退n步

1
2
3
4
5
// 它们都返回前进或后退之后的迭代器
std::next(it); // 前进 1 步
std::next(it, n); // 前进 n 步
std::prev(it); // 后退 1 步
std::prev(it, n); // 后退 n 步

对于vector的push_back不适用的情况

若已知结果vector的大小，可提前创建一个该大小的vector，然后直接使用索引向vector中从后向前赋值。比如，从大到小地往vector中添加值，但又要求最终vector是递增的情况。

对于在for循环里使用size()函数可能会出现的意外情况

拿vector来说，其size()函数接口返回的是向量的元素个数，它是size_t类型，即无符号整型unsigned int或unsigned long类型，如果拿它与另一个整数相减得到了一个负数，那么这个负数将会被隐式的转型为一个超级大的数（因为它的类型是无符号的嘛），这时候在for循环里的判条件将会产生意想不到的结果。

1
2
3
4
5
6
7
8
9
10
vector<int> nums{1, 2, 3}; // nums.size() == 3 为 unsigned 类型
for(int i = 0; i < nums.size() - 4; i++) {
    // 将无限循环, 因为 nums.size() - 4 == -1 == INT_MAX 或 LONG_MAX
}

// 所以最好在循环外面用一个 int 变量先存一下大小
int n = nums.size(); // n == 3 为 int 类型
for(int i = 0; i < n - 4; i++) {
    // 0 < -1 不会进入循环
}

卡特兰数

问题：一个合法的表达式由()包围，()可以嵌套和连接，如(())()也是合法括号表达式。现在有n对()，它们可以组成的合法括号表达式的个数为多少？

用栈检验括号序列是否有序。设置一个栈，每读入一个括号，若是左括号，则压栈；若是右括号，并且与当前栈顶的左括号相匹配，则出栈，继续读下一个括号，如果读入的右括号与当前栈顶的左括号不匹配，则属于不合法的情况。在初始和结束时，栈应该是空的。n对括号出栈顺序的总数就是本题中所有合法括号表达式的数目。

假设序列为[0, 1, 2, ..., n-1]。对于序列入栈出栈，长度为0的序列的出栈序列总数记为C(0)，长度为1的序列的出栈序列总数记为C(1)，长度为n的序列的出栈序列总数记为C(n)，易知C(0) = 0，C(1) = 1。

假设序列为[0, 1, 2, ..., n-1]，其中有k。对于序列入栈出栈，若k最后出栈，则出栈次序为，先是比k小的[0, 1, ... , k-1]，情况有C(k)种，后是比k大的[k+1, ..., n-1]，情况有C(n-k-1)，最后是k。[0, 1, ... , k-1]和[k+1, ..., n-1]都是合法出栈次序。

例如对于序列[0, 1, 2, 3, 4, 5, 6, 7]，k=5，一种出栈次序为[0, 2, 1, 4, 3, 7, 6, 5]。

由于k为不同值的情况相互独立，而且比k大的[k+1, ..., n-1]和比k小的[0, 1, ... , k-1]也相互独立，可以推出：

image-20210908151604357

1
2
3
4
5
6
7
8
9
10
11
12
13
int catalan(int n) {
    vector<int> dp(n + 1);
    dp[0] = 1;
    dp[1] = 1;

    for(int i = 2; i <= n; i++) {
        for(int j = 0; j < i; j++) {
            dp[i] += dp[j] * dp[i - j - 1];
        }
    }

    return dp[n];
}

相似问题：

  1. 圆周上有标号为1, 2, 3, 4, ..., 10的共计10个点，这10个点配对可连成5条弦，且这些弦两两不相交的方式数目？(C(5))

  2. 游乐园门票5元一张，每人限购一张。现在有10个小朋友排队购票，其中5个小朋友每人只有5元的钞票一张，另5个小朋友每人只有10元的钞票一张，售票员没有准备零钱。问：有多少种排队方法，使售票员总能找的开零钱？(将持5元者到达视作将5元入栈，持10元者到达视作使栈中某5元出栈，C(5))

  3. 饭后，姐姐洗碗，妹妹把姐姐洗过的碗一个一个放进碗橱摞成一摞。一共有n个不同的碗，洗前也是摞成一摞的，也许因为小妹贪玩而使碗拿进碗橱不及时，姐姐则把洗过的碗摞在旁边，问：小妹摞起的碗有多少种可能的方式？(C(n))

  4. n + 2条边的多边形，能被分割成三角形的方案数有（C(n)）。例如6边型的分割方案有C(4) = 14。

  5. 拥有n + 1个叶子节点的二叉树的数量为多少？（C(n)）。例如4个叶子节点的所有二叉树形态有C(3) = 5。

  6. n*n的方格地图中，从一个角到另外一个角，不跨越对角线的路径数，例如，4×4方格地图中的路径有：

  7. 再来一道阿里巴巴的笔试题目：说16个人按顺序去买烧饼，其中8个人每人身上只有一张5块钱，另外8个人每人身上只有一张10块钱。烧饼5块一个，开始时烧饼店老板身上没有钱。16个顾客互相不通气，每人只买一个。问这16个人共有多少种排列方法能避免找不开钱的情况出现。

    C8 = 1430，所以总数为1430 * 8! * 8！。这里乘以两个8!是因为每个人都不一样，持5块和10块分别的有8!中排列方式。它不像括号生成，左括号和左括号，或者右括号和右括号没区别。

  8. 腾讯实习招聘笔试题：在图书馆一共6个人在排队，3个还《面试宝典》一书，3个在借《面试宝典》一书，图书馆此时没有了面试宝典了，求他们排队的总数？

    C3 = 5，同题7理，总数为5 * 3！* 3！= 180。

向上取整

如x/y向上取整，可以用(x+y-1)/y。更方便的是调用标准库函数std::ceil(double(x)/y)。

将一个整数变成无限循环小数

例如，123变成0.123123123...。可将123除以999。一般的，对于整数a，变成无限循环小数的方式是a / (a的位数 - 1)。

证明：

Image_20210412135943

另外，求取一个整数a的位数可以用to_string(a).size()或1 + (int)log10(a)。

整数拼接比大小

要求两个整数x，y如何拼接得到结果更大或更小时，就要想到先转成字符串，然后比较string(x) + string(y)和string(y) + string(x)。

位运算总结

  • 计算二进制数中1的个数

    • 巧用n & (n - 1)：n - 1导致二进制数字n最右边的1变成0，此1右边的0变成1；n & (n - 1)导致二进制数字n最右边的1变成0，其余位不变。因此可以循环执行此过程并计数，直到n变为0。
    • n & -n可以获取n的二进制位表示中最低位的1。因为，负数表示正数取反加一，再相与后会导致除了最低位的1保持不变，其它位全变为0。

  • 异或运算

    异或运算简单理解就是不进位的加法运算。1 + 1 = 0，1 + 0 = 0 + 1 = 1，0 + 0 = 0。所以异或运算满足加法的一些运算规律：

    • 交换律

      x ^ y = y ^ x。

    • 结合律

      (x ^ y) ^ z = x ^ (y ^ z)。

    • 分配律

      (x1 & y1) ^ (x1 & y2) ^ (x2 & y1) ^ (x2 & y2) = (x1 ^ x2) & (y1 ^ y2)。

    • 对任何数x有

      x ^ 0 = x，x ^ x = 0，x ^ FFFFFFFF = !x。

  • 判断奇偶性

    数字的奇偶性取决于其最低位为1还是0。

    1
    2
    3
    4
    5
    6
    if(a & 1) {
        // 奇数
    }
    else {
        // 偶数
    }

哈希表的键设定问题

最常用的做为键的就是整数和字符串了，大多数题目都是这样。但有时候会遇到一种情况，就是说我们希望用两个以上的变量值的组合来确定对应的值，这怎么处理呢？

小技巧是，将这些变量统一转为字符串，再拼接在一起做为键。如：

1
2
3
4
unordered_map<string, int> mapping;
int key1, key2;
string key = to_string(key1) + "," + to_string(key2);
mapping[key] = value;

模幂运算的技巧

先说常用的求模运算技巧，对乘积的结果求模，等价于先对每个因子都求模，再对因子求模的结果的乘积再求模。

image-20210908151709526

证明过程如下：

假设A, B, C, D为任意常数，那么，

image-20210908151737555

又因为，

image-20210908151759130

所以，

image-20210908184330852

求幂运算的话，就是要知道可根据幂指数的奇偶性优化求解效率：

img

同余定理

image-20210908151821823

最小公倍数和最大公约数

1
2
3
4
// 辗转相除法求最大公约数
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}
1
2
3
4
// 最小公倍数
int lcm(int a, int b) {
    return a * b / gcd(a, b);
}