lc-day20

发表于

748. 最短补全词

题目

简单签到题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    string shortestCompletingWord(string licensePlate, vector<string>& words) {
        unordered_map<char, int> p;
        for(int i = 0; i < licensePlate.size(); i++){
            if(licensePlate[i] == ' ') continue;
            if(licensePlate[i] >= '0' && licensePlate[i] <= '9') continue;
            p[tolower(licensePlate[i])]++;
        }
        int idx = -1, len = 1010;
        for(int i = 0; i < words.size(); i++){
            unordered_map<char, int> pp;
            for(auto c : words[i]){
                pp[c]++;
            }
            bool flag = false;
            for(auto &[c, n] : p){
                if(n > pp[c]) {
                    flag = true;
                    break;
                }
            }
            if(!flag) {
                if(len > words[i].size()) {
                    len = words[i].size();
                    idx = i;
                }
            }
        }
        return words[idx];
    }
};

js版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * @param {string} licensePlate
 * @param {string[]} words
 * @return {string}
 */
var shortestCompletingWord = function(licensePlate, words) {
    const p = new Array(26).fill(0);
    for(const ch of licensePlate){
        if(/^[a-zA-Z]+$/.test(ch)){
            p[ch.toLowerCase().charCodeAt() - 'a'.charCodeAt()]++;
        }
    }
    let idx = -1;
    for(let i = 0; i < words.length; i++){
        const c = new Array(26).fill(0);
        for(let j = 0; j < words[i].length; j++){
            const ch = words[i][j];
            c[ch.toLowerCase().charCodeAt() - 'a'.charCodeAt()]++;
        }
        let ok = true;
        for(let j = 0; j < 26; j++){
            if(c[j] < p[j]) {
                ok = false;
                break;
            }
        }
        if(ok && (idx < 0 || words[i].length < words[idx].length))
        idx = i;
    }
    return words[idx];
};

714. 买卖股票的最佳时机含手续费

题目

为什么要minprice-fee 当我买完一次股票后, 如果它紧接着又上涨了, 那后面就不用出手续费了, 直到这个上涨区间断掉, 手续费只用扣掉一次, 这样就形成了局部最优解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int result = 0;
        int minprice = prices[0];
        for(int i = 1; i < prices.size(); i++){
            //新的买入, 实际操作就是存储这个最低价格, 
            //并没有真正的
            if(prices[i] < minprice) minprice = prices[i];

            //亏本价, 继续持有
            if(prices[i] > minprice && prices[i] <= minprice + fee) 
            continue;

			//如果大于最大价+手续费,  买入并且将minprice-fee
            if(prices[i] > minprice + fee) {
                result += prices[i] - minprice - fee;
                minprice = prices[i] - fee;
            }
        }
        return result;
    }
};