## 每日一题 !!! warning 菜鸟的日常做题打卡😢 ⭐: 需要再回顾 !!! ### [3403. 从盒子中找出字典序最大的字符串 I(2025-06-04)](https://leetcode.cn/problems/find-the-lexicographically-largest-string-from-the-box-i/description/?envType=daily-question&envId=2025-06-04) > (字典序越长越大，同样长就比较大小) 贪心，有长的走长的就行。 - 时间复杂度: $ O(n) $· - 空间复杂度: $ O(n) $ ```cpp class Solution { public: string answerString(string word, int numFriends) { int n = word.size(); // 特殊情况 if (numFriends == 1) return word; // 最长能走的长度 int targetLen = n - numFriends + 1; string ans; for (int i = 0; i < n; ++ i) { ans = max(ans, word.substr(i, min(targetLen, n - i))); } return ans; } }; ``` ### [1061. 按字典序排列最小的等效字符串(2025-06-05)](https://leetcode.cn/problems/lexicographically-smallest-equivalent-string/description/?envType=daily-question&envId=2025-06-04) > 并查集模板题，找每个块中权重最小的值 - 时间复杂度: $ O(n + m) $, $ n $ 为 $ s_1 $的长度, $ m $ 为 $ baseStr $ 的长度 - 空间复杂度: $ O(26) $ ```cpp class Solution { public: // 并查集 int f[26]; int find(int x) { if (f[x] != x) f[x] = find(f[x]); return f[x]; } // 合并且路径压缩 void merge(int a, int b) { int fa = find(a), fb = find(b); if (fa == fb) return; if (fa < fb) { f[fb] = fa; } else { f[fa] = fb; } } string smallestEquivalentString(string s1, string s2, string baseStr) { int n = s1.size(); for (int i = 0; i < 26; ++ i) f[i] = i; for (int i = 0; i < n; ++ i) { merge((s1[i] - 'a'), (s2[i] - 'a')); } string s = ""; for (int i = 0; i < baseStr.size(); ++ i) { s += 'a' + f[find(baseStr[i] - 'a')]; } return s; } }; ``` ### [2434. 使用机器人打印字典序最小的字符串（2025-06-06）](https://leetcode.cn/problems/using-a-robot-to-print-the-lexicographically-smallest-string/description/?envType=daily-question&envId=2025-06-06) > 题目中的 $ t $ 为先进后出，为栈模式，为了保证字典序，则控制出来的数字最小，使用单调栈来保证。当栈顶（最小）中的数比后缀最小数组中的数还小，则可以出栈（后续没有更小的数了），否则入栈。 - 时间复杂度: $ O(n) $ - 空间复杂度: $ O(n) $ ```cpp class Solution { public: string robotWithString(string s) { int n = s.size(); // 模拟栈 vector stack(n); int t = -1; // 后缀最小数 vector suf_min(n, 'z'); suf_min[n - 1] = min(suf_min[n - 1], s[n - 1]); for (int i = n - 1; i >= 1; -- i) { suf_min[i - 1] = min(suf_min[i], s[i - 1]); } string ans = ""; for (int i = 0; i < n; ++ i) { // 栈顶比后缀中最小还要小就出栈 while (t > -1 && stack[t] <= suf_min[i]) { ans += stack[t--]; } stack[++t] = s[i]; } // 清空栈 while (t > -1) { ans += stack[t--]; } return ans; } }; ``` ### [3170. 删除星号以后字典序最小的字符串（2025-06-07）](https://leetcode.cn/problems/lexicographically-minimum-string-after-removing-stars/description/?envType=daily-question&envId=2025-06-07) 贪心：删除离 `*` 最近的最小字符，就能让前面的大字符不向前移动使用栈来保持每次删除的是离当前最近的最小的 - 时间复杂度: $ O(n) $ - 空间复杂度: $ O(n) $ ```cpp class Solution { public: string clearStars(string s) { int idx = 0; int n = s.size(); vector stack[26]; for (int i = 0; i < n; ++ i) { if (s[i] != '*') { stack[s[i] - 'a'].push_back(i); continue; } for (auto& ve : stack) { if (!ve.empty()) { s[ve.back()] = '*'; ve.pop_back(); break; } } } erase(s, '*'); return s; } }; ``` ### [386. 字典序排数（2025-06-08）](https://leetcode.cn/problems/lexicographical-numbers/description/?envType=daily-question&envId=2025-06-08) 直接dfs扫一遍就行 - 时间复杂度: $ O(n) $ - 空间复杂度: $ O(1) $ ```cpp class Solution { public: vector ans; vector lexicalOrder(int n) { for (int i = 1; i <= 9; ++ i) { dfs(i, n); } return ans; } void dfs(int num, int limit) { if (num > limit) return; ans.push_back(num); for (int i = 0; i <= 9; ++ i) dfs(num * 10 + i, limit); } }; ``` ### ⭐[440. 字典序的第K小数字（2025-06-09）](https://leetcode.cn/problems/k-th-smallest-in-lexicographical-order/description/?envType=daily-question&envId=2025-06-09) 在10叉树上做二分，跳跃的是维护的子节点个数 ```txt 第一层 1 2 2 - 1 = 1 第二次 10 —— 19 20 21 ... 20 - 10 = 10 ``` - 时间复杂度: $ O(n) $ - 空间复杂度: $ O(1) $ ```cpp class Solution { public: // 计算 l 到 r 中间的数量 int dfs(long long l, long long r, int n) { if (l > n) return 0; int ans = 0; ans += min(r, n + 1LL) - l; ans += dfs(l * 10, r * 10, n); return ans; } int findKthNumber(int n, int k) { int node = 1; k--; // 二分 while (k > 0) { // 第 node 层的数量 int sum = dfs(node, node + 1, n); if (k - sum < 0) { node *= 10; k --; } else { node += 1; k -= sum; } } return node; } }; ``` ### [3442. 奇偶频次间的最大差值 I（2025-06-10）](https://leetcode.cn/problems/maximum-difference-between-even-and-odd-frequency-i/description/?envType=daily-question&envId=2025-06-10) - 时间复杂度: $ O(n) $ - 空间复杂度: $ O(n) $ ```cpp class Solution { public: int maxDifference(string s) { vector cnt(26, 0); for (char c : s) { cnt[c - 'a'] += 1; } int maxn = 0, minn = INT_MAX; for (int i : cnt) { if (i % 2 == 0 && i != 0) { minn = min(minn, i); } else { maxn = max(maxn, i); } } return maxn - minn; } }; ``` ### [3423. 循环数组中相邻元素的最大差值（2025-06-12）](https://leetcode.cn/problems/maximum-difference-between-adjacent-elements-in-a-circular-array/description/?envType=daily-question&envId=2025-06-12) - 时间复杂度: $ O(n) $ - 空间复杂度: $ O(1) $ ```cpp class Solution { public: int maxAdjacentDistance(vector& nums) { int ans = 0; nums.push_back(nums[0]); for (int i = 0; i < nums.size() - 1; ++ i) { ans = max(ans, abs(nums[i + 1] - nums[i])); } return ans; } }; ``` ### [2566. 替换一个数字后的最大差值（2025-06-14）](https://leetcode.cn/problems/maximum-difference-by-remapping-a-digit/?envType=daily-question&envId=2025-06-14) ```cpp class Solution { public: string replace(string s, char des, char target) { for (int i = 0; i < s.size(); ++ i) { if (s[i] == des) s[i] = target; } return s; } int minMaxDifference(int num) { string s = to_string(num); string a = s, b = s; int i = 0, n = s.size(); while (i < n && a[i] == '9') ++ i; a = replace(a, a[i], '9'); i = 0; while (i < n && b[i] <= '0') ++ i; b = replace(b, b[i], '0'); return stoi(a) - stoi(b); } }; ``` ### [1432. 改变一个整数能得到的最大差值（2025-06-15）](https://leetcode.cn/problems/max-difference-you-can-get-from-changing-an-integer/description/?envType=daily-question&envId=2025-06-15) - 时间复杂度: $ O(n) $ - 空间复杂度: $ O(n) $ ```cpp class Solution { public: string replace(string s, char des, char target) { for (int i = 0; i < s.size(); ++ i) { if (s[i] == des) s[i] = target; } return s; } int maxDiff(int num) { string s = to_string(num); string a = s, b = s; int i = 0, n = s.size(); while (i < n && a[i] == '9') ++ i; // 找到最前面的非 9 数字，修改成9 a = replace(a, a[i], '9'); i = 0; // 找到最前面的且不会生成前缀 0 的数字 if (b[0] != '1') { // 首字母改成最小 b = replace(b, b[0], '1'); } else { // 首字母已经最小就从第二个开始改为 0 且不会把首字母 1 修改掉 i = 1; while (i < n && b[i] <= '1') ++ i; b = replace(b, b[i], '0'); } // cout << a << " " << b << endl; return stoi(a) - stoi(b); } }; ``` ### [2016. 增量元素之间的最大差值（2025-06-16）](https://leetcode.cn/problems/maximum-difference-between-increasing-elements/description/?envType=daily-question&envId=2025-06-16) - 时间复杂度: $ O(n) $ - 空间复杂度: $ O(1) $ ```cpp class Solution { public: int maximumDifference(vector& nums) { int minn = nums[0], ans = INT_MIN; for (int i = 1; i < nums.size(); ++ i) { ans = max(ans, nums[i] - minn); minn = min(minn, nums[i]); } return ans == INT_MIN ? -1 : (ans <= 0 ? -1 : ans); } }; ``` ### [⭐3405. 统计恰好有 K 个相等相邻元素的数组数目（2025-06-17）](https://leetcode.cn/problems/count-the-number-of-arrays-with-k-matching-adjacent-elements/submissions/637759087/?envType=daily-question&envId=2025-06-17) !!! warning 除了python写的简便一些，别的都要预处理。 !!! 长度为 $ n $ 的列表中, 有 $ k $ 对相同的数对 $ <=> $ 有 $ n - k - 1 $ 对不相同的数对即找出 $ n - k - 1 $ 个子数组，每个组数组与旁边的子数组不相同就行划分边界种类: $ C_{n - 1}^{n - k - 1} = C_{n - 1}^{k} $ 颜色划分: 第一个区域 $ m $ 种，其他的区域都是 $ {(m - 1)}^{n - k - 1} $ 种一共 $ C_{n - 1}^{k} \times m \times {(m - 1)}^{n - k - 1} $ - 时间复杂度: $ O(log(n - k)) $ - 空间复杂度: $ O(1) $ ```python3 class Solution: def countGoodArrays(self, n: int, m: int, k: int) -> int: mod = int(1e9 + 7) split_no_equal = comb(n - 1, k) % mod return split_no_equal * m * pow(m - 1, n - k - 1, mod) % mod ``` ### [2966. 划分数组并满足最大差限制（2025-06-18）](https://leetcode.cn/problems/divide-array-into-arrays-with-max-difference/description/?envType=daily-question&envId=2025-06-18) - 时间复杂度: $ O(nlogn) $ - 空间复杂度: $ O(logn) $ ```cpp class Solution { public: vector> divideArray(vector& nums, int k) { sort(nums.begin(), nums.end()); vector> ans; int n = nums.size(); for (int i = 2; i < nums.size(); i += 3) { if (nums[i] - nums[i - 2] > k) { return {}; } ans.push_back({nums[i - 2], nums[i - 1], nums[i]}); } return ans; } }; ``` ### [2294. 划分数组使最大差为 K（2025-06-19）](https://leetcode.cn/problems/partition-array-such-that-maximum-difference-is-k/description/?envType=daily-question&envId=2025-06-19) 排序 + 贪心，要最后的子序列最少，那么每个子数组满足条件的长度越长越好。 - 时间复杂度: $ O(nlogn) $ - 空间复杂度: $ O(logn) $ ```cpp class Solution { public: int partitionArray(vector& nums, int k) { sort(nums.begin(), nums.end()); int n = nums.size(); int left = nums[0], ans = 0; for (int i = 1; i < n; ++ i) { if (nums[i] - left <= k) continue; left = nums[i], ans ++; } return ans + 1; } }; ``` ### [3443. K 次修改后的最大曼哈顿距离（2025-06-20）](https://leetcode.cn/problems/maximum-manhattan-distance-after-k-changes/solutions/3061765/heng-zong-zuo-biao-fen-bie-ji-suan-tan-x-lhhi/?envType=daily-question&envId=2025-06-20) - 时间复杂度: $ O(n) $ - 空间复杂度: $ O(1) $ ```cpp class Solution { public: int maxDistance(string s, int k) { int ans = 0, x = 0, y = 0; for (int i = 0; i < s.size(); ++ i) { if (s[i] == 'N') ++ y; else if (s[i] == 'S') -- y; else if (s[i] == 'E') ++ x; else -- x; ans = max(ans, min(abs(x) + abs(y) + k * 2, i + 1)); } return ans; } }; ``` ### [3085. 成为 K 特殊字符串需要删除的最少字符数（2025-06-21）](https://leetcode.cn/problems/minimum-deletions-to-make-string-k-special/description/?envType=daily-question&envId=2025-06-21) #### 暴力法 - 时间复杂度: $ O(n + 26^2) $, $ n $ 为 $ word $ 的长度 - 空间复杂度: $ O(26) $ ```cpp class Solution { public: int minimumDeletions(string word, int k) { vector cnt(26, 0); for (char c : word) cnt[c - 'a'] ++; sort(cnt.begin(), cnt.end()); int sum_save = 0; // 转换成最多能保留的数量 for (int i = 0; i < 26; ++ i) { while (i < 26 && cnt[i] == 0) ++ i; int sum = 0; for (int j = i; j < 26; ++ j) { sum += min(cnt[j], cnt[i] + k); } sum_save = max(sum_save, sum); } // 最少的删除字符 = n - 最多保留的字符 return word.size() - sum_save; } }; ``` #### 排序 + 滑动窗口 - 时间复杂度: $ O(n + 26^log26) $, $ n $ 为 $ word $ 的长度 - 空间复杂度: $ O(26) $ ```cpp class Solution { public: int minimumDeletions(string word, int k) { vector cnt(26, 0); for (char c : word) cnt[c - 'a'] ++; sort(cnt.begin(), cnt.end()); int sum_save = 0, sum_win = 0; for (int i = 0, j = 0; i < 26; ++ i) { // 减少次数浪费 while (i < 26 && cnt[i] == 0) ++ i; // 滑动窗口 while (j < 26 && cnt[j] <= cnt[i] + k) { sum_win += cnt[j]; ++ j; } sum_save = max(sum_save, sum_win + (26 - j) * (cnt[i] + k)); sum_win -= cnt[i]; } return word.size() - sum_save; } }; ``` ### [2138. 将字符串拆分为若干长度为 k 的组（2025-06-22）](https://leetcode.cn/problems/divide-a-string-into-groups-of-size-k/submissions/638841464/?envType=daily-question&envId=2025-06-22) - 时间复杂度: $ O(n / k) $, $ n $ 为 $ s $ 的长度 - 空间复杂度: $ O(1) $ ```cpp class Solution { public: vector divideString(string s, int k, char fill) { int diff = s.size() % k; if (diff != 0) diff = k - diff; s += string(diff, fill); vector ans; for (int i = 0; i < s.size(); i += k) { ans.push_back(s.substr(i, k)); } return ans; } }; ``` ### [2200. 找出数组中的所有 K 近邻下标（2025-06-24）](https://leetcode.cn/problems/find-all-k-distant-indices-in-an-array/description/?envType=daily-question&envId=2025-06-24) - 时间复杂度: $ O(n) $, $ n $ 为 $ nums $ 的长度 - 空间复杂度: $ O(1) $ ```cpp class Solution { public: vector findKDistantIndices(vector& nums, int key, int k) { int n = nums.size(); vector ans; int cnt = 0; for (int i = 0; i < n; ++ i) { if (nums[i] == key) nums[cnt ++] = i; // 防止覆盖 if (cnt < i) nums[i] = -1; } for (int i = 0, j = 0; i < n && j < cnt; ++ i) { while (i < n && i + k >= nums[j] && i - k <= nums[j]) { ans.push_back(i++); } if (i - k > nums[j]) ++ j, --i; } return ans; } }; ```

leetcode每日一题