Leetcode刷题笔记 2

dearfl

2021-06-20

本周Leetcode刷题笔记

345. Reverse Vowels of a String

Q: Given a string s, reverse only all the vowels in the string and return it.

The vowels are 'a', 'e', 'i', 'o', and 'u', and they can appear in both cases.

从两边向中间遍历，都碰到元音之后就交换继续遍历即可。

cpp
bool isVowels(char c) {
    c = tolower(c);
    return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
string reverseVowels(string s) {
    int l = 0, r = s.length() - 1;
    while (l < r) {
        while (l < r && !isVowels(s[l])) l++;
        while (l < r && !isVowels(s[r])) r--;
        swap(s[l++], s[r--]);
    }
    return s;
}

1091. Shortest Path in Binary Matrix

Q: Given an n x n binary matrix grid, return the length of the shortest clear path in the matrix. If there is no clear path, return -1.

A clear path in a binary matrix is a path from the top-left cell (i.e., (0, 0)) to the bottom-right cell (i.e., (n - 1, n - 1)) such that:

All the visited cells of the path are 0.
All the adjacent cells of the path are 8-directionally connected (i.e., they are different and they share an edge or a corner).
The length of a clear path is the number of visited cells of this path.

这个题可以简单的使用BFS做，也可以考虑寻路算法，我第一想法是寻路，就糊了一个简单的实现。

cpp
int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
    int n = grid.size();
    priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> oq;
    set<pair<int, int>> open, close;
    vector<pair<int, int>> direction{ {1, 1}, {1, 0}, {0, 1}, {-1, 1}, {1, -1}, {0, -1}, {-1, 0}, {-1, -1} };
    if (grid[0][0] == 0) {
        oq.emplace(1, pair<int, int>{0, 0});
        open.emplace(0, 0);
    }
    while (!oq.empty()) {
        auto [v, pos] = oq.top();
        auto &[a, b] = pos;
        oq.pop();
        open.erase(pos);
        if (a == n - 1 && b == n - 1) {
            return v;
        }
        if (close.find(pos) == close.end()) {
            close.insert(pos);
            for (auto &[i, j] : direction) {
                int x = a + i, y = b + j;
                if (0 <= x && x < n && 0 <= y && y < n && grid[x][y] == 0 && close.find({x, y}) == close.end()  && open.find({x, y}) == open.end()) {
                    open.emplace(x, y);
                    oq.emplace(v + 1, pair<int, int>{x, y});
                }
            }
        }
    }
    return -1;
}

下面是一份别人实现的BFS，用两个队列依次遍历的做法我好像还是第一次见，感觉不明觉厉。

cpp
int shortestPathBinaryMatrix(vector<vector<int>>& g, int steps = 0) {
    int n = g.size();
    queue<pair<int, int>> q;
    vector<pair<int, int>> direction{ {1, 1},{0, 1},{1, 0},{-1, 1},{1, -1},{0, -1},{-1, 0},{-1, -1} };
    q.emplace(0, 0); // we won't return steps if g[0][0] == 1, so we just push {0, 0} here
    while (!q.empty()) {
        steps++;
        queue<pair<int, int>> q1;
        // for every pos we can reach
        while (!q.empty()) {
            auto [x, y] = q.front();
            q.pop();
            // mark pos as visited
            if (exchange(g[x][y], 1) == 1) {
                continue;
            }
            if (x == n - 1 && y == n - 1) {
                return steps;
            }
            for (auto &[i, j] : direction) {
                int r = x + i, t = y + j;
                if (0 <= r && r < n && 0 <= t && t < n && !g[r][t]) {
                    q1.emplace(r, t);
                }
            }
        }
        // swap queues means we take a extra step
        swap(q, q1);
    }
    return -1;
}

740. Delete and Earn

Q: Given an array nums of integers, you can perform operations on the array.

In each operation, you pick any nums[i] and delete it to earn nums[i] points. After, you must delete every element equal to nums[i] - 1 or nums[i] + 1.

You start with 0 points. Return the maximum number of points you can earn by applying such operations.

从数组中选择一个数n，可以获得对应的n分，但是必须删除所有等于n-1和n+1的数，如果有多个数n，可以获得多个n的分数。求最多可以获得多少分。第一反应我们可以统计不同的数值对应多少分数，然后可以对不同的值进行动态规划。不过我写出来的还是有点繁琐。这里我是先用哈希表存储在将数据移动到vector里，排序再做的，而实际上由于这里数字的范围并不算大，因此可以直接保存到一个大数组内，也不需要排序。

cpp
int deleteAndEarn(vector<int>& nums) {
    unordered_map<int, int> cnt, dp;
    for (const auto &n : nums) {
        cnt[n] += n;
    }
    vector<pair<int, int>> vec{cnt.begin(), cnt.end()};
    sort(vec.begin(), vec.end());
    int lastk = 0, sk = 0;
    for (const auto &[k, v] : vec) {
        if (lastk + 1 < k) {
            dp[k] = dp[lastk] + v;
        } else {
            dp[k] = max(dp[lastk], dp[sk] + v);
        }
        sk = lastk;
        lastk = k;
    }
    int res = 0;
    for (const auto & [k, v] : dp) {
        res = max(res, v);
    }
    return res;
}

可以看到别人的做法可以说是简洁多了，对于每一个数字，我们都有take和skip两种选择，问题的限制是如果当前数字选择take，下一个数字就必须skip，这里是状态机的思想去思考，对于每一步，我们都基于上一步的两个最优状态来进行决策，从而更新当前步骤的状态。

cpp
int deleteAndEarn(vector<int> &nums) {
    vector<int> values(10001, 0);
    for (const auto &n : nums) {
        values[n] += n;
    }
    int take = 0, skip = 0;
    for (int i = 0; i < 10001; i++) {
        int tmp = max(skip + values[i], take);
        skip = take;
        take = tmp;
    }
    return take;
}

1665. Minimum Initial Energy to Finish Tasks

Q: You are given an array tasks where tasks[i] = [actual_i, minimum_i]:

actual_i is the actual amount of energy you spend to finish the $i_{th}$ task.
minimum_i is the minimum amount of energy you require to begin the $i_{th}$ task.

For example, if the task is [10, 12] and your current energy is 11, you cannot start this task. However, if your current energy is 13, you can complete this task, and your energy will be 3 after finishing it.

You can finish the tasks in any order you like.

Return the minimum initial amount of energy you will need to finish all the tasks.

这个问题也挺tricky的，每个任务都有最小要求和实际要求，你可以以任意顺序执行任务，求能完成所有任务的初始能量的最小值。提示实际上有点坑爹，因为提示1说我们可以轻易的求出x是否满足要求，因此我们可以用二分法做。实际上我并没有看出这里的轻易。

当时我猜测应该是可以用<minimum - actual>对任务排序，这样的策略是最优的，但是并没有证明。而且如果这样的策略是最优的话，我们根本不需要用二分法做，只需要倒推就可以得到结果了。

根据别人的解答，我们可以这样理解这个问题，同样是倒推的思维。

假设你是一家公司的总裁，现在你们公司有n个投资者，每个投资者都有一个门槛<minimum - actual>和一个实际的投资额actual，公司的市值需要达到投资者的最低门槛，投资者才会实际投资，而你的目标是获得所有投资者的投资。当公司的市值达不到一个投资者的要求时，你可以自掏腰包来提升公司的市值，但显然你希望你自己投入的越少越好。因此，你将这些投资者按照各自的门槛排序，从最低门槛的投资者开始，如果不够，就自己补足到符合他的门槛。直到公司获得所有的投资。因为每获得一笔投资，公司的市值都会增加，因此这样是最优策略。而最终公司的市值，就对应题目的答案，即能完成所有任务的最小初始能量。

现在从正向来考虑这个问题，对于所有的任务来说，完成这些任务所需要的实际能量是固定的，因此要求最小初始能量实质上就是要求最终剩余能量最小。在公司的例子里，这就对应着你自己的投入。

最后，我当时猜出的代码结果正确，但是一直超时，看样例才知道有组样例的task都是[1, 10000]，可能因此影响了排序算法的效率，换成stable_sort才勉强通过。

cpp
int minimumEffort(vector<vector<int>>& tasks) {
    // 按照门槛排序，门槛相同时，实际投资额无所谓
    stable_sort(tasks.begin(), tasks.end(), [](auto v1, auto v2) { return v1[1] - v1[0] < v2[1] - v2[0]; });
    int res = 0;
    for (const auto &vec : tasks) {
        // 逆推，如果小于门槛则自己补足至门槛
        int actual = vec[0], minimum = vec[1];
        res = max(res + actual, minimum);
    }
    return res;
}

801. Minimum Swaps to Make Sequences Increasing

Q: We have two integer sequences nums1 and nums2 of the same non-zero length.

We are allowed to swap elements nums1[i] and nums2[i]. Note that both elements are in the same index position in their respective sequences.

At the end of some number of swaps, nums1 and nums2 are both strictly increasing. (An array A is strictly increasing if and only if A[0] < A[1] < A[2] < ... < A[A.length - 1].)

Given nums1 and nums2, return the minimum number of swaps to make both sequences strictly increasing. It is guaranteed that the given input always makes it possible.

这个题看起来也挺懵的，思考了一阵之后觉得可以用DP，可以用两个状态表示，比如说dp0[i]表示第i位不交换的情况下最小的交换次数，而dp1[i]表示第i位交换的情况下最小的交换次数，初始状态也简单，dp0[0] = 0, dp1[0] = 1; 接下来可以分类讨论:

如果nums1[i-1] < nums1[i] && nums2[i-1] < nums2[i] && nums1[i-1] < nums2[i] && nums2[i-1] < nums1[i]，那么i-1和i这两位无论交换与否，都满足严格递增的条件，因此：

dp1[i] = min(dp0[i - 1], dp1[i - 1]) + 1;
dp0[i] = min(dp0[i - 1], dp1[i - 1]);

如果只满足nums1[i-1] < nums1[i] && nums2[i-1] < nums2[i]，则说明i-1和i要么都交换，要么都不交换，才能满足严格单调递增的条件，因此：

dp1[i] = dp1[i - 1] + 1;
dp0[i] = dp0[i - 1];

如果只满足nums1[i-1] < nums2[i] && nums2[i-1] < nums1[i]则与情况2相反，i-1和i这两位只能恰好有1位交换，才能满足严格单调递增的条件，因此：

dp1[i] = dp0[i - 1] + 1;
dp0[i] = dp1[i - 1];

理清了这些关系，代码就好写了，同时可以注意到我们并不需要一个数组来存储dp的结果，每一步的结果，都只依赖于上一步的结果，因此可以这样

cpp
int minSwap(vector<int>& nums1, vector<int>& nums2) {
    int n = nums1.size();
    int swap = 1, skip = 0;
    for (int i = 1; i < n; i++) {
        int preSwap = swap, preSkip = skip;
        if (nums1[i-1] < nums1[i] && nums2[i-1] < nums2[i] && nums1[i-1] < nums2[i] && nums2[i-1] < nums1[i]) {
            swap = min(preSkip, preSwap) + 1;
            skip = min(preSkip, preSwap);
        } else if (nums1[i-1] < nums1[i] && nums2[i-1] < nums2[i]) {
            swap = preSwap + 1;
            skip = preSkip;
        } else {
            swap = preSkip + 1;
            skip = preSwap;
        }
    }
    return min(skip, swap);
}

89. Gray Code

Q: An n-bit gray code sequence is a sequence of $2^n$ integers where:

Every integer is in the inclusive range $[0, 2^n - 1]$,
The first integer is 0,
An integer appears no more than once in the sequence,
The binary representation of every pair of adjacent integers differs by exactly one bit, and
The binary representation of the first and last integers differs by exactly one bit.

Given an integer n, return any valid n-bit gray code sequence.

初看也有点懵，关键是相邻的数之间只能有一个位不同，而且必须包含$[0, 2^n-1]$之间所有的整数。

不过很快意识到这个题可以用递归做，如果我有一组n=i时的数组，那么我只需要先遍历一次这个数组，然后将i+1位取反再<反向/循环>遍历一次即可得到n=i+1时对应的数组。而且这里可以比较简单的写成循环的形式。

cpp
vector<int> grayCode(int n) {
    vector<int> res(1 << n, 0);
    for (int i = 0, k = 1; i < n; i++) {
        for (int j = 0; j < k; j++) {
            res[k + j] = res[k - j - 1] | k;
        }
        k = k << 1;
    }
    return res;
}

看讨论时，看到了另一种简单的做法如下，也就是 f(x) = x ^ (x >> 1)，具体就不证明了。

cpp
vector<int> grayCode(int n) {
    vector<int> res(1 << n, 0);
    for (int i = 0; i < (1 << n); i++) {
        res[i] = i ^ (i >> 1);
    }
    return res;
}

1513. Number of Substring with only 1s

Q: Given a binary string s (a string consisting only of '0' and '1's).

Return the number of substrings with all characters 1’s.

Since the answer may be too large, return it modulo $10^9 + 7$.

这个题目相对比较简单，可以想到，每“组”相邻的n个1，都可以增加$\frac{n \times (n + 1)}{2}$个合理的子串。实际写的时候，可以写成这样比较简洁的形式。

cpp
int numSub(string s) {
    int res = 0, count = 0;
    for (const auto c : s) {
        count = c == '1' ? count + 1 : 0;
        res = (res + count) % 1000000007;
    }
    return res;
}

接下来是这周的周赛，我做出来三个，只能说这周相对比较简单吧，其实回头看第四题也不算难，不过缺少经验，确实比较难做出来。

1903. Largest Odd Number in String

Q: You are given a string num, representing a large integer. Return the largest-valued odd integer (as a string) that is a non-empty substring of num, or an empty string “” if no odd integer exists.

A substring is a contiguous sequence of characters within a string.

翻译：找出字符串的最后一个奇数字符

cpp
string largestOddNumber(string num) {
    int i;
    for (i = num.length() - 1; i >= 0; i--) {
        if ((num[i] - '0') % 2 == 1) {
            break;
        }
    }
    return num.substr(0, i + 1);
}

1904. The Number of Full Rounds You Have Played

Q: A new online video game has been released, and in this video game, there are 15-minute rounds scheduled every quarter-hour period. This means that at HH:00, HH:15, HH:30 and HH:45, a new round starts, where HH represents an integer number from 00 to 23. A 24-hour clock is used, so the earliest time in the day is 00:00 and the latest is 23:59.

Given two strings startTime and finishTime in the format “HH:MM” representing the exact time you started and finished playing the game, respectively, calculate the number of full rounds that you played during your game session.

For example, if startTime = “05:20” and finishTime = “05:59” this means you played only one full round from 05:30 to 05:45. You did not play the full round from 05:15 to 05:30 because you started after the round began, and you did not play the full round from 05:45 to 06:00 because you stopped before the round ended.
If finishTime is earlier than startTime, this means you have played overnight (from startTime to the midnight and from midnight to finishTime).

Return the number of full rounds that you have played if you had started playing at startTime and finished at finishTime.

也不难，问特定时间段内有多少个整刻，刻应该是表示15分钟吧。anyway：

cpp
int numberOfRounds(string startTime, string finishTime) {
    int sh = atoi(startTime.substr(0, 2).c_str()), sm = atoi(startTime.substr(3).c_str());
    int fh = atoi(finishTime.substr(0, 2).c_str()), fm = atoi(finishTime.substr(3).c_str());
    if (sh > fh || (sh == fh && sm > fm)) {
        fh += 24;
    }
    return (fh - sh) * 4 + fm / 15 - (sm + 14) / 15;
}

2021-6-22 update: 这道题有一点问题，当起始时间和终止时间再同一个刻里的时候，比如00:01->00:10，代码会输出-1，因此上面的代码需要返回原本结果和0的最大值。即

cpp
return (fh - sh) * 4 + max(0, fm / 15 - (sm + 14) / 15);

但比赛时的数据没有出现这个特殊样例，因此比赛时这样写的人都通过了，然而过后应该是重新计分了，呜呜呜，也就是说我只做对了2题。今天我一看leetcode还以为自己出现幻觉了，呜呜呜。

1905. Count Sub Islands

Q: You are given two m x n binary matrices grid1 and grid2 containing only 0’s (representing water) and 1’s (representing land). An island is a group of 1’s connected 4-directionally (horizontal or vertical). Any cells outside of the grid are considered water cells.

An island in grid2 is considered a sub-island if there is an island in grid1 that contains all the cells that make up this island in grid2.

Return the number of islands in grid2 that are considered sub-islands.

也不算难，就是写起来有点烦，我当时有点懵，写的比较复杂，实际上完全没有必要向我这样先把island的坐标提取出来再判断，边提取坐标边DFS判断应该也是ok的，只能说，能过就行。

cpp
void helper(vector<vector<int>>& grid, vector<pair<int, int>>& island, int x, int y) {
    int direction[4][2] = { {-1, 0}, {0, -1}, {0, 1}, {1, 0} };
    if (0 <= x && x < grid.size() && 0 <= y && y < grid[0].size() && grid[x][y] == 1) {
        grid[x][y] = 0;
        island.emplace_back(x, y);
        for (auto &[m, n] : direction) {
            helper(grid, island, x + m, y + n);
        }
    }
}
vector<vector<pair<int, int>>> getIslands(vector<vector<int>>& grid) {
    vector<vector<pair<int, int>>> ans;
    int count = -1;
    for (int i = 0; i < grid.size(); i++) {
        for (int j = 0; j < grid[i].size(); j++) {
            if (grid[i][j] == 1) {
                vector<pair<int, int>> island;
                helper(grid, island, i, j);
                ans.push_back(island);
            }
        }
    }
    return ans;
}
int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {
    int count = 0;
    for (auto &vec : getIslands(grid2)) {
        bool flag = true;
        for (const auto &[x, y] : vec) {
            flag &= grid1[x][y];
        }
        count += flag;
    }
    return count;
}

1906. Minimum Absolute Difference Queries

Q: The minimum absolute difference of an array a is defined as the minimum value of |a[i] - a[j]|, where 0 <= i < j < a.length and a[i] != a[j]. If all elements of a are the same, the minimum absolute difference is -1.

For example, the minimum absolute difference of the array [5,2,3,7,2] is |2 - 3| = 1. Note that it is not 0 because a[i] and a[j] must be different.

You are given an integer array nums and the array queries where queries[i] = [li, ri]. For each query i, compute the minimum absolute difference of the subarray nums[li…ri] containing the elements of nums between the 0-based indices li and ri (inclusive).

Return an array ans where ans[i] is the answer to the ith query.

A subarray is a contiguous sequence of elements in an array.

The value of |x| is defined as:

x if x >= 0.
-x if x < 0.

应该是我参加以来第一道不是hard的压轴题了，难度也是Medium，可惜我当时没有很好的思路，我当时的思路是DP把所有子串的结果都求出来，然而日常超时。实际上因为题目限制数值范围在1-100之间，因此，我们可以一个数组count[n][k]统计每个数字出现的次数，即count[i][k]表示[0...i]之间k出现的次数，因此我们可以更容易的获取[i...j]之间各个数字出现的次数，然后求出所有出现的数字的最小间隔即可。

cpp
vector<int> minDifference(vector<int>& nums, vector<vector<int>>& queries) {
    vector<vector<int>> preSum(nums.size() + 1, vector<int>(101, 0));
    vector<int> cnt(101), ans;
    for (int i = 1; i <= nums.size(); i++) {
        for (int j = 1; j < 101; j++) {
            preSum[i][j] = preSum[i - 1][j];
        }
        preSum[i][nums[i - 1]]++;
    }
    for (auto &vec : queries) {
        int l = vec[0], r = vec[1] + 1;
        for (int i = 1; i < 101; i++) {
            cnt[i] = preSum[r][i] - preSum[l][i];
        }
        int m = INT_MAX, pre = -1;
        for (int i = 0; i < 101; i++) {
            if (cnt[i] == 0) continue;
            if (pre != -1) m = min(m, abs(i - pre));
            pre = i;
        }
        ans.push_back(m == INT_MAX ? -1 : m);
    }
    return ans;
}

小结：总的来说这周的周赛还行吧，虽然比较简单，但毕竟我开始刷题参赛也不久，慢慢来吧，相比前几次也算是有一点点进步。