leetcode糖果问题,这种做法为什么可行?
leetcode糖果问题
这个官方题解并没有证明,只是说了一下过程。我有以下几点疑问:
left[..]
是在仅符合左规则下分的糖果最少的分配方案吗?同样的right[...]
是在仅符合右规则下分的糖果最少的分配方案吗?就算符合左右规则,为什么这种方案下分的糖果是最少的呢?
var candy = function(ratings) { const n = ratings.length; const left = new Array(n).fill(0); for (let i = 0; i < n; i++) { if (i > 0 && ratings[i] > ratings[i - 1]) { left[i] = left[i - 1] + 1; } else { left[i] = 1; } } let right = 0, ret = 0; for (let i = n - 1; i > -1; i--) { if (i < n - 1 && ratings[i] > ratings[i + 1]) { right++; } else { right = 1; } ret += Math.max(left[i], right); } return ret;};
附:
我凭感觉也写了一种解法,通过了但是我并不知道这是否真的正确。如果是正确的,该怎么证明?如果是错误的,它哪里有问题?
function candy(ratings) {/* candy[i] : the min number of candy the i th people can get based on ratings[0...i], we calculate candy[0...i] if we add ratings[i+1], how to calculate candy[0...i+1] guess(I don't know how to proof): 1. ratings[i+1] > ratings[i], candy[i+1] = candy[i] + 1 2. ratings[i+1] == ratings[i], candy[i+1] = 1 3. ratings[i+1] < ratings[i] candy[i] > 1 => candy[i + 1] = 1 candy[i] == 1 => candy[i] += 1, candy[i] = 1 => if ratings[i-1] > ratings[i], and candy[i-1] >=(actual = ) ratings[i] candy[i-1] += 1 => ... based on rating[0] candy[0] = 1 */const n = ratings.length;const minCandies = Array(n).fill(1);for (let i = 1; i < n; ++i) { if (ratings[i] > ratings[i - 1]) { minCandies[i] = minCandies[i - 1] + 1; } else if (ratings[i] === ratings[i - 1]) { minCandies[i] = 1; } else { minCandies[i] = 1; if (minCandies[i - 1] == 1) { minCandies[i - 1]++; let cur = i - 1; while ( cur - 1 >= 0 && ratings[cur - 1] > ratings[cur] && minCandies[cur - 1] <= minCandies[cur] ) { minCandies[cur - 1]++; cur--; } } }}return minCandies.reduce((pre, cur) => pre + cur);}
left[..]是在仅符合左规则下分的糖果最少的分配方案吗?同样的right[...]是在仅符合右规则下分的糖果最少的分配方案吗?
是
为什么取仅符合左规则的值和仅符合右规则的值的最大值可以同时符合左右规则呢?
如果 rating[i] < rating[i+1]
,那么 left[i] < left[i+1]
, right[i] = 1
最终结果是 candy[i] = max(left[i], right[i]) = max(left[i], 1) = left[i]
, candy[i+1] = max(left[i+1], righ[i+1]) >= left[i+1]
, 所以,candy[i] < cand[i+1]
,满足要求。
大于的情况同上。
相等时任意方案均满足要求。
所以任意相邻两个,用 max(left, right)
均同时满足所有规则。
就算符合左右规则,为什么这种方案下分的糖果是最少的呢?
可以验证只有 1个,2个孩子时是最少的。
可以验证在 rating 严格单调增加于严格单调减小时是最少的。
可以验证,但序列先严格单调增加,再严格单调减小是最少的。
(比如,[1,4,5,3,2]。即存在 k , 对任意 0 < i < k ,有 rating[i-1] < rating[i] < rating[i+1]
; 对任意 k < j < N-1 , 有 rating[j-1] > rating[j] > rating[j+1]
。
否则,利用数学归纳法,如果对 N 个及以下孩子时时最小的。对 N+1 个孩子的情况,除去以上讨论过的情形
1) 如果存在 k,使得 raing[k] == rating[k+1]
,则整个问题可以拆解为 [0..k], [k+1..N] 两个子问题,长度分别为 k+1 与 N-k。两个区间内left, right, candy 的取值均互不影响。由归纳假设,可以得到最小值
2) 否则,则一定存在 k ,使得 rating[k-1] > rating[k] < rating[k+1]
。 此时,可以令 candy[k] = 1
。[0,k]
区间 与 [k,N]
区间相互独立,两个区间内left, right, candy 的取值均互不影响。于是这就形成了两个长度分别为 k+1 与 N-k+1 的子问题。由归纳假设,可知可以分别得到他们的最小值,于是对N+1 的情况也可以得到最小值。
以上方式可以同样用于证明你自己的解法。
我试图使用贪婪算法来计算在JavaScript中达到一定数量所需的最低硬币数量 返回结果将是一个数组,由每个级别的硬币数量组成 我决定做一个函数来解决这个问题,但它不起作用 calculateChange函数包含两个参数:硬币值数组和金额。 第一步是初始化一个sum变量,该变量显示已调度的更改量。我还将创建一个数组变量,该变量将保存某个硬币的分配次数。 为此,我将迭代coins数组并将所有值设置为
problem(https://leetcode.com/problems/candy/description/)语句如下: 有N个孩子站成一排。为每个子级分配一个评等值。您给这些符合以下要求的儿童糖果: 而只给出糖果的总数。我希望修改解决方案,以输出给每个孩子的糖果数量。我的尝试如下: 有人能帮我排除故障或提供一个一次性解决方案吗?
问题内容: 当您将JavaScript代码包装在这样的函数中时: 我注意到,这为许多网页上的我解决了范围界定问题。这种做法叫什么? 问题答案: 该模式称为 自我调用 ( self-invocation) ,一种 自我调用功能 。它可以创建一个闭包,但这是模式的效果(也许是预期的效果),而不是模式本身。
Leetcode加油站问题,这个答案该怎么理解? 题目地址 我在官方题解的下方评论中发现了一个答案,但是对于为什么这个答案可行我并不理解。 为什么sum >= 0说明有解,否则就无解呢? 这个答案我有一些思路。 sum >= 0 将相邻的remainGas[i],且它们的前缀和(这里的前缀和指的是这几个remainGas构成序列的前缀和)都大于等于0,合并成一个节点(此时这个节点代表了一段路径)。
,文字前面跟着已到期或者即将到期,但是这段文字是右对齐,且以最长文本的长度作为整个盒子的宽度,并设置背景色。
我已经实现了极大极小算法(带有阿尔法-贝塔剪枝),但是它的行为方式很有趣。我的球员将创造一个巨大的领先优势,但当它是时候做出最后的,获胜的举动,它不采取这一举措,只是继续拖延游戏。 这是我的极小极大函数: } 起初,我认为问题出在我的评估功能上,但如果是,我找不到它。在这个游戏中,两个玩家都有一个分数,我的函数只是从分数差中计算启发式值。在这里: 我已经把我的代码“翻译”成了英语,所以可能会有错别