LeetCode hints-526互联

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

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

正着推不行就倒着推

结果和顺序无关就可以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

单调栈

分治

求逆序数

排序

快速排序
归并排序
堆排序

bam2hints bamreader directory 2hints