排序

去重排序

vector + sort + unique

1
2
sort(a.begin(), a.end());
a.erase((a.begin(), a.end()), a.end);

桶排序

当需要排序的值有许多重复值时，即数组大小远大于数据的大小时

1
2
3
4
5
6
7
8
for (int i = 1; i <= n; i++)
{
    cin >> x;
    a[x]++;
}
for (int i = 1; i <= n; i++)
    for (int j = 0; j < a[i]; j++)
        cout << i << ' ';

结构体排序

当一个元素有多个值且明确要求有先后顺序时
在结构体里重载比较运算符，自定义sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct book
{
    int a, b, c;
    bool operator>(const book &v) const
    {
        if (a == v.a && b == v.b)
            return c > v.c;
        else if (a == v.a)
            return b > v.b;
        else
            return a > v.a;
    } // 按a,b,c排序
};
sort(a + 1, a + 1 + n, greater<book>()); // 降序

二分

二分查找

1
2
3
4
5
6
7
8
9
//先确定l,r和check()函数，注意l,r的选取确保不会出现死循环
    while (l + 1 != r)
    {
        mid = (l + r) / 2;
        if (check())
            l = mid; // r = mid
        else
            r = mid;
    }

二分答案

位运算

基本运算符

  • &

两个位都为1时，结果位为1，否则为0

做&运算时结果不会变大

  • |

两个位有一个为1时，结果位为1，否则为0

做|运算时结果不会变小

  • ^

两个位不相同时，结果位为1，否则为0
x ^ y= y^ x
(x ^ y) ^ z = x ^ ( y ^ z)
x ^ x = 0
x ^ 0 = x
x ^ y = z => z ^ y = x

  • ~

0->1 , 1->0（非符号位）

  • <<(>>)

将一个数的二进制向左/高位移动指定位数(不带符号位)，低位补0

左移操作<=>对原数进行乘2的幂次方 – 13<<3 == 13 * 2 *2 *2

（将一个数的二进制向右/低位移动指定位数(不带符号位)，高位补0

右移操作<=>对原数除以2的幂次方）

运算操作

  1. 判断数字奇偶性
    x & 1 = 1 => 奇数
    x & 1 = 0 => 偶数
  2. 获取二进制的第i位
    x>>i&1
  3. 修改二进制的第i位为1/0
    x | (1<<i) 1
    x & ~(1<<i) 0
  4. 判断一个数是否为2的幂次方
    x & (x-1) 结果为0，则是
  5. 获取二进制中最低位的1
    lowbit(x) = x & (-x)
    若x = (010010),则lowbit(x) = (000010)

双指针