Leetcode刷题笔记 5

本周Leetcode刷题笔记

本周嗓子一直在咳嗽，去医院检查结果是急性呼吸道感染，吃了点药，也只能说好了点，但是没完全好。anyway，总之我就趁机偷懒了一点，基本上多找了点简单题做做，然后这周也没有双周赛，所以总的来说这周做题量比以往小。然后这周也懒得写之前做的题的笔记了。

867. Transpose Matrix

Given a 2D integer array matrix, return the transpose of matrix.

The transpose of a matrix is the matrix flipped over its main diagonal, switching the matrix’s row and column indices.

矩阵转置，很简单不说了

cpp
vector<vector<int>> transpose(vector<vector<int>>& matrix) {
    int m = matrix.size(), n = matrix.back().size();
    vector<vector<int>> ans(n, vector<int>(m));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            ans[j][i] = matrix[i][j];
        }
    }
    return ans;
}

678. Valid Parenthesis String

Given a string s containing only three types of characters: ‘(‘, ‘)’ and ‘*’, return true if s is valid.

The following rules define a valid string:

  • Any left parenthesis ‘(‘ must have a corresponding right parenthesis ‘)’.
  • Any right parenthesis ‘)’ must have a corresponding left parenthesis ‘(‘.
  • Left parenthesis ‘(‘ must go before the corresponding right parenthesis ‘)’.
  • ‘*’ could be treated as a single right parenthesis ‘)’ or a single left parenthesis ‘(‘ or an empty string “”.

这个题挺有意思的，是之前合法括号字符串的进阶版，引入*作为通配符。星号可以作为左括号，右括号或者空。这个题我没有想出特别好的做法，我主要的想法还是暴力，但是这样对于一些星号很多的特殊样例，绝对会超时。因为这个题的括号只有一种，用贪心的想法是比较好解决的，而关键是如何思考到正确的贪心解法。下面介绍两种别人的贪心解法。

  1. 数左括号个数。这个做法的思路在于我们数左括号的个数，根据这个数决定我们后续需要多少个右括号配对。问题在于星号的不确定性，因此我们维护一个范围[cmin, cmax]，cmin表示我们最少需要这么多个右括号来匹配，cmax表示我们最多可以匹配这么多个右括号。那么怎么样才是不合法的呢？如果在任意时刻，cmax小于0，则说明我们没有足够的左括号来匹配右括号，因此是不合法的。当我们到达字符串的结尾，此时我们已经没有更多的括号可以匹配了，如果此时cmin不等于0，则说明我们存在没有进行匹配的括号，那么也是不合法的。

  2. 双栈模拟。双栈模拟的想法是当我们遇到右括号时，我们应当优先使用左括号进行配对，因为星号是通配符，它可以适用于更多情景。双栈模拟的步骤稍微复杂一些，但我个人觉得更加容易理解一点。双栈模拟的思路是用两个栈保存左括号和星号的位置，当我们遇到右括号时，我们优先使用左括号进行配对。如果没有可以配对的左括号，那么再使用星号进行配对。双栈模拟分为2步，第1步是模拟配对过程，第2步是为剩余没有被配对的左括号寻找匹配的星号。

    1. 第1步，如果碰到一个右括号时，左括号和星号的栈都为空，则说明这个右括号没有能与之配对的符号，字符串非法。否则优先使用左括号配对，一直到字符串结束。

    2. 第2步我们进一步检查两个栈里剩余的字符。我们的目的是为每一个左括号都匹配上相应的右括号(使用剩余的星号)。因此这里存在一个要求，每一个左括号必须在对应的星号前面，否则它们是无法进行配对的。这也是为什么我们要使用栈来存储位置的原因。最后如果每一个剩余的左括号都能配对成功，那么整个字符串都是合法的，至于剩余的星号，我们无需关心。

cpp
// 第1种做法
bool checkValidString(string s) {
    int minl = 0, maxl = 0;
    for (const auto c : s) {
        if (c == '(') {
            minl++, maxl++;
        } else if (c == ')') {
            // minl是我们必须匹配的左括号数量，自然大于小于0
            minl = max(minl - 1, 0);
            maxl--;
        } else {
            // 碰到星号时，minl当成右括号，maxl当成左括号
            minl = max(minl - 1, 0);
            maxl++;
        }
        if (maxl < 0) {
            return false;
        }
    }
    return minl == 0;
}
// 双栈模拟
bool checkValidString(string s) {
    vector<int> open, star;
    for (int i = 0; i < s.length(); i++) {
        if (s[i] == '(') {
            open.push_back(i);
        } else if (s[i] == ')') {
            if (open.empty() && star.empty()) {
                // 两个栈都为空，false
                return false;
            }
            // 优先匹配左括号
            if (!open.empty()) {
                open.pop_back();
            } else {
                star.pop_back();
            }
        } else {
            star.push_back(i);
        }
    }
    while (!open.empty()) {
        int idx = open.back();
        open.pop_back();
        // 如果星号栈为空或者栈顶坐标小于左括号坐标，false
        if (star.empty() || star.back() < idx) {
            return false;
        }
        star.pop_back();
    }
    return true;
}

总的来说其实两种方法都是贪心的思路，这里我也没有严格证明这两种方法都是对的，没办法我实在是太菜了。

1636. Sort Array By Increasing Frequency

Given an array of integers nums, sort the array in increasing order based on the frequency of the values. If multiple values have the same frequency, sort them in decreasing order.

Return the sorted array.

按照数组内元素的出现次数排序，没啥好说的，哈希表统计一下出现次数，再按照哈希表数据排序即可。

cpp
vector<int> frequencySort(vector<int>& nums) {
    unordered_map<int, int> cnt;
    for (const auto n : nums) {
        cnt[n]++;
    }
    sort(nums.begin(), nums.end(), [&cnt](int a, int b) {
        return cnt[a] == cnt[b] ? a > b : cnt[a] < cnt[b];
    });
    return nums;
}

48. Rotate Image

You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

旋转nxn的图像/Matrix，要求原地旋转不申请另外一块图像/Matrix内存。

我的想法其实比较笨，类似于每次都旋转四个对应的位置，比如四个角，又或者(1,0),(n-1,1),(n-2,n-1),(0,n-2)，然后循环的选取应该旋转的位置。

cpp
void rotate(vector<vector<int>>& matrix) {
    int n = matrix.size();
    for (int i = 0; i < n / 2; i++) {
        int k = n - 2 * i;
        for (int j = 0; j < k - 1; j++) {
            swap(matrix[i][i + j], matrix[i + j][i + k - 1]);
            swap(matrix[i][i + j], matrix[i + k - j - 1][i]);
            swap(matrix[i + k - j - 1][i], matrix[i + k - 1][i + k - j - 1]);
        }
    }
}

实际上存在更加通用的做法，即先做行反转，再做转置。包括逆时针旋转也有先做列反转，再做转置的做法。

cpp
void rotate(vector<vector<int> > &matrix) {
    reverse(matrix.begin(), matrix.end());
    for (int i = 0; i < matrix.size(); ++i) {
        for (int j = i + 1; j < matrix[i].size(); ++j)
            swap(matrix[i][j], matrix[j][i]);
    }
}

690. Employee Importance

You have a data structure of employee information, which includes the employee’s unique id, their importance value, and their direct subordinates’ id.

You are given an array of employees employees where:

  • employees[i].id is the ID of the ith employee.
  • employees[i].importance is the importance value of the ith employee.
  • employees[i].subordinates is a list of the IDs of the subordinates of the ith employee.

Given an integer id that represents the ID of an employee, return the total importance value of this employee and all their subordinates.

员工重要度，这个题目没啥好说的，本质上就是构造一个树求子树的和，当然并不需要真的构造一个树的数据结构，只要能表达这个关系即可。分为递归和队列的写法，也都差不多，递归写法这边就懒得写了。

cpp
int getImportance(vector<Employee*> employees, int id) {
    int ans = 0;
    unordered_map<int, Employee*> m;
    for (const auto em : employees) {
        m[em->id] = em;
    }
    deque<int> q;
    q.push_back(id);
    while (!q.empty()) {
        id = q.front();
        q.pop_front();
        ans += m[id]->importance;
        for (const auto k : m[id]->subordinates) {
            q.push_back(k);
        }
    }
    return ans;
}

1162. As Far from Land as Possible

Given an n x n grid containing only values 0 and 1, where 0 represents water and 1 represents land, find a water cell such that its distance to the nearest land cell is maximized, and return the distance. If no land or water exists in the grid, return -1.

The distance used in this problem is the Manhattan distance: the distance between two cells (x0, y0) and (x1, y1) is |x0 - x1| + |y0 - y1|.

求海面离岛屿的最大曼哈顿距离。正常来说这个题的思考是从海面出发，比如做DP啥的，但我也没想出特别好的做法。实际上从岛屿出发还比较容易写，时间复杂度也比较低，为o(n^2)。不过需要使用两个队列的trick。

cpp
int maxDistance(vector<vector<int>>& grid) {
    int ans = -1, n = grid.size();
    vector<pair<int, int>> di = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} };
    deque<pair<int, int>> dq, tmp;
    for (int i = 0; i < grid.size(); i++) {
        for (int j = 0; j < grid[i].size(); j++) {
            if (grid[i][j]) {
                dq.emplace_back(i, j);
            }
        }
    }
    while (!dq.empty()) {
        ans++;
        while (!dq.empty()) {
            auto [y, x] = dq.front();
            dq.pop_front();
            for (const auto &[dy, dx] : di) {
                int nx = x + dx, ny = y + dy;
                if (0 <= nx && nx < n && 0 <= ny && ny < n && grid[ny][nx] == 0) {
                    grid[ny][nx] = 1;
                    tmp.emplace_back(ny, nx);
                }
            }
        }
        swap(dq, tmp);
    }
    return ans ? ans : -1;
}

1041. Robot Bounded In Circle

On an infinite plane, a robot initially stands at (0, 0) and faces north. The robot can receive one of three instructions:

  • “G”: go straight 1 unit;
  • “L”: turn 90 degrees to the left;
  • “R”: turn 90 degrees to the right.

The robot performs the instructions given in order, and repeats them forever.

Return true if and only if there exists a circle in the plane such that the robot never leaves the circle.

这个题看着好像不是很容易，实际上只需要稍微分析就会发现，机器人行进距离发散的条件有且仅有一种，那就是当机器人走完一遍指令集后，运动方向不变且运动距离不为0。当且仅当这两者同时成立时，机器人的运动距离才不会被限制在一个圈内，或者说发散。于是剩下的就只有一些编程技巧了。

cpp
bool isRobotBounded(string instructions) {
    int dire[][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };
    int idx = 0;
    int x = 0, y = 0;
    for (const auto c : instructions) {
        switch (c) {
            case 'G':
                x += dire[idx][0];
                y += dire[idx][1];
                break;
            case 'L':
                idx = (idx + 3) % 4;
                break;
            case 'R':
                idx = (idx + 1) % 4;
                break;
        }
    }
    return !(idx == 0 && (x != 0 || y != 0));
}

566. Reshape the Matrix

In MATLAB, there is a handy function called reshape which can reshape an m x n matrix into a new one with a different size r x c keeping its original data.

You are given an m x n matrix mat and two integers r and c representing the row number and column number of the wanted reshaped matrix.

The reshaped matrix should be filled with all the elements of the original matrix in the same row-traversing order as they were.

If the reshape operation with given parameters is possible and legal, output the new reshaped matrix; Otherwise, output the original matrix.

实现Reshape函数，没啥好说的

cpp
vector<vector<int>> matrixReshape(vector<vector<int>>& mat, int r, int c) {
    int m = mat.size(), n = mat.back().size();
    if (m * n != r * c) {
        return mat;
    }
    vector<vector<int>> ans(r, vector<int>(c));
    for (int i = 0; i < r * c; i++) {
        ans[i / c][i % c] = mat[i / n][i % n];
    }
    return ans;
}

100. Same Tree

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

判断两颗二叉树是否是相同，也没啥好说的。

cpp
/*
 * 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) {}
 * };
 */
// 递归写法
bool isSameTree(TreeNode* p, TreeNode* q) {
    if (!p && !q) {
        return true;
    }
    if (!p || !q) {
        return false;
    }
    if (p->val != q->val) {
        return false;
    }
    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
// 队列写法
bool isSameTree(TreeNode* p, TreeNode* q) {
    deque<pair<TreeNode*, TreeNode*>> dq;
    dq.emplace_back(p, q);
    while (!dq.empty()) {
        auto [a, b] = dq.front();
        dq.pop_front();
        if (a && b) {
            if (a->val != b->val) {
                return false;
            }
            dq.emplace_back(a->left, b->left);
            dq.emplace_back(a->right, b->right);
        } else if (a || b) {
            return false;
        }
    }
    return true;
}

700. Search in a Binary Search Tree

You are given the root of a binary search tree (BST) and an integer val.

Find the node in the BST that the node’s value equals val and return the subtree rooted with that node. If such a node does not exist, return null.

在BST上搜索，也很简单

cpp
/*
 * 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) {}
 * };
 */
// 递归写法
TreeNode* searchBST(TreeNode* root, int val) {
    if (!root || root->val == val) {
        return root;
    }
    return searchBST(root->val > val ? root->left : root->right, val);
}
// 循环写法
TreeNode* searchBST(TreeNode* root, int val) {
    auto p = root;
    while (p) {
        if (p->val == val) {
            break;
        } else if (p->val > val) {
            p = p->left;
        } else {
            p = p->right;
        }
    }
    return p;
}

1816. Truncate Sentence

A sentence is a list of words that are separated by a single space with no leading or trailing spaces. Each of the words consists of only uppercase and lowercase English letters (no punctuation).

For example, “Hello World”, “HELLO”, and “hello world hello world” are all sentences.
You are given a sentence s and an integer k. You want to truncate s such that it contains only the first k words. Return s after truncating it.

简单不提

cpp
string truncateSentence(string s, int k) {
    int i = 0;
    while (k > 0 && i < s.length()) {
        if (s[i] == ' ') {
            k--;
        }
        i++;
    }
    return i == s.length() ? s.substr(0, i) : s.substr(0, i - 1);
}

46. Permutations

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

这个题本身其实还是可以的，不过还是建议使用next_permutation，而且作为写完了Next_Permutation那题的人，我个人觉得这并不算作弊。

cpp
vector<vector<int>> permute(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> ans;
    do {
        ans.push_back(nums);
    } while (next_permutation(nums.begin(), nums.end()));
    return ans;
}

接下来是本周的周赛，本周周赛也是喜忧参半，喜的是本周周赛应该是我参加以来名次最好的一次了，忧的是这次的第四题也太难了，实在打击自信心。不过这次周赛的难度可以说是两个极端，前三题基本非常简单，最后一题也真的是难得发指。只能说下次加油。

1920. Build Array from Permutation

Given a zero-based permutation nums (0-indexed), build an array ans of the same length where ans[i] = nums[nums[i]] for each 0 <= i < nums.length and return it.

A zero-based permutation nums is an array of distinct integers from 0 to nums.length - 1 (inclusive).

连题目都没怎么看懂，但是基本上已经把做法写在了题目里，只能说签到题一般不会出现上周双周赛那样的。

cpp
vector<int> buildArray(vector<int>& nums) {
    vector<int> ans;
    for (const auto i : nums) {
        ans.push_back(nums[i]);
    }
    return ans;
}

1921. Eliminate Maximum Number of Monsters

You are playing a video game where you are defending your city from a group of n monsters. You are given a 0-indexed integer array dist of size n, where dist[i] is the initial distance in meters of the ith monster from the city.

The monsters walk toward the city at a constant speed. The speed of each monster is given to you in an integer array speed of size n, where speed[i] is the speed of the ith monster in meters per minute.

The monsters start moving at minute 0. You have a weapon that you can choose to use at the start of every minute, including minute 0. You cannot use the weapon in the middle of a minute. The weapon can eliminate any monster that is still alive. You lose when any monster reaches your city. If a monster reaches the city exactly at the start of a minute, it counts as a loss, and the game ends before you can use your weapon in that minute.

Return the maximum number of monsters that you can eliminate before you lose, or n if you can eliminate all the monsters before they reach the city.

模拟题，大意是类似植物大战僵尸，每个僵尸有一个距离和速度，它们不停的朝你走来，你有一个远程武器，可以在每分钟开始的时候消灭任意一个僵尸。但是如果任意僵尸靠近到了你身边，则游戏失败。如果一个僵尸在某一分钟开始的时候到达，则你来不及开枪，也算是失败。问你最多可以消灭多少僵尸。

这个问题其实很简单，我们关注的其实不是僵尸的距离或者速度，我们关注的是僵尸到达我们身边的时间，只不过这个时间不一定是整数的，因此我们可以新建一个double数组表示每个僵尸到达的时间，再对它们排序，最后我们按照顺序击杀僵尸即可。如果第i个僵尸在第i分钟之前到达了，那说明我们无法及时消灭它，即失败了。然后这边注意一下0-index还是1-index之类的细节即可。

cpp
int eliminateMaximum(vector<int>& dist, vector<int>& speed) {
    vector<double> reach;
    for (int i = 0; i < dist.size(); i++) {
        reach.push_back(1.0 * dist[i] / speed[i]);
    }
    sort(reach.begin(), reach.end());
    for (int i = 0; i < reach.size(); i++) {
        if (i >= reach[i]) {
            return i;
        }
    }
    return reach.size();
}

1922. Count Good Numbers

A digit string is good if the digits (0-indexed) at even indices are even and the digits at odd indices are prime (2, 3, 5, or 7).

  • For example, “2582” is good because the digits (2 and 8) at even positions are even and the digits (5 and 2) at odd positions are prime. However, “3245” is not good because 3 is at an even index but is not even.

Given an integer n, return the total number of good digit strings of length n. Since the answer may be large, return it modulo 109 + 7.

A digit string is a string consisting of digits 0 through 9 that may contain leading zeros.

计数题，也很简单，本质上因为0-9范围内，偶数有5个，质数有4个，因此本质上这个题就是求power(5, n / 2) * power(4, n / 2) * power(5, n % 2)，由于n非常大，所以需要实现快速幂，且需要对结果取模，但是这个也没有什么难度。

cpp
const int mod = 1000000007;
long long helper(long long n, int k) {
    if (n == 0) {
        return 1;
    }
    if (n == 1) {
        return k;
    }
    long long tmp = helper(n / 2, k) % mod;
    long long s = n % 2 ? k : 1;
    return tmp * tmp % mod * s % mod;
}
int countGoodNumbers(long long n) {
    if (n == 1) {
        return 5;
    }
    long long tmp1 = helper(n / 2, 5) % mod;
    long long tmp2 = helper(n / 2, 4) % mod;
    int tmp3 = n % 2 ? 5 : 1;
    return tmp1 * tmp2 % mod * tmp3 % mod;
}

最后一题实在有点超出我的能力范围，所以这里就不写了。总的来说这周虽然名次还ok，但是因为题目本身也比较简单，所以这个名次也没啥含金量，以后加油吧。