(:100: 代表答主提交答案时在前 100 %)
2. Add Two Numbers: Solution 💯
(这道题对 Python 有毒, 只要时间复杂度大于等于 O(n2) 绝对 TLE, 其它语言 O(n3) 也能过...)
tips: Python 用 Manacher’s Algorithm 比较稳, 其它算法基本 TLE. 本例里用将每个字符当作回文串中心对匹配方式,还是可能 TLE.
tips: 以每 (2 * numRows - 2) 个字符串为一组进行操作,最后一组不足 (2 * numRows - 2) 个字符用特殊字符补齐,最后返回前再将特殊字符去掉
tips: 用动态规划的思路可以解, 递归 Python 会 TLE. 用 re 库可以一句话解决: (return re.match(r'^{0}$'.format(p), s)) 不过不推荐.
tips: bf 做复杂度 O(n2) Python 会 TLE. 用两个游标分别从数组首位出发谁小谁移动, 纪录其中最大值, 复杂度 O(n)
12. Integer to Roman: Solution
13. Roman to Integer: Solution 💯
动态规划思路: 复杂度 O(n2), 状态是: n 个字符串 n <= len(strs) 的最长公共前缀, 转移方程: D(n) = min{D(n-1), L(j)}, 0 <= j <= min{D(n-1), len(str(n))} (大概是这样)
tips: K Sum Problem
16. 3Sum Closest: Solution
tips: 可以看作是有个固定数字的 4 Sum 问题,稍微改下 3 Sum 代码即可, 时间复杂度不增加 O(nlogn)
tips: 简单替换后直接算 kronecker 积, 复杂度 O(n)
tips: backtracking
tips1: 虽然只是让返回去除重复后的数组长度,但是oj还是会判断代码是否真的去掉的是重复的元素,否则即使你返回的长度正确oj依然会 WA
tips2: 不能用len(set(nums)) 一句完成,因为 set 申请了新的空间,而题目要求不能使用新的空间