给出整数数组 A，将该数组分隔为长度最多为 K 的几个（连续）子数组。分隔完成后，每个子数组的中的值都会变为该子数组中的最大值。
返回给定数组完成分隔后的最大和。
示例：
输入：A = [1,15,7,9,2,5,10], K = 3 输出：84 解释：A 变为 [15,15,15,9,10,10,10]
提示：
1 <= K <= A.length <= 500 0 <= A[i] <= 10^6
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/partition-array-for-maximum-sum 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
看到这道题目一开始是在群里，发了英文版的这道题目，大概看了一下，以为是分割成最多 K 个子数组，然后写了一下，最后提交当然是答案错误，反推错误的样例，发现没错啊，然后再看中文题意，发现理解错了。本意是每个子数组长度最多是 K ，然后就没啥思路了。猜想是 DP，可是也没有构造出状态，最后没有做出来。群里人说确实是 DP，然后我瞄了一眼题解，确实很多都是 DP 来做的，自己又朝着 DP 的方向思考，还是没有想出来。今天上午又开始想这道题目：既然是 DP，并且看题解也不是一道复杂的 DP，那么状态应该很简单，只需要构造出一个状态，满足：最优子结构、无后效性即可。然后就开始假设状态，思考决策的过程应该检查哪些状态，有哪些条件，哪些条件是必须的，哪些条件是不需要保存的，对于下一个状态，是不是只和上一个（或者多个）状态的结果有关。最后想到可以用 dp[i] 来表示前 i 个数字的最优解，开始以为也需要保存以第 i 个数字结尾的子数组的长度，后来发现下一个状态并不需要这个东西，因为下一个数字加入进来的时候，并不需要延展以第 i 个数字结尾的子数组，它只需要作为一个以第 i+1 个数字的新数组向左延展就好了，最多延展的长度是 K ，这样可以保证遍历到所有的上一个状态。这样就可以得到最优解即 dp[n] 。
#include <iostream>#include <vector>#include <queue>#include <functional>#include <algorithm> using namespace std; using VI = vector<int>; using PII = pair<int, int>; class Solution { public: int maxSumAfterPartitioning(vector<int>& A, int K) { int len = int(A.
有 n 位用户参加活动，他们的 ID 从 0 到 n - 1，每位用户都 恰好 属于某一用户组。给你一个长度为 n 的数组 groupSizes，其中包含每位用户所处的用户组的大小，请你返回用户分组情况（存在的用户组以及每个组中用户的 ID）。
你可以任何顺序返回解决方案，ID 的顺序也不受限制。此外，题目给出的数据保证至少存在一种解决方案。
示例 1：
输入：groupSizes = [3,3,3,3,3,1,3] 输出：[[5],[0,1,2],[3,4,6]] 解释：其他可能的解决方案有 [[2,1,6],[5],[0,4,3]] 和 [[5],[0,6,2],[4,3,1]]。
示例 2：
输入：groupSizes = [2,1,3,3,3,2] 输出：[[1],[0,5],[2,3,4]]
提示：
groupSizes.length = n 1 < n <= 500 1 <= groupSizes[i] <= n
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/group-the-people-given-the-group-size-they-belong-to 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
这道题目可以说没有任何难度，把组人数相同的人放在一起然后分组即可。
#include <iostream>#include <vector>#include <algorithm>#include <unordered_map>using namespace std; using VI = vector<int>; class Solution { public: vector<vector<int>> groupThePeople(vector<int>& groupSizes) { unordered_map<int, VI> people; for (size_t i = 0; i < groupSizes.
1283. 使结果不超过阈值的最小除数
给你一个整数数组 nums 和一个正整数 threshold ，你需要选择一个正整数作为除数，然后将数组里每个数都除以它，并对除法结果求和。
请你找出能够使上述结果小于等于阈值 threshold 的除数中 最小 的那个。
每个数除以除数后都向上取整，比方说 7/3 = 3 ， 10/2 = 5 。
题目保证一定有解。
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/find-the-smallest-divisor-given-a-threshold 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
这题开始我也没有思路，然后瞄了一眼题解，说是二分。然后自己朝着二分的思路想，发现确实可以二分来做。首先我们知道，当 x 比较大的时候，肯定是一个解，当 x 越大，整个数列的和越小，也就是 F(x) 是递减的，我们需要找到最小的 x 使得 F(x) <= threshold 。由于这个函数单调递减，我们可以考虑二分的思路：首先确定 x 的范围，然后在这个范围中二分；首先，考虑 x 的最大值，原来数组中的最大值一定是解，所以可以把它当作最大值；再考虑 x 的最小值，把原来的数组排序，假设前 n-1 项除以 x 的值都是 1，那么此时第 n 项的值最大，此时对应的 x 值最小，此时 x 为 a[n - 1] / (threshold - (n - 1)) 。剩下的就是写出正确的二分了，注意考虑边界条件，不要死循环。
using VI = vector<int>; class Solution { public: int smallestDivisor(vector<int>& nums, int threshold) { sort(nums.
LeetCode 1268. 搜索推荐系统
输入一个词典，然后输入一个单词，对于单词的每一个前缀，输出字典中以这个前缀开始的单词的字典序最小的 3 个单词。词典长度 1000，词典中每个单词的长度 20000，目标单词长度 1000.
这道题目开始的想法是字典树。可是数据集的范围太大，字典树占用空间太大。然而也没有想到什么好的方法，最后还是用常规的字典树写了一下，竟然过了。
#include <iostream>#include <vector>#include <string>#include <stack> using namespace std; using VS = vector<string>; struct TrieTree { char value; bool is_end; TrieTree *children[26]; TrieTree() { for (int i = 0; i < 26; i++) children[i] = nullptr; is_end = false; } }; void insert_word(TrieTree *root, string s) { for (auto x: s) { int pos = x - 'a'; if (nullptr != root->children[pos]) { root = root->children[pos]; } else { TrieTree *tmp = new TrieTree(); tmp->value = x; root->children[pos] = tmp; root = tmp; } } root->is_end = true; } void print_tree(TrieTree *root, string s, vector<string> &words) { for (int i = 0; i < 26; i++) { TrieTree *child = root->children[i]; if (nullptr !
LeetCode LCP 3. 机器人大冒险
这道题目考察对循环节的理解。开始想得有点儿复杂，分析之后可以发现，关键是如何判断某个点是否在路径上。由于坐标范围过大，显然不能把整条路径计算出来。但是由于整个路径是由相同的路径连起来的，所以考虑循环节。对于一个障碍，找到这个点对应的循环节的起点，然后从起点开始，按照命令把这个循环节里面的点都求一遍，如果某个点能够和这个障碍相等，那么说明可以碰到障碍。对于终点，同样的处理方式，如果所在循环节中的某个点和终点相等，那么说明可以到达终点。命令的个数是 10^3 障碍个数也是 10^3 所以整个复杂度是 10^6 。这是可以接受的。
可以看出整个过程主要的复杂度是如何判断某个障碍是否和对应的循环节中的某个点重合。
上面这种对循环节的处理方式不是很优雅，其实可以把任何一个循环节都对应到第一个循环，然后把这个循环节对应的障碍点也对应到第一个循环节的范围中。这样可以就把第一个循环节的所有的点放到集合中，然后只需要判断障碍点是不是在集合中即可。把点放到集合中的处理方式有很多，可以拼接成字符串，也可以通过其它处理方式，只要保证是一一映射即可。讨论区中看到一种比较有趣的做法，对于一个点 (x, y) 把它映射成一个整数 (long)(x) << 30 | y 这是由于题目中点的坐标范围是 10^9 而 10^9 < (1L << 30) ，所以这可以保证是一一映射。
把任何一个点映射到第一个循环节中的点的方式：找到它所在的第 N 个循环节，然后横纵坐标分别减去 N * deltax 和 N * deltay ，其中 deltax 是在一个循环节中横座标的增量。
所以说做题的时候，有的时候虽然能够做出来，可是还是不能够想到最简单和最优雅的处理方式。还是需要多练习和积累经验。一道题目是值得多次做的，做过第一遍之后，以后应该写出最优的解法和实现方式。
#include <vector>#include <iostream>#include <cmath> using namespace std; class Solution { public: int deltax, deltay; bool robot(string command, vector<vector<int>>& obstacles, int x, int y) { deltax = 0, deltay = 0; for (auto i: command) if (i == 'U') deltay++; else deltax++; for (auto i: obstacles) { if (i[0] > x || i[1] > y) continue; if (check(command, i[0], i[1])) return false; } return check(command, x, y); } bool check(string cmd, int x, int y) { int N, startx, starty, N1; if (cmd[0] == 'U') { N = ceil(1.