leetcode解题记录(1)

作业太多不想做，把最近在leetcode上做的题稍微总结一下，既然标题写了1，就说明还是想把这个做成一个系列的。

粉刷房子

基础的dp题，从上往下挨个算最小值即可，时间O(n)，空间O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int minCost(vector<vector<int>>& costs) {
           if (costs.empty()) return 0;
    int row = costs.size();
    for (size_t i = 1; i < row; i++) {
        costs[i][0] += min(costs[i - 1][1], costs[i - 1][2]);
        costs[i][1] += min(costs[i - 1][0], costs[i - 1][2]);
        costs[i][2] += min(costs[i - 1][0], costs[i - 1][1]);
    }

    auto& l = costs.back();
    return std::min({l[0], l[1], l[2]});
        
    }
};

字符串中的变味词

这题关键是计算位置无关的哈希,并且要注意一点哈希不一定要是一个数字，只要能代表这个字符串位置无关的特征即可，这里是采用最偷懒的字符计数方法：

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
class Solution {
public:
    bool checkInclusion(string s1, string s2) {
           if (s1.size() > s2.size()) return false;
    std::unordered_map<int, int> pattern, cur_pat;
    for (int i = 0; i < s1.size(); i++) {
        pattern[s1[i]]++;
        cur_pat[s2[i]]++;
    }
    if (pattern == cur_pat) return true;
    for (int i = 1; i < s2.size() - s1.size() + 1; i++) {
        auto iter = cur_pat.find(s2[i - 1]);
        if (iter->second == 1) {
            cur_pat.erase(s2[i - 1]);
        } else {
            cur_pat[s2[i - 1]]--;
        }
        cur_pat[s2[s1.size() - 1 + i]]++;
        if (cur_pat == pattern) {
            return true;
        }
    }
    return false;
    }
};

每日温度

最基础的利用单调栈的题了。时间空间都是O(n)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
            std::vector<pair<int, int>> stack;
    std::vector<int> res(temperatures.size(), 0);
    for (int i = 0; i < temperatures.size(); i++) {
        int x = temperatures[i];
        while (!stack.empty() && stack.back().first < x) {
           // printf("%d < %d\n", stack.back().first, x);
            res[stack.back().second] = i - stack.back().second;
            stack.pop_back();
        }
        stack.push_back({x, i});
    }
    return res;
    }
};

LRU缓存

由于LRU(最近最少使用)算法涉及到对列表的随机增删，因此这里使用链表作为数据的载体，哈希表作为快速查询的工具使用，这里使用了C++的std::list,要十分注意其迭代器失效问题：

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <cstdio>
#include <iostream>
#include <list>
#include <unordered_map>
#include <utility>
//test
using namespace std;

class LRUCache {
   public:
    LRUCache(int capacity) { this->cap = capacity; }

    int get(int key) {
        auto iter = this->cache.find(key);
        if (iter == cache.end()) {
            return -1;
        }
        auto value = iter->second->second;
        list.erase(iter->second);
        list.insert(list.begin(), {key, value});
        cache[key] = list.begin();
        return value;
    }

    void put(int key, int value) {
        //找到有没有这个键对应的值
        auto iter = this->cache.find(key);
        if (iter == cache.end()) {
            //没有找到就插入
            this->list.insert(list.begin(), {key, value});
            //更新迭代器
            this->cache[key] = list.begin();
            //如果超了就移除最后一个
            if (list.size() > cap) {
                //获取键的值
                auto last = list.back().first;
                list.pop_back();
                //擦除
                cache.erase(last);
            }
        } else {
            //找到了,擦除旧的，并挪动到头部
            list.erase(iter->second);
            this->list.insert(list.begin(), {key, value});
            this->cache[key] = list.begin();
        }
    }

   private:
    std::list<pair<int, int>> list;
    std::unordered_map<int, std::list<pair<int, int>>::iterator> cache;
    int cap;
};