发表更新算法2 分钟读完 (大约345个字)

LeetCode 524「通过删除字母匹配到字典里最长单词」

算法内容

本文件实现 LeetCode 524「通过删除字母匹配到字典里最长单词」的一种预处理做法。目标是在字典中找出可以由字符串 s 删除若干字符得到的最长单词；若长度相同，返回字典序最小者。

代码先构建 f[i][c]，表示从位置 i 开始往后字符 c 第一次出现的位置，不存在则为 m。匹配某个候选词时，只需按字符不断跳到下一个出现位置，如果任一字符不存在则匹配失败。这样可以把每个单词的匹配成本降为 O(单词长度)，预处理为 O(26m)。文件中带有打印矩阵的调试输出和一个示例调用。

算法实现

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
from typing import List, Tuple, Dict
class Solution:
    def findLongestWord(self, s: str, dictionary: List[str]) -> str:
        m = len(s)
        f = [[0] * 26 for _ in range(m)]
        f.append([m] * 26)
        print([chr(ord('a')+i) for i in range(26)])
        for i in range(m - 1, -1, -1):
            print('[', end='')
            for j in range(26):
                if ord(s[i]) == j + 97:
                    f[i][j] = i
                else:
                    f[i][j] = f[i + 1][j]
                print("'{}', ".format(f[i][j]), end='')
            print()
        res = ""
        for t in dictionary:
            match = True
            j = 0
            for i in range(len(t)):
                if f[j][ord(t[i]) - 97] == m:
                    match = False
                    break
                j = f[j][ord(t[i]) - 97] + 1
            if match:
                if len(t) > len(res) or (len(t) == len(res) and t < res):
                    res = t
        return res

print(Solution().findLongestWord("abpcplea", ["ale","apple","monkey","plea"]))

发表更新算法3 分钟读完 (大约397个字)

107. 二叉树的层序遍历 II

算法内容

本文件实现 LeetCode 107「二叉树的层序遍历 II」。核心思路是先按普通层序遍历从上到下收集每一层节点值，再对结果整体反转，得到自底向上的层序结果。

实现中使用两个队列：s 保存当前层待访问节点，tmp_s 暂存下一层节点。当前层队列清空时，将本层结果写入 res，再把下一层队列转为当前层继续处理。最后通过 reverse(res.begin(), res.end()) 将层序结果倒置。时间复杂度为 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
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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
  struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode() : val(0), left(nullptr), right(nullptr) {}
      TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
      TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 };
#include<vector>
#include<iostream>
#include<stack>
#include<queue>
#include<algorithm>
using namespace std;
class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        queue<TreeNode*> s;
        if(root != nullptr) {
            s.push(root);
        }
        vector<vector<int>> res;
        vector<int> tmp;
        queue<TreeNode*> tmp_s;
        while(!s.empty()) {
            tmp.push_back(s.front()->val);
            TreeNode* tmp_node = s.front();
            if(tmp_node->left != nullptr) {
                tmp_s.push(tmp_node->left);
                // printf("add %d\n", tmp_node->left->val);
            }
            if(tmp_node->right != nullptr) {
                tmp_s.push(tmp_node->right);
                // printf("add %d\n", tmp_node->right->val);
            }
            s.pop();
            if(s.empty() && !tmp_s.empty()) {
                res.push_back(tmp);
                tmp.clear();
                while (!tmp_s.empty()){
                    s.push(tmp_s.front());
                    tmp_s.pop();
                }
            }
        }
        if(!tmp.empty()) {
            res.push_back(tmp);
        }
        reverse(res.begin(),res.end());
        return res;
    }
};
发表更新算法3 分钟读完 (大约450个字)

146. LRU 缓存

算法内容

本文件实现 LeetCode 146「LRU 缓存」。目标是在固定容量下支持 get 和 put，并在容量满时淘汰最近最少使用的键。

代码使用 unordered_map<int, Node*> 做 key 到链表节点的映射，并用带哨兵节点 root 的双向循环链表维护访问顺序。链表头部表示最近使用，尾部表示最久未使用。get 命中后将节点移动到头部；put 已存在时更新值并移到头部，不存在且容量未满时插入新节点，容量已满时复用尾节点并更新映射。平均时间复杂度为 O(1)，空间复杂度为 O(capacity)。

算法实现

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include<vector>
#include<iostream>
#include<stack>
#include<queue>
#include<algorithm>
#include<unordered_map>
using namespace std;

struct Node {
    int val;
    int key;
    Node* next;
    Node* last;
    Node(int val0, int key0, Node* next0=nullptr, Node* last0 = nullptr):key(key0), next(next0), val(val0), last(last0) {}
};
class LRUCache {
public:
    unordered_map<int, Node*> hash;
    Node* root;
    int size = 0;
    int capacity = 0;
    LRUCache(int capacity) {
        root = new Node(-1,-1);
        this->capacity = capacity;
        size = 0;
        root->last = root;
        root->next = root;
    }
    
    int get(int key) {
        Node* cur = hash[key];
        
        // printf("get %d\n", (cur==nullptr? -1 : (cur->val)));
        printAll();
        if(cur == nullptr) return -1;
        remove(cur);
        insertTop(cur);
        printAll();
        return cur->val;
    }
    
    void remove(Node*cur) {
        Node* last = cur->last;
        Node* next = cur->next;
        last->next = next;
        next->last = last;
    }

    void put(int key, int value) {
        // printf("put %d\n", value);
        printAll();
        if(hash[key] != nullptr) {
            Node* cur = hash[key];
            cur->val = value;
            remove(cur);
            insertTop(cur);
            // printf("replace :%d\n", cur->val);
        } else {
            if(size < capacity) {
                Node * cur = new Node(value, key);
                hash[key] = cur;
                insertTop(cur);
                size++;
                // printf("insert :%d\n", cur->val);
            } else {
                Node* cur = root->last;
                if(cur->key != -1){
                    hash[cur->key] = nullptr;
                    hash[key] = cur;
                    
                    cur->val = value;
                    cur->key = key;
                    remove(cur);
                    insertTop(cur);
                }
                // printf("lru :%d\n", cur->val);
            }
            
        }
        printAll();
    }
    void printAll() {
        // Node * cur = root->next;
        // while(cur != root) {
        //     printf("%d ", cur->val);
        //     cur = cur->next;
        // }
        // printf("\n");
    }
    void insertTop(Node* cur) {
        cur->last = root;
        cur->next = root->next;
        root->next->last = cur;
        root->next = cur;
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */
发表更新算法2 分钟读完 (大约364个字)

148. 排序链表

算法内容

本文件实现 LeetCode 148「排序链表」。核心思路是对单链表做归并排序，利用链表切分和有序链表合并完成排序。

split 使用快慢指针找到链表中点，并断开为左右两段；sortList 递归排序左右子链表；merge 使用虚拟头节点把两个有序链表合并。归并排序适合链表结构，因为合并时只需要调整指针，不需要随机访问。时间复杂度为 O(n log n)，递归栈空间复杂度为 O(log 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
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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
#include <vector>
#include <iostream>
#include <stack>
#include <queue>
#include <algorithm>
#include <unordered_map>
struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
using namespace std;
class Solution
{
public:
    ListNode *sortList(ListNode *head)
    {
        ListNode *left, *right;
        int len = split(head, &left, &right);
        if (len > 2)
        {
            left = sortList(left);
            right = sortList(right);
        }
        return merge(left, right);
    }

    ListNode *merge(ListNode *left, ListNode *right)
    {
        ListNode *head = new ListNode(0), *tmp;
        tmp = head;
        while (left != nullptr && right != nullptr)
        {
            if (left->val < right->val)
            {
                tmp->next = left;
                left = left->next;
            }
            else
            {
                tmp->next = right;
                right = right->next;
            }
            tmp = tmp->next;
        }
        if (left != nullptr)
        {
            tmp->next = left;
        }
        if (right != nullptr)
        {
            tmp->next = right;
        }
        tmp = head->next;
        return tmp;
    }

    int split(ListNode *head, ListNode **left, ListNode **right)
    {
        ListNode *v = new ListNode(0);
        v->next = head;
        ListNode *slow = v, *fast = v;
        int len = 0;
        while (fast->next != nullptr)
        {
            slow = slow->next;
            fast = fast->next;
            len++;
            if (fast->next != nullptr)
            {
                fast = fast->next;
                len++;
            }
        }
        *left = head;
        *right = slow->next;
        slow->next = nullptr;
        return len;
    }
};

发表更新算法2 分钟读完 (大约263个字)

17. 电话号码的字母组合

算法内容

本文件实现 LeetCode 17「电话号码的字母组合」。问题要求根据数字到字母的映射，生成所有可能的字符串组合。

代码维护数字串、长度、结果数组和映射表，通过回溯函数 search(depth, s) 逐位枚举当前数字对应的所有字符。当 depth == len 时，说明已经构造出一个完整组合，将其加入结果。若输入为空字符串，直接返回空结果。时间复杂度与组合数量成正比，约为 O(3^m * 4^n)，其中 m/n 分别是映射到 3 个/4 个字母的数字数量。

算法实现

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

#include<vector>
#include<iostream>
#include<stack>
#include<queue>
#include<algorithm>
using namespace std;

class Solution {
public:
    string digits;
    int len;
    vector<string> res;
    vector<string> table;
    vector<string> letterCombinations(string digits) {
        this->digits = digits;
        this->len = digits.length();
        table = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        if(digits == "") return res;
        search(0, "");
        return res;
    }

    void search(int depth, string s) {
        if(depth == len) {
            res.push_back(s);
            return;
        }
        char c = digits[depth] - '2';
        int len = (c == '7'-'2' || c == '9'-'2') ? 4 :  3;
        for(int i = 0; i < len; i++) {
            search(depth+1, s+table[c][i]);
        }
    }

};
发表更新算法3 分钟读完 (大约417个字)

179. 最大数

算法内容

本文件实现 LeetCode 179「最大数」。目标是把一组非负整数重新排列，使拼接后的数字最大。

代码先将整数转换为字符串，再通过自定义比较函数排序。比较两个字符串时，本质上要判断 a + b 和 b + a 哪个更大，排序后顺序拼接即可。实现里手写了整数转字符串和较复杂的循环比较逻辑，并对全 0 的情况做了处理，避免返回多个前导 0。时间复杂度主要来自排序，为 O(n log n * L)，L 为数字字符串比较成本。

算法实现

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include<vector>
#include<iostream>
#include<stack>
#include<queue>
#include<algorithm>
#include<unordered_map>

using namespace std;

class Solution {
public:
    string largestNumber(vector<int>& nums) {
        vector<string> snums;
        for(int n : nums) {
            snums.push_back(toString(n));
        }
        sort(snums.begin(), snums.end(), greater);
        string res = "";
        int len = snums.size();
        int i = 0;
        while(i < len && snums[i] == "0") {
            i++;
        }
        if(i > 0) i--;
        for(; i < len; i++) {
            res += snums[i];
        }
        return res;
    }

    string toString(int a) {
        if(a == 0) return "0";
        stack<int> sa;
        while(a != 0) {
            sa.push(a%10);
            a/=10;
        }
        string res = "";
        while(!sa.empty()) {
            res.push_back(sa.top() + '0');
            sa.pop();
        }
        return res;
    }
    
    static bool greater(string a, string b) {
        int na = a.length(), nb = b.length();
        int nc = na > nb ? nb : na;
        int i = 0,j = 0;
        int last_i = 0, last_j = 0;
        while(i < na && j < nb) {
            while(i < na && j < nb && a[i] == b[j]) {
                i++;
                j++;
            }
            if(i == na && j == nb) {
                return a > b;
            }
            if(i != na && j != nb) {
                i = last_i; j = last_j;
                break;
            } else {
                if(i == na) {
                    i = last_i;
                } else {
                    j = last_j;
                }
                last_i = i;
                last_j = j;
            }
        }
        // cout << "d " << i << " " << j << endl;
        // cout << "a " << a << " " << b << endl;
        while(i < na && j < nb) {
            // cout << "b " << a[i] << " " << b[j] << endl;
            // cout << "c " << i << " " << j << endl;
            if(a[i] > b[j]) {
                return true;
            } else if(a[i] < b[j]) {
                return false;
            }
            i++;
            j++;
        }
        return (na-i) > (nb-j);
        // return false;
    }

    void swap(int &a, int &b) {
        a = a+b;
        b = a-b;
        a = a-b;
    }
};
发表更新算法2 分钟读完 (大约258个字)

198. 打家劫舍

算法内容

本文件实现 LeetCode 198「打家劫舍」。问题要求在不能偷相邻房屋的限制下，获得最大金额。

代码采用自顶向下的记忆化搜索。maxRob(nums, i) 表示上一次选择位置为 i 后，从后续可选位置中能得到的最大收益；每次只尝试选择 i + 2 或 i + 3，用 mem[i + 2] 缓存状态结果。入口从 -2 开始，等价于还没有选择任何房屋。时间复杂度 O(n)，空间复杂度 O(n)。文件中的 main 用一组样例数据做本地验证。

算法实现

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
#include<vector>
#include<iostream>
#include<stack>
#include<queue>
#include<algorithm>
#include<unordered_map>
#include<climits>
#include<set>
using namespace std;

class Solution {
public:
    int n;
    vector<int> mem;
    int rob(vector<int>& nums) {
        this->n = nums.size();
        mem = vector<int>(n+2, -1);
        return maxRob(nums, -2);
    }
    int maxRob(const vector<int>& nums, int i) {
        if(i < n && mem[i+2] != -1) return mem[i+2];
        int a = (i+2 < n ? maxRob(nums, i+2) + nums[i+2] : 0);
        int b = (i+3 < n ? maxRob(nums, i+3) + nums[i+3] : 0);
        mem[i+2] = (a > b? a : b);
        return mem[i+2];
    }
};

int main() {
    Solution s;
    vector<int> v = {226,174,214,16,218,48,153,131,128,17,157,142,88,43,37,157,43,221,191,68,206,23,225,82,54,118,111,46,80,49,245,63,25,194,72,80,143,55,209,18,55,122,65,66,177,101,63,201,172,130,103,225,142,46,86,185,62,138,212,192,125,77,223,188,99,228,90,25,193,211,84,239,119,234,85,83,123,120,131,203,219,10,82,35,120,180,249,106,37,169,225,54,103,55,166,124};
    cout << v.size() << endl;
    cout << s.rob(v) << endl;
    return 0;
}
发表更新算法3 分钟读完 (大约522个字)

2049. 统计最高分的节点数目

算法内容

本文件实现 LeetCode 2049「统计最高分的节点数目」。题目要求删除每个节点后，计算剩余各连通块大小的乘积，并统计最高分节点数量。

第一版使用 unordered_map<int, vector<int>> 建树，先通过 DFS 计算每个节点子树大小，再枚举节点计算分数：父侧连通块大小为 n - size[i]，每个子树连通块大小为对应子节点的 size。SolutionBetter 针对二叉树性质，用 vector<pair<int, int>> 保存左右孩子，避免 map 和动态 vector 带来的额外开销。整体时间复杂度 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
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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#include<vector>
#include<iostream>
#include<stack>
#include<queue>
#include<algorithm>
#include<unordered_map>
#include<climits>
#include<set>
using namespace std;

class Solution {
public:
    template<class T>
    void printVec(const vector<T> &v, const string& head = "") {
        if(head != "") {
            cout << head << ": ";
        }
        for (T i : v) {
            cout << i << " ";
        }
        cout << "\n";
    }
    vector<int> size;
    vector<int> parents;
    unordered_map<int, vector<int>> children;
    int n;
    long long max = LONG_LONG_MIN;
    int maxn = 0;
    int countHighestScoreNodes(vector<int>& parents) {
        int n = parents.size();
        this->parents = parents;
        this->size = vector<int>(n, 1);
        this->n = n;
        for(int i = 0; i < n; i++) {
            getG(i);
        }
        getSize(0);
        for(int i = 0; i < n; i++) {
            calScore(i);
        }
        return maxn;

    }


    int getSize(int root) {
        int childNum = children[root].size();
        if(childNum == 0) {
            size[root] = 1;
        } else if(childNum == 1) {
            size[root] += getSize(children[root][0]);
        } else {
            size[root] += getSize(children[root][0]) + getSize(children[root][1]);
        }
        return size[root];
    }

    void calScore(int i) {
        int parent = parents[i];
        long long res = (parent == -1) ? 1 : (size[0] - size[i]);
        vector<int>& childi = children[i];
        for(int child : childi) {
            res *= size[child];
        }
        if(res > max) {
            max = res;
            maxn = 1;
        } else if(res == max) {
            maxn++;
        }
    }

    void getG(int i) {
        int parent = parents[i];
        if(parent == -1) {
            return;
        } else {
            children[parent].push_back(i);
        }
    }
};

int main() {
    Solution s;
    vector<int> v = {-1,2,0,2,0};
    cout << s.countHighestScoreNodes(v) << endl;
    return 0;
}

class SolutionBetter {
    //不使用map和set
public:
    vector<int> parents;
    vector<pair<int, int>> children;
    vector<int> size;
    int n;
    long long max = LONG_LONG_MIN;
    int maxn = 0;
    int countHighestScoreNodes(vector<int>& parents) {
        int n = parents.size();
        this->parents = parents;
        this->children = vector<pair<int, int>>(n, {-1,-1});
        this->size = vector<int>(n, 1);
        this->n = n;
        for(int i = 0; i < n; i++) {
            int parent = parents[i];
            if(parent == -1) {
                continue;
            } else {
                if(children[parent].first == -1) {
                    children[parent].first = i;
                } else {
                    children[parent].second = i;
                }
            }
        }
        getSize(0);
        for(int i = 0; i < n; i++) {
            int parent = parents[i];
            long long res = (parent == -1) ? 1 : (size[0] - size[i]);
            pair<int, int>& childi = children[i];
            res *= childi.first != -1 ? size[childi.first] : 1;
            res *= childi.second != -1 ? size[childi.second] : 1;
            if(res > max) {
                max = res;
                maxn = 1;
            } else if(res == max) {
                maxn++;
            }
        }
        return maxn;

    }


    int getSize(int root) {
        pair<int, int> child = children[root];
        int a = 0, b = 0;
        if(child.first != -1) {
            a = getSize(child.first);
        }
        if(child.second != -1) {
            b = getSize(child.second);
        }
        size[root] = 1 + a + b;
        return size[root];
    }
};

发表更新算法2 分钟读完 (大约343个字)

2055. 蜡烛之间的盘子

算法内容

本文件实现 LeetCode 2055「蜡烛之间的盘子」。目标是对多个区间查询，统计区间内两根蜡烛之间的盘子数量。

代码预处理三个数组：v 为盘子数量前缀和，left[i] 表示位置 i 左侧最近蜡烛下标，right[i] 表示位置 i 右侧最近蜡烛下标。对于查询 [l, r]，先找到 right[l] 和 left[r] 作为区间内最靠内的两根蜡烛，如果左蜡烛在右蜡烛左侧，就用前缀和相减得到盘子数。预处理 O(n)，每次查询 O(1)，总复杂度 O(n + q)。

算法实现

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
#include<vector>
#include<iostream>
#include<stack>

using namespace std;


class Solution {
public:
    vector<int> platesBetweenCandles(string s, const vector<vector<int>>& queries) {
        int len = s.length();
        vector<int> v(len, 0);
        vector<int> left(len, -1);
        vector<int> right(len, len);
        v[0] = s[0] == '*' ? 1 : 0; 
        int lastLeft = s[0] == '|' ? 0 : -1;
        left[0] = lastLeft;
        for(int i = 1; i < len; i++) {
            int x = s[i] == '*' ? 1 : 0;
            v[i] = v[i-1] + x;
            if(s[i] == '|') {
                lastLeft = i;
            }
            left[i] = lastLeft;
        }
        int lastRight = s[len-1] == '|' ? len-1 : len;
        for(int i = len-2; i >= 0; i--) {
            if(s[i] == '|') {
                lastRight = i;
            }
            right[i] = lastRight;
        }
        vector<int> ans;
        len = queries.size();
        for(int i = 0; i < len; i++) {
            int diff = 0;
            printf("%d, %d\n", right[queries[i][0]], left[queries[i][1]]);
            printf("%d, %d\n", v[right[queries[i][0]]], v[left[queries[i][1]]]);
            if(right[queries[i][0]] < left[queries[i][1]]) {
                diff = v[left[queries[i][1]]] - v[right[queries[i][0]]];
            }
            ans.push_back(diff);
        }
        return ans;
    }
};

int main() {
    Solution s;
    string str = "***|**|*****|**||**|*";
    vector<int> res = s.platesBetweenCandles(str, {{1,17},{4,5},{14,17},{5,11},{15,16}});
    int len = res.size();
    for(int i = 0; i < len; i++) {
        cout << res[i] << " ";
    }
    cout << endl;
    return 0;
}
发表更新算法2 分钟读完 (大约269个字)

207. 课程表

算法内容

本文件实现 LeetCode 207「课程表」。问题可以转化为判断有向图中是否存在环。

代码使用拓扑排序。m 数组统计每门课的入度，g 存储从先修课程指向后续课程的邻接表。先把所有入度为 0 的课程入栈，然后不断弹出课程并降低后继节点入度；当某个后继入度降为 0 时继续入栈。最后如果存在未访问课程，说明图中有环，无法完成所有课程。时间复杂度 O(V + E)，空间复杂度 O(V + E)。

算法实现

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
#include<vector>
#include<iostream>
#include<stack>
#include<queue>
#include<algorithm>
#include<unordered_map>

using namespace std;

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<int> m(numCourses, 0);
        vector<bool> visited(numCourses, false);
        unordered_map<int, vector<int>> g;
        for(vector<int>& p:prerequisites) {
            m[p[0]]++;
            g[p[1]].push_back(p[0]);
        }
        bool find = true;
        stack<int> s;
        for(int i = 0; i < numCourses; i++) {
            if(m[i] == 0) {
                s.push(i);
                visited[i] = true;
            }
        }
        while(!s.empty()) {
            int pos = s.top();
            s.pop();
            vector<int> arcs = g[pos];
            for(int arc : arcs) {
                m[arc]--;
                if(m[arc] == 0) {
                    s.push(arc);
                    visited[arc] = true;
                }
            }
        }
        for(bool visit:visited) {
            if(!visit) {
                return false;
            }
        }
        return true;
    }
};
关注我

链接

分类

最新文章

归档

标签

6.8242
Android1
Android FrameWork1
Android 高级开发瓶颈突破系列课11
Android-官方文档1
Android-官方源码6
Android车载1
Android面试查漏补缺2
C#9
C/C++1
CSharp9
Flutter1
Java基础 字节码2
Kotlin-Android21
Kotlin-Android 实习25
LeetCode45
LeetCode 1013
LeetCode周赛1
Linux/UNIX系统编程手册38
OI KIWI2
OS4
PAT-(Advanced-Level)-Practice2
PAT-(Basic-Level)-Practice44
blockchain1
fedfab13
gallery6
geth1
git1
gradle1
hexo2
linux2
misc1
projects1
shell2
刷题2
动态规划1
多线程1
排序1
数据库2
牛客2
算法69
×