分糖果系列问题

作者：Grey

LeetCode 135. Candy

主要思路

本题有一个贪心点，即：针对局部最小值位置，只需要分一颗糖果即可。

什么是局部最小值?

如果i位置是局部最小值，则有arr[i] < arr[i+1]且arr[i] < arr[i-1]。如果是第一个位置，则只需要满足arr[i] < arr[i+1]，如果是最后一个位置，则只需要满足arr[i] < arr[i-1]。

如果某个位置j不是局部最小值所在位置，则有如下两种情况

第一种情况，如果arr[j] > arr[j-1]，则j位置分的糖果数量的一种可能性是是j-1位置分得糖果的数量加1，

第二种情况，如果arr[j] < arr[j+1]，则j位置分的糖果数量的另外一个可能性是j+1位置分得糖果的数量加1，

上述两种情况取相对大的一个，即为arr[j]上需要分的糖果数量。

如何优雅表示两种情况呢？我们可以设置两个数组，长度和原始数组一样，其中

        int[] left = new int[n]; 
        left[0] = 1;
        for (int i = 1; i < n; i++) {
            left[i] = arr[i] > arr[i - 1] ? left[i - 1] + 1 : 1;
        }

表示arr[j]只考虑和前一个数arr[j-1]得到的结果数组。

        int[] right = new int[n];
        right[n - 1] = 1;
        for (int i = n - 2; i >= 0; i--) {
            right[i] = arr[i] > arr[i + 1] ? right[i + 1] + 1 : 1;
        }

表示arr[j]只考虑和后一个数arr[j+1]得到的结果数组。

最后，每个位置取最大值累加即可

        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += Math.max(left[i], right[i]);
        }

完整代码如下

    public static int candy(int[] arr) {
        if (null == arr || arr.length == 0) {
            return 0;
        }
        int n = arr.length;
        int[] left = new int[n];
        int[] right = new int[n];
        left[0] = 1;
        for (int i = 1; i < n; i++) {
            left[i] = arr[i] > arr[i - 1] ? left[i - 1] + 1 : 1;
        }
        right[n - 1] = 1;
        for (int i = n - 2; i >= 0; i--) {
            right[i] = arr[i] > arr[i + 1] ? right[i + 1] + 1 : 1;
        }
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += Math.max(left[i], right[i]);
        }
        return sum;
    }

牛客：分糖果问题进阶问题

本题和上一问唯一的区别就是，针对相等分数的同学，糖果必须一致，我们可以根据上述代码稍作改动即可, 见如下注释部分。

        int[] left = new int[n];
        int[] right = new int[n];
        left[0] = 1;
        for (int i = 1; i < n; i++) {
            if (arr[i] > arr[i - 1]) {
                left[i] = left[i - 1] + 1;
            } else if (arr[i] == arr[i - 1]) {
                // 在相等的情况下，保留前一个位置的值
                left[i] = left[i - 1];
            } else {
                left[i] = 1;
            }
        }
        right[n - 1] = 1;
        for (int i = n - 2; i >= 0; i--) {
            if (arr[i] > arr[i + 1]) {
                right[i] = right[i + 1] + 1;
            } else if (arr[i] == arr[i + 1]) {
                // 在相等的情况下，保留后一个位置的值
                right[i] = right[i + 1];
            } else {
                right[i] = 1;
            }
        }

完整代码如下

import java.util.Scanner;

// 链接：//www.nowcoder.com/questionTerminal/de342201576e44548685b6c10734716e
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }
        System.out.println(candy(arr));
        in.close();
    }

    // 进阶：相等分数糖果一定要相等
    public static int candy(int[] arr) {
        int n = arr.length;
        int[] left = new int[n];
        int[] right = new int[n];
        left[0] = 1;
        for (int i = 1; i < n; i++) {
            if (arr[i] > arr[i - 1]) {
                left[i] = left[i - 1] + 1;
            } else if (arr[i] == arr[i - 1]) {
                left[i] = left[i - 1];
            } else {
                left[i] = 1;
            }
        }
        right[n - 1] = 1;
        for (int i = n - 2; i >= 0; i--) {
            if (arr[i] > arr[i + 1]) {
                right[i] = right[i + 1] + 1;
            } else if (arr[i] == arr[i + 1]) {
                right[i] = right[i + 1];
            } else {
                right[i] = 1;
            }
        }
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += Math.max(left[i], right[i]);
        }
        return sum;
    }
}

环形分糖果问题

给定一个正数数组arr，表示每个小朋友的得分，任何两个相邻的小朋友，如果得分一样，怎么分糖果无所谓，但如果得分不一样，分数大的一定要比分数少的多拿一些糖果，假设所有的小朋友坐成一个环形，返回在不破坏上一条规则的情况下，需要的最少糖果数。

本题的关键是如何将环状数组转换成非环状数组。由于是环转数组，所以，任何位置作为第一个值都可以。比如：原始数组是: [3, 4, 2, 3, 2]。其答案和如下数组一定是一样的

[2, 3, 4, 2, 3]
[3, 2, 3, 4, 2]
[2, 3, 2, 3, 4]
[4, 2, 3, 2, 3]

为了方便，我们可以选取局部最小值位置作为开头位置，并在数组末尾增加一个相同的局部最小值，这样，例如，原始数组中，2位置的2是局部最小值，那么我们可以选取如下数组

[2, 3, 2, 3, 4]

然后在这个数组后面增加一个同样的局部最小值2，得到新的数组

[2, 3, 2, 3, 4, 2]

假设这个新数组的的长度是n+1，那么前n个数用前面的分糖果问题解决得到的答案，就是环形数组需要的答案。之所以在末尾添加一个局部最小值，就是排除掉环形的影响，转换为前面分糖果的算法模型。

完整代码如下

    public static int minCandy(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        if (arr.length == 1) {
            return 1;
        }
        int n = arr.length;
        int minIndex = 0;
        for (int i = 0; i < n; i++) {
            // 寻找一个局部最小值
            if (arr[i] <= arr[last(i, n)] && arr[i] <= arr[next(i, n)]) {
                minIndex = i;
                break;
            }
        }
        // 原始数组为[3,4,2,3,2]
        // nums数组为[2,3,2,3,4,2]
        int[] nums = new int[n + 1];
        for (int i = 0; i <= n; i++, minIndex = next(minIndex, n)) {
            nums[i] = arr[minIndex];
        }
        int[] left = new int[n + 1];
        left[0] = 1;
        for (int i = 1; i <= n; i++) {
            left[i] = nums[i] > nums[i - 1] ? (left[i - 1] + 1) : 1;
        }
        int[] right = new int[n + 1];
        right[n] = 1;
        for (int i = n - 1; i >= 0; i--) {
            right[i] = nums[i] > nums[i + 1] ? (right[i + 1] + 1) : 1;
        }
        int sum = 0;
        // 这里不是到n而是到n-1，因为n是占位的，不需要统计进去
        for (int i = 0; i < n; i++) {
            sum += Math.max(left[i], right[i]);
        }
        return sum;
    }

    // 环形数组的下一个位置
    private static int next(int i, int n) {
        return i == n - 1 ? 0 : (i + 1);
    }

    // 环形数组的上一个位置
    private static int last(int i, int n) {
        return i == 0 ? (n - 1) : (i - 1);
    }

算法和数据结构笔记

Tags: leetcode 数据结构牛客算法算法和数据结构贪心