leetcode 第 337 场算法比赛

零、背景

这个周末本来提前回来给娃过生日的。
结果娃发高烧，最终住院好久，现在周三了，还在医院住院。
期间医院没网，所以没参加比赛。

PS：我每天会发表一篇 chatGPT 问答的记录，如果你有需要问的问题，可以留言，我问之后，回复给你。

一、奇偶位数

题意：给一个数字，问二进制中奇偶位置分别有多少个 1。

思路：不断模 2 除 2，依次得到奇偶性位置的值，按奇偶性求和即可。

二、检查骑士巡视方案

题意：给一个 n*n 的矩阵，数字值分别是 [0, n * n - 1]。
数字值的含义代表骑士的移动步骤，问步骤移动是否合法。

思路：按照题意依次判断是否可以到达下一步即可。

三、美丽子集的数目

题意：给一个数组和整数 k，问数组中存在多少非空子序列，使得子序列内不存在两个数字的差值等于 k。

方法1：枚举子集。

数组大小为 20，时间复杂度 O(2^20)。
通过递归的方法来枚举子序列，边枚举边判断是否满足要求即可。

小技巧：通过固定数组来代替集合或者hash，从而做到O(1)常数时间复杂度判断出结果。

方法2：动态规划。

分析差值 k 的性质，可以发现差值为 k 的数字取模 k 后值相等。
所以可以根据取模 k 的结果对数组进行分组。

不同分组的数字，永远不可能差值为 k。
故可以单独计算每个分组的答案，由于互相独立，答案需要相乘。

相同分组的数字，排序去重后，只有相邻的数字可能差值为 k。
此时可以动态规划计算出答案。

状态：
f(n)前 n 个数字，不选择最后一个数字的答案数。
F(n)前 n 个数字，选择最后一个数字至少一次的答案数。
V[n]代表第n个数字的个数。

状态转移方程分情况讨论。

不选择：f(n) = F(n-1) + f(n-1)

选择时需要看和前一个数字是否相差 K。
相差 K 时：F(n) = 2^V[n] * f(n-1)
不相差 K 时：F(n) = 2^V[n] * f(n)

状态转移复杂度：O(n)
排序复杂度：O(n log(n))

四、 执行操作后的最大 MEX

题意：给一个数组和整数 k，每次可以从数组中选择一个数字加或减 k ，求任意次操作之后，数组的 MEX 最大是多少。

思路：与上一题类似，加减 k 不会改变模 k 后的余数。
所以可以先对所有数组模 k，并统计每个余数的个数。

方法一：模拟

循环判断每个数字对应的余数个数是否大于 0，大于 0 了代表当前数字可以得到，余数个数减一。
当遇到余数个数为 0 的数字时，就是答案 MEX。

方法二：数学计算。

找到个数最少的余数，如果存在多个，去最小的那个。
假设第一个余数最少的余数是 a，个数是 b，则答案是 k * b + a。

五、最后

这次比赛最后两道题很类似，第三题是动态规划很巧妙，第四题数学计算也很有意思。

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号ID：tiankonguse-code