专栏首页算法修养LeetCode 135 Candy

LeetCode 135 Candy

LeetCode 135 Candy

思路:

将数组排序。然后根据值从小到大,在数组中依次标记值。

c++

class Solution {
public:
    int can[100005];
    int a[100005];
    vector<int> b[100005];
    int tag[100005];
    int candy(vector<int>& ratings) {
        
        int l=ratings.size();
        int ans=0;
        memset(vis,0,sizeof(vis));
        for(int i=0;i<l;i++)
        {
            a[i]=ratings[i];
        }
        sort(a,a+l);
        int rank=0;
        for(int i=0;i<l;i++)
        {
            if(tag[a[i]]==0)
                tag[a[i]]=++rank;
        }
        for(int i=0;i<l;i++)
        {
            b[tag[ratings[i]]].push_back(i);
        }
        for(int i=1;i<=rank;i++)
        {
            for(int k=0;k<b[i].size();k++)
            {
                int j=b[i][k];
                 int x=1,y=1;
                 if(j-1>=0&&can[j-1]!=0)
                 {
                      if(ratings[j-1]==ratings[j])
                          x = 1;
                      else
                          x=can[j-1]+1;
                            
                 }
                 if(j+1<l&&can[j+1]!=0)
                 {
                      if(ratings[j+1]==ratings[j])
                           y=1;
                      else
                           y=can[j+1]+1;
                 }
                        
                 can[j]=max(x,y); 
                 ans+=can[j];
             }

        }
        
        return ans;
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • POJ-1088 滑雪 (记忆化搜索,dp)

    滑雪 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 86318 ...

    ShenduCC
  • LeetCode 1292. Maximum Side Length of a Square with Sum Less than or Equal to Threshold

    ShenduCC
  • 天梯赛 大区赛 L3-014.周游世界 (Dijkstra)

    L3-014. 周游世界 时间限制 200 ms 内存限制 65536 kB 代码长度限制 8000 B 判题程序 Standar...

    ShenduCC
  • 数独终盘生成的几种方法

    为了完成矩阵的转换,我们需要有可用的数独终盘矩阵作为种子矩阵才行。可以采用如下做法完成:

    孟君
  • LeetCode 75. Sort Colors题目分析

    给定一个包含红,白,蓝且长度为 n 的数组,将数组元素进行分类使相同颜色的元素相邻,并按照红、白、蓝的顺序进行排序。 我们可以使用整数 0,1 和 2 分别代...

    desperate633
  • 1009 产生数 2002年NOIP全国联赛普及组

    009 产生数 2002年NOIP全国联赛普及组 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 De...

    attack
  • POJ-3866-Exclusive Access 2

    ACM模版 描述 ? ? ? 题解 这绝对是我做过最长的题,也是最难理解的题,翻译成中文都很难理解。 简单的说,就是安排任务使用两个资源的顺序,使最坏情况下,执...

    f_zyj
  • POJ-1088 滑雪 (记忆化搜索,dp)

    滑雪 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 86318 ...

    ShenduCC
  • LeetCode 1292. Maximum Side Length of a Square with Sum Less than or Equal to Threshold

    ShenduCC
  • 洛谷P2196 挖地雷(dp)

    attack

扫码关注云+社区

领取腾讯云代金券