题目分享

大于等于序列前缀和的最小缺失整数 题目描述 给你一个下标从 0 开始的整数数组 nums。 如果一个前缀 nums[0..i] 满足：对于 1 <= j <= i 的所有元素都有 nums[j] = nums[j - 1] + 1，那么我们称这个前缀是一个 顺序前缀。特殊情况是，只包含 nums[0] 的前缀（也就是 nums[0..0]）也是一个 顺序前缀。 请你返回 nums 中没有出现过的 最小 整数 x，满足 x 大于等于 最长 顺序前缀的 和。（力扣 2996） 先别急着写代码，把题目看懂 这题考察的其实不是算法有多难，而是你读题读得够不够细。很多同学一上来就懵，觉得这不就是个"找缺失整数"吗？其实坑藏在"前缀"和"最长"这两个词里。 坑一：什么是"顺序前缀"？——必须从下标 0 开始 先看一个具体例子，比如输入： ums = [3, 4, 5, 1, 12, 14, 13] 很多人第一反应是：哎，12, 13, 14 不也是连续的（每个都比前一个大 1）吗？怎么最长顺序前缀不是它们？ 这里就是最容易踩的坑！ “前缀”（prefix）的定义，是从 nums[0] 开始、连续的一段。 前缀永远要从数组的第一个元素 nums[0] 出发： nums[0..0] = [3] nums[0..1] = [3, 4] nums[0..2] = [3, 4, 5] nums[0..3] = [3, 4, 5, 1] 而 12, 13, 14 虽然在数组里彼此连续，但它们不是从 nums[0] 开始的，所以它们根本不叫"前缀"，直接被排除掉。 ...

最小回文排列的解法 题目描述 给你一个回文字符串 s，返回它的按字典序最小的回文排列。 回文：从前往后和从后往前读都一样。 排列：字符串中所有字符的重排。 字典序：从第一个字符开始比，谁先小谁就小；前面对完都一样，短的更小。（力扣 3517） 解决方法 1. 常见的想法 把所有回文排列都列出来，排个序，取第一个？No，能解决，但是—— 给你二十个字符串让你全排列，你不崩溃，计算机也要崩溃了。暴力当然可解，前提是数据量够小。 2. 换个思路：只看一半 既然是回文，左右两半肯定一样，我们只关心一半就行。 那先统计每个字母出现了几次，一个循环搞定。 int cnt[26] = {0}; for (char c : s) cnt[c - 'a']++; // 遍历 s，把每个字符转成 0~25 的索引，计数 每个字符都至少出现两次？No——出现奇数次的字符只能有一个（它正好放正中间）。比如 ababa：a 出现 3 次，b 出现 2 次，拿一个 a 当中间，剩下两个 a 两个 b。 3. 拼出左半部分 把每个字符频次的一半按字母序拼起来，得到左半部分 half，顺便记下中间那个奇数字符。 string half; char mid = 0; for (int i = 0; i < 26; ++i) { half.append(cnt[i] / 2, 'a' + i); // 频次一半个 'a'+i 拼进 half if (cnt[i] % 2 == 1) mid = 'a' + i; // 奇数次的那个字符当中间 } 这样 half 天然就是字典序最小的左半部分。 4. 生成右半部分 把 half 反转就是右半部分，回文就拼成了。 string right = half; reverse(right.begin(), right.end()); if (mid) return half + mid + right; // 有中间字符 return half + right; // 没有中间字符 完整代码如下 #include <string> #include <algorithm> using namespace std; class Solution { public: string smallestPalindrome(string s) { int cnt[26] = {0}; for (char c : s) cnt[c - 'a']++; string half; char mid = 0; for (int i = 0; i < 26; ++i) { half.append(cnt[i] / 2, 'a' + i); if (cnt[i] % 2 == 1) mid = 'a' + i; } string right = half; reverse(right.begin(), right.end()); if (mid) return half + mid + right; return half + right; } };

第 K 小的最小回文排列（进阶版） 题目描述 这是上一篇《最小回文排列 I》的进阶版。上一篇只要最小的那个回文排列，这一篇要第 k 小的那个。 给你一个回文字符串 s 和一个整数 k，返回 s 的所有回文排列中按字典序第 k 小的那个；如果不存在第 k 个，返回空字符串 ""。 回文、排列、字典序这些概念上一篇讲过，不懂先去看上一篇，这里不重复了。（力扣 3518） 解决方法 1. 还是老套路：只看一半 上一篇说过，回文左右两半一样，所以问题就变成了——求半边串的第 k 个排列。这一步完全一样，不重复讲了。 但是！！上一篇只取最小那个，直接从小到大拼 half 就行。这一篇要第 k 个，那排序不能偷懒了，得自己动手算排列数。 所以核心难点就一个：怎么在不去重、不暴力全排列的情况下，算出"以某个字符开头一共有多少种排列"。 下面重点讲这个。 2. 统计频次 + 检查可行性（跟上一篇一样） 老规矩，先数每个字母出现几次，检查能不能构成回文（奇数次字符最多一个）。 vector<int> cnt(26, 0); for (char c : s) cnt[c - 'a']++; // 统计每个字符出现的次数 // 检查可行性：最多只能有一个字符出现奇数次 int oddCount = 0; char midChar = 0; for (int i = 0; i < 26; i++) { if (cnt[i] % 2 == 1) { oddCount++; midChar = 'a' + i; // 记录中间字符 } } if (oddCount > 1) return ""; // 超过一个奇数次，无法构成回文 3. 构建半边串的频次（跟上一篇一样） 回文 = 左半边 + （中间字符） + 左半边反转，所以只需要排列左半边。 vector<int> halfCnt(26, 0); // 半边串里每个字符出现的次数 int total = 0; for (int i = 0; i < 26; i++) { halfCnt[i] = cnt[i] / 2; // 每个字符取一半 total += halfCnt[i]; // 半边串的总长度 } 4. 排列数怎么算？（新知识，重点！） 现在要算：用这些字母（可能有重复）能排成多少种不同的串？ ...