算法题三-贪心算法类型

求最后一块石头的重量

如题

有一堆石头，每块石头的重量都是正整数。

每一回合，从中选出两块最重的石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

• 如果 x == y，那么两块石头都会被完全粉碎；
• 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
  最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。`

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/last-stone-weight
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我自己的题解

public static int lastStoneWeight(int[] stones) {
    int result=0;
    //直接排序
    Arrays.sort(stones);
    //循环相减
    for (int i = stones.length-1; i >0; i--) {
        int r=0;
        if(stones.length==1){

            break;
        }

        //如果结果为0代表x==y 两个都摧毁
        r=stones[i]-stones[i-1];
        if(r==0){
            stones[i] = stones[stones.length-1];
            stones[i-1] = stones[stones.length-2];

            stones = Arrays.copyOf(stones, stones.length-1);
            stones = Arrays.copyOf(stones, stones.length-1);
            i--;
        }else{
            stones[i] = stones[stones.length-1];
            stones = Arrays.copyOf(stones, stones.length-1);
            stones[i-1]=r;

        }
        //进行排序进行下次轮询准备
        Arrays.sort(stones);
        //判断数组长度 如果为0 直接跳出

        if(stones.length==0)
         return  0;


    }
    result=stones[0];
    return result;


}

只能算解出来了，并不能达到最优

看这位老兄的代码

 Arrays.sort(stones);
        int end=0;

        for (int i = 0; i <stones.length ; i++) {
            end =stones.length-1;
             if (stones.length==1){
            return stones[0];
        }
            if (stones[end]==stones[end-1]){
                stones[end]=0;
                stones[end-1]=0;
            }else {
                stones[end]=stones[end]-stones[end-1];
                stones[end-1]=0;

            }
            Arrays.sort(stones);
        }
        return stones[stones.length-1];

作者：cztchange
链接：https://leetcode-cn.com/problems/last-stone-weight/solution/wo-de-ti-jie-gen-bie-ren-bu-yi-yang-java-by-cztcha/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

他的题解

1.先对数组进行排序,用Arrays.sort()
2.题目要求每次都是取出最大的,所以对数组的最后两个进行判断
3,如果相等,则两个都等于0,如果不等,则最后一个的值减掉倒数第二个的值,赋值,倒数第二个的值变为0
4在循环内对数组进行排序,每碰撞一次,这样能确保每次都是两个最大的值比较
5最后返回最后一位的值
6因为对数据结构不太熟悉,有很多更好的解法,一开始担心每次循环都要排序时间会超时,可能是测试数据的长度较短

作者：cztchange
链接：https://leetcode-cn.com/problems/last-stone-weight/solution/wo-de-ti-jie-gen-bie-ren-bu-yi-yang-java-by-cztcha/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

当需要 所谓 粉碎这个操作的时候我想的是直接从数组删除

使用了这个方法Arrays.copyOf实际上只需要吧值设为空就行，不影响结果同时也减少了内存使用

其余的都能简化 次要的