資訊專欄INFORMATION COLUMN
摘要：保證高的小朋友拿到的糖果更多，我們建立一個(gè)分糖果數(shù)組。首先，分析邊界條件如果沒有小朋友，或者只有一個(gè)小朋友，分別對(duì)應(yīng)沒有糖果，和有一個(gè)糖果。排排坐，吃果果。先往右，再往左。右邊高，多一個(gè)?？偤图由闲∨笥芽倲?shù)，就是要準(zhǔn)備糖果的總數(shù)啦。
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?
ExampleGiven ratings = [1, 2], return 3.
Given ratings = [1, 1, 1], return 3.
Given ratings = [1, 2, 2], return 4. ([1,2,1]).
Note保證rating高的小朋友拿到的糖果更多，我們建立一個(gè)分糖果數(shù)組A。小朋友不吃糖果，考試拿A也是可以的。
首先，分析邊界條件：如果沒有小朋友，或者只有一個(gè)小朋友，分別對(duì)應(yīng)沒有糖果，和有一個(gè)糖果。
然后我們用兩個(gè)for循環(huán)來更新分糖果數(shù)組A。
排排坐，吃果果。先往右，再往左。右邊高，多一個(gè)。左邊高，吃得多。
這樣，糖果數(shù)組可能就變成了類似于[0, 1, 0, 1, 2, 3, 0, 2, 1, 0]，小朋友們一定看出來了，這個(gè)不是真正的糖果數(shù)，而是根據(jù)考試級(jí)別ratings給高分小朋友的bonus。
好啦，每個(gè)小朋友至少要有一個(gè)糖果呢。
bonus總和加上小朋友總數(shù)n，就是要準(zhǔn)備糖果的總數(shù)啦。
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;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/65962.html
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...
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...
摘要：建立兩個(gè)堆，一個(gè)堆就是本身，也就是一個(gè)最小堆另一個(gè)要寫一個(gè)，使之成為一個(gè)最大堆。我們把遍歷過的數(shù)組元素對(duì)半分到兩個(gè)堆里，更大的數(shù)放在最小堆，較小的數(shù)放在最大堆。同時(shí)，確保最大堆的比最小堆大，才能從最大堆的頂端返回。 Problem Numbers keep coming, return the median of numbers at every time a new number a...
摘要：首先，我們應(yīng)該了解字典樹的性質(zhì)和結(jié)構(gòu)，就會(huì)很容易實(shí)現(xiàn)要求的三個(gè)相似的功能插入，查找，前綴查找。既然叫做字典樹，它一定具有順序存放個(gè)字母的性質(zhì)。所以，在字典樹的里面，添加，和三個(gè)參數(shù)。 Problem Implement a trie with insert, search, and startsWith methods. Notice You may assume that all i...
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...
閱讀 3060·2021-10-12 10:12
閱讀 5394·2021-09-26 10:20
閱讀 1527·2021-07-26 23:38
閱讀 2817·2019-08-30 15:54
閱讀 1650·2019-08-30 13:45
閱讀 1968·2019-08-30 11:23
閱讀 3092·2019-08-29 13:49
閱讀 836·2019-08-26 18:23
