题目分享

题目描述 给你一个下标从 1 开始、长度为 n 的整数数组 nums。 对于 nums[i]，如果 n 能够被 i 整除，也就是 n % i == 0，那么称它为一个特殊元素。 请返回所有特殊元素的平方和。（力扣 2778） 这是一道非常简单的题：枚举下标，判断是否为 n 的因子，是的话就把平方加到答案里。 class Solution { public: int sumOfSquares(vector<int>& nums) { int n = nums.size(); int ans = 0; for (int i = 1; i <= n; ++i) { if (n % i == 0) { ans += nums[i - 1] * nums[i - 1]; } } return ans; } }; 这里最容易出错的地方只有一个：题目下标从 1 开始，而 C++ 数组下标从 0 开始。因此判断用 i，取值用 nums[i - 1]。 这道题其实就三件事 说白了，就是下面三件事： 哪些位置要算？ 这些位置怎么算？ 数组变不变，要查几次？ 原题的答案也很简单： 要算的位置：i 是 n 的因子； 算法：把 nums[i - 1] 的平方加起来； 查询：数组不变，只查一次。 后面说的“扩展”，就是把这三件事分别换一下，看看原来的代码还能不能用。 一、换个条件：不一定只看因子 1. 从“因子”改成“质因子” 比如题目改成：只有当 i 是 n 的质因子时，才把它加进答案。那怎么办？很简单，平方和不用改，只改前面的判断： ...

题目 给你一个只包含小写字母的字符串 s，你需要找到 s 中最多数目的非空子字符串，满足如下条件： 这些字符串之间互不重叠。也就是说对于任意两个子字符串 s[i..j] 和 s[x..y]，要么 j < x，要么 i > y。 如果一个子字符串包含字符 char，那么 s 中所有 char 字符都应该在这个子字符串中。 请你找到满足上述条件的最多子字符串数目。如果有多个解法有相同的子字符串数目，请返回这些子字符串总长度最小的一个解。可以证明最小总长度解是唯一的。 请注意，你可以以任意顺序返回最优解的子字符串。 题目分析 先把两个条件翻译成人话 条件 2 是最关键、也最容易被忽略的一句。 它说的是：你不能"只要一部分"。比如 s 里有三个 a，那么任何一个包含 a 的子串，必须把这三个 a 全部包进去。 这句话有一个很强的推论： 每个字符一旦被占用，它绑定的区间就被钉死了，只能往外扩，不能往里缩。 也就是说，“能选的区间"不是随便取的，而是由字符串本身唯一决定的。我们真正的自由度只剩一条：在这些固定区间里挑几个互不重叠的。 第一步：先看每个字符的"势力范围” 拿题目的例子说： s = "adefaddaccc" 下标 0 1 2 3 4 5 6 7 8 9 10 字符 a d e f a d d a c c c 先不管条件 2，只看"第一次出现"和"最后一次出现"，得到每个字符的原始区间： ...

题目描述 给你一个下标从 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; } };

题目描述 这是上一篇《最小回文排列 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. 排列数怎么算？（新知识，重点！） 现在要算：用这些字母（可能有重复）能排成多少种不同的串？ ...