LeetCode
34 分钟 读完 (大约 5132 个字) ...次访问

2020-04 LeetCode每日一题做题记录

Apr.30 快乐数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def isHappy(self, n: int) -> bool:
        def change(x: int) -> int:
            ret = 0
            while x:
                x, digit = divmod(x, 10)
                ret += digit * digit
            return ret
        
        st = set()
        while n not in st:
            if n == 1:
                return True
            st.add(n)
            n = change(n)
        return False

Apr.29 山脉数组中查找目标值

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
// 4 ms, 7.2 MB
/**
 * // This is the MountainArray's API interface.
 * // You should not implement it, or speculate about its implementation
 * class MountainArray {
 *   public:
 *     int get(int index);
 *     int length();
 * };
 */

class Solution {
public:
    template<typename Func>
    int binary_search(MountainArray& mountainArr, int target, int l, int r, Func func) {
        target = func(target);
        while (l <= r) {
            int mid = (l + r) / 2;
            int cur = func(mountainArr.get(mid));
            if (cur == target) return mid;
            if (cur < target) l = mid + 1;
            else r = mid - 1;
        }
        return -1;
    }

    int findInMountainArray(int target, MountainArray &mountainArr) {
        int l = 0, r = mountainArr.length() - 1;
        while (l < r) {
            int mid = (l + r) / 2;
            if (mountainArr.get(mid) < mountainArr.get(mid + 1)) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        int peak = l;
        int index = binary_search(mountainArr, target, 0, peak, [](int x) {
            return x;
        });
        if (index != -1) return index;
        index = binary_search(mountainArr, target, peak + 1, mountainArr.length() - 1, [](int x) {
            return -x;
        });
        return index;
    }
};

Apr.28 数组中数字出现的次数

分组异或。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 40 ms, 16.1 MB
class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        int xor_all = 0;
        for (int val : nums) xor_all ^= val;
        // xor_all 中 1 的位表示两个只出现过一次的数中这一位不同
        int bit = xor_all & -xor_all; // 以 lowbit(xor_all) 区分两个组别
        int a = 0, b = 0; // 对这两个组别分别做异或
        for (int val : nums) {
            if (val & bit) a ^= val;
            else b ^= val;
        }
        return {a, b};
    }
};

Apr.27 搜索旋转排序数组

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
// 0 ms, 6.4 MB
class Solution {
public:
    int search(vector<int>& nums, int target) {
        if (nums.empty()) {
            return -1;
        }

        int p = 0, q = 1;
        while (q) {
            if (p + q >= nums.size() || nums[p + q] < nums[p]) {
                q >>= 1;
            } else {
                p += q;
                q <<= 1;
            }
        }

        // nums[p] is the biggest value in nums.
        int l, r;
        if (target >= nums[0]) { // the target's index is in [0, p].
            l = -1;
            r = p + 1;
        } else { // the target's index is in [p+1, nums.size()-1].
            l = p;
            r = nums.size();
        }
        while (l + 1 < r) {
            int mid = (l + r) >> 1;
            if (nums[mid] <= target) {
                l = mid;
            } else {
                r = mid;
            }
        }
        return l >= 0 && nums[l] == target ? l : -1;
    }
};

Apr.26 合并K个排序链表

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
// 60 ms, 10.4 MB
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    struct Cmp {
        bool operator()(const ListNode* a, const ListNode* b) const {
            return a->val > b->val;
        }
    };
    
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, Cmp> heap;
        
        for (ListNode* listHead : lists) {
            if (listHead) heap.push(listHead);
        }
        
        ListNode dummy;
        ListNode* last = &dummy;
        while (!heap.empty()) {
            ListNode* now = heap.top();
            heap.pop();
            
            if (now->next) heap.push(now->next);
            
            last->next = now;
            last = now;
        }
        
        return dummy.next;
    }
};

Apr.25 全排列

解法一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 4 ms, 7.4 MB
class Solution {
public:
    void dfs(vector<vector<int>>& ans, vector<int>& now, const vector<int>& nums, int visit) {
        if (visit == (1 << nums.size()) - 1) {
            ans.emplace_back(now);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            if (!((visit >> i) & 1)) {
                now.push_back(nums[i]);
                dfs(ans, now, nums, visit ^ (1 << i));
                now.pop_back();
            }
        }
    }
    
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<int> tmp;
        dfs(ans, tmp, nums, 0);
        return ans;
    }
};

解法二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 4 ms, 7.2 MB
class Solution {
public:
    void solve(vector<vector<int>>& res, vector<int>& nums, int pos) {
        if (pos == nums.size()) {
            res.emplace_back(nums);
            return;
        }
        for (int i = pos; i < nums.size(); i++) {
            swap(nums[pos], nums[i]);
            solve(res, nums, pos + 1);
            swap(nums[pos], nums[i]);
        }
    }
    
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ans;
        solve(ans, nums, 0);
        return ans;
    }
};

Apr.24 数组中的逆序对

经典问题，可用归并排序或树状数组解决。我的解法是离散化树状数组。时间复杂度 $O(N logN)$ ，空间复杂度 $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
// 468 ms, 45.3 MB
class Solution {
public:
    vector<int> tree;
    vector<int> tmp;
    
    void init(int n) {
        tree.resize(n + 1);
    }
    
    int lowbit(int x) {
        return x & -x;
    }
    
    void add(int x, int y, int n) {
        while (x <= n) {
            tree[x] += y;
            x += lowbit(x);
        }
    }
    
    int sum(int x) {
        int sum = 0;
        while (x) {
            sum += tree[x];
            x -= lowbit(x);
        }
        return sum;
    }
    
    int getId(int val) {
        return lower_bound(tmp.begin(), tmp.end(), val) - tmp.begin() + 1;
    }
    
    int reversePairs(vector<int>& nums) {
        int ans = 0;
        tmp.insert(tmp.begin(), nums.begin(), nums.end());
        sort(tmp.begin(), tmp.end());
        tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());

        init(tmp.size());
        for (int i = 0; i < nums.size(); i++) {
            int id = getId(nums[i]);
            ans += i - sum(id);
            add(id, 1, tmp.size());
        }
        
        return ans;
    }
};

Apr.23 硬币

完全背包。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 76 ms, 14.2 MB
class Solution {
public:
    int waysToChange(int n) {
        vector<int> dp(n + 1);
        dp[0] = 1;
        for (int val : {1, 5, 10, 25}) {
            for (int i = val; i <= n; i++) {
                dp[i] = (dp[i] + dp[i - val]) % 1000000007;
            }
        }
        return dp[n];
    }
};

Apr.22 二叉树的右视图

DFS，对于每个结点的子树，先遍历右子树，再遍历左子树。时间复杂度 $O(N)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 40 ms, 13.9 MB
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:
        ans = []
        
        def traverse(root: TreeNode, depth: int):
            if not root:
                return
            if len(ans) <= depth:
                ans.append(root.val)
            traverse(root.right, depth + 1)
            traverse(root.left, depth + 1)
        
        traverse(root, 0)
        return ans

Apr.21 统计「优美子数组」

双指针，当维护的区间中的奇数个数cnt达到k时，保存此位置为k_cnt_right_begin，然后再将右端点r往右移直到指针到数组边界或右边的数字是个奇数（会导致cnt加1）。此时移动左端点l，每次移动对答案的贡献是r - k_cnt_right_begin + 1，即左端点为l，右端点落在[k_cnt_right_begin, r]的区间。移动l并更新cnt直到cnt < k。此时再移动右指针。重复以上步骤直到遍历完数组即可。

时间复杂度 $O(N)$ ，空间复杂度 $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
// 380 ms, 62.9 MB
class Solution {
public:
    int numberOfSubarrays(vector<int>& nums, int k) {
        int n = nums.size();
        
        int l = 0, r = -1, cnt = 0;
        int ans = 0;
        while (r + 1 < n) {
            // 在 cnt < k 时继续拓展右端点
            while (r + 1 < n && cnt < k) cnt += nums[++r] & 1;
            if (r >= n) break;
            int k_cnt_right_begin = r;

            // 在维持 cnt == k 的前提下，再尽量移动右端点
            while (r + 1 < n && !(nums[r + 1] & 1)) ++r;

            // 则满足 cnt == k 的区间的左端点为 l
            // 右端点为 [k_cnt_right_begin, r] 之一
            while (l <= r && cnt == k) {
                ans += r - k_cnt_right_begin + 1;
                cnt -= nums[l++] & 1;
            }
        }
        
        return ans;
    }
};

Apr.20 岛屿数量

通过 BFS 或 DFS 搜索遍历每一个连通块即可。但 BFS 在队列上所消耗的空间为 $O(max(N, M))$ ，DFS在栈上所消耗的空间为 $O(N*M)$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 80 ms, 14.4 MB
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid:
            return 0
        
        n, m = len(grid), len(grid[0])
        # 为了保护 grid 数组，不直接使用 grid 数组进行标记
        vis = [[False] * m for _ in range(n)]
        q = collections.deque()
        ans = 0
        for i in range(n):
            for j in range(m):
                if grid[i][j] == '1' and vis[i][j] == False:
                    q.append((i, j))
                    vis[i][j] = True
                    ans += 1
                    while q:
                        x, y = q.popleft()
                        for a, b in (x-1, y), (x+1, y), (x, y-1), (x, y+1):
                            if 0 <= a < n and 0 <= b < m and grid[a][b] == '1' and not vis[a][b]:
                                q.append((a, b))
                                vis[a][b] = True
        return ans

Apr.19 统计重复个数

Apr.18 盛最多水的容器

1
2
3
4
5
6
7
8
9
10
11
12
# 68 ms, 15.2 MB
class Solution:
    def maxArea(self, height: List[int]) -> int:
        l, r = 0, len(height) - 1
        ans = 0
        while l < r:
            ans = max(ans, (r - l) * min(height[l], height[r]))
            if height[l] < height[r]:
                l += 1
            else:
                r -= 1
        return ans

Apr.17 跳跃游戏

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 8 ms, 7.8 MB
class Solution {
public:
    bool canJump(vector<int>& nums) {
        const int n = nums.size();
        
        int rightmost = 0;
        for (int i = 0; i < n && i <= rightmost; i++) {
            rightmost = max(rightmost, i + nums[i]);
        }
        
        return rightmost >= n - 1;
    }
};

Apr.16 合并区间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 52 ms, 14.6 MB
class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort()
        ans = []
        left, right = -1, -1
        for interval in intervals:
            if interval[0] > right:
                if left != -1:
                    ans.append([left, right])
                left, right = interval
            else:
                right = max(right, interval[1])
                # why max: cases like [[1, 4], [2, 3]]
        if left != -1:
            ans.append([left, right])
        return ans

Apr.15 01矩阵

以各 $0$ 节点为起点进行广度搜索即可，时间复杂度 $O(NM)$，空间复杂度 $O(NM)$ 。

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
// 136 ms, 25.3 MB
class Solution {
public:
    using PII = pair<int, int>;
    const int INF = 0x3F3F3F3F;
    
    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
        if (matrix.empty()) {
            return {};
        }

        const int n = matrix.size();
        const int m = matrix[0].size();
        const int go[4][2] = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};

        queue<PII> q;
        vector<vector<int>> dist(n, vector<int>(m, INF));
        
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (matrix[i][j] == 0) {
                    q.emplace(i, j);
                    dist[i][j] = 0;
                }
        
        while (!q.empty()) {
            PII now = q.front();
            q.pop();
            for (int i = 0; i < 4; i++) {
                int x = now.first + go[i][0];
                int y = now.second + go[i][1];
                if (x >= 0 && y >= 0 && x < n && y < m && dist[x][y] == INF) {
                    dist[x][y] = dist[now.first][now.second] + 1;
                    q.emplace(x, y);
                }
            }
        }
        
        return dist;
    }
};

或用DP解，从左上角开始递推一次，再从右下角开始递推一次。时间复杂度 $O(NM)$，空间复杂度 $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
// 140 ms, 23 MB
class Solution {
public:
    const int INF = 0x3F3F3F3F;
    
    vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
        if (matrix.empty()) {
            return {};
        }

        const int n = matrix.size();
        const int m = matrix[0].size();
        vector<vector<int>> dist(n, vector<int>(m, INF));
        
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (matrix[i][j] == 0)
                    dist[i][j] = 0;
        
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) {
                if (i - 1 >= 0) dist[i][j] = min(dist[i][j], dist[i - 1][j] + 1);
                if (j - 1 >= 0) dist[i][j] = min(dist[i][j], dist[i][j - 1] + 1);
            }
        
        for (int i = n - 1; i >= 0; i--)
            for (int j = m - 1; j >= 0; j--) {
                if (i + 1 < n) dist[i][j] = min(dist[i][j], dist[i + 1][j] + 1);
                if (j + 1 < m) dist[i][j] = min(dist[i][j], dist[i][j + 1] + 1);
            }

        return dist;
    }
};

Apr.14 两数相加

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
// 52 ms, 73.9 MB
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        stack<int> s1, s2;
        for (; l1; l1 = l1->next) s1.push(l1->val);
        for (; l2; l2 = l2->next) s2.push(l2->val);
        int carry = 0;
        ListNode* ans = nullptr;
        while (!s1.empty() || !s2.empty() || carry != 0) {
            int a = s1.empty() ? 0 : s1.top();
            int b = s2.empty() ? 0 : s2.top();
            if (!s1.empty()) s1.pop();
            if (!s2.empty()) s2.pop();
            int cur = a + b + carry;
            carry = cur / 10;
            cur %= 10;
            ListNode* curnode = new ListNode(cur);
            curnode->next = ans;
            ans = curnode;
        }
        return ans;
    }
};

Apr.13 设计推特

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
// 76 ms, 20.5 MB
class Twitter {
public:
    /** Initialize your data structure here. */
    Twitter(): time(0) {}
    
    /** Compose a new tweet. */
    void postTweet(int userId, int tweetId) {
        mp[userId].addTweet(time, tweetId);
    }
    
    /** Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent. */
    vector<int> getNewsFeed(int userId) {
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> heap;
        for (int followee : mp[userId].followees) {
            for (const pair<int, int>& timeId : mp[followee].tweets) {
                heap.push(timeId);
                if (heap.size() > 10) heap.pop();
            }
        }
        for (const pair<int, int>& timeId : mp[userId].tweets) {
            heap.push(timeId);
            if (heap.size() > 10) heap.pop();
        }
        vector<int> res;
        res.reserve(heap.size());
        while (!heap.empty()) {
            res.push_back(heap.top().second);
            heap.pop();
        }
        reverse(res.begin(), res.end());
        return res;
    }
    
    /** Follower follows a followee. If the operation is invalid, it should be a no-op. */
    void follow(int followerId, int followeeId) {
        if (followerId == followeeId) return;
        mp[followerId].followees.insert(followeeId);
    }
    
    /** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
    void unfollow(int followerId, int followeeId) {
        mp[followerId].followees.erase(followeeId);
    }

private:
    struct Node {
        unordered_set<int> followees;
        list<pair<int, int>> tweets; // 1st-time, 2nd-id
        
        void addTweet(int& time, int id) {
            if (tweets.size() == 10) tweets.pop_back();
            tweets.emplace_front(++time, id);
        }
    };
    
    int time;
    unordered_map<int, Node> mp;
};

/**
 * Your Twitter object will be instantiated and called as such:
 * Twitter* obj = new Twitter();
 * obj->postTweet(userId,tweetId);
 * vector<int> param_2 = obj->getNewsFeed(userId);
 * obj->follow(followerId,followeeId);
 * obj->unfollow(followerId,followeeId);
 */

Apr.12 交点

参考官方题解

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
class Solution:
    def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:
        # 判断 (xk, yk) 是否在「线段」(x1, y1)~(x2, y2) 上
        # 这里的前提是 (xk, yk) 一定在「直线」(x1, y1)~(x2, y2) 上
        def inside(x1, y1, x2, y2, xk, yk):
            # 若与 x 轴平行，只需要判断 x 的部分
            # 若与 y 轴平行，只需要判断 y 的部分
            # 若为普通线段，则都要判断
            return (x1 == x2 or min(x1, x2) <= xk <= max(x1, x2)) and (y1 == y2 or min(y1, y2) <= yk <= max(y1, y2))
        
        def update(ans, xk, yk):
            # 将一个交点与当前 ans 中的结果进行比较
            # 若更优则替换
            return [xk, yk] if not ans or [xk, yk] < ans else ans
        
        x1, y1 = start1
        x2, y2 = end1
        x3, y3 = start2
        x4, y4 = end2

        ans = list()
        # 判断 (x1, y1)~(x2, y2) 和 (x3, y3)~(x4, y3) 是否平行
        if (y4 - y3) * (x2 - x1) == (y2 - y1) * (x4 - x3):
            # 若平行，则判断 (x3, y3) 是否在「直线」(x1, y1)~(x2, y2) 上
            if (y2 - y1) * (x3 - x1) == (y3 - y1) * (x2 - x1):
                # 判断 (x3, y3) 是否在「线段」(x1, y1)~(x2, y2) 上
                if inside(x1, y1, x2, y2, x3, y3):
                    ans = update(ans, x3, y3)
                # 判断 (x4, y4) 是否在「线段」(x1, y1)~(x2, y2) 上
                if inside(x1, y1, x2, y2, x4, y4):
                    ans = update(ans, x4, y4)
                # 判断 (x1, y1) 是否在「线段」(x3, y3)~(x4, y4) 上
                if inside(x3, y3, x4, y4, x1, y1):
                    ans = update(ans, x1, y1)
                # 判断 (x2, y2) 是否在「线段」(x3, y3)~(x4, y4) 上
                if inside(x3, y3, x4, y4, x2, y2):
                    ans = update(ans, x2, y2)
            # 在平行时，其余的所有情况都不会有交点
        else:
            # 联立方程得到 t1 和 t2 的值
            t1 = (x3 * (y4 - y3) + y1 * (x4 - x3) - y3 * (x4 - x3) - x1 * (y4 - y3)) / ((x2 - x1) * (y4 - y3) - (x4 - x3) * (y2 - y1))
            t2 = (x1 * (y2 - y1) + y3 * (x2 - x1) - y1 * (x2 - x1) - x3 * (y2 - y1)) / ((x4 - x3) * (y2 - y1) - (x2 - x1) * (y4 - y3))
            # 判断 t1 和 t2 是否均在 [0, 1] 之间
            if 0.0 <= t1 <= 1.0 and 0.0 <= t2 <= 1.0:
                ans = [x1 + t1 * (x2 - x1), y1 + t1 * (y2 - y1)]

        return ans

Apr.11 鸡蛋掉落

参考官方题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        def f(x):
            ans = 0
            r = 1
            for i in range(1, K+1):
                r *= x-i+1
                r //= i
                ans += r
                if ans >= N: break
            return ans

        lo, hi = 1, N
        while lo < hi:
            mi = (lo + hi) // 2
            if f(mi) < N:
                lo = mi + 1
            else:
                hi = mi
        return lo

Apr.10 翻转字符串里的单词

模拟即可。这里给出原地算法和非原地算法。先给出空间 $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
// 16 ms, 8.2 MB
class Solution {
public:
    string reverseWords(string s) {
        string word;
        string res;
        
        auto update = [&word, &res] {
            if (!res.empty()) res += ' ';
            res.append(word.rbegin(), word.rend());
            word.clear();
        };
        
        for (int i = (int)s.size() - 1; i >= 0; i--) {
            if (s[i] == ' ') {
                if (!word.empty()) update();
            } else {
                word += s[i];
            }
        }
        
        if (!word.empty()) update();
        
        return res;
    }
};

我的额外空间 $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
// 8 ms, 7.6 MB
class Solution {
public:
    string reverseWords(string s) {
        reverse(s.begin(), s.end());
        int wordBegin = -1;
        int pos = 0;
        
        auto update = [&] (int i) {
            if (wordBegin == -1) return;
            if (pos) s[pos++] = ' '; // 不是第一个单词
            for (int j = wordBegin; j < i; ) s[pos++] = s[j++];
            reverse(s.begin() + pos - (i - wordBegin), s.begin() + pos); 
            wordBegin = -1;
        };
        
        for (size_t i = 0; i < s.size(); i++) {
            if (s[i] == ' ') update(i);
            else if (wordBegin == -1) wordBegin = i;
        }
        
        update(s.size());
        s.erase(s.begin() + pos, s.end());
        
        return s;
    }
};

Apr.9 括号生成

如下是我的解法。其中parenthesToAdd表示还需要加多少个左括号，parenthesToEnd表示还需要加多少个右括号：

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
// 4 ms, 13.9 MB
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> res;
        string tmp;
        dfs(res, n, 0, tmp);
        return res;
    }

private:
    void dfs(vector<string>& res, int parenthesToAdd, int parenthesToEnd, string &now) {
        if (parenthesToAdd == 0 && parenthesToEnd == 0) {
            res.emplace_back(now);
            return;
        }
        if (parenthesToAdd > 0) {
            now.push_back('(');
            dfs(res, parenthesToAdd - 1, parenthesToEnd + 1, now);
            now.pop_back();
        }
        if (parenthesToEnd > 0) {
            now.push_back(')');
            dfs(res, parenthesToAdd, parenthesToEnd - 1, now);
            now.pop_back();
        }
    }
};

官方题解极简写法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 20 ms, 15.5 MB
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        if (n == 0) {
            return vector<string>{""};
        }
        vector<string> res;
        for (int c = 0; c < n; c++) {
            for (const string& left : generateParenthesis(c)) {
                for (const string &right : generateParenthesis(n - c - 1)) {
                    res.emplace_back("(" + left + ")" + right);
                }
            }
        }
        return res;
    }
};

Apr.8 机器人的运动范围

首先这是一个bfs问题，我们可以直接用bfs解决。
特别地，本题有一个优化：假设左上角为坐标原点$(0,0)$，则每次bfs扩展时仅需扩展该点的右边和下边。如果有一个可达的新点在当前点的正上方，则那个点一定已经被之前bfs时某一次访问过。

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
// 0 ms, 7.1 MB
class Solution {
public:
    int movingCount(int m, int n, int k) {
        auto digitSum = [](int x) {
            int res = 0;
            while (x) {
                res += x % 10;
                x /= 10;
            }
            return res;
        };
        
        // use vector<char> instead of vector<bool>
        vector<vector<char>> vis(m, vector<char>(n));
        
        queue<pair<int, int>> q;
        q.emplace(0, 0);
        vis[0][0] = 1;
        
        const int dx[] = {0, 1};
        const int dy[] = {1, 0};
        int ans = 0;
        
        while (!q.empty()) {
            auto now = q.front();
            ++ans;
            q.pop();
            for (int i = 0; i < 2; i++) {
                pair<int, int> next(now.first + dx[i], now.second + dy[i]);
                if (next.first < m && next.second < n && digitSum(next.first) + digitSum(next.second) <= k &&
                   !vis[next.first][next.second]) {
                    q.emplace(next.first, next.second);
                    vis[next.first][next.second] = 1;
                }
            }
        }
        
        return ans;
    }
};

Apr.7 旋转矩阵

原地算法，旋转过程如代码下方注释所示。

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
// 8 ms, 7.4 MB
class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        const int n = matrix.size();
        for (int i = 0; i < n / 2; i++) { // 每次循环处理一圈 从外到内
            for (int j = i; j < n - 1 - i; j++) {
                swap(matrix[i][j], matrix[j][n - 1 - i]);
                swap(matrix[i][j], matrix[n - 1 - i][n - 1 - j]);
                swap(matrix[i][j], matrix[n - 1 - j][i]);
            }
        }
    }
};

/*
 5  1  9 11    [11] 1  9 [5]   [16] 1  9  5    [15] 1  9  5
 2  4  8 10      2  4  8 10      2  4  8 10      2  4  8 10
13  3  6  7     13  3  6  7     13  3  6  7     13  3  6  7
15 14 12 16     15 14 12 16     15 14 12[11]   [16]14 12 11

15  1  9  5     15[10] 9  5     15[12]  9  5    15[13] 9  5
 2  4  8 10      2  4  8 [1]     2  4   8  1     2  4  8  1
13  3  6  7     13  3  6  7     13  3   6  7   [12] 3  6  7
16 14 12 11     16 14 12 11     16 14 [10]11    16 10 12 11 
...
*/

Apr.6 编辑距离

时间复杂度 $O(N*M)$ 的DP。见官方题解。

Apr.5 LFU缓存

解法一：双哈希表配合链表，时间复杂度 $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
65
66
67
68
69
70
71
72
73
// 256 ms, 39.8 MB
class LFUCache {
private:
    struct Node {
        int key, value, freq;
    };

    typedef typename list<Node>::iterator iter_type;
    map<int, iter_type> key_iter_map;
    map<int, list<Node>> frequency_nodeList_map;
    int capacity;
    int minFreq;

public:
    LFUCache(int _capacity) : capacity(_capacity), minFreq(-1) {}

    int get(int key) {
        auto it = key_iter_map.find(key);
        if (it == key_iter_map.end()) return -1;
        return visit(it, it->second->value);
    }

    void put(int key, int value) {
        auto iter = key_iter_map.find(key);
        if (iter == key_iter_map.end()) {
            if (int(key_iter_map.size()) == capacity) {
                dropLFU();
            }
            if (int(key_iter_map.size()) < capacity) {
                minFreq = 1;
                frequency_nodeList_map[1].push_front({key, value, 1});
                key_iter_map.emplace(key, frequency_nodeList_map[1].begin());
            }
        } else {
            visit(iter, value);
        }
    }

    // 用参数value代替缓存中原有的value,更新访问频率和最后一次访问时间,返回修改前的value
    int visit(map<int, iter_type>::iterator iter, int value) {
        int freq = iter->second->freq;
        iter_type nodeIter = iter->second;
        int oldValue = nodeIter->value;

        frequency_nodeList_map[freq].erase(nodeIter);
        if (freq == minFreq && frequency_nodeList_map[freq].empty()) {
            ++minFreq;
            frequency_nodeList_map.erase(freq);
        }

        frequency_nodeList_map[freq + 1].push_front({iter->first, value, freq + 1});
        iter->second = frequency_nodeList_map[freq + 1].begin();

        return oldValue;
    }

    void dropLFU() {
        if (key_iter_map.empty()) return;
        auto iter = --frequency_nodeList_map[minFreq].end();
        key_iter_map.erase(iter->key);
        frequency_nodeList_map[minFreq].pop_back();
        if (frequency_nodeList_map[minFreq].empty()) {
            frequency_nodeList_map.erase(minFreq);
            ++minFreq;
        }
    }
};
/**
 * 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);
 */

解法二：单哈希表配合双向链表，时间复杂度 $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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
// 216 ms, 39.8 MB
class LFUCache {
private:
    struct Node {
        int key, value, freq;
    };

    using pair_list_iter_t = list<pair<int, list<Node>>>::iterator;
    using node_list_iter_t = list<Node>::iterator;
    unordered_map<int, pair<pair_list_iter_t, node_list_iter_t>> keyItersMap;
    list<pair<int, list<Node>>> freqNodeList;
    int capacity;
    int size;

public:
    LFUCache(int _capacity) : capacity(_capacity), size(0) {
        freqNodeList.emplace_back(INT_MAX, list<Node>());
    }

    int get(int key) {
        auto iter = keyItersMap.find(key);
        if (iter == keyItersMap.end()) return -1;
        pair_list_iter_t pairListIter = iter->second.first;
        node_list_iter_t nodeListIter = iter->second.second;
        pair_list_iter_t nextPairListIter = pairListIter;
        ++nextPairListIter;
        int freq = nodeListIter->freq;
        int value = nodeListIter->value;
        if (nextPairListIter->first != freq + 1) {
            nextPairListIter =
                freqNodeList.insert(nextPairListIter, make_pair(freq + 1, list<Node>()));
        }
        nextPairListIter->second.push_front({key, value, freq + 1});
        keyItersMap[key] = make_pair(nextPairListIter, nextPairListIter->second.begin());
        pairListIter->second.erase(nodeListIter);
        if (pairListIter->second.empty()) freqNodeList.erase(pairListIter);
        return value;
    }

    void put(int key, int value) {
        auto iter = keyItersMap.find(key);
        if (iter == keyItersMap.end()) {
            if (size == capacity) {
                pair<int, list<Node>>* front = &freqNodeList.front();
                if (front->first != INT_MAX) {
                    keyItersMap.erase(front->second.back().key);
                    front->second.pop_back();
                    if (front->second.empty()) freqNodeList.pop_front();
                    --size;
                }
            }
            if (size < capacity) {
                pair<int, list<Node>>* front = &freqNodeList.front();
                if (front->first != 1) {
                    freqNodeList.push_front(make_pair(1, list<Node>()));
                    front = &freqNodeList.front();
                }
                front->second.push_front({key, value, 1});
                keyItersMap[key] = make_pair(freqNodeList.begin(), front->second.begin());
                ++size;
            }
        } else {
            pair_list_iter_t pairListIter = iter->second.first;
            node_list_iter_t nodeListIter = iter->second.second;
            pair_list_iter_t nextPairListIter = pairListIter;
            ++nextPairListIter;
            int freq = nodeListIter->freq;
            if (nextPairListIter->first != freq + 1) {
                nextPairListIter = freqNodeList.insert(nextPairListIter, make_pair(freq + 1, list<Node>()));
            }
            nextPairListIter->second.push_front({key, value, freq + 1});
            keyItersMap[key] = make_pair(nextPairListIter, nextPairListIter->second.begin());
            pairListIter->second.erase(nodeListIter);
            if (pairListIter->second.empty()) freqNodeList.erase(pairListIter);
        }
    }
};
/**
 * 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);
 */

Apr.4 接雨水

定义以下两个数组

$leftMax[i]=max(leftMax[i-1], height[i])$，特别地 $leftMax[0] = height[0]$；

$rightMax[i] = max(rightMax[i + 1], height[i])$，特别地 $rightMax[n - 1] = height[n - 1]$。

则第 $i (1 \le i \le n-2)$ 个位置内接到的雨水 $trap[i]$ 为

$max(0, min(leftMax[i-1], rightMax[i+1])-height[i])$

也即

$min(leftMax[i], rightMax[i]) - height[i]$

维护从左到右的最大值和从右到左的最大值可以在时间复杂度$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
// 8 ms, 6.9 MB
class Solution {
public:
    int trap(vector<int>& height) {
        if (height.empty()) return 0;
        
        const int n = height.size();
        vector<int> leftMax(n);
        vector<int> rightMax(n);
        
        leftMax[0] = height[0];
        for (int i = 1; i < n; i++)
            leftMax[i] = max(leftMax[i - 1], height[i]);
        
        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--)
            rightMax[i] = max(rightMax[i + 1], height[i]);
        
        int ans = 0;
        for (int i = 1; i < n - 1; i++) {
            ans += max(0, min(leftMax[i - 1], rightMax[i + 1]) - height[i]);
            // 或 ans += min(leftMax[i], rightMax[i]) - height[i];
        }
        return ans;
    }
};

基于公式 $min(leftMax[i], rightMax[i]) - height[i]$。我们假设存在两个变量并赋予初值$left=0$与$right=n-1$，并维护两个变量$lmax$与$rmax$，它们的值为$lmax=leftMax[left]$与$rmax=rightMax[right]$。现在考虑把$left$和$right$尽量往中间推进。

假设我们现在想把$left$往右推进，由公式 $trap[i]=min(leftMax[i], rightMax[i]) - height[i]$，那么也就意味着式子$leftMax[left] \le rightMax[left]$需要被满足。对$right$同理。这样我们能得到一个时间$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
// 8 ms, 6.7 MB
class Solution {
public:
    int trap(vector<int>& height) {
        if (height.empty()) return 0;
        
        const int n = height.size();
        int left = 0, right = n - 1;
        int leftMax = 0, rightMax = 0;
        
        int ans = 0;
        
        while (left <= right) {
            if (leftMax <= rightMax) { // 或 height[left] < height[right]
                leftMax = max(leftMax, height[left]);
                ans += leftMax - height[left];
                ++left;
            } else {
                rightMax = max(rightMax, height[right]);
                ans += rightMax - height[right];
                --right;
            }
        }
        
        return ans;
    }
};

Apr.3 字符串转换整数 (atoi)

本题主要考察的是代码功底，其中要注意判断溢出的处理。如果条件允许可以直接用long long，但下面给出的是用int的解决办法，稍微麻烦些，但是只用了32位的int就解决了问题。

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
// 4 ms, 6.2 MB
class Solution {
public:
    int myAtoi(string str) {      
        if (str.empty()) {
            return 0;
        }

        int res = 0;
        bool neg = false; // 数是否为负
        size_t i = 0;
		
        // 丢弃无用的开头空格
        while (str[i] == ' ') i++;

        // 判断正负号
        if (str[i] == '+' || str[i] == '-') {
            neg = (str[i] == '-');
            i++;
        }

        for (; i < str.size() && isdigit(str[i]); i++) {
            int now = str[i] - '0';
            if (neg) {
                if (res < INT_MIN / 10 || (res == INT_MIN / 10 && now > INT_MAX % 10 + 1)) {
                    return INT_MIN;
                }
                res = res * 10 - now;
            } else {
                if (res > INT_MAX / 10 || (res == INT_MAX / 10 && now > INT_MAX % 10)) {
                    return INT_MAX;
                }
                res = res * 10 + now;
            }
        }
        return res;
    }
};

Apr.2 生命游戏

按照题意模拟即可。下面给出的是原地算法。刚看到这题的时候可能会想再开一个二维数组用于存储新状态，其实所给的参数里面已经有很大的冗余空间给我们使用了（32位的int，只用了1位，还有31位可以拿来存储其他状态）。

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
// 0 ms, 6.9 MB
class Solution {
public:
    void gameOfLife(vector<vector<int>>& board) {
        if (board.empty()) return;
        
        const int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
        const int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
        const int m = board.size();
        const int n = board[0].size();
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int aliveCount = 0;
                for (int k = 0; k < 8; k++) {
                    int x = i + dx[k], y = j + dy[k];
                    if (0 <= x && x < m && 0 <= y && y < n && isAlive(board[x][y])) {
                        ++aliveCount;
                    }
                }
                if (board[i][j]) {
                    // 第1位表示当前状态，第2位表示下一状态
                    if (aliveCount == 2 || aliveCount == 3) board[i][j] |= 2;
                } else {
                    if (aliveCount == 3) board[i][j] |= 2;
                }
            }
        }
        
        for (int i = 0; i < m; i++) 
            for (int j = 0; j < n; j++)
                board[i][j] >>= 1; // 取下一状态
    }

private:
    bool isAlive(int value) {
        return value & 1;
    }
};

Apr.1 有效括号的嵌套深度

由于所给的字符串保证是有效括号字符串，所以将每个括号尽量平均分配即可。
官方题解中考虑的奇偶性更巧妙，但不容易想到。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 0 ms, 7.3 MB
class Solution {
public:
    vector<int> maxDepthAfterSplit(string seq) {
        const int n = seq.size();
        vector<int> res;
        res.reserve(n);
        int depth[2] = {};
        
        for (int i = 0; i < n; i++) {
            if (seq[i] == '(') {
                int smallId = depth[0] > depth[1];
                res.push_back(smallId);
                ++depth[smallId];
            } else {
                int bigId = depth[0] < depth[1];
                res.push_back(bigId);
                --depth[bigId];
            }
        }
        return res;
    }
};
解决Navicat连接MySQL不成功的问题
C++右值引用

分类

标签云

ACM C++ C++11 Linux MySQL Navicat Python STL VMware Valgrind memcheck 数据结构

最新文章

文章

标签

ACM 2
C++ 1
C++11 3
Linux 2
MySQL 1
Navicat 1
Python 1
STL 7
VMware 1
Valgrind 1
memcheck 1
数据结构 7
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×