Leetcode第49场双周赛

Leetcode第49场双周赛

Louis 2629 2021-04-15

image.png
周赛连接：第 49 场双周赛
又是大家喜闻乐见的临时紧急事项清单，这次是第49场双周赛。想加快一下速度，所以周赛和双周赛混着来，虚拟竞赛，不会影响排名，坐稳了。

判断国际象棋棋盘中一个格子的颜色

题目连接：判断国际象棋棋盘中一个格子的颜色

我的解法：

没必要说太多的一个简单题，先判断行，再根据列判断是否需要取反。

class Solution {
private:
    string black = "aceg";
public:
    bool squareIsWhite(string coordinates) {
        bool ret;
        if (black.find(coordinates[0]) != string::npos) {
            ret = false;
        } else {
            ret = true;
        }
        if ((coordinates[1] - '1') % 2 != 0) {
            ret = !ret;
        }
        return ret;
    }
};

别人的答案：

class Solution:
    def squareIsWhite(self, coordinates):
        stage = (ord(coordinates[0]) - ord('a')) % 2
        num = (int(coordinates[1]) - 1) % 2
        return True if stage ^ num else False

作者：qingfengpython
链接：https://leetcode-cn.com/problems/determine-color-of-a-chessboard-square/solution/5705-pan-duan-guo-ji-xiang-qi-qi-pan-zho-xuln/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

直接与a作差，减少了用一个字符串保存黑色格开头的行。可以优化点内存占用。

句子相似性 III

题目连接：句子相似性 III

思路：

  1. 按照长短交换两个字符串
  2. 循环遍历放进vector
  3. 将相同的部分出列

由于为了分析字符串遍历了好多次，解法明细不是最优的，于是没有往下写码，而是看了别人的题解。

别人的解法：

class Solution {
public:
    bool areSentencesSimilar(string sentence1, string sentence2) {
        if (sentence1.size() < sentence2.size()) swap(sentence1, sentence2);
        //first
        if (sentence2 == sentence1) return true;
        deque<string> q1, q2;
        string w;
        istringstream cinA(sentence1);
        istringstream cinB(sentence2);
        while (cinA >> w)
            q1.push_back(w);
        while (cinB >> w)
            q2.push_back(w);
        //3 possibilities:
        while (true) {
            if (!q2.empty() && q1.back() == q2.back()) {
                q1.pop_back();
                q2.pop_back();
            } else if (!q2.empty() && q1.front() == q2.front()) {
                q1.pop_front();
                q2.pop_front();
            } else break;
        }
        return q2.empty();
    }
};

秒啊，秒啊

几个很有意思的地方：

  1. 使用istringstream让字符串自动按照空格分隔成单词，避免自己写垃圾算法
  2. 使用双端队列，数据可以从两头出列，避免使用vector需要erase的场景。

统计一个数组中好对子的数目

题目链接：统计一个数组中好对子的数目

我的思路：

  1. 能够形成好对子的数，各个位的差值相同。
class Solution {
public:
    int countNicePairs(vector<int>& nums) {
        //
    }
};

该题的难点在于数据很大，数据量也很大，如果单独分拆的话，必须超时。看看有没有什么好玩的解法吧。

别人的解法：

这道题只要拿草纸画一下示例即可得到结果，我们通过计算每个数与rev该数的绝对值。
看列表中存在相同数目的数字到底有多少，然后等差的数列求和即可得到最终结果。

from collections import Counter

class Solution:
    def countNicePairs(self, nums):
        total = 0
        tmp = []
        for i in nums:
            tmp.append(abs(i) - int(str(i)[:: -1]))
        for i in Counter(tmp).values():
            i -= 1
            total += (i + 1) * i // 2
        return total % (10**9 + 7)

作者：qingfengpython
链接：https://leetcode-cn.com/problems/count-nice-pairs-in-an-array/solution/5708-tong-ji-yi-ge-shu-zu-zhong-hao-dui-ixtio/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

尾声

又是一次输的很惨的周赛，不懂输入流和双端队列，题目完成度很低。好消息是通过多次挨打，能够通过阅读题解得到提高。

Leetcode