C++实现LeetCode(135.分糖果问题)

2024-10-01 09:56:06

[LeetCode] 135.Candy 分糖果问题

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?

这道题看起来很难，其实解法并没有那么复杂，当然我也是看了别人的解法才做出来的，先来看看两遍遍历的解法，首先初始化每个人一个糖果，然后这个算法需要遍历两遍，第一遍从左向右遍历，如果右边的小盆友的等级高，等加一个糖果，这样保证了一个方向上高等级的糖果多。然后再从右向左遍历一遍，如果相邻两个左边的等级高，而左边的糖果又少的话，则左边糖果数为右边糖果数加一。最后再把所有小盆友的糖果数都加起来返回即可。代码如下：

解法一：

class Solution {
public:
    int candy(vector<int>& ratings) {
        int res = 0, n = ratings.size();
        vector<int> nums(n, 1);
        for (int i = 0; i < n - 1; ++i) {
            if (ratings[i + 1] > ratings[i]) nums[i + 1] = nums[i] + 1;
        }
        for (int i = n - 1; i > 0; --i) {
            if (ratings[i - 1] > ratings[i]) nums[i - 1] = max(nums[i - 1], nums[i] + 1);
        }
        for (int num : nums) res += num;
        return res;
    }
};

下面来看一次遍历的方法，相比于遍历两次的思路简单明了，这种只遍历一次的解法就稍有些复杂了。首先我们给第一个同学一个糖果，那么对于接下来的一个同学就有三种情况：

1. 接下来的同学的rating等于前一个同学，那么给接下来的同学一个糖果就行。

2. 接下来的同学的rating大于前一个同学，那么给接下来的同学的糖果数要比前一个同学糖果数加1。

3.接下来的同学的rating小于前一个同学，那么我们此时不知道应该给这个同学多少个糖果，需要看后面的情况。

对于第三种情况，我们不确定要给几个，因为要是只给1个的话，那么有可能接下来还有rating更小的同学，总不能一个都不给吧。也不能直接给前一个同学的糖果数减1，有可能给多了，因为如果后面再没人了的话，其实只要给一个就行了。还有就是，如果后面好几个rating越来越小的同学，那么前一个同学的糖果数可能还得追加，以保证最后面的同学至少能有1个糖果。来一个例子吧，四个同学，他们的rating如下：

1 3 2 1

先给第一个rating为1的同学一个糖果，然后从第二个同学开始遍历，第二个同学rating为3，比1大，所以多给一个糖果，第二个同学得到两个糖果。下面第三个同学，他的rating为2，比前一个同学的rating小，如果我们此时给1个糖果的话，那么rating更小的第四个同学就得不到糖果了，所以我们要给第四个同学1个糖果，而给第三个同学2个糖果，此时要给第二个同学追加1个糖果，使其能够比第三个同学的糖果数多至少一个。那么我们就需要统计出多有个连着的同学的rating变小，用变量cnt来记录，找出了最后一个减小的同学，那么就可以往前推，每往前一个加一个糖果，这就是个等差数列，我们可以直接利用求和公式算出这些rating减小的同学的糖果之和。然后我们还要看第一个开始减小的同学的前一个同学需不需要追加糖果，只要比较cnt和pre的大小，pre是之前同学得到的最大糖果数，二者做差加1就是需要追加的糖果数，加到结果res中即可，参见代码如下：

解法二：

class Solution {
public:
    int candy(vector<int>& ratings) {
        if (ratings.empty()) return 0;
        int res = 1, pre = 1, cnt = 0;
        for (int i = 1; i < ratings.size(); ++i) {
            if (ratings[i] >= ratings[i - 1]) {
                if (cnt > 0) {
                    res += cnt * (cnt + 1) / 2;
                    if (cnt >= pre) res += cnt - pre + 1;
                    cnt = 0;
                    pre = 1;
                }
                pre = (ratings[i] == ratings[i - 1]) ? 1 : pre + 1;
                res += pre;
            } else {
                ++cnt;
            }
        }
        if (cnt > 0) {
            res += cnt * (cnt + 1) / 2;
            if (cnt >= pre) res += cnt - pre + 1;
        }
        return res;
    }
};

参考资料：

https://discuss.leetcode.com/topic/5243/a-simple-solution

https://discuss.leetcode.com/topic/8208/one-pass-constant-space-java-solution

https://discuss.leetcode.com/topic/17722/two-c-solutions-given-with-explanation-both-with-o-n-time-one-with-o-1-space-the-other-with-o-n-space

到此这篇关于C++实现LeetCode(135.分糖果问题)的文章就介绍到这了,更多相关C++实现分糖果问题内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

C++实现LeetCode(134.加油站问题)

[LeetCode] 134.Gas Station 加油站问题 There are N gas stations along a circular route, where the amount of gas at station i is gas[i]. You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1)
C++实现LeetCode(133.克隆无向图)

[LeetCode] 133. Clone Graph 克隆无向图 Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node in the graph contains a val (int) and a list (List[Node]) of its neighbors. Example: Input: {"$id":
C++实现LeetCode(130.包围区域)

[LeetCode] 130. Surrounded Regions 包围区域 Given a 2D board containing 'X' and 'O'(the letter O), capture all regions surrounded by 'X'. A region is captured by flipping all 'O's into 'X's in that surrounded region. Example: X X X X X O O X X X O X X O
C++实现LeetCode(200.岛屿的数量)

[LeetCode] 200. Number of Islands 岛屿的数量 Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four
C++验证LeetCode包围区域的DFS方法

验证LeetCode Surrounded Regions 包围区域的DFS方法在LeetCode中的Surrounded Regions 包围区域这道题中,我们发现用DFS方法中的最后一个条件必须是j > 1,如下面的红色字体所示,如果写成j > 0的话无法通过OJ,一直百思不得其解其中的原因,直到有网友告诉我说他验证了最后一个大集合在本地机子上可以通过,那么我也来验证看看吧. class Solution { public: void solve(vector<vector<
C++实现LeetCode(138.拷贝带有随机指针的链表)

[LeetCode] 138. Copy List with Random Pointer 拷贝带有随机指针的链表 A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null. Return a deep copy of the list. Example 1: Input: {"$id"
C++实现LeetCode(129.求根到叶节点数字之和)

[LeetCode] 129. Sum Root to Leaf Numbers 求根到叶节点数字之和 Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number. An example is the root-to-leaf path 1->2->3 which represents the number 123. Find the total sum
C++实现LeetCode(128.求最长连续序列)

[LeetCode] 128.Longest Consecutive Sequence 求最长连续序列 Given an unsorted array of integers, find the length of the longest consecutive elements sequence. Your algorithm should run in O(n) complexity. Example: Input: [100, 4, 200, 1, 3, 2] Output: 4 Expl
C++实现LeetCode(135.分糖果问题)

[LeetCode] 135.Candy 分糖果问题 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 high
Python实现的基于优先等级分配糖果问题算法示例

本文实例讲述了Python实现的基于优先等级分配糖果问题算法.分享给大家供大家参考,具体如下: 问题: 有n个人,每个人有一定的优先等级,等级高的人要比身边等级低得人得到的多,每个人都不会分不到思路: 可以采用两头遍历的方法,顺序遍历保证等级高的人会比左边的人多,倒序遍历可以保证等级高的人比右边的人多下面是具体实现: #!usr/bin/env python #encoding:utf-8 ''''' __AUthor__:沂水寒城功能:分糖果 ''' def split_candy(ra
.NET开发实现一个微信跳一跳的辅助程序

前言相信大家应该都知道了,最近微信更新了,出现了一个小游戏"跳一跳",玩了一下赶紧还蛮有意思的但纯粹是拼手感的,玩了好久,终于搞了个135分拿了个第一名,没想到过一会就被朋友刷下去了,最高的也就200来分把,于是就想着要是开发个辅助就好了,于是简单想了一下最高游戏先来说下这个游戏的界面和规则: 先看看界面规则: 按住屏幕按一定时间松开就可以跳跃,跳跃到前方的图案中得1分,图按中间得2分(连续多个中间累加2分,比如第一个2分第二个4分第三个6分最高累计32分) 其它规则
C++实现LeetCode(93.复原IP地址)

[LeetCode] 93.Restore IP Addresses 复原IP地址 Given a string containing only digits, restore it by returning all possible valid IP address combinations. Example: Input: "25525511135" Output: ["255.255.11.135", "255.255.111.35"] 这
2分法分页存储过程脚本实例

需要说明的是:这个存储过程参数比较多,我再实际使用中又在外面单独写了一个类,页面调用直接调用封装的类,方法有很多,主要是思路,大家可以参考下. 代码修改集中在类似复制代码代码如下: if @Sort=0set @strTmp = @strTmp + '<(select min(' elseset @strTmp = @strTmp + '>(select max(' 另外94行主要是配合我自己写的类,显示记录条数分页数等信息,如果不需要就去掉. 复制代码代码如下: 1ALTER PROC
js canvas仿支付宝芝麻信用分仪表盘

这是一个仿支付宝芝麻信用分的一个canvas,其实就是一个动画仪表盘. 首先, 上原图: 这个是在下支付宝上的截图,分低各位见笑了.然后看下我用canvas实现的效果图: <canvas id="canvas" width="400" height="700" data-score='724'></canvas>  唉,总感觉不像.这个是G
jQuery 实现倒计时天,时,分,秒功能

1.HTML部分 135天7时46分25秒 2.js部分 <script src="https://c
vscode中配置LeetCode插件的教程(愉快刷题)

大家好,今早在B站看到up主的vscode里藏了leetcode插件,这才知道原来还有这款神器.但是没想到在用的时候遇到了一些麻烦,花了一点时间才解决.所以写这篇文章除了给大家安利这个好用的插件之外,也是为了帮助更多的同学避免踩坑. 简介vscode vscode在工业界鼎鼎大名,被誉为微软少有的拿得出手的精品(逃).原本是不想过多赘述的,但是鉴于许多粉丝还是正在上学的萌新,所以花点笔墨简单介绍一下. vscode是微软开发的编辑器,严格说起来它并不是一个IDE,只是一个编辑器.但是由于它支持嵌
python 输入字符串生成所有有效的IP地址(LeetCode 93号题)

这题的官方难度是Medium,点赞1296,反对505,通过率35.4%.从各项指标来说看起来有些中规中矩,实际上也的确如此.这道题的解法和立意都有些显得新意不足,但总体来说题目的质量还是可以的,值得一做. 题意给定一个由数字组成的字符串,我们希望通过这个字符串得到所有有效ip地址的组合.对于一个有效的ip地址而言,它应该有4个数字组成,每一个数字的范围在0到255之间. 一个字符串可能可以转化成多个ip地址,我们需要存储下来所有可以成立的情况. 样例 Input: "25525511135&
如何用C++制作LeetCode刷题小技巧-错题记录本

一 . 刷题小技巧 1,c++中的for(auto a:b)用法 for(auto a:b)中b为一个容器,效果是利用a遍历并获得b容器中的每一个值,但是a无法影响到b容器中的元素. for(auto &a:b)中加了引用符号,可以对容器中的内容进行赋值,即可通过对a赋值来做到容器b的内容填充. 2,c++中map的元素进行按照值排序(默认按照键排序) 为什么不能对map进行按值排序呢?因为sort排序只能对线性结构进行排序,而map是采用红黑树的数据结构. 一是通过将map转换到序列容器,再用

C++实现LeetCode(135.分糖果问题)

[LeetCode] 135.Candy 分糖果问题

相关推荐

随机推荐