[LintCode/LeetCode] Candy

baishancloud 发布于2019-08-14 15:43 / 3352人阅读

摘要：保证高的小朋友拿到的糖果更多，我们建立一个分糖果数组。首先，分析边界条件如果没有小朋友，或者只有一个小朋友，分别对应没有糖果，和有一个糖果。排排坐，吃果果。先往右，再往左。右边高，多一个。总和加上小朋友总数，就是要准备糖果的总数啦。

Problem

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

Given ratings = [1, 2], return 3.

Given ratings = [1, 1, 1], return 3.

Given ratings = [1, 2, 2], return 4. ([1,2,1]).

Note

保证rating高的小朋友拿到的糖果更多，我们建立一个分糖果数组A。小朋友不吃糖果，考试拿A也是可以的。
首先，分析边界条件：如果没有小朋友，或者只有一个小朋友，分别对应没有糖果，和有一个糖果。
然后我们用两个for循环来更新分糖果数组A。
排排坐，吃果果。先往右，再往左。右边高，多一个。左边高，吃得多。
这样，糖果数组可能就变成了类似于[0, 1, 0, 1, 2, 3, 0, 2, 1, 0]，小朋友们一定看出来了，这个不是真正的糖果数，而是根据考试级别ratings给高分小朋友的bonus。
好啦，每个小朋友至少要有一个糖果呢。
bonus总和加上小朋友总数n，就是要准备糖果的总数啦。

Solution

public class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        if (n < 2) return n;
        int[] A = new int[n];
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i-1]) A[i] = A[i-1]+1;
        }
        for (int i = n-2; i >= 0; i--) {
            if (ratings[i] > ratings[i+1]) A[i] = Math.max(A[i], A[i+1]+1);
        }
        int res = n;
        for (int a: A) res += a;
        return res;
    }
}

服务器托管云服务器 Candy

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65962.html

[LintCode/LeetCode] Word Break

Problem Given a string s and a dictionary of words dict, determine if s can be break into a space-separated sequence of one or more dictionary words. Example Given s = lintcode, dict = [lint, code]. R...

dunizb 2019-08-14 15:30 评论0 收藏0
[LintCode/LeetCode] First Unique Character in a S

Problem Given a string, find the first non-repeating character in it and return its index. If it doesnt exist, return -1. Example Given s = lintcode, return 0. Given s = lovelintcode, return 2. Tags A...

Xufc 2019-08-15 13:27 评论0 收藏0
[LintCode/LeetCode] Find Median From / Data Stream

摘要：建立两个堆，一个堆就是本身，也就是一个最小堆另一个要写一个，使之成为一个最大堆。我们把遍历过的数组元素对半分到两个堆里，更大的数放在最小堆，较小的数放在最大堆。同时，确保最大堆的比最小堆大，才能从最大堆的顶端返回。 Problem Numbers keep coming, return the median of numbers at every time a new number a...

zxhaaa 2019-08-14 14:35 评论0 收藏0
[LintCode/LeetCode] Implement Trie

摘要：首先，我们应该了解字典树的性质和结构，就会很容易实现要求的三个相似的功能插入，查找，前缀查找。既然叫做字典树，它一定具有顺序存放个字母的性质。所以，在字典树的里面，添加，和三个参数。 Problem Implement a trie with insert, search, and startsWith methods. Notice You may assume that all i...

付永刚 2019-08-14 15:23 评论0 收藏0
[LintCode/LeetCode] Binary Tree Pruning

Problem Binary Tree PruningWe are given the head node root of a binary tree, where additionally every nodes value is either a 0 or a 1. Return the same tree where every subtree (of the given tree) not...

rockswang 2019-08-16 12:37 评论0 收藏0