LeetCode hints

通过样例得到一些通用性质，从单点出发结合要求什么，初步判断可以应用什么算法，之前见没见过类似的，见过就转换成之前会做的，怎么转换需要思考。

想不出来可以先出朴素的算法，然后才考虑优化

正着推不行就倒着推

结果和顺序无关就可以sort数组，复杂的需要sort index(由小到大排序且保持原序)

int ids[n];
iota(ids, ids + n, 0);
sort(ids, ids + n, [&](int i, int j) { return nums[i] < nums[j]; });

如果时间要求高，可以空间换时间，map用起来

switch比hashmap要快，int数组比map要快(但要注意+EXT防止越界)

枚举：

遇到影响全局的操作，一般会想到枚举操作次数。
非0即1的check，只check0或者1就可以了。

连续数组考虑双指针(同向，相向)，前缀和

双指针

• 同向双指针：
• 滑动窗口(遍历右指针，然后固定右指针移动左指针)
• 单调性：从满足到不满足/从不满足到满足，才能用双指针的滑动窗口
• 209, 713，3
• 相向双指针:
  • 167要求单调；15，11，42

前缀和

• 前缀和不取当前元素
• 不一定求数组sum前缀和，要灵活变通，如1248:可以求奇数个数和
• 前缀异或和为0，表示两个数相等

二分

数组有序，答案有单调性，可以二分

看到「最大化最小值」或者「最小化最大值」就要想到二分答案

贪心

• 局部最优，可以推出全局最优
• 如果 k=0，k=1，应该如何选择呢？（思考问题可以先从一些简单的情况开始）

动态规划

DFS

两种写法

• 选/不选：全部结果在最后的递归统一出

  • class Solution {
    public:
        int beautifulSubsets(vector<int>& nums, int k) {
            int cnt[3001]{};
            int ans=-1;
            function<void(int)> dfs = [&](int i){
                if(i==nums.size())
                {
                    ans++;
                    return;
                }
                dfs(i+1);
                int x = nums[i] + k;
                if(cnt[x-k]==0 && cnt[x+k]==0)
                {
                    cnt[x]++;
                    dfs(i+1);
                    cnt[x]--;
                }
            };
            dfs(0);
            return ans;
        }
    };

• 遍历起始点：每个递归都是一次可行解

  • class Solution {
    public:
        int beautifulSubsets(vector<int>& nums, int k) {
            int cnt[3001]{};
            int ans=-1;
            function<void(int)> dfs = [&](int j){
                ans++;
                if(j==nums.size())return;
                for(int i=j;i<nums.size();i++)
                {
                    int x = nums[i] + k;
                    if(cnt[x-k]==0&&cnt[x+k]==0)
                    {
                        cnt[x]++;
                        dfs(i+1);
                        cnt[x]--;
                    }
                }
            };
            dfs(0);
            return ans;
        }
    };
    

     

BFS

单调栈

分治

• 求逆序数

排序

• 快速排序
• 归并排序
• 堆排序