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.
A:
--------------------1st pass--------------------------------
简直TMD被忽悠了。 没想到如此地简单。
solution 就是简单的一遍遍地遍历,然后,看是否有变化, 有需要变化的,则改之。
public class Solution { public int candy(int[] ratings) { int n = ratings.length; int arrCandy[] = new int[n]; Arrays.fill(arrCandy,1); boolean changed = true; while(changed){ changed = false; for(int i =1;i<n;i++) if(ratings[i]>ratings[i-1] && arrCandy[i]<=arrCandy[i-1]){ arrCandy[i]=arrCandy[i-1]+1; changed = true; } for(int i=n-2;i>=0;i--) if(ratings[i]>ratings[i+1] && arrCandy[i] <= arrCandy[i+1]){ arrCandy[i] = arrCandy[i+1]+1; changed=true; } } int sum = 0; for(int i =0;i<n;i++) sum+=arrCandy[i]; return sum; } }-----------------------这个方法,关键的地方是在左右两边分别按照ascending 和descending来做。
这样就排除了一些极端的情况。而如果是random的数的话,很快就排好了。
--------------第二遍---------------while里,只用了一个for 循环, 里面处理了两种情况---------导致一些ratings = 1 到2000 时, 会TLE
------------------Solution 2---------------来自网上----
初始化所有小孩糖数目为1,从前往后扫描,如果第i个小孩等级比第i-1个高,那么i的糖数目等于i-1的糖数目+1;从后往前扫描,如果第i个的小孩的等级比i+1个小孩高,但是糖的数目却小或者相等,那么i的糖数目等于i+1的糖数目+1。
该算法时间复杂度为O(N)
public class Solution { public int candy(int[] ratings) { int n = ratings.length; int[] nCandy = new int[n]; Arrays.fill(nCandy,1); for(int i =1;i<n;i++) if(ratings[i]>ratings[i-1]) nCandy[i]= nCandy[i-1] +1; for(int i = n-1;i>0;i--) if(ratings[i-1] > ratings[i] && nCandy[i-1] <= nCandy[i] ) nCandy[i-1]= nCandy[i] +1; int count = 0; for(int i = 0;i<n;i++) count += nCandy[i]; return count; } }
Learned:
6: 哎,
int i ;
for(i =0;i<5;i++){
}
System.out.println(i); -----------> 结果是5
No comments:
Post a Comment