最后一块石头的重量 leetcode

leetcode 题库 1046 最后一块石头的重量

使用了二分查找和插入排序的方法

一、题目描述：

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

每一回合，从中选出两块 最重的 石头，然后将它们一起粉碎。

假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

如果 x == y，那么两块石头都会被完全粉碎；

如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/last-stone-weight

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、解题思路

一、初始化

对数组中的元素进行排序;

这样做有以下两个好处：

1、能从数组的末尾取出最重的两块石头

2、取出两块最重的石头之后，剩余的石头仍然保持有序，

可以使用 二分查找 找到 新石头 在数组中插入的位置。

关于如何进行二分查找，这里有篇非常好的讲解，对二分查找，寻找左侧边界的二分查找，

寻找右侧边界的二分查找都做了详细的介绍

地址：https://leetcode-cn.com/problems/binary-search/solution/er-fen-cha-zhao-xiang-jie-by-labuladong/

二、当两块最重的石头重量相同时

设保存石头重量的数组名称为 stones

1、将两块石头同时粉碎，但是并不会产生新的石头

2、创建新数组 newStones 用来保存新的数据(新数组的长度为 stones.length - 2)

3、将 stones 前 stones.length - 2 的数据依次复制到新数组 newStones 中

三、当两块石头单位重量不同时

1、在数组 stones 取出两块最重的石头

2、将两块石头粉碎，并形成新的石头 newStone

3、使用新石头 newStone 在数组 Stones 中查找新石头需要插入的的位置 i

（查找插入位置时需要排除掉最后的两块石头，即返回 i 的范围为 0 <= i < stones.length - 2）

4、创建新数组 newStones 用来保存新的数据(新数组的长度为 stones.length - 1)

5、将数组 stones i 之前的数据依次插入到 newStones 数组 i 之前的位置

5、将 newStone 插入到 newStones 的 i 位置

6、将 stones i 位置和 i 之后的数据插入依次插入到 newStones i 之后的位置

四、结果返回

当数组的长度为 0 或者是为 1 时返回结果

当数组长度为 0 时返回 0

当数组的长度为 1 时，返回数组中的第一个元素

三、代码如下

public int lastStoneWeight(int[] stones) {
       //用来保存新的数据
       int[] newStones = stones;
       Arrays.sort(newStones);
       for (; newStones.length > 1; ) {
           int max_1 = newStones[newStones.length - 1];
           int max_2 = newStones[newStones.length - 2];
           int t = max_1 - max_2;
           int[] original = newStones;
           if (t == 0) {
               //每次都会创建一个新数组
               newStones = new int[newStones.length - 2];
               //将 stones 前 stones.length - 2 的数据依次复制到新数组 newStones 中
               copyArray(original, 0, newStones, 0, newStones.length);
           } else {
               //每次都会创建一个新数组
               newStones = new int[newStones.length - 1];
			//排除掉最后的两块石头
               int index = leftBoundBinarySearch(original, t, 0, original.length - 2);
               //original 0 ~ index - 1   arr 0 ~ index - 1
               //将数组 stones i 之前的数据依次插入到 newStones 数组 i 之前的位置
               copyArray(original, 0, newStones, 0, index);
               //arr index
               //将 newStone 插入到 newStones 的 i 位置
               newStones[index] = t;
               //将 stones i 之后的数据插入依次插入到 newStones i 之后的位置
               copyArray(original, index, newStones, index + 1, newStones.length - index - 1);
           }
       }
       return newStones.length == 0 ? 0 : newStones[0];
   }

   /**
    * @param originalArr   数据来源的数组
    * @param originalIndex 从数据来源的那个下标开始取值
    * @param targetArr     复制的目标数组
    * @param targetIndex   从目标数组的哪个下标开始赋值
    * @param len           需要赋值的长度
    */
   private void copyArray(int[] originalArr, int originalIndex, int[] targetArr, int targetIndex, int len) {
       for (int i = 0; i < len; i++) {
           targetArr[targetIndex + i] = originalArr[originalIndex + i];
       }
   }

   /**
    * 寻找左侧边界的二分搜索
    *
    * @param nums
    * @param target
    * @return
    */
   int leftBoundBinarySearch(int[] nums, int target, int l, int r) {
       if (nums.length == 0) return -1;
       int left = l;
       int right = r; // 注意

       while (left < right) { // 注意
           int mid = (left + right) / 2;
           if (nums[mid] == target) {
               right = mid;
           } else if (nums[mid] < target) {
               left = mid + 1;
           } else if (nums[mid] > target) {
               right = mid; // 注意
           }
       }
       return left;
   }

打赏