首页 > 其他分享 >135. 分发糖果(leetcode)

135. 分发糖果(leetcode)

时间:2024-08-27 21:48:49浏览次数:12  
标签:分发 ratings int 左边 正确性 num 135 leetcode

https://leetcode.cn/problems/candy/description/

贪心,策略是确定一侧的正确性,再确定另一侧的正确性,最后综合作为正确答案,其中先确定一侧的正确性是局部最优,确定两侧的正确性的局部最优,且找不到反例就可以推出全局最优答案

class Solution {
    public int candy(int[] ratings) {
        int[] num=new int[ratings.length];
        Arrays.fill(num,1);

        // 计算右边孩子大于左边孩子的情况
        for(int i=1;i<ratings.length;i++)
            if(ratings[i]>ratings[i-1])
                num[i]=num[i-1]+1;

        // 计算左边孩子大于右边孩子的情况
        for(int i=ratings.length-2;i>=0;i--)
            if(ratings[i]>ratings[i+1])
            {
                // 取左边和右边+1的最大值,作为本值
                // 即只需要比相邻的最大值大1即可
                // 即 : num[i]=Math.max(num[i-1],num[i+1]+1);
                // 但是上面的循环已经计算过了,此时的num[i]一定比左边大,因此只需要让num[i]和num[i+1]+1比较即可
                num[i]=Math.max(num[i],num[i+1] + 1);
            }
            
        int res=0;
        for(int i=0;i<ratings.length;i++)res+=num[i];
        return res;
    }
}

 

标签:分发,ratings,int,左边,正确性,num,135,leetcode
From: https://www.cnblogs.com/lxl-233/p/18383615

相关文章

  • 程序员必备的的5个刷题网站。大厂面试稳了 力扣 https://leetcode.cn
    程序员必备的的5个刷题网站。大厂面试稳了力扣https://leetcode.cn1、leetcode力扣。网址:https://leetcode.cnLeetCode是一个定位为求职的刷题网站,其中又以算法题为主。很多大厂在面试的时候,都会考算法。有空就刷一刷这里面的算法题,你的算法水平肯定会有大幅的提升,不管是求职,......
  • LeetCode 算法:爬楼梯 c++
    原题链接......
  • 代码随想录训练营day29|134.加油站,135. 分发糖果,860.柠檬水找零,406.根据身高重建队列
    加油站想法:暴力遍历?好吧第一遍写的时候读错题意了,以为是比较gas[i]与cost[i+1]的值,shit。intsum1=0,sum2=0;for(intg:gas)sum1+=g;for(intc:cost)sum2+=c;if(sum1<sum2)return-1;//如果gas没cost多intyouliang=0;intn=gas.size()......
  • 搜索二维矩阵 II(LeetCode)
    题目编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性:每行的元素从左到右升序排列。每列的元素从上到下升序排列。解题"""时间复杂度为O(m+n),其中m是矩阵的行数,n是矩阵的列数。"""defsearchMatrix(matrix,t......
  • 每日一题:Leetcode-47 全排列
    力扣题目解题思路java代码力扣题目:给定一个可包含重复数字的序列 nums ,按任意顺序 返回所有不重复的全排列。示例1:输入:nums=[1,1,2]输出:[[1,1,2],[1,2,1],[2,1,1]]示例2:输入:nums=[1,2,3]输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]解......
  • 【Leetcode 2032 】 至少在两个数组中出现的值 —— 哈希表与按位运算符(最全的注解)
    给你三个整数数组 nums1、nums2 和 nums3 ,请你构造并返回一个 元素各不相同的 数组,且由 至少 在 两个 数组中出现的所有值组成。数组中的元素可以按 任意 顺序排列。示例1:输入:nums1=[1,1,3,2],nums2=[2,3],nums3=[3]输出:[3,2]解释:至少在两个数组中出......
  • LeetCode刷题笔记8.19-8.24
    LeetCode刷题笔记8.19-8.2476.最小覆盖子串(8.19)算法常见技巧——滑动窗口滑动窗口即维护一个窗口(特定数据结构),来替代暴力遍历子结构这种“笨办法”窗口所涉及到的元素由left和right两个指针选定,选定范围从(left,right]开始,随着right指针向后遍历,寻找符合题意的某个可行解......
  • LeetCode 690. 员工的重要性(哈希表、深度优先搜索dfs)
    题目:690.员工的重要性思路:先用哈希表map将每个员工的信息映射到员工ID对应的下标位置。接着使用深度优先搜索dfs,来记录总和即可。细节看注释/*//DefinitionforEmployee.classEmployee{public:intid;intimportance;vector<int>subordinates;......
  • Java | Leetcode Java题解之第374题猜数字大小
    题目:题解:publicclassSolutionextendsGuessGame{publicintguessNumber(intn){intleft=1,right=n;while(left<right){//循环直至区间左右端点相同intmid=left+(right-left)/2;//防止计算时溢出......
  • 数据结构:189(轮转数组)leetcode(OJ)
    给定一个整数数组 nums,将数组中的元素向右轮转 k 个位置,其中 k 是非负数。示例1:输入:nums=[1,2,3,4,5,6,7],k=3输出:[5,6,7,1,2,3,4]解释:向右轮转1步:[7,1,2,3,4,5,6]向右轮转2步:[6,7,1,2,3,4,5]向右轮转3步:[5,6,7,1,2,3,4]示例 2:输入:n......