星黎殿

统计字典序元音字符串的数目难度 Easy Medium Hard 思路三种做法，暴力、记忆化搜索、动态规划。 DP 做法中，每一步能取的字母，实际上就是小于等于自己的字母，加总即可。 代码记忆化搜索1234567891011class Solution: def countVowelStrings(self, n: int) -> int: # 记忆化搜索 @cache def dfs(cur_pos, cur_ch): nonlocal n if cur_pos == n: return 1 return sum([dfs(cur_pos + 1, i) for i in range(cur_ch, 5)]) return dfs(0, 0) 动态规划12345678910class Solution: def countVowelStrings(self, n: int) -> int: ...

统计只差一个字符的子串数目难度 Easy Medium Hard 思路首先考虑暴力法，看字符串长度为 100，简单估计了下感觉会超时。 然后考虑不同字符出现的位置，可能是开头（其后为连续相同串），中间（两侧为连续相同串），末尾（其前为连续相同串）。 然后……就没有然后了…… 打开题解，啪啪打脸。暴力是可以通过的…… 看 DP 解法，嗯，枚举不同字符，应该说想的比较接近了。 暴力法没什么说的。 DP 是说，枚举两字符串中不同的字符，用两个二维数组记录不同字符对两侧的连续相同串长度。对于一对不同字符，可以组成的符合条件的子串数量，应当为两侧连续相同串长度加一的积。 代码暴力1234567891011121314151617class Solution: def countSubstrings(self, s: str, t: str) -> int: # 暴力，枚举 ans = 0 for i in range(len(s)): for j in range(len(t)): ...

周赛情况等这周抽空补做下…… 模型测试新任务，要在 MMLU 数据集上测试 ChatGLM-6B、T5-3B、Flan-T5-3B 三个模型的效果。进展更新在仓库里。周日先初步测试了下 ChatGLM-6B，慢是真的慢……得学下怎么 finetuning。 CPP其实也忘得差不多了，忽然要教别人，也只能现学现卖了hh

周赛情况一个小时多完成 3 题。 第三题耗了一个小时，状态压缩硬是超时。再看第四题，发现这个倒是挺简单。最后排名 1600+，预期分数没变化。 要是上周不 unrate，这周再先做四再看 3，估计就上 knight 了…… 6319. 奇偶位数简单题 12345678910class Solution: def evenOddBit(self, n: int) -> List[int]: ans = [0, 0] cur = 0 while n: if (n & 1) == 1: ans[cur] += 1 n >>= 1 cur = (cur + 1) % 2 return ans 6322. 检查骑士巡视方案其实就是逐步检查移动是否合法，先遍历一遍，把每一步记录下就行。被初始位置不在 (0, 0) 的情况阴了一下。 1234567891011121314class Solution: def ...

解释模拟退火算法是启发式算法的一种。 所谓退火，指的是固体温度越高时，其内部粒子能量越大，运动无序且越快速。而当温度降低后，内部粒子趋于稳定、有序。 模拟退火算法基于这一原理，将初始解（多个）所处状态假定为高温状态。在高温状态下，针对每一个解生成邻域解，并基于一定规则更新解。一轮更新过后，降低温度，进入下一轮更新，直到温度低于指定的最低温度。然后从所有解中选一个最好的。 实例假设我们要在固定 的情况下，找到最小化 Rastrigin 函数的 值（），那么应当执行以下步骤： 初始化温度为 ，生成随机初始解（多个）。 遍历每一个当前解： 计算对应的价值（Rastrigin 函数值，）。 生成邻域解。 如果邻域解合法，计算对应价值。 如果价值小于原解的价值，更新解。 如果价值大于原解的价值，以概率 更新解。 降低温度 重复步骤 2 - 3，直到当前温度低于指定温度。 从所有解中取最好作为最优解。 代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495 ...

1616. 分割两个字符串得到回文串难度 Easy Medium Hard 思路首先想到枚举分割点直接判断，但取子串和取反的操作会导致超时。 从最长逆序长度考虑。 先将 a 和 b 分别作为 s1 s2 来考虑。 初始 break_point = -1 两指针分别从 s1 的首部，s2 的尾部出发，字符相同则更新 break_point 并前进，不同则终止。 此时 break_point 只有三种情况： 等于 -1 ，说明不行。 大于等于 s1 长度的一半，说明可以。 大于 -1 且小于 s1 长度的一半，需要进一步判断。此时已经可以确定生成的回文串的首尾，只要确定其中间部分。中间部分可以取 s1 的中间，也可以取 s2 的中间，任意一种成立均可以。两种都不成立则说明不行。 以上任意一种情况成立时返回 True 否则最终返回 False。 代码1234567891011121314151617181920212223242526272829class Solution: def checkPalindromeFormation(self, a: str, b: str ...

周赛情况34 分钟完成 3 题，0 WA 。第四题没什么思路。 6315. 统计范围内的元音字符串数简单题 123class Solution: def vowelStrings(self, words: List[str], left: int, right: int) -> int: return sum(word[0] in ['a', 'e', 'i', 'o', 'u'] and word[-1] in ['a', 'e', 'i', 'o', 'u'] for word in words[left:right+1]) 6316. 重排数组以得到最大前缀分数要前缀和中正数最多，只要按正数、0、负数的顺序排好就行，即降序排列。 123456789101112class Solution: def maxScore(self, nums: List[ ...

这篇周总结本来应该是上周日写的，但一直拖到今天。原因嘛……解锁了 VSCode 连接服务器写代码的体验之后，已经快一周没开 Mint 了…… 周赛情况久违地 AK 了，虽然 WA 三发还是两发来着。离绿牌又近了一步。 想说的就这么多，别的隔一周都给忘光了，就这样吧……

本周学习情况主要是在上课，但也保证了每日一题打卡，并额外刷了十道左右的 Medium+ 题。 下周计划刷一些洛谷的题目，其题设更接近真实工作时的环境。 课程笔记暂不更新，基本第一周的课都没有太多要记的。 周赛10 分钟做出了两题，第二题 WA 一发。 第三题直到最后一秒才做出来，可惜提交时刚好12点整，通过了但是不算分。 最后 1600 名左右，又要掉分了，离 1880 又远了一些。 P1 6369. 左右元素和的差值没啥说的 12345class Solution: def leftRigthDifference(self, nums: List[int]) -> List[int]: n = len(nums) ans = [abs(sum(nums[:idx]) - sum(nums[idx + 1:])) for idx in range(n)] return ans P2 6368. 找出字符串的可整除数组直接转换成整型或者累加数字都会溢出，要利用模运算的性质，防止溢出。 1234567891011121314clas ...

1238. 循环码排列难度 Easy Medium Hard 思路在看这题之前，先看 89. 格雷编码 。与本题的不同之处在于，No.89 要求第一位是恒定的 0 。 格雷编码的定义基本就是题干描述。而如何生成这样一个编码，大致有两种方法——归纳和公式。 归纳法的证明比较麻烦，就略过了。 使用公式生成格雷编码： $g_i = i \oplus \lfoor \frac{i}{2} \rfloor$ 下面证明其正确性。 当 $i$ 为偶数，显然 $i +1$ 是奇数，其二进制形式仅区别于最低的一位。而 $\lfoor \frac{i}{2} \rfloor$ 和 $\lfoor \frac{i +1}{2} \rfloor$ 是相等的（比如 4 和 5）。因此得出的 $g_i$ 也仅相差一位。 当 $i$ 为奇数，我们将其与 $i + 1$的二进制形式作对比，可以从高位到低位分为三个部分。第一个部分中，两者完全相同；第二个部分中， $i$ 均为 0 ， $i +1$ 均为 1 ；第三个部分中， $i$ 均为 1 ， $i + 1$ 均为0。两者右移一位，在高位补 0 ...