NC130:分糖果问题

分糖果问题

http://www.nowcoder.com/questionTerminal/76039109dd0b47e994c08d8319faa352

解法1:左右各遍历一次

  • 把所有孩子的糖果数初始化为 1;

  • 先从左往右遍历一遍,如果右边孩子的评分比左边的高,则右边孩子的糖果数更新为左边孩子的 糖果数加 1;

  • 再从右往左遍历一遍,如果左边孩子的评分比右边的高,且左边孩子当前的糖果数不大于右边孩子的糖果数,
    则左边孩子的糖果数更新为右边孩子的糖果数加 1。

  • 通过这两次遍历, 分配的糖果就可以满足题目要求了。

    import java.util.*;
    public class Solution {
      /**
       * pick candy
       * @param arr int整型一维数组 the array
       * @return int整型
       */
      public int candy (int[] arr) {
          // write code here
          int[] tmp= new int[arr.length];
          Arrays.fill(tmp,1);
          int count=0;
    
          for(int i=1;i<arr.length;i++){
              if(arr[i]>arr[i-1]){
                  tmp[i]=tmp[i-1]+1;
              }
          }
           for(int i=arr.length-1;i>0;i--){
              if(arr[i-1]>arr[i]){
                  tmp[i-1]=Math.max(tmp[i-1],tmp[i]+1);
              }
          }
          for(int i:tmp)
              count+=i;
          return count;
      }
    }

    解法2:每次记录一个up连续上升的个数,down连续下降的个数,peak当前峰的高度

    图片说明

    import java.util.*;
    public class Solution {
      public int candy (int[] arr) {
          // write code here
          int up = 0, down = 0, peak = 1, res = 1;
          for (int i = 1; i < arr.length; i++) {
              res++;
              if (arr[i] > arr[i - 1]) {
                  up++;
                  res += up;
                  down = 0;
                  peak = up + 1;
              }
              else if (arr[i] == arr[i - 1]) {
                  up = 0;
                  down = 0;
                  peak = 1;
              }
              else {
                  up = 0;
                  res += down;
                  down++;
                  if (down >= peak) 
                     res++;
              }
          }
          return res;
      }
    }
名企高频面试算法题解 文章被收录于专栏

牛客题霸 - 程序员面试高频题 - 题解

全部评论
算法题做了几十道,一道都不会
点赞 回复 分享
发布于 2023-11-02 19:07 湖北
res++; 修改为初始化res = arr.length
点赞 回复 分享
发布于 2023-03-11 18:15 广东
太强了,最后一个else的逻辑,以简洁的方式覆盖了多种情况,我脑子怎么也想不出来,牛!!!
点赞 回复 分享
发布于 2022-09-19 14:46 黑龙江
解法2图文并茂,谢谢博主的分享!!!
点赞 回复 分享
发布于 2022-02-27 13:21

相关推荐

仁者伍敌:服务员还要脱颖而出,这是五星级酒店吗
点赞 评论 收藏
分享
风中翠竹:真的真的真的没有kpi。。。面试官是没有任何kpi的,捞是真的想试试看这个行不行,碰碰运气,或者是面试官比较闲现在,没事捞个人看看。kpi算HR那边,但是只有你入职了,kpi才作数,面试是没有的。
双非有机会进大厂吗
点赞 评论 收藏
分享
头顶尖尖的程序员:我也是面了三四次才放平心态的。准备好自我介绍,不一定要背熟,可以记事本写下来读。全程控制语速,所有问题都先思考几秒,不要急着答,不要打断面试官说话。
点赞 评论 收藏
分享
评论
37
8
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务