贪心算法试做

最近做到了如何用贪心算法求解均分纸牌问题,在这里讲一下我的思路,
0)假设纸牌数量可以是负数
1)对于最左边的纸牌,为了使它的纸牌数达到平均,只要还没有达到平均无论其余子情况如何移动,一定有一步是把自己多余的纸牌移动到右边,或者是从右边移动进来自己差了多少张纸牌
2)第一堆牌只有和右边进行交互是合法的,步骤1是必须的
3)处理好第一堆后,其余操作一定不涉及第一堆,否则答案更劣(经过前一堆是没有意义的)
4)无视第一堆,于是现在又是情况1了(子结构)
5)对于一个会出现负数的方案,通过调整移动顺序,一定可以转变为一个不出现负数的方案。
代码如下:

public class AverageCardProblem {
public static int moveCards(int[] groups) {
int count = 0, sum = 0;
for (int i = 0; i < groups.length; i++) {
sum += groups[i];
}
int average = sum / groups.length;
for (int i = 0; i < groups.length-1; i++) {
if (groups[i] == average) {
continue;
} else {
groups[i + 1] += groups[i] - average;
count++;
}
}
return count;
}

public static int[] createCards(int n) {
    int[] groups = new int[]{7, 3, 3, 8, 5, 4, 13, 11, 7, 11};
    return groups;
}

}

上一篇:ckedit4.1使用记录


下一篇:[Swift]LeetCode830. 较大分组的位置 | Positions of Large Groups