algo-aha

一组数最多改一个数，能否变成非递减（<=）

• https://leetcode.com/problems/non-decreasing-array

bool checkPossibility(vector<int>& nums) {
    // 贪心法。找到违反<=关系的x[i]>x[i+1]，优先改小x[i]：x[i]=x[i+1]。
    // （后面是否满足<=待后面循环去检查，前面满足要还需x[i-1]<=x[i+1]）
    // 无法改小时改大x[i+1]：x[i+1]=x[i]。
    int cnt = 0;
    for (int i = 0; i + 1 < nums.size(); i++) {
        if (nums[i] <= nums[i+1]) continue;
        if (cnt++ > 0) return false;
        // 优先改小x[i]
        if (i-1 < 0 || nums[i-1] <= nums[i+1]) {
            nums[i] = nums[i+1];
        } else {
            nums[i+1] = nums[i];
        }
    }
    return true;
}

有多少相差k的不同数对

• https://leetcode.com/problems/k-diff-pairs-in-an-array

int findPairs(vector<int>& nums, int k) {
    if (k < 0) return 0;
    unordered_map<int, int> cnt;
    for (int num : nums) cnt[num]++;

    int ans = 0;
    for (auto &e : cnt) {
        if (k == 0) ans += e.second >= 2;
        else ans += cnt.count(e.first + k);
    }
    return ans;
}

最多连续数的子集

• https://leetcode.com/problems/longest-consecutive-sequence/

int longestConsecutive(vector<int>& nums) {
    // 把数都塞到集合中，然后取出无x-1的数x
    // 看后序的x+1,x+2,...是否也在集合中
    unordered_set<int> st;
    for (int num : nums)
        st.insert(num);

    int ans = 0;
    for (int num : nums) {
        if (st.count(num - 1)) continue;
        int len = 1;
        while (st.count(num + len))
            len++;
        ans = max(ans, len);
    }
    return ans;
}

每个数最多可重复两次，把多的去掉

• https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/

int removeDuplicates(vector<int>& nums) {
    const int N = nums.size(), k = 2;
    if (N <= k) return N;
    
    int out = k;
    for (int in = k; in < N; in++) {
        if (nums[in] != nums[out-k]) {
            nums[out++] = nums[in];
        }
    }
    return out;
}