zkkKillua's Blog
0%

发表于 更新于 分类于

框架

1
2
3
4
5
6
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {

    }
};

1. 完全背包

背包容量：amount
物品价值：coins
物品体积：coins
恰好达到价值amount
dp[i][j]原本记录前i种物品装入容量为j的背包能达到的最大价值。但是此处由于容量就代表了价值，所以dp[i][j]此处可以记录前i种金额装入容量为j的背包（达到j的价值）需要的最少的钱的张数。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int maxVal = 0x3f3f3f3f;
        int n = coins.size();
        vector<int> dp(amount + 1, maxVal);
        dp[0] = 0;

        for (int i = 0; i < n; i++) {
            for (int j = coins[i]; j <= amount; j++) {
                dp[j] = min(dp[j], dp[j - coins[i]] + 1);
            }
        }

        if (dp[amount] >= maxVal)
            return -1;
        else
            return dp[amount];
    }
};
阅读全文 »

发表于 更新于 分类于

框架

1
2
3
4
5
6
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        
    }
};

1. 递归

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
class Solution {
public:
    void recursion(string s, int total, int cur) {
        if (total == n) {
            while (cur > 0) {
                s += ')';
                cur--;
            }
            vec.push_back(s);
            return;
        }
        
        recursion(vec, s + '(', total + 1, cur + 1, n);
        if (cur > 0)
            recursion(vec, s + ')', total, cur - 1, n);
    }

    vector<string> generateParenthesis(int n) {
        vec.clear();
        this->n = n;

        recursion(ans, "(", 1, 1);

        return ans;
    }

private:
    vector<string> vec;
    int n;
};

发表于 更新于 分类于

框架

1
2
3
4
5
6
class Solution {
public:
    int movingCount(int m, int n, int k) {

    }
};

1. BFS

BFS到相邻节点，判断要求是否超过k。
时间O(mn)，空间由于需要一个网格记录是否访问过，也是O(mn). 

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
class Solution {
public:
    int movingCount(int m, int n, int k) {
        int id[2] = {0, 1};
        int jd[2] = {1, 0};
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        queue<pair<int, int>> q;
        q.push(make_pair(0, 0));
        visited[0][0] = true;
        int ans = 1;

        while (!q.empty()) {
            pair<int, int> cur = q.front();
            q.pop();
            int i = cur.first, j = cur.second;
            for (int mv = 0; mv < 2; mv++) {
                if (i + id[mv] < m && j + jd[mv] < n && !visited[i + id[mv]][j + jd[mv]]) {
                    int sum = 0;
                    int loci = i + id[mv], locj = j + jd[mv];
                    while (loci > 0) {
                        sum += loci % 10;
                        loci /= 10;
                    }
                    while (locj > 0) {
                        sum += locj % 10;
                        locj /= 10;
                    }
                    if (sum <= k) {
                        q.push(make_pair(i + id[mv], j + jd[mv]));
                        ans++;
                    }
                    visited[i + id[mv]][j + jd[mv]] = true;
                }
            }
        }

        return ans;
    }
};

发表于 更新于 分类于

框架

1
2
3
4
5
6
class Solution {
public:
    int trap(vector<int>& height) {
        
    }
};

1. 按列计算+dp

首先想到的是计算出一个“坑”，然后算这个坑可以储存多少水。
但实际上也可以按列计算，计算每一列可以储存多少水，然后求和。
算每一列存水的数量的方法就是找到该位置左侧的最大值和右侧的最大值，从而围成一个“坑”。
所以：遍历每一个柱子，然后查找其左侧的最大值和右侧的最大值，时间复杂度是O(n^2)。
可以使用记忆化搜索，leftIndex[i]和rightIndex[i]分别记录第i个元素左侧的最大高度的索引和右侧最大高度的索引。
转移方程为leftIndex[i] = i-1 || leftHeight[i-1]
这样，时间复杂度就降低为O(n)，而空间复杂度升高为O(n)。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        int ans = 0;

        vector<int> leftIndex(n, 0), rightIndex(n, n - 1);
        for (int i = 1; i < n - 1; i++) {
            leftIndex[i] = height[leftIndex[i - 1]] >= height[i - 1] ? leftIndex[i - 1] : i - 1;
            rightIndex[n - i - 1] = height[rightIndex[n - i]] >= height[n - i] ? rightIndex[n - i] : n - i;
        }

        for (int i = 1; i < n - 1; i++) {
            int minHeight = min(height[leftIndex[i]], height[rightIndex[i]]);
            if (minHeight > height[i])
                ans += minHeight - height[i];
        }

        return ans;
    }
};
阅读全文 »

发表于 更新于 分类于

框架

1
2
3
4
5
6
class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {

    }
};

1. 先转置后对称

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                swap(matrix[i][j], matrix[j][i]);
      
        for (int i = 0; i < n; i++)
            for (int j = 0; j <= (n - 1) / 2; j++)
                swap(matrix[i][j], matrix[i][n - 1 - j]);
    }
};
阅读全文 »

发表于 更新于 分类于

框架

1
2
3
4
5
6
class Solution {
public:
    int minDistance(string word1, string word2) {
        
    }
};

1. dp

设dp[i][j]代表word1[0~i]与word2[0~j]部分需要的最少的操作数。
设dp[i][j]代表word1的前i个字符和word2的前j个字符部分需要的最少操作数。（这样要简单得多）
状态转移方程为：
dp[i][j] = dp[i - 1][j - 1], 当word1[i - 1] == word2[j - 1]时。
dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1, 当word1[i - 1] != word2[j - 1]时。
上述情况需要由三种状态转移而来，分别是：修改，删除word1[i-1]，添加word2[j-1]。 

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
class Solution {
public:
    int minDistance(string word1, string word2) {
        int n1 = word1.length(), n2 = word2.length();
        if (n1 == 0 || n2 == 0)
            return n1 + n2;

        int **dp = new int*[n1 + 1];
        for (int i = 0; i < n1 + 1; i++)
            dp[i] = new int[n2 + 1]{0};
        
        for (int i = 0; i <= n1; i++)
            dp[i][0] = i;
        for (int i = 0; i <= n2; i++)
            dp[0][i] = i;
        
        for (int i = 1; i <= n1; i++) {
            for (int j = 1; j <= n2; j++) {
                if (word1[i - 1] == word2[j - 1])
                    dp[i][j] = dp[i - 1][j - 1];
                else {
                    int temp = min(dp[i - 1][j], dp[i][j - 1]);
                    dp[i][j] = min(temp, dp[i - 1][j - 1]) + 1;
                }
            }
        }

        int ans = dp[n1][n2];
        for (int i = 0; i < n1 + 1; i++)
            delete []dp[i];
        delete []dp;
        return ans;
    }
};

发表于 更新于 分类于

框架

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class LFUCache {
public:
    LFUCache(int capacity) {

    }
  
    int get(int key) {

    }
  
    void put(int key, int value) {

    }
};

/**
 * Your LFUCache object will be instantiated and called as such:
 * LFUCache* obj = new LFUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

1. 模拟

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
struct node {
    node (int k = 0, int v = 0, int f = 0) {
        key = k;
        value = v;
        freq = f;
    }

    int key;
    int value;
    int freq;
};

class LFUCache {
public:
    LFUCache(int capacity) {
        key_table.clear();
        freq_table.clear();
        this->capacity = capacity;
        minFreq = 0;
    }
  
    int get(int key) {
        if (key_table.count(key) == 0)
            return -1;
      
        int val = key_table[key]->value, freq = ++(key_table[key]->freq);
        freq_table[freq].push_front(*(key_table[key]));
        freq_table[freq - 1].erase(key_table[key]);
        if (freq_table[freq - 1].empty()) {
            // freq_table.erase(freq - 1);
            if (minFreq == freq - 1)
                minFreq = freq;
        }
        key_table[key] = freq_table[freq].begin();

        return val;
    }
  
    void put(int key, int value) {
        if (capacity == 0)
            return;

        if (key_table.count(key) == 1) {
            if (get(key) != value)
                key_table[key]->value = value;
        } else {
            if (key_table.size() == capacity) {
                key_table.erase(freq_table[minFreq].back().key);
                freq_table[minFreq].pop_back();
                // if (freq_table[minFreq].empty())
                    // freq_table.erase(minFreq);
            }
            freq_table[1].push_front(node(key, value, 1));
            key_table[key] = freq_table[1].begin();
            minFreq = 1;
        }
    }
private:
    unordered_map<int, list<node>::iterator> key_table;
    unordered_map<int, list<node> > freq_table;
    int minFreq;
    int capacity;
};

/**
 * Your LFUCache object will be instantiated and called as such:
 * LFUCache* obj = new LFUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */
阅读全文 »

发表于 更新于 分类于

框架

1
2
3
4
5
6
class Solution {
public:
    int myAtoi(string str) {
        
    }
};

1. 直接模拟

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
class Solution {
public:
    int myAtoi(string str) {
        int n = str.length();
        int flag = 1;
        long long ans = 0;
        //判断是否溢出的时候可以比较int ans和INT_MAX / 10的关系，这样就不会ans * 10溢出了。
        bool hasNumber = false;

        for (int i = 0; i < n; i++) {
            if (str[i] != ' ' && str[i] != '+' && str[i] != '-' && !(str[i] >= '0' && str[i] <= '9') && !hasNumber)    //数字前有其他字符
                return 0;
            else if (!(str[i] >= '0' && str[i] <= '9') && hasNumber)    //数字后有其他字符
                return flag * ans;
            else if (str[i] == '-' || str[i] == '+') {   //数字符号
                if (i + 1 < n && (str[i + 1] >= '0' && str[i + 1] <= '9')) {
                    hasNumber = true;
                    if (str[i] == '-')
                        flag = -1;
                } else
                    return 0;
            } else if (str[i] >= '0' && str[i] <= '9') {      //是数字
                hasNumber = true;
                ans = ans * 10 + (str[i] - '0');
                if (flag == 1 && ans >= pow(2, 31) - 1)
                    return pow(2, 31) - 1;
                else if (flag == -1 && ans >= pow(2, 31))
                    return -pow(2, 31);
            }
        }

        return flag * ans;
    }
};

2. 自动机

阅读全文 »

发表于 更新于 分类于

框架

1
2
3
4
5
6
class Solution {
public:
    void gameOfLife(vector<vector<int>>& board) {

    }
};

1. 额外空间直接遍历

时间O(mn)，空间O(mn)。 

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
class Solution {
public:
    void gameOfLife(vector<vector<int>>& board) {
        vector<vector<int>> ans(board);
        int m = board.size(), n = board[0].size();
        int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
        int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int live = 0;
                for (int k = 0; k < 8; k++) {
                    int x = i + dx[k], y = j + dy[k];
                    if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 1)
                        live++;
                }
                if (board[i][j] == 1) {
                    if (live < 2)
                        ans[i][j] = 0;
                    else if (live == 2 || live == 3)
                        ans[i][j] = 1;
                    else if (live > 3)
                        ans[i][j] = 0;
                } else if (board[i][j] == 0 && live == 3)
                    ans[i][j] = 1;
            }
        }

        board = ans;
    }
};
阅读全文 »

发表于 更新于 分类于

框架

1
2
3
4
5
6
class Solution {
public:
    vector<int> maxDepthAfterSplit(string seq) {

    }
};

1. 直接模拟

首先遍历一遍获得最大深度maxDepth，若想令max(depth(A), depth(B))的可能取值最小，则结果必为(maxDepth+1)/2。
因此再次遍历序列，将深度小于最大深度一半的括号都分到A类中，之后的括号除去与A左括号匹配的右括号之外，其余全部放入B类中。
时间复杂度O(n)。 

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
class Solution {
public:
    vector<int> maxDepthAfterSplit(string seq) {
        int n = seq.length();
        int maxDepth = 0, curDepth = 0;
        for (int i = 0; i < n; i++) {
            if (seq[i] == '(')
                curDepth++;
            else {
                maxDepth = maxDepth >= curDepth ? maxDepth : curDepth;
                curDepth--;
            }
        }

        int halfDepth = (maxDepth + 1) / 2;
        vector<int> ans(n);
        for (int i = 0; i < n; i++) {
            if (seq[i] == '(') {
                curDepth++;
                if (curDepth <= halfDepth)
                    ans[i] = 0;
                else 
                    ans[i] = 1;
            }
            else {
                if (curDepth <= halfDepth)
                    ans[i] = 0;
                else
                    ans[i] = 1;
                curDepth--;
            }
        }

        return ans;
    }
};