消消乐java算法

消消乐java算法

Java算法题——牛牛消消乐

今天做算法题，遇到了这个题目，随后想把自己的想法写出来。

题目是：

“曾经有两次消除的机会摆在我面前，我却没有珍惜……”牛牛回忆道。

牛牛正在玩一款全新的消消乐游戏。这款游戏的主体是由一列列的方块构成，牛牛的目标就是要尽量消除这些方块。

每次操作，牛牛可以选择某个高度 x ，将所有高度大于等于 x 的那些列全部消除 x 个方块，随后方块会下落，以填补消除造成的空白。

牛牛这一局的发挥极佳，眼看就要破纪录了，却发现自己只剩下了两次消除机会。

为了不错失这千载难逢的机会，他决定写个程序来算出最优解。

简明题意：

给定一个数组 nums ，其中有 n 个非负整数。你的目的是进行 两次 操作，使得数组的元素之和最小。

每次操作形如：任选一个整数 x ，将数组中所有 大于等于 x 的数减去 x 。

示例1

输入

[2, 1, 3]

输出

0

说明

初始数组为 [2, 1, 3]。

先选择 x = 2，则所有大于等于 2 的元素减去 2 ，变成 [0, 1, 1]。

再选择 x = 1，则所有大于等于 1 的元素减去 1 ，变成 [0, 0, 0]。

所以数组元素之和的最小值为 0。

我的解法

import java.util.*;

public class Solution {

/**

* 返回两次操作后，数组元素之和的最小值

* @param nums int整型一维数组 这你你需要操作的数组

* @return long长整型

*/

public long minimumValueAfterDispel (int[] nums) {

// write code here

Arrays.sort(nums);

long sum = 0;//记录整个数组的和

long max = 0;//记录能够减去的最大值

for(int j=0;j

sum += nums[j];

int index1 = j;

int index2 = j;

int index3 = j;

for(int i=0;i<=j;i++){

while(index1 > 0 && nums[index1-1] >= nums[j]-nums[i]){

index1--;

}

while(index2 > i && nums[index2-1] >= nums[j]-nums[i]){

index2--;

}

while(index3 < nums.length && (long)nums[index3] < (long)nums[i]+nums[j]){

index3++;

}

/*

假设两次减去的数为a,b(a

1.a=nums[j]-nums[i] b=nums[i]

2.a=nums[i] b=nums[j]-nums[i]

3.a=nums[i] b=nums[j]

分段函数的边界:

1. index1 < i < j < nums.length 其实index1大于i时不碍事 i-index1变成负数不会影响max的计算

2. i < index2 < j < nums.length

3. i < j < index3 < nums.length

对于第一种情况 index1到i之间的数只能减去a 即 nums[j]-nums[i], i到j之间的数只能减去b 即nums[i] , j到最后的数可以减去a+b 即nums[j]

对于第二种情况 i到index2之间的数只能减去a 即 nums[i], index2到j之间的数只能减去b 即nums[j]-nums[i] , j到最后的数可以减去a+b 即nums[j]

对于第三种情况 i到j之间的数只能减去a 即 nums[i], j到index3之间的数只能减去b 即nums[j], index3到最后的数可以减去a+b 即nums[j]+nums[i]

*/

long tmp1 = (i-index1)*((long)nums[j]-nums[i]) + (j-i)*(long)nums[i] + (nums.length-j)*(long)nums[j];

long tmp2 = (index2-i)*((long)nums[i]) + (j-index2)*((long)nums[j]-nums[i]) + (nums.length-j)*(long)nums[j];

long tmp3 = (j-i)*(long)nums[i] + (index3-j)*(long)nums[j] + (nums.length-index3)*((long)nums[i]+nums[j]);

max = Math.max(max,tmp1);

max = Math.max(max,tmp2);

max = Math.max(max,tmp3);

}

}

return sum - max;

}

}

原文链接：.html