Leetcode刷题笔记 6

dearfl

2021-07-11

本周Leetcode刷题笔记

本周也是划水的一周，咳嗽断断续续，还忙里抽闲玩游戏，所以基本只随意做了些题目。

876. Middle of the Linked List

Given a non-empty, singly linked list with head node head, return a middle node of linked list.

If there are two middle nodes, return the second middle node.

获取链表的中点，经典快慢指针

cpp
/**
 * 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* middleNode(ListNode* head) {
        ListNode *fast = head, *slow = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
};

1582. Special Positions in a Binary Matrix

Given a rows x cols matrix mat, where mat[i][j] is either 0 or 1, return the number of special positions in mat.

A position (i,j) is called special if mat[i][j] == 1 and all other elements in row i and column j are 0 (rows and columns are 0-indexed).

简单题，我的做法其实比较繁琐

cpp
class Solution {
public:
    int numSpecial(vector<vector<int>>& mat) {
        int m = mat.size(), n = mat.back().size(), ans = 0;
        for (int i = 0; i < m; i++) {
            int idx = -1, cnt = 0, s = 0;
            for (int j = 0; j < n; j++) {
                if (mat[i][j]) {
                    idx = j;
                    cnt++;
                }
            }
            if (cnt == 1) {
                for (int k = 0; k < m; k++) {
                    s += mat[k][idx];
                }
                if (s == 1) {
                    ans++;
                }
            }
        }
        return ans;
    }
};

这里推荐一个简单的做法，当然是我从讨论里抄来的

cpp
int numSpecial(vector<vector<int>>& mat) {
    vector<int> rows(mat.size()), cols(mat[0].size());
    for (int i = 0; i < rows.size(); ++i)
        for (int j = 0; j < cols.size(); ++j) {
            if (mat[i][j])
                ++rows[i], ++cols[j];
        }
    int res = 0;
    for (int i = 0; i < rows.size(); ++i)
        for (int j = 0; j < cols.size(); ++j)
            if (mat[i][j] && rows[i] == 1 && cols[j] == 1)
                ++res;
    return res;
}

236. Lowest Common Ancestor of a Binary Tree

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

思考的时候有点问题，以为是个很简单的题目，实际上p和q的父节点是无法直接获取的，因此我们无法轻易的获取整棵树的层次结构。先看代码：

cpp
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* helper(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == p || root == q || root == nullptr) {
            return root;
        }
        auto l = helper(root->left, p, q), r = helper(root->right, p, q);
        if (l && r) {
            return root;
        }
        return l ? l : r;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        return helper(root, p, q);
    }
};

如果碰到了p或者q，就返回该节点，其他情况下，我们返回的都是空指针，这样在递归返回之后，我们就可以判断p节点或者q节点是否在该根节点下。对于根节点，我们分别遍历他的左右节点，如果返回的结果均不为空指针，则说明p和q分别在跟节点的左右节点下，因此p和q的最低公共祖先即为根节点本身。如果返回的结果只有一个有效节点，另一个是空指针，则我们只需要返回该结果即可。

637. Average of Levels in Binary Tree

Given the root of a binary tree, return the average value of the nodes on each level in the form of an array. Answers within 10-5 of the actual answer will be accepted.

层序遍历求每层的平均值，我个人比较喜欢双队列的做法

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) {}
 * };
 */
class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        deque<TreeNode *> dq, swp;
        vector<double> ans;
        dq.push_back(root);
        long long sum = 0, cnt = 0;
        while (!dq.empty()) {
            sum = 0, cnt = 0;
            while (!dq.empty()) {
                auto node = dq.front();
                dq.pop_front();
                sum += node->val;
                cnt++;
                if (node->left) {
                    swp.push_back(node->left);
                }
                if (node->right) {
                    swp.push_back(node->right);
                }
            }
            ans.push_back(1.0 * sum / cnt);
            swap(dq, swp);
        }
        return ans;
    }
};

985. Sum of Even Numbers After Queries

We have an array nums of integers, and an array queries of queries.

For the i-th query val = queries[i][0], index = queries[i][1], we add val to nums[index]. Then, the answer to the i-th query is the sum of the even values of A.

(Here, the given index = queries[i][1] is a 0-based index, and each query permanently modifies the array nums.)

Return the answer to all queries. Your answer array should have answer[i] as the answer to the i-th query.

简单题，根据相应的query更新结果即可。

cpp
class Solution {
    public:
        vector<int> sumEvenAfterQueries(vector<int>& nums, vector<vector<int>>& queries) {
            vector<int> ans;
            int s = 0;
            for (const auto n : nums) {
                if (n % 2 == 0) {
                    s += n;
                }
            }
            for (const auto query : queries) {
                int val = query[0], idx = query[1];
                int v1 = nums[idx], v2 = v1 + val;
                s -= v1 % 2 == 0 ? v1 : 0;
                s += v2 % 2 == 0 ? v2 : 0;
                nums[idx] += val;
                ans.push_back(s);
            }
            return ans;
        }
};

829. Consecutive Numbers Sum

Given a positive integer n, how many ways can we write it as a sum of consecutive positive integers?

某次面试的时候做过这个题，不过当时没有细想，写的非常丑，这次仔细思考了一下，发现其实比较简单。

cpp
class Solution {
public:
    int consecutiveNumbersSum(int n) {
        int ans = 0;
        for (int i = 1; (i - 1) * i < 2 * n; i++) {
            if ((n - (i - 1) * i / 2) % i == 0) {
                ans++;
            }
        }
        return ans;
    }
};

假设一共有k个数，第一个数为a，则这些数的总和为$s = \frac{(a + a + k - 1) \times k}{2}$，那么我们可以得到$a = \frac{s - \frac{1}{2}(k-1)k}{k}$，能表示为连续整数之和等价于a为整数，而a为整数等价于(s - k * (k - 1) / 2) % k == 0。我们从k=1开始遍历，直到s - k * (k - 1) / 2小于0为止。

接下来是本周的双周赛和周赛，本周双周赛我做的还行，虽然最后一题还是不会。周赛因为最后两题都难度很大，所以做的比较差，总之这周还行吧，继续加油。

1925. Count Square Sum Triples

A square triple (a,b,c) is a triple where a, b, and c are integers and a2 + b2 = c2.

Given an integer n, return the number of square triples such that 1 <= a, b, c <= n.

签到题，o(N^3)算法走起

cpp
class Solution {
public:
    int countTriples(int n) {
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = i; j <= n; j++) {
                for (int k = i + 1; k <= n; k++) {
                    if (i * i + j * j == k * k) {
                        ans += 2;
                    }
                }
            }
        }
        return ans;
    }
};

1926. Nearest Exit from Entrance in Maze

You are given an m x n matrix maze (0-indexed) with empty cells (represented as ‘.’) and walls (represented as ‘+’). You are also given the entrance of the maze, where entrance = [entrancerow, entrancecol] denotes the row and column of the cell you are initially standing at.

In one step, you can move one cell up, down, left, or right. You cannot step into a cell with a wall, and you cannot step outside the maze. Your goal is to find the nearest exit from the entrance. An exit is defined as an empty cell that is at the border of the maze. The entrance does not count as an exit.

Return the number of steps in the shortest path from the entrance to the nearest exit, or -1 if no such path exists.

寻路问题，返回最短路径的长度，简单的BFS即可。这里因为我个人比较喜欢双队列的trick，又有点嫌麻烦没用deque<pair<int,int>>而是直接用了deque<int>，所以写的不是很明白。不过大体思路基本都没什么问题，就懒得改了。

cpp
class Solution {
public:
    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
        int h = maze.size(), w = maze.back().size(), x = entrance[1], y = entrance[0];
        maze[y][x] = '*';
        deque<int> dq, swp;
        int di[][2] = { {0, 1}, {1, 0}, {-1, 0}, {0, -1} };
        int ans = 0;
        dq.push_back(y * w + x);
        while (!dq.empty()) {
            ans++;
            while (!dq.empty()) {
                int k = dq.front();
                dq.pop_front();
                int m = k / w, n = k % w;
                for (auto [a, b] : di) {
                    int s = m + a, d = n + b;
                    if (0 <= s && s < h && 0 <= d && d < w) {
                        if (maze[s][d] == '.') {
                            maze[s][d] = '*';
                            if (s == 0 || s == h - 1 || d == 0 || d == w - 1) {
                                return ans;
                            }
                            swp.push_back(s * w + d);
                        }
                    }
                }
            }
            swap(dq, swp);
        }
        return -1;
    }
};

1927. Sum Game

Alice and Bob take turns playing a game, with Alice starting first.

You are given a string num of even length consisting of digits and ‘?’ characters. On each turn, a player will do the following if there is still at least one ‘?’ in num:

Choose an index i where num[i] == ‘?’.
Replace num[i] with any digit between ‘0’ and ‘9’.
The game ends when there are no more ‘?’ characters in num.

For Bob to win, the sum of the digits in the first half of num must be equal to the sum of the digits in the second half. For Alice to win, the sums must not be equal.

For example, if the game ended with num = “243801”, then Bob wins because 2+4+3 = 8+0+1. If the game ended with num = “243803”, then Alice wins because 2+4+3 != 8+0+3.
Assuming Alice and Bob play optimally, return true if Alice will win and false if Bob will win.

本周做出的最难题目，大意是两人玩游戏，有一个长度为偶数只包含数字或问号的字符串，由AB两人分别将问号替换为具体的数字，A的目的是使字符串前后两半的和不相等，而B的目的则相反。假设A和B都使用最佳策略，问A是否必胜。

首先很容易想到的一点是，假如问号个数为奇数个，则A必胜。因为此时由A最后操作，而A只需要两边不相等即可，因此A必胜。

另外一个点则是，如果两边都有问号，则这些问号可以被抵消。这一点没有严格的证明，但是我们可以这样稍微思考一下，作为A来说，他是希望两边的差尽可能大的，因此他可以在和比较大的那边放9，而作为回应，B只能在另外一边同样放9来抵消这个差距。因此这些问号就这样被抵消了。

当我们抵消完某一边的问号之后，真正的问题就浮出水面了。我们先考虑一个简单例子：52??，这个例子A是必胜的，只要A将某一个问号替换为9，那么无论如何B都失败了。为什么会这样，因为左边的和为7小于9，那么大于9如何呢？99??，A也是必胜的，A只需要将其中某个问号替换为0，则B无论如何也会失败。那么等于9呢，54??，这样的情况则B是必胜的，为什么，因为无论A将某一个问号替换成多少，都存在另一个对应的数，可以让两边相等。到这里我们大致有了一些思路，也就是如果一对问号如果换成两个和为9的数，能让两边的和相等，则B必胜，否则A必胜。如果有多对问号，则每对问号都需要满足这个条件。

分析到这里，题目就做出来了，当然我的代码写的很差，这里我放上我写的代码和某大佬的代码做对比。

cpp
class Solution {
public:
    bool sumGame(string num) {
        int n = num.length(), half = n / 2;
        int s1 = 0, s2 = 0, cnt1 = 0, cnt2 = 0;
        for (int i = 0; i < half; i++) {
            if (num[i] == '?') {
                cnt1++;
            } else {
                s1 += num[i] - '0';
            }
        }
        for (int i = half; i < n; i++) {
            if (num[i] == '?') {
                cnt2++;
            } else {
                s2 += num[i] - '0';
            }
        }
        if (cnt1 + cnt2 == 0) {
            return s1 != s2;
        }
        if ((cnt1 + cnt2) % 2 == 1) {
            return true;
        }
        if (cnt1 == cnt2 && s1 == s2) {
            return false;
        }
        if ((cnt1 > cnt2 && s1 > s2) || (cnt1 < cnt2 && s1 < s2)) {
            return true;
        }
        return cnt1 > cnt2 ? s2 - s1 != (cnt1 - cnt2) / 2 * 9 : s1 - s2 != (cnt2 - cnt1) / 2 * 9;
    }
};
class Solution {
public:
    bool sumGame(string num) {
        int n = num.length(), x = 0, a = 0, b = 0;
        for (int i = 0; i < n / 2; i++) {
            num[i] == '?' ? a++ : x += num[i] - '0';
        }
        for (int i = n / 2; i < n; i++) {
            num[i] == '?' ? b++ : x -= num[i] - '0';
        }
        if (a + b & 1) {
            return true;
        }
        return x - 9 * b + (a + b) / 2 * 9;
    }
};

1929. Concatenation of Array

Given an integer array nums of length n, you want to create an array ans of length 2n where ans[i] == nums[i] and ans[i + n] == nums[i] for 0 <= i < n (0-indexed).

Specifically, ans is the concatenation of two nums arrays.

Return the array ans.

周赛签到题，不提。

cpp
class Solution {
public:
    vector<int> getConcatenation(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            nums.push_back(nums[i]);
        }
        return nums;
    }
};

1930. Unique Length-3 Palindromic Subsequences

Given a string s, return the number of unique palindromes of length three that are a subsequence of s.

Note that even if there are multiple ways to obtain the same subsequence, it is still only counted once.

A palindrome is a string that reads the same forwards and backwards.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

For example, “ace” is a subsequence of “abcde”.

周赛第二题，求字符串的子序列里长度为3的回文子序列有多少。字符串本身只由26个小写字母构成。

这个题的切入点在于虽然字符串总长度可能非常长，但字符串本身只由26个小写字母构成，而长度为3的回文子序列的总量很有限，只有最多26x26=676个，那么我们可以将每种字符的下标存储下来，再穷举所有的回文序列，判断该序列是否存在于字符串中。

cpp
class Solution {
public:
    int countPalindromicSubsequence(string s) {
        int ans = 0;
        vector<vector<int>> idx(26);
        for (int i = 0; i < s.length(); i++) {
            // 记录下所有字符对应的坐标，这里的坐标肯定是递增的
            idx[s[i] - 'a'].push_back(i);
        }
        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < 26; j++) {
                // 判断子序列 { 'a' + i, 'a' + j, 'a' + i } 是否存在
                if (idx[i].size() < 2 || idx[j].empty()) {
                    // 显然不成立
                    continue;
                }
                // 这里l是字符i首次出现的位置，r是最后出现的位置
                // 我们需要确定字符j是否在区间(l, r)内出现过
                int l = idx[i].front(), r = idx[i].back();
                // [it1, it2) 是一个区间，区间内的坐标k均满足 l < k < r，因此如果该区间不为空，则我们可以得到一个回文子序列
                auto it1 = upper_bound(idx[j].begin(), idx[j].end(), l);
                auto it2 = lower_bound(idx[j].begin(), idx[j].end(), r);
                if (it1 != it2) {
                    ans++;
                }
            }
        }
        return ans;
    }
};

这个问题的另一个思路是，对于每种可能的字符，我们都获取它们的最左和最右的位置，然后将所有中间的字符都算做一种，这种方法需要用set来进行去重。也比较简单，我这里就不写了。

总的来说，这周的双周赛做的还不错，周赛就很一般了，不过这周周赛难度确实比较大，也是没办法的事，下周加油。另外最近发现vim真的挺好用的，定义个宏啥的真的可以省非常多操作。