谈一道LeetCode——分发糖果

老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。

你需要按照以下要求，帮助老师给这些孩子分发糖果：

那么这样下来，老师至少需要准备多少颗糖果呢？

示例 1:

输入: [1,0,2]

输出: 5

解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。

示例 2:

输入: [1,2,2]

输出: 4

解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。

第三个孩子只得到 1 颗糖果，这已满足上述两个条件。

先看题目要求，

1.每个孩子至少分配到 1 个糖果。

2.相邻的孩子中，评分高的孩子必须获得更多的糖果。

总的糖果最少

总结我们所有可能会遇到的情况，总的解决方法就是首先保证1越多越好，能发一个最好，之后以相差1的情况发放。

每个孩子至少一个糖果，那么什么样的情况孩子会得到一个糖果呢？

当这个孩子i，ratings{i] >ratings[i-1]，且ratings{i] <ratings[i+1]，边界可以单独考虑，简而言之就是处于“低谷”，“波谷”，以数学上的话来说，是函数的极小值。除此之外呢？

还有一种情况，连续的相同的值，而且是有条件的，例如，[1，2，3，3，2，1]，这种情况两个3处是1吗，不是，[1，2，3，3，3，2，1]，这种情况呢？

实际上，判断是不是发一个，可以这样想，如果上升之后就下降，就不是了，如果停留了，那可能是。

还有便是，连续的变化的时候，就是单调递增和递减时，以初始值为1，公差为 1 的等差数列发放

具体考虑便是，当单调递增时，初始值为1，当前发放的糖果比前一个多一个，如果到达了波峰，最高点，有可能下一个值补是最大值，有可能还是。

当不是最大值，意味着走“下坡路”了，此时，我们需要知道当前下降趋势走到了哪？将走到的地方记做极小值，此处发放一个糖果，以1的等差数列逆推之前的发放糖果数

如果还是最大值，但下一个不是最大值，其实处理方法跟之前一样

但是下下一个值还是最大值呢，那么下一个最大值为1

以几个个例子来看：

[1,2,3,2,1] ==> [1,2,3,2,1]

[1,2,3,3,2,1] ==> [1,2,3,3,2,1]

[1,2,3,3,3,2,1] ==> [1,2,3,1,3,2,1]

[1,2,3,3,3,3,3,2,1] ==> [1,2,3,1,1,1,3,2,1]

首先用第一种方法，这种方法其实不是第一次用了，接雨水有一个方法和这个类似

使用两个vector<int>left,vector<int>right

一种从左到右记录“单调递增的序列”，实际是ratings的单调递增序列(从左到右)

另一种从右到左记录“单调递增的序列”，实际是ratings的单调递减序列(从左到右)

先举个例子：

ratings: [1,2,3,3,2,1,0,1,3,2,1]

left:[1,2,3,1,1,1,1,2,3,1,1]

right: [1,1,1,4,3,2,1,1,3,2,1]

汇总时，取两者的最大值就可以了

下面是程序：

这是提交结果：

由于提交有了一段时间，实际结果是，时间上还不错，但是空间上不佳

补：left[i]=1，这个地方似乎可以一开始给left赋初值。

接下来，我们使用另一种方法，不使用两个vector，边遍历边处理，过程稍微复杂了一点

具体过程和思路中基本一致，部分细节上有些差别，都在程序的注释里面了

下面是程序：

下面是系统结果：

空间上有明显改善。

#include <stdio.h>

void rerange(int x[])

{

    int temp = x[0] / 2, l, m

    l = temp

    for (int i = 1 i < 10 i++)

    {

        m = x[i] / 2

        x[i] = m + temp

        temp = m

    }

    x[0] = temp + l

    for (int i = 0 i < 10 i++)

    {

        printf("%d ", x[i])

        if (x[i] % 2)

        {

            x[i] += 1

        }

    }

    printf("\n")

}

int main()

{

    int a[10] = {12, 2, 8, 22, 16, 4, 10, 6, 14, 20}

    int n = 5

    for (int i = 0 i < n i++)

    {

        printf("第%d次调整:\n", i + 1)

        rerange(a)

    }

    return 0

}//解决请采纳

#include <stdio.h>

#include <math.h>

float GetSweets(int seqNum){

    if(seqNum < 1)

    {

        return 0

    }

    else if(seqNum%2 == 0){

        return pow(3.0,(seqNum/2 -1))

    }

    else 

    { 

        return pow(2.0,(seqNum/2))

    }

}

int main(void)

 {

    printf("第九个孩子得到：%d 个糖果\n",(int)GetSweets(9))

    printf("第十个孩子得到：%d 个糖果\n",(int)GetSweets(10))

    return 0

}

试试看行不行。我调用了下pow来算幂次方。哥们，函数已经写好了，你修改下参数不就得到结果了...看来你是真不会写程序啊....sorry啊，哥们儿，一个整除和取余弄混了，你再试下。

---