题目
有n个动物重量分别a1，a2，a3....an,
这群动物一起玩叠罗汉游戏
规定从左往右选择动物，每只动物左边动物的总重量不超过自己的重量
返回最多能选多少个动物，求一个高效的算法
比如有7个动物，从左往右重量依次为 1，3，5，7，9，11，21
最多能选5个动物 1，3，5，9，21
注意：
- 实际给定的数组可能是无序的
- 要求从左往右选动物，且不能打乱原始数组
分析
这道题应该怎么做呢？
确定你审清楚了题目意思，这点很重要，不然浪费了磨脑壳，朝着错误的方向努力，什么也不值了
- 题目没有说给定的数据是有序的
- 选择的动物不能随便改变原数组顺序
- 总重量不超过的意思就是 <=
我们一般人考虑问题都是从简单到复杂，以循序渐进的方式进行，所以从选择1个动物开始分析
数组 1， 3， 5， 7， 9， 11， 21
index 0 1 2 3 4 5 6
定义两个数组
len - 能够选择的动物的数量
ends - 最后一只动物选定之后，累计的总重量
选择到第1只
数组长度，也就是动物的数量为 1 len[1]
因为当前就1只，左边没有动物，重量当然不可能超过自己 0 <= 1
算上自己的总重量 ends[1]
选择到第2只 重量3
左边 1 < 3,
动物的数量为 len[1, 2]
累计重量 ends[1, 4]
选择到第3只 重量5
左边 1 + 3 < 5
动物数量 len [1， 2， 3]
累计重量 4 + 5 = 9 ends[1, 4, 9]
选择到第4只 重量7
左边9 > 7
所以左边 累计重量应该选4合适 4 + 7 = 11 累计重量为11
动物数量继续保持在3 len[1， 2， 3， 3]，
选择1， 3， 7， 累计重量 11 是否合适
1，3，7累计重量11， 1， 3， 5累计重量9，都是3只动物，
但是 9 比 11更合适，因为9更小，后面可以累加的动物数量更多
动物数量 len[1， 2， 3， 3]
累计重量 ends[1， 4， 9, 跳过] 第4只动物就会被跳过
选择到第5只 重量9
左边9 <= 9
动物数量 len[1， 2， 3， 3， 4]
累计重量 ends[1， 4， 9， 跳过， 18]
选择到第6只 重量11
左边 18 > 11
所以左边累计重量应该选9合适 9 + 11 = 20, 累计重量20
动物数量继续保持在4 len[1， 2， 3， 3， 4， 4]，
选择1， 3， 5， 11， 累计重量 20是否合适
1，3，5，9累计重量18， 1，3，5，11 累计重量20， 都是4只动物，
但是 18 比 20更合适，因为18更小，后面可以累加的动物数量更多
动物数量 len[1，2，3，3，4，4]
累计重量 ends[1，4，9，条狗，18，跳过]
选择到第7只 重量21
左边 18 < 21
动物数量 len[1，2， 3，3， 4， 4， 5]
累计重量 ends[1，4，9， 跳过， 18， 跳过， 39]
最终索引到最后一只动物， 动物数量为5只
累计重量数组 ends[1，4，9， 跳过， 18， 跳过， 39]
最终纳入的动物为 1， 3， 5， 9， 21
实现
public class Algorithm0001 {
// 有n个动物重量分别a1，a2，a3....an,
//
// 这群动物一起玩叠罗汉游戏
//
// 规定从左往右选择动物，每只动物左边动物的总重量不超过自己的重量
//
// 返回最多能选多少个动物，求一个高效的算法
//
// 比如有7个动物，从左往右重量依次为 1，3，5，7，9，11，21
//
// 最多能选5个动物 1，3，5，9，21
//
// 注意：
//
// - 实际给定的数组可能是无序的
// - 要求从左往右选动物，且不能打乱原始数组
public static int[] maxAnimal(int[] srcArray) {
int index = 0; // 按顺序从第一个动物开始
// 存储累计重量
int[] ends = new int[srcArray.length];
// 存储纳入的动物重量
int[] valids = new int[srcArray.length];
// 纳入的动物数量
int validCount = 0;
// 0- index, 1-validCount
int[] opt = new int[2];
opt[0] = index;
opt[1] = validCount;
conquer(srcArray, valids, ends, opt);
index = opt[0];
validCount = opt[1];
int[] mArray = new int[validCount];
for (int i = 0; i < validCount; i++) {
mArray[i] = valids[i];
}
return mArray;
}
public static void conquer(int[] srcArray, int[] valids, int[] ends, int[] opt) {
int index = opt[0];
int validCount = opt[1];
if (index < srcArray.length) {
if (index == 0) {
valids[validCount] = srcArray[index];
ends[validCount] = srcArray[index];
validCount++;
} else {
if (ends[validCount - 1] <= srcArray[index]) {
valids[validCount] = srcArray[index];
ends[validCount] = ends[validCount - 1] + srcArray[index];
validCount++;
} else if (ends[validCount - 1] > srcArray[index]) {
if (validCount >= 2) {
// 比较累计重量数组 倒数第二项的累计重量+当前索引的动物重量 与 最后一项累计重量 的大小
if (ends[validCount - 1] > ends[validCount - 2] + srcArray[index]) {
// 说明 当前索引的动物 与 当前已纳入的最后一只动物 相比， 替换已纳入的最后一只动物 更好
valids[validCount - 1] = srcArray[index];
ends[validCount - 1] = ends[validCount - 2] + srcArray[index];
}
// else 说明 当前索引的动物 与 当前已纳入的最后一只动物 相比， 保持当前 已纳入的动物 更好， 继续索引下一只
} else {
// 当前只有1只动物纳入， 但是当前索引的动物重量 比 已纳入的唯一动物重量 小，应该把小的重量的动物纳入，替换掉原来的
valids[validCount - 1] = srcArray[index];
ends[validCount - 1] = srcArray[index];
}
}
}
opt[0] = ++index;
opt[1] = validCount;
conquer(srcArray, valids, ends, opt);
}
}
public static void main(String[] args) {
int n = 1000;
// 随机一些数
List<Integer> mArrayList = new ArrayList();
for (int i = 0; i < n; i++) {
mArrayList.add((int) (Math.random() * 2 * n) + 1);
}
mArrayList.sort(new Comparator() {
@Override
public int compare(Object o1, Object o2) {
return (Integer) o1 - (Integer) o2;
}
});
int[] array = new int[n];
for (int i = 0; i < n; i++) {
array[i] = mArrayList.get(i);
}
for (int i = 0; i < array.length; i++) {
System.out.print(array[i]);
System.out.print(" ");
if (i % 10 == 0 && i > 0) {
System.out.print("\n");
}
}
System.out.print("\n");
System.out.print("\n");
int[] mArray = maxAnimal(array);
for (int i = 0; i < mArray.length; i++) {
System.out.print(mArray[i]);
System.out.print(" ");
if (i % 10 == 0 && i > 0) {
System.out.print("\n");
}
}
}
}
网友评论