随手记 10 分钟读完 (大约1526个字) 0次访问

LeetCode

注意事项

  • 统计单词数直接 int a[300] 这样可以省去 - 'a' 这一步操作。

  • 代码中的 printf 不会影响最后的结果，猜测是去比较返回值。

    • 上一条提到的不会影响结果，但是会影响耗时，所以还是要删除中间的输出。

  • 函数里面定义数组，需要初始化。

    • vector<int>v(10, 0)

    • vector<vector<int>> dp(k, vector<int>(1 << n)); 二维 vector

  • sort 手动传入 cmp 需要是 static 类型

  • sort(a.begin(), a.end(), [](vector<int>&x, vector<int>&y){return x[0]<y[0];});

    • lambda 里面的参数需要是引用，如果是拷贝构造，在 n=1e5 时会超时。

  • 枚举子集 | CP Wiki n 个元素的子集枚举 $$O(3^n)$$ 复杂度

    • 枚举 i 的子集
      • (j - 1) 将 j 最右边的 1 变成 0，得到小于 j 最大的一个二进制数
      • (j - 1) & i 保证一定是 i 的子集
1
2
3
4
5
for (int i = 1; i < (1 << n); ++i) {
    for (int j = i; j; j = (j - 1) & i) {
   // ...
    }
}

  • 0x3f3f3f3f 的十进制是1061109567，是10^9级别的，自身相加不会超过 int 范围，可以 memset 初始化

  • [[vector]] 取指定位置的迭代器

1
2
3
4
vector<int>::iterator it;
it = a.begin()+4;
it = advance(a.begin(), 4);
it = next(a.begin(), 4);

  • 位运算的优先级

    • a+b^c
      • 先算 a+b

  • ?=: 运算符优先级

    • (a[i]^b[k]) + i==0?0:dp[i-1][j]
      • 加法优先级大于 ?=:

  • __builtin_popcount

    • 统计一个 int 中 1 的个数

  • 二进制表示中最低位

    • n & (n - 1)

      • 该位运算技巧可以直接将 n 二进制表示的最低位 1 移除

    • n & (-n)

      • 该位运算技巧可以直接获取 n 二进制表示的最低位的 1

  • set、tuple、map 一起使用

1
2
3
4
5
6
7
8
9
10
11
set<tuple<int, int, int>>use;

// 插入元素
use.emplace({1, 2, 3});

// 删除第一个元素
use.erase(use.begin());

//访问
auto p = *use.begin();
int x = std::get<0>(p);

复盘

补题

LeetCode

https://blog.xiang578.com/post/logseq/LeetCode.html

作者

Ryen Xiang

发布于

2024-10-05

更新于

2024-10-05

许可协议

网络回响

评论

关注我

最新文章

×