LeetCode每日一题:Day88
统计字典序元音字符串的数目难度
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: ...
LeetCode每日一题:Day86
统计只差一个字符的子串数目难度
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)): ...
2023年第13周总结
周赛情况等这周抽空补做下……
模型测试新任务,要在 MMLU 数据集上测试 ChatGLM-6B、T5-3B、Flan-T5-3B 三个模型的效果。进展更新在仓库里。周日先初步测试了下 ChatGLM-6B,慢是真的慢……得学下怎么 finetuning。
CPP其实也忘得差不多了,忽然要教别人,也只能现学现卖了hh
2023年第12周总结
周赛情况一个小时多完成 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 ...
LeetCode每日一题:Day77
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 ...
2023年第11周总结
周赛情况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[ ...
2023年第10周总结
这篇周总结本来应该是上周日写的,但一直拖到今天。原因嘛……解锁了 VSCode 连接服务器写代码的体验之后,已经快一周没开 Mint 了……
周赛情况久违地 AK 了,虽然 WA 三发还是两发来着。离绿牌又近了一步。
想说的就这么多,别的隔一周都给忘光了,就这样吧……
2023年第9周总结
本周学习情况主要是在上课,但也保证了每日一题打卡,并额外刷了十道左右的 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 ...
LeetCode每日一题:Day54
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 ...