发表于

  • 最值

  • 二分查找（解的值域范围具有单调性，小于x的值范围都符合，大于x的值范围都不符合）

  • 动态规划

  • 二分查找

  • 使……最大值尽可能小

  • 前缀和

  • 子数组

  • 动态规划

  • 将数组分割为割为m段，求……

  • 滑动窗口
    • 长度固定的子数组

数值范围

int：4字节，32位，最大值:$2^{31}-1=2147483647$，最小值$-2147483648$。

$105$的数据范围不能用$O(n2)$解法
$10^9$的时间复杂度不行

数据范围 复杂度
$10^5$ $nlog(n)$

区间

对于两个区间$[S_1,e_1)$和$[S_2,e_2)$，如果两者没有交集，则此时应当满足$s_1 \ge e_2$或者$s_2 \ge e_1$，即如果$s_1 <e_2 且 s_2<e_1$，两者会产生交集。

num/mid上取整
(num-1)/mid+1 (num+mid-1)/mid

K小问题

k 小问题有三种解法：按位确定答案（多用于字符串和二进制数），用堆维护当前最小答案（用于 kkk 比较小的情况），二分（用于 kkk 比较大的情况）。

字符串

出现的大小写字母集合

因此可以利用二进制位来进行标记，lower标记字符中出现过小写英文字母，upper标记字符中出现过大写英文字母。如果满足lower=upper，则认为字符串中所有的字符都满足大小写形式同时出现。

1763. 最长的美好子字符串

字符是否出现
1684. 统计一致字符串的数目 - 力扣（LeetCode）

数组

「长度固定的子数组」就要想到滑动窗口对角线上是否放置元素

  • record.count(x-y)

  • record.count(x+y)

出现超过一半的数字

找出数组中出现次数超过数组长度一半的数字

169. 多数元素

  1. 哈希表记录出现次数

  2. 排序后取中位数

  3. 抵消法

  4. 快排取中位数

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int cnt=0,pre=nums[0];
        for(int num:nums){
            if(cnt==0){
                pre=num;
            }
            if(num==pre){
                cnt++;
            }else{
                cnt--;
            }
        }
        return pre;
    }
};

动态规划

动态规划的题目分为两大类，一种是求最优解类，典型问题是背包问题，另一种就是计数类，比如这里的统计方案数的问题，它们都存在一定的递推性质。「将数组分割为割为m  段，求……」是动态规划题目常见的问法。410. 分割数组的最大值

二分查找

适合求解具有单调最优性质的题目

「使……最大值尽可能小」是二分搜索题目常见的问法。410. 分割数组的最大值

预处理回文数

枚举回文数左半部分

vector<int> pal;

auto init=[]{
    // 严格按顺序从小到大生成所有回文数（不用字符串转换）
    for(int base=1;base<=10000;base*=10){
        //生成奇数长度回文数
         for(int i=base;i<base*10;i++){
             int x=i;
             for(int t=i/10;t;t/=10){
                 x=x*10+t%10;
             }
             pal.push_back(x);
         }

         //生成偶数长度回文数
         if(base<=1000){
             for(int i=base;i<base*10;i++){
                 int x=i;
                 for(int t=i;t;t/=10){
                     x=x*10+t%10;
                 }
                 pal.push_back(x);
             }
         }
    }
    pal.push_back(1'000'000'001); // 哨兵，防止下面代码中的 i 下标越界
    return 0;
}();