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?
Solution 1:
两头扫瞄,第一次从左到右,第二次从右到左,这样递增和递减的关系就刚好相反。每一个递增都加一,递减就不变。
public int candy(int[] ratings) { int n = ratings.length; int[] candy = new int[n]; Arrays.fill(candy, 1); for(int i=1, k=1; i<n; i++) { if(ratings[i] > ratings[i-1]) { candy[i] = ++k; } else { k = 1; } } for(int i=n-2, k=1; i>=0; i--) { if(ratings[i] > ratings[i+1]) { // i.e. [4,2,3,4,1], the previous candy count may be larger than ++k, we should get the larger one. candy[i] = Math.max(candy[i], ++k); } else { k = 1; } } int sum = 0; for(int num : candy) { sum += num; } return sum; }
上面代码中的K其实可以用candy数组中的上个元素的值替代,因为只要比上一个元素值大1就行。
所以代码可以改成这个样子:
public int candy(int[] ratings) { int n = ratings.length; int[] candy = new int[n]; Arrays.fill(candy, 1); for(int i=1; i<n; i++) { if(ratings[i] > ratings[i-1]) { candy[i] = candy[i-1] + 1; } } for(int i=n-2; i>=0; i--) { if(ratings[i] > ratings[i+1]) { // i.e. [4,2,3,4,1], the previous candy count may be larger than candy[i+1]+1, we should get the larger one. candy[i] = Math.max(candy[i], candy[i+1] + 1); } } int sum = 0; for(int num : candy) { sum += num; } return sum; }
Solution 2:
网上很多文章给出了这种解法。我在leetcode上测试了下,会曝出运行超时。
public int candy(int[] ratings) { if (ratings.length == 0) return 0; int[] d = new int[ratings.length]; d[0] = 1; for (int i = 1; i < ratings.length; i++) { if (ratings[i] == ratings[i - 1]) d[i] = 1; else if (ratings[i] > ratings[i - 1]) d[i] = d[i - 1] + 1; else {// should give less candy than prev child d[i] = 1; if (d[i - 1] == 1) { int j = i; while (j > 0 && ratings[j - 1] > ratings[j] && d[j - 1] == d[j]) { //only push backwards when ratings diff but candy are same d[j - 1]++; j--; } } } } int sum = 0; for (int i = 0; i < ratings.length; i++) { sum += d[i]; } return sum; }
相关推荐
javascript js_leetcode题解之135-candy.js
python python_leetcode题解之135_Candy
"135", // id "titleSlug": "candy", // 题目url "title": "Candy", // 题目标题 "content": "<p>There are <em>N ...", // 题目描述 "difficulty": "Hard", // 难度 ...
java java_leetcode题解之Candy.java
- **2.1.22 Candy** - 分发糖果问题,确保相邻的孩子获得的糖果数量不同。 - 实现思路:动态规划,先从左到右分配,再从右到左分配。 - **2.1.23 Single Number** - 找出数组中只出现一次的数字。 - 实现思路...
candy 贪心 gas-station 动态规划 palindrome-partitioning-ii 动态规划 triangle 树 sum-root-to-leaf-numbers 动态规划 distinct-subsequences 递归 valid-palindrome 模拟 pascals-triangle 模拟 pasca
LeetCode.135分发糖果135. 分发糖果解题思路:3、最后发放糖果时必须同时满足左规则、右规则,所以取左右规则最大值public int candy
leetcode 和 oj #问题列表(按标题升序) 标题|添加日期|AC 利率 ---|---|---|--- 3Sum |2012-01-17|16.4% 3Sum Closest|2012-01-18|26.8% 4Sum|2012-01-26 |21.3% 二进制加法|2012-04-02|25.6% 两个数相加|2011-11-...
- **Candy**:分糖果,确保每个孩子至少得到一块糖,尽可能公平。 - **Word Break**:判断一个字符串是否可以拆分为一个词汇表中的单词序列。 7. **链表(Linked List)**: - **Linked List Cycle**:检测链表...
candy: minimum_depth_binary_tree: twoSum: regularExpressionMathcing: sameTree: find_content_children: LeetCode 算法题 时间复杂度和空间复杂度权衡,时间复杂度的提升是以空间复杂度为代价的 仔细观察,...
我自己在新学erlang,在LeetCode OJ上找了题目练习,题目很适合新手熟悉语言,但是LeetCode OJ里面只有几门主流语言的答案,下面是已完成的erlang源代码,后续有空再做其他问题续传,题目包含:(源码开头都有题目...
leetcode最大蓄水量 记录数据结构和leetCode算法题 数据结构 sparsearray 稀疏数组 singlequeue 数组模拟队列 circelqueue 数组模拟环形队列 singlequeue 单向链表 doublelink 双向链表 circlesinglelink 环形链表 ...
谷歌师兄的leetcode刷题笔记 甜蜜银行 :candy: Sweet Bank 是Kotlin中的一个 Android 应用程序,我开发它是为了尝试移动开发的一些原则,例如范围分离、设计模式(例如 MVVM)等等。 我使用 Starling Bank API 来...
《Candy_leetcode:刷leetcode的代码汇总》 在编程领域,LeetCode是一个深受程序员喜爱的在线平台,它提供了大量的编程题目,旨在帮助用户提升算法技能、深化对数据结构的理解以及提高解决实际问题的能力。本资源...
leetcode打不开玩具问题 编码练习 string input; while (getline(cin, input)) { cout << "input: " << input << endl; string output = candyCrush(input); cout << "output: " << ...
11. LeetCode题目案例:文档中提到了一些特定的LeetCode题目案例,如SetMatrixZeroes、GasStation、Candy、SingleNumber等。这些案例覆盖了数组、单链表、字符串等数据结构的多种操作,体现了各种算法应用场景。 12...
应用程序三重子序列128最长连续序列164最大间隔桶287查找重复数135Candy很少考330Patching Array很少考 LifeInterval57Insert Interval56Merge Intervals252Meeting Rooms253Meeting客房II352Data流从数据Stream53...
- **分发糖果(Candy)**: 给定评分,每个孩子至少分配1颗糖果,相邻的孩子如果评分不同,则评分较高的孩子必须获得更多的糖果。 ##### 链表(LinkedList) - **合并两个有序链表(Merge Sorted Lists)**: 合并两个已...
leetcode_easy_python 挑战1431:给定数组糖果和整数extraCandies,其中candy [i]代表第i个孩子拥有的糖果数量。 对于每个孩子,检查是否有一种方法可以在孩子之间分配额外的糖果,以便他或她可以在其中拥有最多的...
这是一个学习《小灰算法》《算法4》的仓库,里面有对《小灰算法》和《算法4》的代码实现,里面涉及数据结_Candy-leetcode