[2.10]\560. Subarray Sum Equals K

传送门

分析：前缀和

 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 subarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> sum(n+1, 0);
        for (int i=0; i<n; i++) {
            sum[i+1] = sum[i] + nums[i];
        }
        int ans = 0;
        unordered_map<int, int> mp;
        for (int i=1; i<=n; i++) {
            if (sum[i] == k) ans ++;
            if (mp.find(sum[i] - k) != mp.end()) {//前面存在前缀和sum[j](=sum[i]-k)
                ans += mp[(sum[i]-k)];
            }
            mp[sum[i]] ++;	// 前缀和为sum[i]的数量+1
        }
        return ans;
    }
};

[02.13]\78. Subsets

传送门

分析：求子集，任意顺序输出

三种方法：1）dfs+回溯；2）迭代法；3）位操作

 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

//方法1： TC：O(n!)，SC: O(n) + O(n!)
class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> temp;
        dfs(nums, res, temp, 0);
        return res;
    }
    void dfs(vector<int>& nums, vector<vector<int>>& res, vector<int>& temp, int idx) {
        res.push_back(temp);
        for (int i=idx; i<nums.size(); i++) {
            temp.push_back(nums[i]);
            dfs(nums, res, temp, i+1);
            temp.pop_back();
        }
    }
};

// 方法2；迭代法	TC：O(n * 2^n)  SC：O(1)+O(2^n * n)
class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        // Example, nums = [1,2,3]
        vector<vector<int>> res = {{}};
        for (int& num: nums) { 
            int n = res.size();
            // Round1, num=1, 即RoundX, num=X
            for (int i=0; i<n; i++) {
                /** Initialize；res=[[]]
                Round 1,
                    After step1: res=[[], []]
                    After step2: res=[[], [1]]
                Round 2,
                    After step1: res=[[], [1], []]
                    After step2: res=[[], [1], [2]]
                    After step1: res=[[], [1], [2], [1]]
                    After step2: res=[[], [1], [2], [1, 2]]
                Similarly，and so on
                */
                res.push_back(res[i]);      // step1
                res.back().push_back(num);  // step2
            }
        }
        return res;
    }

};

/* 方法3：位操作法 TC：O(2^n * n)   SC：O(2^n * n)
nums[i]     1     2       3
0(000), [], [],   [],     []
1(001), [], [1],  [1],    [1] 
2(010), [], [],   [2],    [2]
3(011), [], [1],  [1,2],  [1,2]
4(100), [], [],   [],     [3]
5(101), [], [1],  [1],    [1,3]
6(110), [], [],   [2],    [2,3]
7(111), [], [1],  [1,2],  [1,2,3]
创建2^n个的vector<int>的一维数组，(n=(1<<nums.size()) ),对应的二进制位表示中1对应的位置的数组元素nums[i]来填充vector
*/   
class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        // Example, nums = [1,2,3]
        int n=nums.size();
        int cnt = (1<<n);
        vector<vector<int>> res(cnt);
        for (int i=0; i<cnt; i++) {
            for (int j=0; j<nums.size(); j++) {
                if((i>>j) & 1) { // 对应的二进制位是1,
                    res[i].push_back(nums[j]);
                }
            }
        }
        return res;
    }
};

[02.14]\104. Maximum Depth of Binary Tree

传送门

分析：求树的最大深度

1
2
3
4
5
6
7

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (!root) return 0;
        return 1 + max(maxDepth(root->left), maxDepth(root->right));
    }
};

[02.15]\136. Single Number

传送门

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for (int x: nums) {
            res ^= x;
        }
        return res;
    }
};

[02.16]\24. Swap Nodes in Pairs

传送门

分析：交换链表的相邻节点并返回修改后的链表。

双指针方法； 1）指针的指针；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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

/**
 * 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) {}
 * };
 */
// 新建一个闲置节点, 其next节点为head
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummy = new ListNode(0);
        ListNode* pre = dummy;
        dummy->next = head;
        ListNode* slow, *fast;
        while((slow=pre->next) && (fast=slow->next)) { // slow为空 或者 slow->next为空时循环结束
            slow->next = fast->next;	// 第一个节点放在第二个节点后
            // 第二个节点放在第一个节点前（分两步，处理前面的指针和后面指针）
            fast->next = slow;			// 1；第二个节点的next节点指向slow
            pre->next = fast;			// 2；上一个pairs的尾节点指向fast
            // next pairs
            pre = slow;					// 处理下一个pairs
        }
        return dummy->next;
    }
};

// 指针的指针；相比上面的	方法，节省了dummy的空间
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode **pp=&head; // pointer of the pointer
        ListNode* slow, *fast;
        while ((slow = *pp) && (fast = slow->next)) {
            slow->next = fast->next;
            fast->next = slow;
            *pp = fast;     // 相当于pre->next = fast
            pp = &(slow->next); // next pairs
        }
        return head;
    }
};

[02.17]\39. Combination Sum

传送门

Example 1:

1
2
3
4
5
6

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

分析：(跟硬币找零方案数目基本一样)最直接的想法就是 排序后去重，每次都拿最小的一个整数来试探。 即dfs+回溯；时间复杂度O(N^(M/min_cand + 1)); M = target, min_cand = min(candidates);

  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

// 自顶向下，dfs+回溯
class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end()); 
        candidates.erase(unique(candidates.begin(), candidates.end()), candidates.end()); // 去重
        vector<vector<int>> res;
        vector<int> temp;
        dfs(candidates, res, temp, target, 0);
        return res;
    }
    void dfs(vector<int>& candidates, vector<vector<int>> &res, vector<int> &temp, int target, int index) {
        if (target == 0) {
            res.push_back(temp);
            return ;
        }
        // while循环内执行 尽可能能够放置最小的一个整数的逻辑
        while (index < candidates.size() && target - candidates[index] >= 0) {
            temp.push_back(candidates[index]);
            dfs(candidates, res, temp, target-candidates[index], index); //此处是index 表示有可能一个数出现两次，比如例1中的[2,2,3] 2出现两次
            index ++;          // 试探下一个整数
            temp.pop_back();    // 回溯
        }
    }
};

// 自底向上，DP
// 参考https://leetcode.com/problems/combination-sum/discuss/1103237/C%2B%2B-Best-and-easy-DP-Solution
// 这种解法写法倒是简单，开始不太明白 for(auto vec: dp[k-candidate])这里，但是结合例子以及知道vec的类型是vector<int>就容易理解了。
/***
Example 1:
Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

对照代码打印内容理解:
candidate=2
k=2
打印组成和为2的若干个元素
和为2的vec打印 开始
2 
和为2的vec打印 结束
2 
k=3
k=4
打印组成和为4的若干个元素
和为4的vec打印 开始
2 2 
和为4的vec打印 结束
2 2 
k=5
k=6
打印组成和为6的若干个元素
和为6的vec打印 开始
2 2 2 
和为6的vec打印 结束
2 2 2 
k=7
candidate=3
k=3
打印组成和为3的若干个元素
和为3的vec打印 开始
3 
和为3的vec打印 结束
3 
k=4
2 2 
k=5
打印组成和为5的若干个元素
和为5的vec打印 开始
2 3 
和为5的vec打印 结束
2 3 
k=6
打印组成和为6的若干个元素
和为6的vec打印 开始
3 3 
和为6的vec打印 结束
2 2 2 
3 3 
k=7
打印组成和为7的若干个元素
和为7的vec打印 开始
2 2 3 
和为7的vec打印 结束
2 2 3 
candidate=6
k=6
打印组成和为6的若干个元素
和为6的vec打印 开始
6 
和为6的vec打印 结束
2 2 2 
3 3 
6 
k=7
2 2 3 
candidate=7
k=7
打印组成和为7的若干个元素
和为7的vec打印 开始
7 
和为7的vec打印 结束
2 2 3 
7 
**/
class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector< vector <vector<int>>> dp(target+1);
        // dp[i] 存储和为i的所有可能的组成结果
        dp[0] = {{}};	// 这里的花括号{}容易误解成字典，但是需要说明这里是空的二维数组初始化
        for (int &candidate: candidates) {	// 遍历所有的candidate 
            cout <<"candidate="<<candidate<<endl;
            for (int k=candidate; k<=target; k++) {
                // 寻找所有和为k的数组元素（<=candidate）组成
                cout<<"k="<<k<<endl;
                for (auto vec: dp[k-candidate]) { // vec类型是vector<int>
                    // cout<<typeid(vec).name()<<endl;
                    vec.push_back(candidate);
                    cout << "打印组成和为"<<k<<"的若干个元素"<<endl;
                    cout<<"和为"<<k<<"的vec打印 开始"<<endl;
                    for (auto x: vec) {
                        cout <<x<<" ";
                    }
                    cout << endl;
                    cout<<"和为"<<k<<"的vec打印 结束"<<endl;
                    dp[k].push_back(vec);
                }
                // for (auto vec: dp[k]) {
                //     for (auto x: vec) {
                //         cout <<x << " ";
                //     }
                //     cout << endl;
                // }
            }
        }
        return dp[target];
    }
};

[02.18]\402. Remove K Digits

传送门

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    string removeKdigits(string num, int k) {
        string res = "";
        for (char &ch: num) {
            while (res.size() && res.back() > ch && k) {
                // 保证删除的整数是降序 即可保证结果res最小
                res.pop_back();
                k --;
            }
            if (res.size() || ch != '0') { // 插入字符串不能存在前导0
                res.push_back(ch);
            }
        }
        // cout << res << endl;
        while (res.size() && k--) { // 保证删除k个数，比如num="1324", k=3.此时res="124"，继续删掉后面两个字符得到正确结果1
            res.pop_back();
        }
        return res != "" ? res : "0";
    }
};

[02.19]\1675. Minimize Deviation in Array

传送门

分析：奇数 至多进行一次double操作，而偶数 则可以一直divide直到其变为奇数。 具体见代码。

 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

class Solution {
public:
    int minimumDeviation(vector<int>& nums) {
        int res = 1e9+1, minItem = 1e9+1;
        priority_queue<int> pq;
        for (int& x: nums) {
            if (x & 1) { // x is odd
                x = (x<<1);
            }
            pq.push(x);
            minItem = min(minItem, x);
        }
        while (!(pq.top() & 1)) { // pq.top() is even
            // 经过若干个操作后认为最大值为奇数，原因如下:
            /** 通过题意知，可以通过增大奇数或减小偶数来减少deviation，
            若队列头部有一个奇数t，则不可能再减小max了；
                那么考虑增大min，若t是偶数，只可能减小，若t是奇数，double一次变成偶数(2 * current_min > current_max)，此时deviation 必定大于原来的deviation
            若队列头部有一个偶数t，则只可能将t/2减小本身
            */
            res = min(res, pq.top()-minItem);
            minItem = min(minItem, pq.top()>>1);
            pq.push(pq.top()>>1);
            pq.pop();
        }
        return min(res, pq.top()-minItem);
    }
};

[02.20]\1288. Remove Covered Intervals

传送门

分析：先排序，排序后 二维数组先按第一个数大小排序，然后按第二个大小排序。

那么举例：

1
2
3
4
5
6

intervals = [[1,4],[3,6],[2,8],[2,6]]
排序后的结果为 [[1,4],[2,6],[2,8],[3,6]]
(1)|_ _ _ _|(4)				x1 = 1, x2 = 4 		res = 1
  (2)|_ _ _ _ _|(6)			x1 = 2, x2 = 6		res = 2
  (2)|_ _ _ _ _ _ _|(8)		x1 = 2, x2 = 8		res = 2
    (3)|_ _ _ _|(6)			x1 = 3, x2 = 6		res = 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    int removeCoveredIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end());
        int res = 1, x1 = intervals[0][0], x2 = intervals[0][1];
        for (int i=1; i<intervals.size(); i++) {
            int nx1 = intervals[i][0], nx2 = intervals[i][1];
            if (nx2 > x2) {
                if (nx1 != x1) {
                    res ++;
                }
                x1 = nx1;
                x2 = nx2;
            }
        }
        return res;
    }
};

[02.21]\169. Majority Element

传送门

分析：n个数中找到最多的那个元素。最直接的方法：排序然后取最中间的那个数。但是限制线性时间和O(1)空间的话，可以考虑设置一个计数变量count 用于记录出现次数最多的那个数次数 - 其他数出现次数的总和。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int count = 1, res = nums[0];
        for (int i=1; i<nums.size(); i++) {
            if (nums[i] == res) {
                count ++;
            } else {
                if (count == 0) {
                    count ++;
                    res = nums[i];
                    continue;
                }
                count --;
            }
        }
        return res;
    }
};

[02.22]\171. Excel Sheet Column Number

传送门

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
public:
    int titleToNumber(string columnTitle) {
        int res = 0;
        for (char& ch: columnTitle) {
            res = res * 26 + (ch - 'A' + 1);
        }
        return res;
    }
};

[02.23]\133. Clone Graph

传送门

分析：DFS或BFS，unordered_map防止重复访问

 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 Node.
class Node {
public:
    int val;
    vector<Node*> neighbors;
    Node() {
        val = 0;
        neighbors = vector<Node*>();
    }
    Node(int _val) {
        val = _val;
        neighbors = vector<Node*>();
    }
    Node(int _val, vector<Node*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};
*/
// BFS
class Solution {
public:
    Node* cloneGraph(Node* node) {
        if (node == NULL) return NULL;
        // cout << node->val <<endl;
        Node* res = new Node(node->val, {});
        ump[node] = res;
        queue<Node*> q;
        q.push(node);
        while (!q.empty()) {
            Node* head = q.front();
            q.pop();
            for (Node* neighbor: head->neighbors) {
                if (ump.find(neighbor) == ump.end()) { // 当前neighbor不在ump中
                    ump[neighbor] = new Node(neighbor->val, {}); // 新建neighbor <-> neighbors of neighbor
                    q.push(neighbor);
                }
                ump[head] -> neighbors.push_back(ump[neighbor]); // neighbors of head <-> ump[neighbor]
            }
        }
        return res;
    }
private: 
    unordered_map<Node*, Node*> ump;
};

// DFS
class Solution {
public:
    Node* cloneGraph(Node* node) {
        if (node == NULL) return NULL;
        if (ump.find(node) == ump.end()) {
            ump[node] = new Node(node->val, {});
            for (Node* neighbor: node->neighbors) {
                ump[node] -> neighbors.push_back(cloneGraph(neighbor));
            }
        }
        return ump[node];
    }
private: 
    unordered_map<Node*, Node*> ump;
};

[02.24]\148. Sort List

传送门

分析：TC O(logn), SC: O(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

/**
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* midpoint(ListNode* head) {
        if (head == NULL || head -> next == NULL) {
            return head;
        }
        ListNode *slow = head, *fast = head->next;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
    ListNode* mergeTwoLists(ListNode* a, ListNode* b) {
        if (a == NULL) return b;
        if (b == NULL) return a;
        ListNode* temp;
        if (a->val <= b->val) {
            temp = a;
            temp->next = mergeTwoLists(a->next, b);
        } else {
            temp = b;
            temp->next = mergeTwoLists(a, b->next);
        }
        return temp;
    }
    ListNode* mergeLists(ListNode* a, ListNode* b) {
        ListNode* dummy = new ListNode(0);
        ListNode* cur = dummy;
        while (a && b) {
            if (a->val <= b->val) {
                cur->next = a;
                a = a->next;
            } else {
                cur->next = b;
                b = b->next;
            }
            cur = cur->next;
        } 
        cur->next = a ? a : b;
        return dummy->next;
    }
    ListNode* sortList(ListNode* head) {
        if (head == NULL || head->next == NULL) {
            return head;
        }    
        ListNode* mid = midpoint(head);
        ListNode *a = head, *b = mid->next;
        mid->next = NULL; // 中间断开 成两条链
        a = sortList(a);
        b = sortList(b);
        return mergeLists(a, b);
    }
};

[02.25]\165. Compare Version Numbers

传送门

分析：按照'.‘从左到右分开的子串转换成十进制依次比较，若两个在某一个子串不等，则直接返回1或-1，否则遍历完毕表示两个string按照题意其version是相等的，则返回0。TC：O(m+n)，SC：O(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

class Solution {
public:
    int compareVersion(string version1, string version2) {
        int m = version1.size(), n = version2.size();
        for (int i=0, j=0; i<m || j<n; ++i, ++j) {
            int num1 = 0, num2 = 0;
            while (i<m && version1[i] != '.') {
                num1 = num1 * 10 + (version1[i] - '0');
                ++ i;
            }
            while (j<n && version2[j] != '.') {
                num2 = num2 * 10 + (version2[j] - '0');
                ++ j;
            }
            if (num1 < num2) {
                return -1;
            } else if (num1 > num2) {
                return 1;
            }
        }
        // 两个string全部遍历完毕才能确定是相等的
        // 例如 version1 = "1", version2 = "1.0.1"
        return 0;  
    }
};

[02.26]\847. Shortest Path Visiting All Nodes

传送门

Constraints:

  • n == graph.length
  • 1 <= n <= 12
  • 0 <= graph[i].length < n
  • graph[i] does not contain i.
  • If graph[a] contains b, then graph[b] contains a.
  • The input graph is always connected.

题意：给定n个标记[0, n-1]的节点组成的一个图。graph[i]表示与节点i相连。返回访问所有节点的最短路径长度（可以从任意节点开始，可以多次访问一个节点，也可以重复使用边）。

分析：题目给出了Constraints，看到n的范围是[1, 12]，所以最先想到 dfs + 记忆化可能可以解决。

 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

// DFS + 记忆化，TC：O(n^2 * 2^n)【编码状态可能有2^n * n种】，SC：O(n * 2^n)
class Solution {   
public:
    int shortestPathLength(vector<vector<int>>& graph) {
        int n = graph.size();
        int mask = (1 << n) -1;	// 自顶向下，所以mask初始值是 (1<<n) - 1
        vector<vector<int>> cache(n+1, vector<int>(mask+1, 0)); // 记忆化，dp[i][mask] 存储节点i出发，编码状态为mask的最小值
        int res = INT_MAX;	
        for (int i = 0; i < n; ++ i) {
            res = min(res, dfs(i, graph, cache, mask));
        }
        return res;
    }   
private:
    int dfs(int node, vector<vector<int>>& graph, vector<vector<int>>& cache, int mask) {
        
        if (cache[node][mask] != 0) {
            return cache[node][mask];
        }
        if ((mask & (mask - 1)) == 0) { // 只有一个节点被访问过 即当前节点node
            return 0;
        }
        cache[node][mask] = INT_MAX - 1;	// 避免进入无限循环
        for (int neighbor: graph[node]) {
            if ((mask & (1 << neighbor)) != 0) {    // 对于节点neighbor
                int hasVisited = dfs(neighbor, graph, cache, mask); // 已经访问过
                int notVisited = dfs(neighbor, graph, cache, mask^(1<<node)); // 没访问过
                cache[node][mask] = min(cache[node][mask], 1 + min(hasVisited, notVisited));
            }
        }
        return cache[node][mask];   
    }
};

// BFS TC: O(n * n*2^n), SC: O(n * 2^n)
class Solution {
    class Tuple {
    public:
        int node, mask, steps;
        Tuple(int _node, int _mask, int _steps) : node(_node), mask(_mask), steps(_steps) {}
    };
public:
    int shortestPathLength(vector<vector<int>>& graph) {
        int n = graph.size();
        if (n == 1) return 0;
        
        int endingMask = (1<<n) - 1;
        vector<vector<bool>> visited(n, vector<bool>(endingMask+1, false));
        queue<Tuple> que;
        for (int i=0; i<n; ++i) {
            que.push(Tuple(i, 1<<i, 0));
            visited[i][1<<i] = 1;
        }
        while (!que.empty()) {
            auto cur = que.front();
            que.pop();
            int node = cur.node, mask = cur.mask, steps = cur.steps;
            if (mask == endingMask) {
                return steps;
            }
            for (int neighbor: graph[node]) {
                int nextMask = mask | (1 << neighbor);
                if (!visited[neighbor][nextMask]) {
                    visited[neighbor][nextMask] = true;
                    que.push(Tuple(neighbor, nextMask, steps+1));
                }
            }
        }
        return -1; // 不会到达这儿
    }
};

[02.27]\662. Maximum Width of Binary Tree

传送门

 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

/**
 * 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) {}
 * };
 */
class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        queue<pair<TreeNode*, unsigned long long>> que;
        // unsigned long long: runtime error: signed integer overflow: 2 * 6917529027641081854 cannot be represented in type 'long long' (solution.cpp)
        que.push({root, 0});
        int maxWidth = 0;
        while (!que.empty()) {
            int size = que.size();
            unsigned long long left = que.front().second, right;
            while (size--) {
                auto cur = que.front();
                que.pop();
                TreeNode* curNode = cur.first;
                right = cur.second;
                if (curNode->left != NULL) que.push({curNode->left, 2 * right + 1});
                if (curNode->right != NULL) que.push({curNode->right, 2 * right + 2});
            }
            maxWidth = max(maxWidth, int(right - left + 1));
        }
        return maxWidth;
    }
};

[02.28]\228. Summary Ranges

传送门

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums) {
        vector<string> res;
        if (nums.size() == 0) return res;
        int n = nums.size();
        for (int i=0; i<n; ++i) {
            bool flag = false;
            res.push_back(to_string(nums[i]));
            while (i+1 < n && nums[i+1] == nums[i] + 1) {
                flag = true;
                ++i;
            }
            if (flag) {
                res.back() += "->" + to_string(nums[i]);
            }
        }
        return res;
    }
};