算法基础

二分查找

https://leetcode.cn/problems/binary-search/?envType=problem-list-v2&envId=binary-search

非递归

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) return mid;
            if (nums[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return -1;
    }
};

寻找旋转数组最小值

有时候循环条件是left < right，有时候是left <= right，具体看题目要求。 数组长度为2时，left == mid，所以left必须left = mid + 1，否则会死循环。 如果希望right不会比left小，那么right = mid，否则right = mid - 1。

class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0;
        int right = nums.size() - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] > nums.back()) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return nums[left];
    }
};

前缀和

CF1426D：给一个长为n的序列，求至少插入几个数，使得连续子序列的和均不为0

解：求前缀和，若出现2个相等的前缀和prefix[i]、prefix[j]，则说明i-1到j之间的数和为0

// Copyright (c) 2021, Jiang Yinzuo. All rights reserved.

#include <cstdio>
#include <unordered_set>
using std::unordered_set;

long long a[200009];

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%lld", a + i);
    }

    unordered_set<long long> prefixs;
    prefixs.insert(0);
    long long prefix = 0;
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        prefix += a[i];
        if (prefixs.find(prefix) != prefixs.end()) {
            ++ans;
            prefixs.clear();
            prefix = a[i];
            prefixs.insert(0);
        }
        prefixs.insert(prefix);
    }
    printf("%d\n", ans);
    return 0;
}

滑动窗口 [interview]

Leetcode

双指针 [interview]

Leetcode 盛水最多的容器

单调栈 [interview]

接雨水

维护一个单调递减的栈

去除重复字母