分享幾道適合用來面試的 LeetCode 演算法題

2019 年 10 月 8 日
筆記

閱讀本文大概需要 3 分鐘。

Hi，大家好，這幾天公司忙著年會，整個大部門去西安出差了幾天，今天剛剛回來，所以我這幾天沒有怎麼搭理公號。

年會那會也忙不少事情，由於今年是我剛剛入職，所以還要表演節目，排練了一個舞蹈《紅昭願》上台表演，為此也花了不少心思，另外其他時間就是參加年度總結大會，整個時間安排還是比較緊的。

不過這期間抽空也做了點東西，最近幾天我一個在忙著搭建 NightTeam 的官網和部落格，另外又整理了一下爬蟲第二版的書稿，出於安全考慮再刪減和修改一些敏感內容。本想今天把前者寫一篇記錄發出來的，但感覺今天時間不太夠了，明天再發吧。

另外想到前一陣子還和好朋友合作了一個公號，叫做「CodeWeekly」，目標就是在於分享一些 LeetCode 或周賽題解，提供一些題目的解析。這位朋友是一位 ACM 大神，獲得過多個 ACM 國際比賽的獎牌了，這個號也主要由他來打理，品質還是很有保證的。正好上周 LeetCode 周賽的題目品質還是比較高的，上周日他在號裡面分享了一下題解，我看完之後確實收穫也挺大的，感覺確實可以好好研讀一下，甚至把這幾道題目作為面試題來對待了。

所以這篇文章就轉來分享一下上周 LeetCode 周賽的幾道比較不錯的演算法題，並附上詳細的解析，大家有興趣可以看看。

題目在 LeetCode 官方網站上面，周賽鏈接是：https://leetcode.com/contest/weekly-contest-155，大家可以先去了解一下，然後再回來看看解析會更好。

下面就是題解了，希望對大家有幫助。

比賽總結：本期周賽題目品質較高，更多側重於對思維和常見演算法的理解和考察，總體考察的知識點很多，但是程式碼量除了最後一題以外並不大，適合用作面試題目。

Easy 5197. 最小絕對差

題目

給你個整數數組 arr，其中每個元素都不相同。

請你找到所有具有最小絕對差的元素對，並且按升序的順序返回。

示例 1：輸入：arr = [4,2,1,3] 輸出：[[1,2],[2,3],[3,4]]

示例 2：輸入：arr = [1,3,6,10,15] 輸出：[[1,3]]

示例 3：輸入：arr = [3,8,-10,23,19,-4,-14,27] 輸出：[[-14,-10],[19,23],[23,27]]

題目解析

O(n^2log(n))解法

拿到題目(特別是面試的時候)，我們首先需要保證自己能給出來一個可行解。那麼對於這道題目，我們可以按照下列思路來得到一個結果：

枚舉所有的二元組<i,j>，計算arr[i]和arr[j]的差，記錄其中的最小值。
枚舉所有的二元組<i,j>，計算arr[i]和arr[j]的差，將差值等於最小值的二元組記錄。
將所有二元組按升序排序。

前兩步需要遍歷所有的二元組，所以計算複雜度為: O(n^2),而第三步我們還需要對二元組排序，所以時間複雜度為O(n^2log(n))。

O(nlog(n))解法

那麼，至少我們現在有一個O(n^2log(n))的演算法了，我們來思考一下有沒有什麼優化空間。題目要求最小的絕對差，那麼如果要差最小的話，兩個做差的數一定會是序列排序後相鄰的兩個數。

基於這個結論，我們可以將整個數組排序，然後計算所有相鄰的數的差，再仿照上面的思路求得所有的元素對，現在的思路是：

排序數組，枚舉所有相鄰的二元組<i,i+1>，計算arr[i]和arr[i+1]的差，記錄其中的最小值。
枚舉所有的二元組<i,i+1>，計算arr[i]和arr[i+1]的差，將差值等於最小值的二元組記錄。
將所有二元組按升序排序。

由於我們現在只計算相鄰元素的差，所以枚舉的時間複雜度從O(n^2)降為了O(n)，總體時間複雜度為O(nlog(n))。下面為實現程式碼。

class Solution(object):      def minimumAbsDifference(self, arr):          """          :type arr: List[int]          :rtype: List[List[int]]          """          arr = sorted(arr)          mindiff = min([arr[i]-arr[i-1] for i in range(1,len(arr))])          arr = [[arr[i-1],arr[i]] for i in range(1,len(arr)) if mindiff == arr[i]-arr[i-1]]          return arr

Medium 5198. 丑數 III

題目

請你幫忙設計一個程式，用來找出第 n 個丑數。

丑數是可以被 a 或 b 或 c 整除的正整數。

示例 1：輸入：n = 3, a = 2, b = 3, c = 5 輸出：4 解釋：丑數序列為 2, 3, 4, 5, 6, 8, 9, 10… 其中第 3 個是 4。

示例 2：輸入：n = 4, a = 2, b = 3, c = 4 輸出：6 解釋：丑數序列為 2, 3, 4, 6, 8, 9, 12… 其中第 4 個是 6。

題目解析

題目本身來說並不算太難，但是有不少同學被丑數本身的定義繞進去了。這也是演算法題目題面中很容易發生的事情，那就是題目所給的定義不一定就是其原有定義。例如我們回到這道題，丑數的定義為能被所給abc任一整除的正整數，顯然是和之前丑數相關題目是不一樣的。在這種時候，我們需要跳開之前的固有思維，來重新考慮在所給條件下，如何求當前的"丑數"。

暴力解法

我們同樣有一個可以暴力解決問題的辦法，那就是我們從1開始枚舉，然後看看這個數能不能被abc其中某個數整除來判斷其是不是丑數，最後到第n個丑數就是我們的答案了。這樣做的話時間複雜度為O(n),由於n給的10^9，超過了我們說的10^8的限制，所以顯然會超時(當然這和面試能拿到一些分數並不衝突，所以並不是完全沒有意義)。

O(log(n))解法

原始問題有a,b,c三個因子，我們可以先試圖簡化問題來尋找靈感。

假設我們現在只有一個a: 例如a等於2，那麼丑數序列就是2,4,6,8…，那麼這時如果給了一個數n，那麼我們知道[1,n]中一共有Floor(n/2)個丑數，其中Floor是向下取整。如果n也是丑數，那麼n一定是第Floor(n/2)個丑數。
假設我們現在有a和b: 例如a等於2，b等於3，那麼丑數序列是2,3,4,6,8,9…，這時再給一個整數n，[1,n]中又有多少丑數呢？對於區間[1,n]，他能被2整除的數有Floor(n/2)個，這些數肯定是丑數沒錯了，他能被3整除的數有Floor(n/3)個，這些數也是丑數。但是我們別忘了，還有一些數是能同時被2和3整除的，也就是能被6整除，這些數我們計算了兩次。那麼減掉這些重複的數以後，剩餘的丑數還剩下Floor(n/2)+Floor(n/3)-Floor(n/6)個。那麼我們知道，在[1,n]區間內有這麼多醜數。

我們現在可以回到原問題的三個數了，這就是一個典型的容斥原理了，如下圖，對於3個數的情況，對應的丑數數量為Floor(n/a)+Floor(n/b)+Floor(n/c)-Floor(n/lcm(a,b))-Floor(n/lcm(b,c))-Floor(n/lcm(a,c))+Floor(n/lcm(a,b,c))，其中lcm是最小公倍數。通過這個公式，我們可以方便的求出[1,n]中的丑數數量。

但是這離我們解決問題還有一段距離，我們現在想知道的是第n個丑數是什麼，而不是[1,n]中有多少丑數。我們來思考一下對於第n個丑數Un來說，他會滿足什麼性質：

顯然[1,Un]中有n個丑數。
[1,Un-1]中有n-1個丑數。

那麼由於隨著數的變大，丑數的數量肯定是單調遞增的，那麼我們可以利用二分查找來逐步逼近某個臨界點，滿足[1,Un]有n個丑數且[1,Un-1]中有n-1個丑數。這樣時間複雜度僅為二分查找的時間複雜度O(log(n))。還有一點是關於最大公約數的實現，程式碼里是直接調的系統庫，但是我們也需要知道最大公約數是有O(log(n))級別的實現方法的，文末也會給出相關資料【1】。以下是實現程式碼。

from fractions import gcd  class Solution(object):      def nthUglyNumber(self, n, a, b, c):          """          :type n: int          :type a: int          :type b: int          :type c: int          :rtype: int          """          //最小公倍數          def lcm(a,b):              return a*b/gcd(a,b)          //計算[1,mid]有多少丑數          //這種實現時間複雜度會高一個log(n)數量級，最小公倍數可以預處理。          def get_idx(mid):              return mid // a + mid // b + mid // c - mid //lcm(a,b) - mid//lcm(b,c) - mid //lcm(c,a) + mid//lcm(lcm(a,b),c)          l = 1; r = 2*10**9+1          while ( l < r ):              mid = (l+r+1)/2              idx = get_idx(mid)              if idx == n:                  l = mid                  break              elif idx < n:                  l = mid              elif idx > n:                  r = mid-1          //這裡的實現略微有些不一樣，可以思考一下現在的做法          return l-min(l%a,min(l%b,l%c))

Medium 5199. 交換字元串中的元素

題目

給你一個字元串s，以及該字元串中的一些「索引對」數組 pairs，其中pairs[i] = [a, b]表示字元串中的兩個索引（編號從0開始）。

你可以任意多次交換在pairs中任意一對索引處的字元。

返回在經過若干次交換後，s 可以變成的按字典序最小的字元串。

示例 1: 輸入：s = "dcab", pairs = [[0,3],[1,2]] 輸出："bacd" 解釋：交換 s[0] 和 s[3], s = "bcad" 交換 s[1] 和 s[2], s = "bacd"

示例 2：輸入：s = "dcab", pairs = [[0,3],[1,2],[0,2]] 輸出："abcd" 解釋：交換 s[0] 和 s[3], s = "bcad" 交換 s[0] 和 s[2], s = "acbd" 交換 s[1] 和 s[2], s = "abcd"

題目解析

這道題理論上我們也是可以暴力的：搜索所有的交換然後同時保留我們的中間狀態，記錄全部狀態的字典序最小值，但是這樣的話是一個指數級別複雜度的演算法了。

考慮一個字元串s，如果他的位置a和b能交換，且b和c能交換，那麼由於我們的交換沒有限制，我們可以把abc三個位置排成任意我們想要的排列。

這裡我們可以簡單證明一下，對於a和b能交換的情況，我們可以得到[a,b]和[b,a]兩種排列，即2個數的時候我們可以得到任意排列。

那麼三個數的時候，例如[a,b,c]，由於2個數的時候我們可以得到任意排列，那麼我們最後把c不停地向前交換，可以把c放在任意位置，也即是3個數我們也可以得到任意排列。我們還可以繼續推廣一下，如果有[a,b],[b,c][c,d],[d,e]...，對於[a,b,c,d,e...]位置的字母，我們可以得到其任意排列。

這個結論就很有作用了，令place={a,b,c,d,e...}，由於我們需要原始字元串最小，那麼對於place位置的字母，肯定是將其重排為字典序最小字元串，如下圖，假設紅色部分為一個place集合。

那麼原問題就可以分為兩步：

得到每個點所屬的place集合
將所有place集合中的字元重排為字典序最小排列。

先來解決第一個問題，我們要知道哪些點屬於同一個place集合，那麼對於所有給的邊[a,b]，我們知道[a,b]是屬於一個集合的，如果集合還有邊連向外面例如[a,c]，我們知道c也屬於這個集合。這種問題特性我們可以使用並查集來進行維護，最後得到每個點所屬的集合id。對於不了解並查集的同學，這裡也整理了一些資料【2】。而第二個問題就很簡單了，我們直接將對應位置的字元進行排序即可。

並查集時間複雜度為O(n)，排序時間複雜度為O(log(n))，所以總體時間複雜度為O(nlog(n))，當然，由於這裡是字元串排序，我們可以使用桶排序來將時間複雜度優化為O(n)。

下面是實現程式碼

import numpy as np  class Solution(object):      def smallestStringWithSwaps(self, s, pairs):          """          :type s: str          :type pairs: List[List[int]]          :rtype: str          """          #並查集的find函數          def ffind(a):              if a == fa[a]:                  return a              f = ffind(fa[a])              fa[a] = f              return f          #並查集的union函數          def union(a,b):              a = ffind(a)              b = ffind(b)              fa[a] = b          #並查集維護集合          n = len(s)          fa = np.arange(n)          for a,b in pairs:              union(a,b)          for i in range(n):              ffind(i)          #得到所有place集合          unique_fa = np.unique(fa)            #得到所有place集合中對應的字元串並排序          fa_str = {x:'' for x in unique_fa}          for i in range(n):              fa_str[fa[i]] += s[i]          for x in unique_fa:              fa_str[x] = sorted(fa_str[x])          fa_cnt = {x:0 for x in unique_fa}          #將排序完的字元串反映射回原串得到最後結果          ans = ''          for i in range(n):              x = fa[i]              ans += fa_str[x][fa_cnt[x]]              fa_cnt[x] += 1          return ans

Hard 5200. 項目管理

提示：該題實際難度略小於hard，可以嘗試

題目

公司共有 n 個項目和 m 個小組，每個項目要不沒有歸屬，要不就由其中的一個小組負責。

我們用 group[i] 代表第 i 個項目所屬的小組，如果這個項目目前無人接手，那麼 group[i] 就等於 -1。（項目和小組都是從零開始編號的）

請你幫忙按要求安排這些項目的進度，並返回排序後的項目列表：

同一小組的項目，排序後在列表中彼此相鄰。項目之間存在一定的依賴關係，我們用一個列表 beforeItems 來表示，其中 beforeItems[i] 表示在進行第 i 個項目前（位於第 i 個項目左側）應該完成的所有項目。結果要求：

如果存在多個解決方案，只需要返回其中任意一個即可。

如果沒有合適的解決方案，就請返回一個空列表。

示例 1：輸入：n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3,6],[],[],[]] 輸出：[6,3,4,1,5,2,0,7]

示例 2：輸入：n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3],[],[4],[]] 輸出：[] 解釋：與示例 1 大致相同，但是在排序後的列表中，4 必須放在 6 的前面。

題目解析

這道題是一道拓撲排序的變種，本身雖然比較複雜但是理清楚了並不是特別難，之所以被排到hard可能是因為題目實在是太難懂了~ ~。在讀了十多遍題目以後大概理解了這道題要我們做什麼：

有很多任務，任務分成了若干個組，一個組的任務必須要連續做完，不能先做組a的任務，然後去做組b的，然後又跑來做組a的。
任務之間有一些依賴關係，對於每個任務給了其依賴任務，需要所有依賴任務完成後才能開始該任務，例如1:[2,6]，那麼任務1需要在任務2和任務6都完成以後才能開始。
最後，我們還是要一個合法的任務序列，保證依賴關係不衝突，且組內的任務是連著做的。

那麼根據這些條件，一個可能的依賴情況是這樣的：

我們看到，依賴關係實際上分為兩種，一種是組內依賴關係(紅色箭頭)，一種是組間依賴關係(綠色箭頭)。由於一個組的任務需要連著做，我們先不考慮組內依賴關係，那麼從組的角度來看：

這就是一個典型的拓撲排序問題了！我們可以很容易的求出可行的調度序列，當然這個序列是組級別的，也即是我們先執行哪個組的任務，再執行哪個組的任務的序列。

那麼組的執行順序知道了，接下來我們只需要看每個組內的任務該如何執行就可以了。如下圖，對於一個組內的任務，我們發現他還是一個樸素的拓撲排序問題：

那麼接下里的思路也有了，我們對於每個組內的任務再分別建圖求拓撲序，最後根據組級別的拓撲序將結果整合起來就可以了。當然，如果任一個拓撲排序發現無可行解，那麼整個系統就無可行解。

總體時間複雜度為O(N)，以下為實現程式碼：

import Queue  import numpy as np  class Solution(object):      def sortItems(self, n, m, group, beforeItems):          """          :type n: int          :type m: int          :type group: List[int]          :type beforeItems: List[List[int]]          :rtype: List[int]          """          #組內拓撲排序          def get_group_ans(group_points,group_edges):              #組內級別建圖              graph = {group_point:[] for group_point in group_points}              degree = {group_point:0 for group_point in group_points}              for x,y in group_edges:                  graph[y].append(x)                  degree[x] += 1              #top sort              q = Queue.Queue()              for graph_point in group_points:                  if degree[graph_point] == 0:                      q.put(graph_point)                #組內拓撲排序              task_res = []              while not q.empty():                  x = q.get()                  task_res.append(x)                  for y in graph[x]:                      degree[y] -= 1                      if degree[y] == 0:                          q.put(y)              if len(task_res) != len(group_points):                  return None              return task_res          group_cnt = max(group)+1          for i in range(n):              if group[i] == -1:                  group[i] = group_cnt                  group_cnt += 1          #組級別建圖          group_ids = np.unique(group)          graph = {group_id:[] for group_id in group_ids}          degree = {group_id:0 for group_id in group_ids}          group_inner_edges = {group_id:[] for group_id in group_ids}          group_points = {group_id:[] for group_id in group_ids}          for i in range(n):              groupa = group[i]              group_points[groupa].append(i)              for j in beforeItems[i]:                  groupb = group[j]                  if groupa == groupb:                      group_inner_edges[groupa].append([i,j])                      continue                  graph[groupb].append(groupa)                  degree[groupa] += 1            #組級別拓撲排序          q = Queue.Queue()          for group_id in group_ids:              if degree[group_id] == 0:                  q.put(group_id)          group_res = []          while not q.empty():              x = q.get()              group_res.append(x)              for y in graph[x]:                  degree[y] -= 1                  if degree[y] == 0:                      q.put(y)            if len(group_res) != len(group_ids):              return []          #根據組拓撲序整合結果          task_res = []          for group_id in group_res:              ans = get_group_ans(group_points[group_id],group_inner_edges[group_id])              if ans is None:                  return []              task_res += ans          return task_res

參考資料：

[1] 輾轉相除法求最大公約數 https://blog.csdn.net/qq_41575507/article/details/90752742 [2] 並查集 https://baike.baidu.com/item/%E5%B9%B6%E6%9F%A5%E9%9B%86/9388442?fr=aladdin https://blog.csdn.net/niushuai666/article/details/6662911

最後大家如果想了解更多優質 LeetCode 題解和周賽解析的話，可以關注一下「CodeWeekly」這個公號，希望對大家有幫助，謝謝。

崔慶才

靜覓部落格部落客，《Python3網路爬蟲開發實戰》作者