学习数据结构与算法的关键在于掌握问题背后的算法思维框架,你的思考越抽象,它能覆盖的问题域就越广,理解难度也更复杂。在这个专栏里,小彭与你分享每场 LeetCode 周赛的解题报告,一起体会上分之旅。
本文是 LeetCode 上分之旅系列的第 36 篇文章,往期回顾请移步到文章末尾~
T1. 满足目标工作时长的员工数目
T2. 统计完全子数组的数目
T3. 包含三个字符串的最短字符串
T4. 统计范围内的步进数字数
https://leetcode.cn/problems/number-of-employees-who-met-the-target/
简单模拟题。
class Solution { public: int numberOfEmployeesWhoMetTarget(vector<int>& hours, int target) { int ret = 0; for (int i = 0; i < hours.size(); i++) { if (hours[i] >= target) ret++; } return ret; } };
class Solution: def numberOfEmployeesWhoMetTarget(self, hours: List[int], target: int) -> int: return sum(e >= target for e in hours)
复杂度分析:
https://leetcode.cn/problems/count-complete-subarrays-in-an-array/
枚举子数组,求满足条件的子数组数
class Solution { public: int countCompleteSubarrays(vector<int>& nums) { int n = nums.size(); int ret = 0; // 目标元素个数 int target = unordered_set<int>(nums.begin(), nums.end()).size(); // 枚举子数组 for (int i = 0; i < nums.size(); i++) { unordered_set<int> curSet; for (int j = i; j < nums.size(); j++) { curSet.insert(nums[j]); if (curSet.size() == target) { ret += n - j; break; } } } return ret; } };
复杂度分析:
在题解一中,当子数组的满足条件时,我们不再需要扩展右指针 j,其实左指针 i 也类似。当存在子数组 [i, j] 满足条件时,我们可以收缩左指针到 [i+1, j],如果子数组依然满足条件,则可以继续记录子数组个数 n - j 个。
class Solution { public: int countCompleteSubarrays(vector<int>& nums) { int n = nums.size(); int ret = 0; // 目标元素个数 int target = unordered_set<int>(nums.begin(), nums.end()).size(); // 滑动窗口 unordered_map<int, int> cnts; int i = 0; for (int j = 0; j < nums.size(); j++) { cnts[nums[j]]++; while (cnts.size() == target) { ret += n - j; if (--cnts[nums[i]] == 0) cnts.erase(nums[i]); i++; } } return ret; } };
复杂度分析:
相似题目:
https://leetcode.cn/problems/shortest-string-that-contains-three-strings/
首先,合并字符串 a 和字符串 b 可以用前后缀分解来模拟:a 的最长后缀与 b 的最长前缀匹配,得到的合并字符串是最短的。而对于目标答案的合并方案来说,必然是 [a, b, c] 的全排列中的一种:
虽然,严谨来说局部贪心是错误的(即先将 a 和 b 合并得到最短字符串 ab,再将 ab 与 c 合并)。例如以下测试用例,这说明在第一次合并中选择最短的字符串,不一定是全局最短的字符串。但是,最优解必然可以通过全排列中的其他方案获得。因此,直接使用 “局部贪心” 即可。
a = "cdaa" b = "aaef" c = "daaae" # a + b + c 其中 a + b = "cdaaef",无法与 c 合并得到最优解 “cdaaaef” # a + c + b 可以得到最优解 “cdaaaef”
class Solution: def minimumString(self, a: str, b: str, c: str) -> str: def merge(a: str, b: str) -> str: if b in a: return a for i in range(min(len(a), len(b)), 0, -1): # 前后缀对比 if a[-i:] == b[:i]: return a + b[i:] return a + b ret = "" for a, b, c in permutations((a, b, c)): temp = merge(merge(a,b), c) # 优先最短字符串,再考虑字典序最小 if (ret == "" or len(temp) < len(ret) or (len(temp) == len(ret) and temp < ret)): ret = temp return ret
复杂度分析:
题解一时间复杂度的瓶颈在 merge 函数,对于两个字符串的最长的前后缀匹配长度,这正好就是 KMP 算法中求解 next 数组的步骤,而 KMP 算法的时间复杂度是 O(n),存在优化空间。
另外还有一个细节,在合并 a 和 b 时我们在中间插入分隔符 “#”,这是为了避免匹配长度大于 a 或 b的长度。例如:
a = "cac" b = "aca" # 那么 a + b = "cacaca" 会出现匹配长度大于 a 或 b的长度
class Solution: def minimumString(self, a: str, b: str, c: str) -> str: def merge(a: str, b: str) -> str: if b in a: return a # 拼接字符串,以计算 b 的后缀与 a 的前缀的匹配长度 s = a + "#" + b # KMP 求 next 数组 j, next = 0, [0] * len(s) for i in range(1, len(s)): while j > 0 and s[i] != s[j]: j = next[j - 1] if s[i] == s[j]: j += 1 next[i] = j # next[-1]: s[-1] 的最长匹配前缀 return b + a[next[-1]:] ret = "" for a, b, c in permutations((a, b, c)): temp = merge(merge(a,b), c) # 优先最短字符串,再考虑字典序最小 if (ret == "" or len(temp) < len(ret) or (len(temp) == len(ret) and temp < ret)): ret = temp return ret
复杂度分析:
https://leetcode.cn/problems/count-stepping-numbers-in-range/
相对标准的数位 DP 模板题。
class Solution { val MOD = 1000000007 fun countSteppingNumbers(low: String, high: String): Int { // 数位 DP return ((f(high) - f(low) + if (check(low)) 1 else 0) + MOD) % MOD } private fun f(num: String): Int { val memo = Array(num.length) { Array(10) { IntArray(2) { -1 } } } return dp(memo, 0, num, '0', false, true) } private fun check(num: String) : Boolean { for (i in 1 until num.length) { if (Math.abs(num[i] - num[i - 1]) != 1) return false } return true } // dp[i, pre, isNumber] private fun dp(memo: Array<Array<IntArray>>, i: Int, high: String, pre: Char, isNumber: Boolean, isLimit: Boolean): Int { // 终止条件 if (i == high.length) { return if (isNumber) 1 else 0 } // 读备忘录 if (!isLimit && -1 != memo[i][pre - '0'][if (isNumber) 1 else 0]) { return memo[i][pre - '0'][if(isNumber) 1 else 0] } var ret = 0 val lower = '0' val upper = if (isLimit) high[i] else '9' for (choice in lower .. upper) { if (!isNumber || Math.abs(choice - pre) == 1) { ret = (ret + dp(memo, i + 1, high, choice, isNumber || choice != '0', isLimit && choice == upper)) % MOD } } if (!isLimit) memo[i][pre - '0'][if (isNumber) 1 else 0] = ret return ret } }
复杂度分析: