Go語言LeetCode題解1046最后一塊石頭的重量
題目描述
1046. 最后一塊石頭的重量 - 力扣（LeetCode）
有一堆石頭，每塊石頭的重量都是正整數(shù)。
每一回合，從中選出兩塊 最重的 石頭，然后將它們一起粉碎。假設(shè)石頭的重量分別為 x 和 y，且 x <= y。那么粉碎的可能結(jié)果如下：
- 如果 x == y，那么兩塊石頭都會(huì)被完全粉碎；
- 如果 x != y，那么重量為 x 的石頭將會(huì)完全粉碎，而重量為 y 的石頭新重量為 y-x。
最后，最多只會(huì)剩下一塊石頭。返回此石頭的重量。如果沒有石頭剩下，就返回 0。
示例：
輸入：[2,7,4,1,8,1]
輸出：1
解釋：
先選出 7 和 8，得到 1，所以數(shù)組轉(zhuǎn)換為 [2,4,1,1,1]，
再選出 2 和 4，得到 2，所以數(shù)組轉(zhuǎn)換為 [2,1,1,1]，
接著是 2 和 1，得到 1，所以數(shù)組轉(zhuǎn)換為 [1,1,1]，
最后選出 1 和 1，得到 0，最終數(shù)組轉(zhuǎn)換為 [1]，這就是最后剩下那塊石頭的重量。
提示：
1 <= stones.length <= 30
1 <= stones[i] <= 1000
思路分析
- 這里用到了Arrays.sort排序，得到了從小到大的數(shù)組。
- 接下來用lastIndex指針指向未被粉碎的最后一個(gè)元素，取兩個(gè)最大的石頭，下標(biāo)lastIndex,lastIndex-1。兩者相減的差值賦給lastIndex-1,再移動(dòng)下lastIndex指針就相當(dāng)于刪除了最后一個(gè)元素了
- 也可以改寫成遞歸，思路是一樣的。
AC 代碼
import java.util.Arrays;
class Solution {
//一堆石頭 每一顆石頭重量都是整數(shù)
// 每一回合 選出兩顆重量最大的石頭 x、y x<=y
// x==y 完全粉碎 x!=y y=y-x
// 最后最多會(huì)剩下一顆石頭 返回該石頭重量 如果沒有剩下 則返回0
private int lastIndex;
private int left;
public int lastStoneWeight(int[] stones) {
lastIndex = stones.length-1;
Arrays.sort(stones);
while (lastIndex>=1){
left = stones[lastIndex]-stones[lastIndex-1];
if (left==0){
lastIndex=lastIndex-2;
if (lastIndex==-1){
return 0;
}
}else {
stones[--lastIndex]=left;
Arrays.sort(stones);
}
}
return stones[lastIndex];
}
}
參考
非排序法 - 最后一塊石頭的重量 - 力扣（LeetCode）
以上就是Go語言LeetCode題解1046最后一塊石頭的重量的詳細(xì)內(nèi)容，更多關(guān)于Go題解最后一塊石頭重量的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
golang實(shí)戰(zhàn)之truncate日志文件詳解
這篇文章主要給大家介紹了關(guān)于golang實(shí)戰(zhàn)之truncate日志文件的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2018-07-07
bitset包是一個(gè)將非負(fù)整數(shù)映射到布爾值的位的集合，這篇文章主要通過開源包bitset來為大家分析一下位集合的設(shè)計(jì)和實(shí)現(xiàn)，感興趣的可以學(xué)習(xí)一下2023-08-08
Windows+Linux系統(tǒng)下Go語言環(huán)境安裝配置過程
Go 語言被設(shè)計(jì)成一門應(yīng)用于搭載 Web 服務(wù)器，存儲(chǔ)集群或類似用途的巨型中央服務(wù)器的系統(tǒng)編程語言。這篇文章主要介紹了Windows+Linux系統(tǒng)下Go語言環(huán)境搭建配置過程,針對(duì)每種系統(tǒng)給大家講解的非常詳細(xì)，需要的朋友可以參考下2021-06-06
解決vscode中g(shù)olang插件依賴安裝失敗問題
這篇文章主要介紹了解決vscode中g(shù)olang插件依賴安裝失敗問題,本文給大家介紹的非常詳細(xì)，具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2019-08-08
這篇文章主要介紹了Go 修改map slice array元素值操作，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2020-12-12
Go語言中make和new函數(shù)的用法與區(qū)別
這篇文章介紹了Go語言中make和new函數(shù)的用法與區(qū)別，文中通過示例代碼介紹的非常詳細(xì)。對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2022-07-07
淺談Golang中創(chuàng)建一個(gè)簡(jiǎn)單的服務(wù)器的方法
這篇文章主要介紹了淺談Golang中創(chuàng)建一個(gè)簡(jiǎn)單的服務(wù)器的方法，golang中的net/http包對(duì)網(wǎng)絡(luò)的支持非常好，這樣會(huì)讓我們比較容易的建立起一個(gè)相對(duì)簡(jiǎn)單的服務(wù)器，有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-06-06
Golang 使用map需要注意的幾個(gè)點(diǎn)
這篇文章主要介紹了Golang 使用map需要注意的幾個(gè)點(diǎn)，幫助大家更好的理解和學(xué)習(xí)golang，感興趣的朋友可以了解下2020-09-09
這篇文章主要介紹了golang頻率限制 rate詳解，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2020-12-12
詳解Go語言Sync.Pool為何不加鎖也能夠?qū)崿F(xiàn)線程安全
在這篇文章中，我們將剖析sync.Pool內(nèi)部實(shí)現(xiàn)中，介紹了sync.Pool比較巧妙的內(nèi)部設(shè)計(jì)思路以及其實(shí)現(xiàn)方式。在這個(gè)過程中，也間接介紹了為何不加鎖也能夠?qū)崿F(xiàn)線程安全，感興趣的可以學(xué)習(xí)一下2023-04-04