抽奖名单 | LeetCode周赛313，赞助商是不错的外企，值得加入

关注、星标下方公众号，和你一起成长

作者 | 梁唐

出品 | 公众号： Coder梁 （ID： Coder_LT ）

大家好，我是梁唐。

今天是国庆假期的第三天，也是周一，所以即使过节LeetCode周赛系列也依然更新。

昨天的周赛是LeetCode周赛第313场，由airwallex赞助。之前老梁和这家公司打过交道，他们很喜欢代码能力强的同学。是一家总部位于澳洲的外企，感兴趣的同学可以投递一下相关岗位。

对于这一场比赛大家的反应都是第四题比较难，并且在比赛的时候通过的人数还非常多。还有同学扒出了最后一题的极端case只有一个，加上特判就能通过。

我想了一下，似乎这题想要卡时间就只有这一种极端的case，毕竟题目给的字符串长度有限。如果真是这样，那这题是属于有点为了难而难了。

公因子的数目

给你两个正整数 a 和 b ，返回 a 和 b 的 公 因子的数目。

如果 x 可以同时整除 a 和 b ，则认为 x 是 a 和 b 的一个 公因子

题解

求两个数公因子的数量，其实就是求两个数最大公约数的因子的数量。

我们可以使用 gcd 函数直接求出两个数的最大公约数，接着枚举一下它的因子数量即可。注意完全平方根只能算一个因子，比如 6 和 36/6 是同一个因子，不要计算两次。

class Solution {public:    int commonFactors(int a, int b) {        int c = gcd(a, b);        int ret = 0;        for (int i = 1; i * i <= c; i++) {            if (c % i == 0) {                ret += i == c / i ? 1 : 2;            }        }        return ret;    }};

沙漏的最大总和

给你一个大小为 m x n 的整数矩阵 grid 。

按以下形式将矩阵的一部分定义为一个 沙漏 ：

返回沙漏中元素的 最大 总和。

注意： 沙漏无法旋转且必须整个包含在矩阵中。

题解

数据范围不大，枚举送分题。

class Solution {public:    int maxSum(vector<vector>& grid) {        int n = grid.size();        int m = grid[0].size();                auto get_sum = [&](int x, int y) -> int {            int s = 0;            for (int i = x-2; i <= x; i++) {                for (int j = y-2; j <= y; j++) {                    s += grid[i][j];                }            }            s -= (grid[x-1][y-2] + grid[x-1][y]);            return s;        };                int ret = 0;                for (int i = 2; i < n; i++) {            for (int j = 2; j < m; j++) {                ret = max(ret, get_sum(i, j));            }        }        return ret;    }};

最小 XOR

给你两个正整数 num1 和 num2 ，找出满足下述条件的整数 x ：

x 的置位数和 num2 相同，且

x XOR num1 的值 最小

注意 XOR 是按位异或运算。

返回整数 x 。题目保证，对于生成的测试用例， x 是 唯一确定 的。

整数的 置位数 是其二进制表示中 1 的数目。

题解

比较容易想到我们可以算出 num2 的置位数，然后枚举所有可能组成的整数，再找到和 num1 异或之后最小的一个，但很遗憾，这样做会超时。极端情况：一共有32个二进制位，如果 num2 的置位数是16，那么情况总数是  ，会超时。

所以我们不能枚举，需要结合异或操作的特性来构造。异或操作的原理为当两个二进制相同时结果为0，不同时结果为1。我们要使异或之后的值尽可能小，就需要让尽可能多的二进制置为0。

如果 num2 的置位数小于 num1 ，那么我们不能覆盖所有 num1 等于1的二进制位。我们可以贪心，尽可能覆盖值比较大的二进制位。如果 num2 的置位数大于 num1 ，我们可以将所有 num1 的二进制位都置为0，但1的个数还有剩余，我们一样使用贪心的思路，尽可能放在低位。

class Solution {public:    int minimizeXor(int num1, int num2) {       // num2的置位数        int n2 = 0;        for (int i = 0; i < 31; i++) {            if ((1 << i) & num2) n2++;        }               // 记录num1哪些位置为1        vector bits(32, 0);       // num1的置位数        int n1 = 0;        for (int i = 0; i < 31; i++) {            if ((1 << i) & num1) {                bits[i] = 1;                n1++;            }        }                int ret = num1;                if (n2 > n1) {           // 能将n1全部置为0，多余的摆放在低位            n2 -= n1;            for (int i = 0; i < 31; i++) {                if (n2 == 0) break;                if (bits[i] == 0) {                    ret += (1 << i);                    n2--;                }            }        }else {           // 不能将n1全部置为0，尽可能空出低位            n1 -= n2;            for (int i = 0; i < 31; i++) {                if (n1 == 0) break;                if (bits[i] > 0) {                    ret -= (1 << i);                    n1--;                }            }        }                return ret;    }};

对字母串可执行的最大删除数

给你一个仅由小写英文字母组成的字符串 s 。在一步操作中，你可以：

删除 整个字符串 s ，或者

对于满足 1 <= i <= s.length / 2 的任意 i ，如果 s 中的 前 i 个字母和接下来的 i 个字母 相等 ，删除 前 i 个字母。

例如，如果 s = "ababc" ，那么在一步操作中，你可以删除 s 的前两个字母得到 "abc" ，因为 s 的前两个字母和接下来的两个字母都等于 "ab" 。

返回删除 s 所需的最大操作数。

题解

直接枚举会超时，因为字符串比较是否相等是一个  的操作。在极端情况下（所有字符均相等时）我们会进行  次比较，显然会超时。

我的想法是尽可能减少比较字符串的次数，由于我打算采用搜索的算法来解，那么也就是尽可能减少搜索的次数。由于我们删除字符串是从头部开始的，所以采用距离末尾的长度来表示中间的子状态。 dp[i] 表示的是最后长度为 i 的子串最多删除的次数。

如果找不到可以删除的字母，那么 dp[i]=1 ，否则 dp[i] = max(dp[j]) + 1 。这里的 j 是指删除若干字母之后剩余的长度。整个过程都是通过递归实现的，显然在递归时某些状态会重复出现，所以我们可以使用记忆化搜索的方法，将这些重复出现的状态缓存起来。

class Solution:    def deleteString(self, s: str) -> int:       # 记忆化搜索        dt = {}        dt[0] = 0                def dfs(s):            l = len(s)            if l in dt:                return dt[l]                        ret = 0            flag = False            # 枚举所有可以删除的可能            for i in range(1, l // 2 + 1):                if s[:i] == s[i: 2*i]:                   # 递归                    ret = max(ret, dfs(s[i:]))                    flag = True                        r = ret + 1 if flag else 1            # 更新缓存            dt[l] = r            return r                return dfs(s)

赛后看了一下大佬的题解，发现除了记忆化搜索之外，还可以通过对字符串求hash的方法来加速字符串比较的速度。对字符串hash之后，只需要判断某一段字符对应的hash值是否相等就能等价判断字符串是否相等，这样就把  的字符串比较降低到了  。

因为我hash算法用得很少，不是非常熟，所以搬运一下TsReaper大佬的代码仅供参考。

class Solution {    const int MOD = 998244353;    const int BASE = 131;public:    int deleteString(string s) {        // 计算前缀哈希值        int n = s.size();        vector P(n + 1);        P[0] = 1;        for (int i = 1; i <= n; i++) P[i] = P[i - 1] * BASE % MOD;        vector H(n + 1);        for (int i = 1; i <= n; i++) H[i] = (H[i - 1] * BASE + s[i - 1]) % MOD;        int ans = 1;        vector f(n + 1, (int) -1e9);        f[0] = 0;        for (int i = 1; i <= n; i++) for (int j = 0; j < i; j++) {            int len = i - j;            if (i + len > n) continue;            // 计算两个子串的哈希值            long long h1 = (H[i] - H[i - len] * P[len] % MOD + MOD) % MOD;            long long h2 = (H[i + len] - H[i] * P[len] % MOD + MOD) % MOD;            if (h1 == h2) f[i] = max(f[i], f[j] + 1);            ans = max(ans, f[i] + (i == n ? 0 : 1));        }        return ans;    }};

中奖名单

最后公布一下前两天送书活动的中奖名单：

恭喜这三位小伙伴中奖，请后台回复“微信”添加老梁微信领取。

感谢大家的阅读~

喜欢本文的话不要忘记三连~