算法题--给小朋友发糖问题
2020-05-07 本文已影响0人
岁月如歌2020
image.png
0. 链接
1. 题目
There are N children standing in a line. Each child is assigned a rating value.
You are giving candies to these children subjected to the following requirements:
Each child must have at least one candy.
Children with a higher rating get more candies than their neighbors.
What is the minimum candies you must give?
Example 1:
Input: [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.
Example 2:
Input: [1,2,2]
Output: 4
Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
The third child gets 1 candy because it satisfies the above two conditions.
2. 思路1: 双向加成法
- 基本思路是:
- 首先初始化一个
candies数组, 表示每个小孩分到的糖数, 初始为1 - 先自
i=1开始从左到右遍历ratings数组, 当遇到ratings[i] > ratings[i - 1]，即遇到一个分数比左边邻居高的小朋友时, 则 将他的糖数变为max(candies[i], candies[i - 1] + 1), 确保他的糖比左边小朋友多 - 再从
i = n - 2开始从右到左遍历ratings数组, 当遇到ratings[i] > ratings[i + 1]时, 即遇到一个分数比右边邻居高的小朋友时, 则将他的糖数变为max(candies[i], candies[i + 1] + 1), 确保他的糖同时也比右边的邻居多
- 分析:
- 对于每个节点, 都要遍历2遍 因此时间复杂度为
O(n), 空间复杂度为O(n)
- 复杂度
- 时间复杂度
O(n) - 空间复杂度
O(n)
3. 代码
# coding:utf8
from typing import List
class Solution:
def candy(self, ratings: List[int]) -> int:
n = len(ratings)
if n == 0:
return 0
candies = [1] * n
for i in range(1, n):
if ratings[i] > ratings[i - 1]:
new_num = max(candies[i], candies[i - 1] + 1)
candies[i] = new_num
for i in range(n - 2, -1, -1):
if ratings[i] > ratings[i + 1]:
new_num = max(candies[i], candies[i + 1] + 1)
candies[i] = new_num
return sum(candies)
def my_test(solution, ratings):
print('input: ratings={}; output: {}'.format(ratings, solution.candy(ratings)))
solution = Solution()
my_test(solution, [1, 0, 2])
my_test(solution, [1, 2, 2])
my_test(solution, [2, 2, 3, 1, 0, 1, 0, 3, 2, 1, 0])
输出结果
input: ratings=[1, 0, 2]; output: 5
input: ratings=[1, 2, 2]; output: 4
input: ratings=[2, 2, 3, 1, 0, 1, 0, 3, 2, 1, 0]; output: 21
4. 结果
image.png
5. 思路2: 曲线法
- 过程
- 增加up, down, peak， 从左到右只遍历1次
- up表示当前ratings连续上升的步数, down表示当前ratings连续下降的步数, peak表示最近的1次连续上升阶段的步数
- 关于发糖的问题，可以换个角度来看待，即如果将ratings值随下标的变化，看做一个曲线的话，这个曲线可以看成是若干个连续上升的上坡、若干个平坡、若干个下坡构成；
- 当处于上坡阶段时，我们给第一步的小孩先发1颗糖， 轮到给第二个小朋友发的时候，就不能只发1颗糖了，因为他比第一个小朋友rating高, 所以给他发2颗糖，依次类推，给第up个小朋友，就发up颗糖, 顺便更新下peak，表示连续up的步数
- 当处于平坡的时候，意味着只需要给小孩发1颗糖就好了，因为他没有超过他左边邻居的rating值嘛, 另外peak也重置为1
- 当处于下坡的时候，此时第一个处于下坡的小孩，要发的糖数要分情况对待，
- 当
down < peak时，即当前是从一个峰值直接转而下跌，则只需要给这个小孩发1颗糖,同时递增down；同理，当遇到下坡第2个小孩的时候，给他发1颗糖的同时，要给第1个小孩再补一颗糖，这一步要发出去2颗糖；遇到下坡第3个小孩的时候，给他发1颗糖的同时，要给前2个小孩各多发1颗糖，这次发出去3颗糖；可以看出在下坡第down步的时候，发出去down颗糖 - 当
down >= peak时, 表示当前已经下坡太多步了，此时下坡处第1个小孩的数量，已经赶上了峰值处小孩的糖数量，为了保持峰值小孩的糖数量处于优势，从当前到以后每下坡1步，都要额外给峰值小孩补1颗糖，所以每步发出去down + 1颗糖
- 当
- 将汇总的发糖数
candies返回即可
- 分析
利用此法, 在两个指针start和end的帮助下，每个节点只被遍历1次，就得出了结论，时间复杂度降低到了O(n), 空间复杂度仍然是O(1) - 时间复杂度
O(n) - 空间复杂度
O(1)
6. 代码
# coding:utf8
from typing import List
class Solution:
def candy(self, ratings: List[int]) -> int:
n = len(ratings)
if n <= 1:
return n
up = 1
peak = up
down = 0
candies = 1
for i in range(1, len(ratings)):
if ratings[i] > ratings[i - 1]:
up += 1
peak = up
down = 0
candies += up
elif ratings[i] < ratings[i - 1]:
up = 1
down += 1
candies += down if down < peak else down + 1
else:
up = 1
down = 0
peak = up
candies += 1
return candies
def my_test(solution, ratings):
print('input: ratings={}; output: {}'.format(ratings, solution.candy(ratings)))
solution = Solution()
my_test(solution, [1, 0, 2])
my_test(solution, [1, 2, 2])
my_test(solution, [2, 2, 3, 1, 0, 1, 0, 3, 2, 1, 0])
输出结果
input: ratings=[1, 0, 2]; output: 5
input: ratings=[1, 2, 2]; output: 4
input: ratings=[2, 2, 3, 1, 0, 1, 0, 3, 2, 1, 0]; output: 21
7. 结果
image.png
