美文网首页
leetcode--16. single-number II

leetcode--16. single-number II

作者: yui_blacks | 来源:发表于2018-12-06 16:43 被阅读0次

    题目:
    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?
    有N个孩子站在一排。为每个孩子分配一个评等值。
    你给这些孩子提供糖果,这些孩子必须有以下条件:
    每个孩子必须至少有一个糖果。评分高的孩子比邻居得到更多的糖果。
    你必须给多少最低限度的糖果?

    思路:

    • 思路一:
      若用动态规划:
    1. 根据限制我们可以想到一个二维数组,从初次扫描开始,每次扫描将评估值与同行前一个结点和前一行后一个结点的值比较,如果大于就加一。
    2. 何时结束:N个值,最多进行N次循环,因为最多N个不同的数,最大糖果差为N。
      本题,使用N * N的数组会超出内存限制,于是改用2 * N的数组,其实,也只用到两行,前一行,后一行。
    • 思路二:
      第一遍从左向右扫描保证比左边邻居大1
      第二遍从右向左扫描保证比右边邻居大1
    import java.util.*;
    public class Solution {
        public int candy(int[] ratings) {
            if(ratings.length == 0)
                return 0;
            if(ratings.length == 1)
                return 1;
            int[] candy = new int[ratings.length];
            Arrays.fill(candy, 1);
            int sum = 0;
            for(int i = 0; i < ratings.length - 1; i++)
                if(ratings[i] < ratings[i + 1])
                    candy[i + 1] = candy[i] + 1;
            for(int i = ratings.length - 1; i > 0; i--){
                sum += candy[i];
                if(ratings[i] < ratings[i - 1] && candy[i] >= candy[i-1])
                    candy[i-1] = candy[i] + 1;
            } 
            sum += candy[0];
            return sum;
        }
    }
    

    相关文章

      网友评论

          本文标题:leetcode--16. single-number II

          本文链接:https://www.haomeiwen.com/subject/ormocqtx.html