算法小技巧总结

2020/02/05 Algorithm

本文总结在刷题和工作中遇到的各种算法的小技巧。


Bit Manipulation 位操作

首先记住:尽量对每一个位操作使用括号

这个非常重要,因为位操作符的优先级通常非常低。如果不用括号,非常容易出错。例如,y = x & -x 错误,要写成 y = x & (-x)

(x >> i) & 1

将 x 的第 i 位移动到最右边的第 0 位,再判断它的值。这经常用来判断 x 的第 i 位是 1 还是 0。

x | (1 << i)

将 x 的第 i 位(从右边开始)设置为 1,其余不变。同理还有类似的:

  • 把第 i 位设置成 0x & !(1 << i),即 AND 一个第 i 位是 0 其余位都是 1 的整数;
  • flip 第 i 位:这个有点麻烦,个人感觉,简单的方法是,首先判断 x 的第 i 位是 1 还是 0,然后再用上面这两种方法将该位设置成 1 或者 0。

x & (-x)

把 x 的除了最低位的1以外的其它所有位全部清零。这个通常应用到 BIT 二叉检索树中。例如,用 x += (x & (-x)),用于每次在最低位的 1 处加 1。

x & (x - 1)

把 x 的最低位的 1 清零,其余不变。这和上面的x & (-x)正好相反。不过注意,因为这里用到了 x -1,所以当x = INT_MIN 或 0 时,该式子不成立,因此这两个数字需要单独判断。

显然,该式子可以用来判断一个数是不是2的幂次方,例如 2,4,8,16,32 等等,因为这种数只有 1 位是 1,其余都是 0,因此,(x & (x-1)) == 0

注意,该式子在使用时候一定记得在最外面加上括号,例如 (x & (x-1)) == 0 是正确的,而 x & (x-1) == 0 是错误的。

~x

x 的 flip,即把所有的位都反过来。注意它和 -x 不同。

-x = ~x+1

即,相反数其实就等于把数 flip 后加 1。这个性质看似没啥用,不过可以用于“不用减号来计算两个整数的差 a - b ” 这个问题。

异或操作符 ^ 的几个性质

x ^ y = y ^ x

交换律。

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

结合律。

x ^ y = z,那么 x ^ z = y,并且 y ^ z = x

这条非常关键,其实很容易验证是正确的。

x ^ x = 0, 以及 0 ^ x = x ^ 0 = x

一个数异或0还是它本身。相应的,x ^ 1 = ~x,即一个数异或 1 就变成了把它的全部位取反。

x ^ y ^ x = y

即,如果两个数相同,那么它们之间的异或因为等于 0,就被消去了。因此,它可以用来排除成对出现的元素的影响。例如,一个数组所有数字都出现 2 次,只有一个数出现了 1 次,要求找出这个数。这就可以用最后这个性质来解决。

使用二维点作为 hashmap 的 key 值

如何将一个二维的 int 坐标点 {x,y} 作为 hashmap 的 key 值?通常 pair<int, int> 并不能作为 std::map 或者 set 的 key 值。

普遍性做法:自定义 hash,或者使用 boost_combine

  • https://en.cppreference.com/w/cpp/utility/hash
  • https://stackoverflow.com/questions/4870437/pairint-int-pair-as-key-of-unordered-map-issue/4870467

上面链接给出了一些例子。标准方法是,先用 std::hash 分别生成这个 pair 中两个元素的hash 值 h1 和 h2,然后,有两种方法生成这个pair的hash:

  • 使用 h1 ^ (h2 « 1),这个结果就是最终的hash
  • 使用boost::hash_combine()函数,参见下面代码。

感觉上,使用 boost 要更加 general 一些,适用于几乎所有类型,参见下面代码。

namespace std {
    
template <class T, class U>
struct hash< std::pair<T, U> > {
    size_t operator()( std::pair<T, U> const &p) const {
        std::size_t _1 = std::hash<T>()(p.first);
        std::size_t _2 = std::hash<T>()(p.second);
        std::size_t retval = 0;
        boost::hash_combine(retval, _1);
        boost::hash_combine(retval, _2);
        return retval;
    }
};

注意,上面代码是直接在 namespace std 中定义这个 hash 结构体。这样的一个好处是,使用该 hash 定义 hashmap 时和普通时候完全相同:

unordered_map<std::pair<int, int>, double> mp;

即它省略了定义 hashmap 时的第三个参数:struct 类型名称。如果不是定义在 std 空间的话,第三个参数则不能省略。例如,如果在其它的 namespace A 中(或者直接没有在任何 namespace 中)定义了 hash 结构体,那么使用时就必须是:

unordered_map<std::pair<int, int>, double, A::hash_struct_name> mp;

将两个短的 int 合成为一个 int

上面的普遍性做法比较繁琐,在解决一个小问题时显然不太实用。如果 x 和 y 不太大,例如小于 2^16 = 65536,那么其实可以直接用一个 int 作为 key 值,将 x 放高 16 位,y 放低 16 位就行了。最简单且效率最高的方法。

auto encode = [](int x, int y) {
    return (x << 16) | y;
};
auto decode = [](int key) {
    int x = (key >> 16);
    int y = (key & 0xFFFF);
    return vector<int>({x, y});
};

当然,如果更懒的话,直接用一个 hashmap 保存 key -->{x,y} 映射就行了,这样连 decode() 函数都不需要了,空间换时间。

优点 转换方法简单;最终使用了int作为key值,int hash的复杂度非常低。另外位操作的复杂度也非常低,因此该方法效率最高。

缺点 只能用于x和y不太大的情况,不过2^16其实已经是很大的值了,因此该方法通常都能用。

将矩阵行列的而为坐标转换成一个int

如果 {x, y} 是来自矩阵的行列值,那么它们通常很小。此时显然可以用 key = x * n + y 将其转换成一维坐标后作为 key 值,这里 n 是矩阵宽度。key值转二维也很简单了:x = key / n; y = key % n

和上个方法相比,该方法其实有些多余,并且时间复杂度高很多,因为它需要用乘除和取余数。因此,它通常仅用于某些特殊问题本来就需要用像 x * n + y 这种值的时候。

使用long long int 或者普通的int

通常可以将两个普通的 int32 连起来成为一个 long long int,这就可以作为key值了。例如把 x 放在 key 的高 32 位,y 放在低 32 位。

auto encode = [](int x, int y) {
    return ((long long)(x) << 32) | y;
};
auto decode = [](long long key) {
    int x = int(key >> 32);
    int y = int(key & 0xFFFFFFFFLL); // LL is for long long type
    return vector<int>({x, y});
};

优点 位操作效率高;适用于所有 int 类型,几乎不用担心越界(当然如果 x 和 y 本身就是 long long 的话就没办法了,用下面的 string 方法吧)

缺点 空间消耗大;long long hash 显然还是比普通 int hash 的复杂度高一些。

使用 string 作为 key 值

这个最简单了,直接用 std::string 将 x 和 y 连起来就行了,中间随意用一个分隔符就行。

string key = to_string(x) + " " + to_string(y)

将 string 转换成二维坐标时,可以先确定空格符的位置,然后再 split。例如:

auto pos = key.find_first_of(' ');
x = stoi(key.substr(0, pos));
y = stoi(key.substr(pos + 1));

当然,也可以用 istringstream 来 split string,不过效率会低一点。

优点 适用于所有类型,完全不用担心越界,即便 x 和 y 本身就很大(例如本身就是 long long);可以用于坐标值不是整数的情况,例如有些时候会用字符作为坐标值。

缺点 可以算是时间复杂度最高的方法,因为 string hash 相对最复杂,当然远不如 int hash。

取余数计算Modulo

(A + B) % C = (A % C + B % C) % C
(A - B) % C = (A % C - B % C) % C
(A * B) % C = ((A % C) * (B % C)) % C

链表 Linked List

一次遍历就可以获取链表中间的位置

设计快慢指针,快指针是慢指针的两倍就行了。

数组Vector

O(1) 时间删除 vector 中的某一个值 i

一般情况下是无法在 O(1) 时间删除任意一个vector中的值 i 的。一种特殊做法是,将 vec[i] 和 vec.back() 互换,然后 vec.pop_back()。这虽然会改变之前的 vec.back() 元素的位置,但只有这一个元素的位置改变了,其余都不变。这已经是影响最小的了。这可以结合另一个 hashmap 使用,它存储数组元素 –> 位置的映射,那么就只需要修改 map 中的 vec.back() 元素的位置到新的位置(其实就是 i)即可。整个流程的时间就是 O(1)。

Search

    Table of Contents