本文是收集了LeetCode各路大神的思路，供自己和各位算友共同学习进不！！！ 本文是收集了LeetCode各路大神的思路，供自己和各位算友共同学习进不！！！ 本文是收集了LeetCode各路大神的思路，供自己和各位算友共同学习进不！！！
小扣在秋日市集选择了一家早餐摊位，一维整型数组 staple 中记录了每种主食的价格，一维整型数组 drinks 中记录了每种饮料的价格。小扣的计划选择一份主食和一款饮料，且花费不超过 x 元。请返回小扣共有多少种购买方案。
注意：答案需要以 1e9 + 7 (1000000007) 为底取模，如：计算初始结果为：1000000008，请返回 1
示例 1： 输入：staple = [10,20,5], drinks = [5,5,2], x = 15 输出：6 解释：小扣有 6 种购买方案，所选主食与所选饮料在数组中对应的下标分别是： 第 1 种方案：staple[0] + drinks[0] = 10 + 5 = 15； 第 2 种方案：staple[0] + drinks[1] = 10 + 5 = 15； 第 3 种方案：staple[0] + drinks[2] = 10 + 2 = 12； 第 4 种方案：staple[2] + drinks[0] = 5 + 5 = 10； 第 5 种方案：staple[2] + drinks[1] = 5 + 5 = 10； 第 6 种方案：staple[2] + drinks[2] = 5 + 2 = 7。
示例 2： 输入：staple = [2,1,1], drinks = [8,9,5,1], x = 9 输出：8 解释：小扣有 8 种购买方案，所选主食与所选饮料在数组中对应的下标分别是： 第 1 种方案：staple[0] + drinks[2] = 2 + 5 = 7； 第 2 种方案：staple[0] + drinks[3] = 2 + 1 = 3； 第 3 种方案：staple[1] + drinks[0] = 1 + 8 = 9； 第 4 种方案：staple[1] + drinks[2] = 1 + 5 = 6； 第 5 种方案：staple[1] + drinks[3] = 1 + 1 = 2； 第 6 种方案：staple[2] + drinks[0] = 1 + 8 = 9； 第 7 种方案：staple[2] + drinks[2] = 1 + 5 = 6； 第 8 种方案：staple[2] + drinks[3] = 1 + 1 = 2；
提示： 1 <= staple.length <= 10^5 1 <= drinks.length <= 10^5 1 <= staple[i],drinks[i] <= 10^5 1 <= x <= 2*10^5
1、排序 2、双指针 3、i 从前往后， j 从后往前，找到 staple[i] + drinks[j] <= x 的位置 4、就可以往答案里加了
class Solution { public: int breakfastNumber(vector<int>& staple, vector<int>& drinks, int x) { const int mod = 1e9 + 7; int ans = 0; sort(staple.begin(), staple.end()); sort(drinks.begin(), drinks.end()); int j = drinks.size() - 1; for (int i = 0; i < staple.size(); i++) { // i 从前往后， j 从后往前，找到 staple[i] + drinks[j] <= x 的位置 while (j >= 0 && staple[i] + drinks[j] > x) j--; if (j == -1) break; ans += j + 1; ans %= mod; } return ans; } };小扣出去秋游，途中收集了一些红叶和黄叶，他利用这些叶子初步整理了一份秋叶收藏集 leaves， 字符串 leaves 仅包含小写字符 r 和 y， 其中字符 r 表示一片红叶，字符 y 表示一片黄叶。 出于美观整齐的考虑，小扣想要将收藏集中树叶的排列调整成「红、黄、红」三部分。每部分树叶数量可以不相等，但均需大于等于 1。每次调整操作，小扣可以将一片红叶替换成黄叶或者将一片黄叶替换成红叶。请问小扣最少需要多少次调整操作才能将秋叶收藏集调整完毕。
示例 1： 输入：leaves = “rrryyyrryyyrr” 输出：2 解释：调整两次，将中间的两片红叶替换成黄叶，得到 “rrryyyyyyyyrr”
示例 2： 输入：leaves = “ryr” 输出：0 解释：已符合要求，不需要额外操作
提示： 3 <= leaves.length <= 10^5 leaves 中只包含字符 ‘r’ 和字符 ‘y’
思路与算法
由于我们想要将收藏集中树叶的排列调整成「红、黄、红」三部分，因此我们可以用 3 个状态分别表示其中的每一部分，即状态 0 和状态 2 分别表示前面和后面的红色部分，状态 1 表示黄色部分。
此时，我们就可以尝试使用动态规划解决本题了。我们用f[i][j] 表示对于第 0 片到第 i 片叶子（记为leaves[0…i]）进行调整操作，并且第 i 片叶子处于状态 j 时的最小操作次数。在推导状态转移方程时，我们可以分别对于每一种状态进行分析。
当 j=0 时，我们需要将第 i 片叶子变成红色，并且第 i−1 片叶子也只能处于 j=0 的状态（因为没有编号更小的状态了），因此有状态转移方程： f[i][0]=f[i−1][0]+isYellow(i)
其中 isYellow(i) 为示性函数，当第 i 片叶子为黄色时为 1，红色时为 0。
当 j=1 时，我们需要将第 i片叶子变成黄色，而第 i−1 片叶子既可以处于 j=1 的状态，也可以处于 j=0 的状态，我们选择其中的较小值，因此有状态转移方程：
f[i][1]=min{f[i−1][0],f[i−1][1]}+isRed(i)
其中 isRed(i) 为示性函数，当第 i片叶子为红色时为 1，黄色时为 0。
当 j=2 时，我们需要将第 i 片叶子变成红色，而第 i−1 片叶子即可以处于 j=2 的状态，也可以处于 j=1 的状态（注意这里不能处于 j=0 的状态，因为每一种状态包含的叶子数量必须至少为 1），我们选择其中的较小值，因此有状态转移方程：
f[i][2]=min{f[i−1][1],f[i−1][2]}+isYellow(i)
最终的答案即为 f[n−1][2]，其中 nn 是字符串leaves 的长度，也就是树叶的总数。
由于 因为每一种状态包含的叶子数量必须至少为 1，因此不仅需要特别注意 j=2 时的状态转移方程，还需要考虑每个状态本身是否是符合要求的。对于状态 f[i][j] 而言，它包含了leaves[0…i] 共 i+1 片叶子以及 j+1个状态，因此 叶子的数量必须大于等于状态的数量，即满足i≥j。这样一来，所有 i<j 的状态 f[i][j] 都是不符合要求的。观察上面的状态转移方程，我们在每一步转移时都是取最小值，因此我们可以将所有不符合要求的状态置为一个极大值（例如n+1 或整数类型的上限等）。
同时需要注意的是，当 i=0 时，f[i][…] 会从f[i−1][…] 转移而来，但后者是没有意义的，因此我们需要对 f[i][…] 进行特殊处理。由于当 i=0 时，j 也只能为 0，因此我们有： f[0][0]=isYellow(0) 作为唯一的边界条件。
class Solution { public int minimumOperations(String leaves) { int n = leaves.length(); int[][] f = new int[n][3]; f[0][0] = leaves.charAt(0) == 'y' ? 1 : 0; f[0][1] = f[0][2] = f[1][2] = Integer.MAX_VALUE; for (int i = 1; i < n; ++i) { int isRed = leaves.charAt(i) == 'r' ? 1 : 0; int isYellow = leaves.charAt(i) == 'y' ? 1 : 0; f[i][0] = f[i - 1][0] + isYellow; f[i][1] = Math.min(f[i - 1][0], f[i - 1][1]) + isRed; if (i >= 2) { f[i][2] = Math.min(f[i - 1][1], f[i - 1][2]) + isYellow; } } return f[n - 1][2]; } }时间复杂度：O(n)O(n)，其中 nn 是字符串 \textit{leaves}leaves 的长度。 空间复杂度：O(n)O(n)。 可以使用「降维」优化，用三个变量代替状态数组，即可将空间复杂度降低到 O(1)O(1)。具体操作留给读者自行实现。
小扣注意到秋日市集上有一个创作黑白方格画的摊位。摊主给每个顾客提供一个固定在墙上的白色画板，画板不能转动。画板上有 n * n 的网格。绘画规则为，小扣可以选择任意多行以及任意多列的格子涂成黑色，所选行数、列数均可为 0。
小扣希望最终的成品上需要有 k 个黑色格子，请返回小扣共有多少种涂色方案。
注意：两个方案中任意一个相同位置的格子颜色不同，就视为不同的方案。
示例 1： 输入：n = 2, k = 2 输出：4 解释：一共有四种不同的方案： 第一种方案：涂第一列； 第二种方案：涂第二列； 第三种方案：涂第一行； 第四种方案：涂第二行。
示例 2： 输入：n = 2, k = 1 输出：0 解释：不可行，因为第一次涂色至少会涂两个黑格。
示例 3： 输入：n = 2, k = 4 输出：1 解释：共有 2*2=4 个格子，仅有一种涂色方案。
限制： 1 <= n <= 6 0 <= k <= n * n
首先我们依次枚举涂抹 N 行 M列的情况
每涂抹一行就相当于涂抹了 N * n个格子 每涂抹一列就相当于涂抹了 M * n个格子 而当我们选择涂抹 N 行 M 列时，重复涂过 N*M 个格子去掉这个重复数，再来判断是不是等于k 即 判断 ： （N * n + M * N）— N * M == k 当我们得出某个 N 和 M 组合能够得到k，我们就需要通过数学计算排列组合总数。
class Solution { public int paintingPlan(int n, int k) { int res = 0; //边界问题 if(k == 0)return 1; if(k == n * n)return 1; //第一层循环表示涂 i 行 第二层循环表示涂 j 列 for(int i = 0;i <= n;i++){ for(int j = 0;j <= n;j++) //当你涂了 i 行 j 列 则有 i * n + j * n个方格被涂过了 //去掉重复计入的 i*j个方格 是否等于结果k if((i*n) + (j*n) - (i*j) == k) { res += C(i,n) * C(j,n); } } return res; } //数学里的排列组合 C(愚蠢式写法，勿计较) public int C(int x,int y){ if(x == 0)return 1; int n = 1; for(int i = 0;i < x;i++){ n *= (y - i); } for(int i = 1;i <= x;i++){ n /= i; } return n; } }给定整数 n 和 k，找到 1 到 n 中字典序第 k 小的数字。
注意：1 ≤ k ≤ n ≤ 109。
示例 : 输入: n: 13 k: 2 输出: 10
解释: 字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]，所以第二小的数字是 10。
简而言之，就是根据数字的前缀进行排序， 比如 10 < 9，因为 10 的前缀是 1，比 9 小。 再比如 112 < 12，因为 112 的前缀 11 小于 12。
这样排序下来，会跟平常的升序排序会有非常大的不同。先给你一个直观的感受，一个数乘 10，或者加 1，哪个大？可能你会吃惊，后者会更大。 但其实掌握它的本质之后，你一点都不会吃惊。
画一个图你就懂了。 每一个节点都拥有 10 个孩子节点，因为作为一个前缀 ，它后面可以接 0~9 这十个数字。而且你可以非常容易地发现，整个字典序排列也就是对十叉树进行先序遍历。1, 10, 100, 101, … 11, 110 …
回到题目的意思，我们需要找到排在第k位的数。找到他的排位，需要搞清楚三件事情:
怎么确定一个前缀下所有子节点的个数？ 如果第 k 个数在当前的前缀下，怎么继续往下面的子节点找？ 如果第 k 个数不在当前的前缀，即当前的前缀比较小，如何扩大前缀，增大寻找的范围？ 接下来 ，我们一一拆解这些问题。
现在的任务就是给定一个前缀，返回下面子节点总数。 我们现在的思路就是用下一个前缀的起点减去当前前缀的起点，那么就是当前前缀下的所有子节点数总和啦。
//prefix是前缀，n是上界 var getCount = (prefix, n) => { let cur = prefix; let next = prefix + 1;//下一个前缀 let count = 0; //当前的前缀当然不能大于上界 while(cur <= n) { count += next - cur;//下一个前缀的起点减去当前前缀的起点 cur *= 10; next *= 10; // 如果说刚刚prefix是1，next是2，那么现在分别变成10和20 // 1为前缀的子节点增加10个，十叉树增加一层, 变成了两层 // 如果说现在prefix是10，next是20，那么现在分别变成100和200， // 1为前缀的子节点增加100个，十叉树又增加了一层，变成了三层 } return count;//把当前前缀下的子节点和返回去。 }当然，不知道大家发现一个问题没有，当 next 的值大于上界的时候，那以这个前缀为根节点的十叉树就不是满十叉树了啊，应该到上界那里，后面都不再有子节点。因此，count += next - curcount+=next−cur 还是有些问题的，我们来修正这个问题:
count += Math.min(n+1, next) - cur;你可能会问:咦？怎么是 n+1 ,而不是 nn 呢？不是说好了 nn 是上界吗？
我举个例子，假若现在上界 nn为 12，算出以 1 为前缀的子节点数，首先 1 本身是一个节点，接下来要算下面 10，11，12，一共有 4 个子节点。
那么如果用 Math.min(n, next) - curMath.min(n,next)−cur 会怎么样？
这时候算出来会少一个，12 - 10 加上根节点，最后只有 3 个。因此我们务必要写 n+1。
现在，我们搞定了前缀的子节点数问题。
现在无非就是往子树里面去看。 prefix这样处理就可以了。
prefix *= 10说白了，当前的前缀小了嘛，我们扩大前缀。
prefix ++;框架搭建： 整合一下刚刚的思路。
let findKthNumber = function(n, k) { let p = 1;//作为一个指针，指向当前所在位置，当p==k时，也就是到了排位第k的数 let prefix = 1;//前缀 while(p < k) { let count = getNumber(prefix, n);//获得当前前缀下所有子节点的和 if(p + count > k) { //第k个数在当前前缀下 prefix *= 10; p++; //把指针指向了第一个子节点的位置，比如11乘10后变成110，指针从11指向了110 } else if(p + count <= k) { //第k个数不在当前前缀下 prefix ++; p += count;//注意这里的操作，把指针指向了下一前缀的起点 } } return prefix; };完整代码展示：
/** * @param {number} n * @param {number} k * @return {number} */ var findKthNumber = function(n, k) { let getCount = (prefix, n) => { let count = 0; for(let cur = prefix, next = prefix + 1; cur <= n; cur *= 10, next *= 10) count += Math.min(next, n+1) - cur; return count; } let p = 1; let prefix = 1; while(p < k) { let count = getCount(prefix, n); if(p + count > k) { prefix *= 10; p++; } else if(p + count <= k) { prefix ++; p += count; } } return prefix; };