algo-aha

到某字符的最短距离

• https://leetcode.com/problems/shortest-distance-to-a-character/

vector<int> shortestToChar(string S, char C) {
    // 正反各扫一遍
    // 正向看距离左边e的最小距离，反向看距离右边e的最小距离
    const int N = S.size();
    vector<int> ans(N);
    int idx = -N;
    for (int i = 0; i < N; i++) {
        if (S[i] == C) idx = i;
        ans[i] = i - idx;
    }
    for (int i = idx - 1; i >= 0; i--) {
        if (S[i] == C) idx = i;
        ans[i] = min(ans[i], idx - i);
    }
    return ans;
}

分糖果

• https://leetcode.com/problems/candy/

int candy(vector<int>& ratings) {
    const int N = ratings.size();
    vector<int> candies(N, 1);
    for (int i = 1; i < N; i++) { // 只考虑比左侧分高的
        if (ratings[i] > ratings[i-1]) {
            candies[i] = candies[i-1] + 1;
        }
    }
    for (int i = N - 2; i >= 0; i--) { // 只考虑比右侧分高的
        if (ratings[i] > ratings[i+1]) {
            candies[i] = max(candies[i], candies[i+1] + 1);
        }
    }

    return accumulate(begin(candies), end(candies), 0);
}