【算法題】力扣第 302 次周賽 - 簡潔的 Scala 鏈?zhǔn)讲僮?/h1>
最近因?yàn)樵趯W(xué) Scala，所以又重新開始在力扣上打打周賽，一邊練習(xí)練習(xí)。今天的周賽題目感覺還挺簡單的，用 Scala 基本可以用 filter-map-reduce 的鏈?zhǔn)讲僮?API 在幾行內(nèi)搞定，所以分享一下。（以下所有題目原題版權(quán)歸力扣所有，貼出來只是方便讀者閱讀。題目來源：https://leetcode.cn/contest/weekly-contest-302）
6120. 數(shù)組能形成多少數(shù)對
首先是第一題簡單難度的 6120. 數(shù)組能形成多少數(shù)對。
題目如下：
給你一個(gè)下標(biāo)從 0 開始的整數(shù)數(shù)組
nums。在一步操作中，你可以執(zhí)行以下步驟：
從
nums選出 兩個(gè) 相等的 整數(shù)從
nums中移除這兩個(gè)整數(shù)，形成一個(gè) 數(shù)對請你在
nums上多次執(zhí)行此操作直到無法繼續(xù)執(zhí)行。返回一個(gè)下標(biāo)從 0 開始、長度為
2的整數(shù)數(shù)組answer作為答案，其中answer[0]是形成的數(shù)對數(shù)目，answer[1]是對nums盡可能執(zhí)行上述操作后剩下的整數(shù)數(shù)目。示例 1：
輸入：nums?=?[1,3,2,1,3,2,2]
輸出：[3,1]
解釋：
nums[0]?和?nums[3]?形成一個(gè)數(shù)對，并從?nums?中移除，nums?=?[3,2,3,2,2]?。
nums[0]?和?nums[2]?形成一個(gè)數(shù)對，并從?nums?中移除，nums?=?[2,2,2]?。
nums[0]?和?nums[1]?形成一個(gè)數(shù)對，并從?nums?中移除，nums?=?[2]?。
無法形成更多數(shù)對。總共形成?3?個(gè)數(shù)對，nums?中剩下?1?個(gè)數(shù)字。示例 2：
輸入：nums?=?[1,1]
輸出：[1,0]
解釋：nums[0]?和?nums[1]?形成一個(gè)數(shù)對，并從?nums?中移除，nums?=?[]?。
無法形成更多數(shù)對。總共形成?1?個(gè)數(shù)對，nums?中剩下?0?個(gè)數(shù)字。示例 3：
輸入：nums?=?[0]
輸出：[0,1]
解釋：無法形成數(shù)對，nums?中剩下?1?個(gè)數(shù)字。提示：
1 <= nums.length <= 100
0 <= nums[i] <= 100
解題思路
遍歷數(shù)組，把同一大小的數(shù)字?jǐn)?shù)出有多少個(gè)，然后將這些個(gè)數(shù)除以2的商和余數(shù)求和即可
通過代碼
不考慮為了閱讀方便而添加的換行符的話，等效于一行搞定……
6164. 數(shù)位和相等數(shù)對的最大和
第二題是中等難度的 6164. 數(shù)位和相等數(shù)對的最大和
題目
給你一個(gè)下標(biāo)從 0 開始的數(shù)組
nums，數(shù)組中的元素都是 正 整數(shù)。請你選出兩個(gè)下標(biāo)i和j（i != j），且nums[i]的數(shù)位和 與nums[j]的數(shù)位和相等。請你找出所有滿足條件的下標(biāo)
i和j，找出并返回nums[i] + nums[j]可以得到的 最大值 。示例 1：
輸入：nums?=?[18,43,36,13,7]
輸出：54
解釋：滿足條件的數(shù)對?(i,?j)?為：
-?(0,?2)?，兩個(gè)數(shù)字的數(shù)位和都是?9?，相加得到?18?+?36?=?54?。
-?(1,?4)?，兩個(gè)數(shù)字的數(shù)位和都是?7?，相加得到?43?+?7?=?50?。
所以可以獲得的最大和是?54?。示例 2：
輸入：nums?=?[10,12,19,14]
輸出：-1
解釋：不存在滿足條件的數(shù)對，返回?-1?。
提示：
1 <= nums.length <= 105
1 <= nums[i] <= 109
解題思路
先求出每個(gè)數(shù)組元素的數(shù)位和
再將數(shù)位和相等的元素組成相應(yīng)的集合（這里如果集合大小均小于 2，即找不到相等數(shù)對的話，直接返回 -1）
在各個(gè)集合內(nèi)中找到最大的兩個(gè)數(shù)求和，即得到每個(gè)集合的最大和
各個(gè)集合的最大和再一起找到最大值就是題目要找到的解了
通過代碼
sumDigit 的實(shí)現(xiàn)不想使用 toString 的話（效率較低）可以換成 while 循環(huán)的實(shí)現(xiàn)：
6121. 裁剪數(shù)字后查詢第 K 小的數(shù)字
第三題是中等難度的 6121. 裁剪數(shù)字后查詢第 K 小的數(shù)字
題目
給你一個(gè)下標(biāo)從 0 開始的字符串?dāng)?shù)組
nums，其中每個(gè)字符串 長度相等 且只包含數(shù)字。再給你一個(gè)下標(biāo)從 0 開始的二維整數(shù)數(shù)組
queries，其中queries[i] = [ki, trimi]。對于每個(gè)queries[i]，你需要：
將
nums中每個(gè)數(shù)字 裁剪 到剩下 最右邊trimi個(gè)數(shù)位。在裁剪過后的數(shù)字中，找到
nums中第ki小數(shù)字對應(yīng)的 下標(biāo) 。如果兩個(gè)裁剪后數(shù)字一樣大，那么下標(biāo) 更小 的數(shù)字視為更小的數(shù)字。將
nums中每個(gè)數(shù)字恢復(fù)到原本字符串。請你返回一個(gè)長度與
queries相等的數(shù)組answer，其中answer[i]是第i次查詢的結(jié)果。提示：
裁剪到剩下
x個(gè)數(shù)位的意思是不斷刪除最左邊的數(shù)位，直到剩下x個(gè)數(shù)位。
nums中的字符串可能會有前導(dǎo) 0 。示例 1：
輸入：nums?=?["102","473","251","814"],?queries?=?[[1,1],[2,3],[4,2],[1,2]]
輸出：[2,2,1,0]
解釋：
1.?裁剪到只剩?1?個(gè)數(shù)位后，nums?=?["2","3","1","4"]?。最小的數(shù)字是?1?，下標(biāo)為?2?。
2.?裁剪到剩?3?個(gè)數(shù)位后，nums?沒有變化。第?2?小的數(shù)字是?251?，下標(biāo)為?2?。
3.?裁剪到剩?2?個(gè)數(shù)位后，nums?=?["02","73","51","14"]?。第?4?小的數(shù)字是?73?，下標(biāo)為?1?。
4.?裁剪到剩?2?個(gè)數(shù)位后，最小數(shù)字是?2?，下標(biāo)為?0?。
???注意，裁剪后數(shù)字?"02"?值為?2?。示例 2：
輸入：nums?=?["24","37","96","04"],?queries?=?[[2,1],[2,2]]
輸出：[3,0]
解釋：
1.?裁剪到剩?1?個(gè)數(shù)位，nums?=?["4","7","6","4"]?。第?2?小的數(shù)字是?4?，下標(biāo)為?3?。
???有兩個(gè)?4?，下標(biāo)為?0?的?4?視為小于下標(biāo)為?3?的?4?。
2.?裁剪到剩?2?個(gè)數(shù)位，nums?不變。第二小的數(shù)字是?24?，下標(biāo)為?0?。
提示：
1 <= nums.length <= 100
1 <= nums[i].length <= 100
nums[i]只包含數(shù)字。所有
nums[i].length的長度 相同 。
1 <= queries.length <= 100
queries[i].length == 2
1 <= ki <= nums.length
1 <= trimi <= nums[0].length
解題思路
周賽的時(shí)候，看題目一開始沒看懂，看了老半天…… 其實(shí)題目不難。
其實(shí)題目意思就是對于每一個(gè) queries 數(shù)組里面的元素（我們后續(xù)稱元素為 arr, 對應(yīng)結(jié)構(gòu)為 Array(arr(0), arr(1))） 對應(yīng)一次查詢，需要對 nums 數(shù)組執(zhí)行操作，然后把操作的結(jié)果按照 queries 的順序返回。
而上面所說的操作，其實(shí)就是對于 nums 數(shù)組的每一個(gè)元素，取它的后 arr(1) 位，然后找到第 arr(0) ?。ㄗ⒁膺@里是從 1 開始的，因?yàn)檫@個(gè)我錯(cuò)誤提交了一次）的數(shù)的索引，返回即可
通過代碼
還是相當(dāng)于一行秒了……
6122. 使數(shù)組可以被整除的最少刪除次數(shù)
最后一題是困難難度的 6122. 使數(shù)組可以被整除的最少刪除次數(shù)
題目
給你兩個(gè)正整數(shù)數(shù)組
nums和numsDivide。你可以從nums中刪除任意數(shù)目的元素。請你返回使
nums中 最小 元素可以整除numsDivide中所有元素的 最少 刪除次數(shù)。如果無法得到這樣的元素，返回-1。如果
y % x == 0，那么我們說整數(shù)x整除y。示例 1：
輸入：nums?=?[2,3,2,4,3],?numsDivide?=?[9,6,9,3,15]
輸出：2
解釋：
[2,3,2,4,3]?中最小元素是?2?，它無法整除?numsDivide?中所有元素。
我們從?nums?中刪除?2?個(gè)大小為?2?的元素，得到?nums?=?[3,4,3]?。
[3,4,3]?中最小元素為?3?，它可以整除?numsDivide?中所有元素。
可以證明?2?是最少刪除次數(shù)。示例 2：
輸入：nums?=?[4,3,6],?numsDivide?=?[8,2,6,10]
輸出：-1
解釋：
我們想?nums?中的最小元素可以整除?numsDivide?中的所有元素。
沒有任何辦法可以達(dá)到這一目的。提示：
1 <= nums.length, numsDivide.length <= 105
1 <= nums[i], numsDivide[i] <= 109
解題思路
求出
numsDivide所有元素的最大公約數(shù)（greatest common divisor，簡寫為 gcd）。這是可以整除numsDivide所有元素的最大值。將
nums中小于等于最大公約數(shù)的數(shù)字排序，從小到大尋找可以整除最大公約數(shù)的數(shù)字（如果可以整除最大公約數(shù)，即可整除所有numsDivide的元素）如果找到，返回相應(yīng)的未過濾未排序的原數(shù)組索引，否則返回 -1
通過代碼
代碼中 gcd(arr: Array[Int]) 方法按 while 循環(huán)迭代可以寫成：
可以看出，遞歸的寫法簡潔很多。
總結(jié)
可以看出，使用 filter-map-reduce 的鏈?zhǔn)讲僮鞯姆绞骄帉懘a，可以大大減輕我們的書寫量，讓我們的編程重點(diǎn)放在算法本身而不是編寫繁復(fù)的 for、while 循環(huán)的具體邏輯上。對于主要邏輯都是集中于遍歷操作內(nèi)，不涉及一些高級數(shù)據(jù)結(jié)構(gòu)或算法的題目，這種處理方式往往可以在幾行之內(nèi)把問題解決。
順便貼一道這周刷題做的一道簡單題 劍指 Offer 06. 從尾到頭打印鏈表 的代碼，也可以展示出 Scala 鏈?zhǔn)讲僮鹘Y(jié)合 Stream 的方便簡潔
這里也順便吐槽一下，有些人習(xí)慣于寫 Java、Scala 的時(shí)候用 for、while 循環(huán)，這本無可厚非。但是動(dòng)不動(dòng)就是鏈?zhǔn)讲僮?API 可讀性差，不得不說那就是不學(xué)無術(shù)還自欺欺人了。硬要說缺點(diǎn)，那 Stream 確實(shí)也有它的缺點(diǎn) —— 運(yùn)行時(shí)間相對較慢（但其實(shí)并沒有像有些人說的那樣慢特別多，網(wǎng)上很多自己測試的微基準(zhǔn)測試代碼不寫預(yù)熱測試的我也是醉了），以及無法運(yùn)行調(diào)試（好像最近看到有文章說最近的 IDEA 版本已經(jīng)有相應(yīng)功能了，不過我還沒有試過）。但這些就是屬于你了解它的優(yōu)缺點(diǎn)后再來取舍使用范圍的考慮了。還沒有了解過就固步自封，我個(gè)人覺得這種態(tài)度是不可取的。
單就力扣刷題而言，鏈?zhǔn)讲僮骶驼宫F(xiàn)出了它優(yōu)秀的一面，耗時(shí)差不多，而書寫簡潔不少。這在周賽的限時(shí)環(huán)境下就更顯重要了。這次因?yàn)轭}目相對容易，所以也是我用 Scala 做力扣周賽以來第一次四道題全部完成（之前參加過三次）。如果之前沒學(xué)習(xí)過鏈?zhǔn)讲僮鞯淖x者，希望我這篇文章能讓你對 Scala 鏈?zhǔn)讲僮鞯木幊逃兴d趣。了解的話，希望能有所幫助。謝謝大家~
（對于 Java 的鏈?zhǔn)讲僮鞲信d趣的話，可以閱讀《Java 8 實(shí)戰(zhàn)》一書，了解相關(guān)的 Stream API）
