LeetCode 初級演算法之字串（上），看看你都學會了嗎？

語言: CN / TW / HK
時間 2022-12-21 03:15:13

theme: juejin highlight: xcode

本文正在參加「金石計劃 . 瓜分6萬現金大獎」

前言：最近自己也開始系統的刷面試題了，演算法是過不去的坎，希望自己能夠堅持下去✊，同行的朋友們共勉。

題一：反轉字串

編寫一個函式，其作用是將輸入的字串反轉過來。輸入字串以字元陣列 s 的形式給出。

不要給另外的陣列分配額外的空間，你必須原地修改輸入陣列、使用 O(1) 的額外空間解決這一問題。

示例 1： swift 輸入： s = ["h","e","l","l","o"] 輸出： ["o","l","l","e","h"] 示例 2： swift 輸入： s = ["H","a","n","n","a","h"] 輸出： ["h","a","n","n","a","H"]

解題思路

核心思想就是首尾替換；

這裡首選使用雙指標，i = 0， j = n-i-1，首尾指標交換值。交換完成之後，同時向中間移動；

程式碼

swift /// s[i] = s[n-i-1] func reverseString(_ s: inout [Character]) { for i in 0..<s.count/2 { s.swapAt(i, s.count-i-1) } }

題二：整數反轉

給你一個 32 位的有符號整數 x ，返回將 x 中的數字部分反轉後的結果。

如果反轉後整數超過 32 位的有符號整數的範圍 [−2^31^,  2^31^ − 1] ，就返回 0。

假設環境不允許儲存 64 位整數（有符號或無符號）。

解題思路 數學計算(取餘、取商)

  1. 擷取個位數
    • 提取個位數 （取餘的過程%）
    • 整數截掉個位數 （取商的過程/）
  2. 將個位數新增翻轉結果的尾部

推演：\ x:    123 —> 12 —> 1 —> 0\ digit: 0   —>  3  —> 2  —> 1\ res:  0    —>  3 —> 32 —> 321

程式碼

swift func reverse(_ x: Int) -> Int { var x = x var resource = 0 while x != 0 { // 取出個位數，並彈出 let digit = x%10 x/=10 // 把個位數推入到結果末尾 resource = resource * 10 + digit // swift中有32位數字的最大、最小可以判斷是否溢位 if resource > Int32.max || resource < Int32.min { return 0 } } return resource }

題三：字串中的第一個唯一字元

給定一個字串 s ，找到 它的第一個不重複的字元，並返回它的索引 。如果不存在，則返回 -1 。

示例 1： swift 輸入: s = "leetcode" 輸出: 0 示例 2： swift 輸入: s = "loveleetcode" 輸出: 2

解題思路： 雜湊表

判斷只出現一次的字元，通過雜湊表快取，應該算是比較容易解題的。\ 這裡首先想到的是使用雜湊表快取字元的index{char:index}。\ 另外還有一種方式是：快取字元出現次數{char:count}。 這兩種方式上還是有一定的區別。這個在後面具體的實現中，我們可以看到。 除此之外，參考雜湊表的實現，可以使用陣列達到一樣的效果。預設一個長度為26的陣列，快取a-z字母分別出現的次數。

解法一：雜湊表 （儲存下標）

兩次迴圈：第一次迴圈儲存雜湊表，第二次迴圈尋找最小下標\ 如果字典中不存在，則通過key=char，value=index來 儲存；\ 如果存在，index改為不合法引數 -1

程式碼

```swift func firstUniqChar(_ s: String) -> Int { var dict = Character: Int for i in 0..<s.count { let charIndex = s.index(s.startIndex, offsetBy: i) let char = s[charIndex] if dict[char] != nil { dict[char] = -1 } else { dict[char] = i } }

var index = s.count;
for (_,value) in dict {
    if value != -1 && value < index {
        index = value
    }
}
if index == s.count { return -1 }
return index

} ```

解法二：雜湊表 （儲存頻次）

上面的解法中，我們看到還需要再排序，不存在提前跳出的可能性，而雜湊表儲存次數，在後面的迴圈中，我們只需要判斷次數dict[char] == 1即可返回。

程式碼

swift func firstUniqChar(_ s: String) -> Int { var dict = [Character: Int]() for char in s { if dict[char] != nil { dict[char]! += 1 } else { dict[char] = 1 } } var index = 0 for char in s { if dict[char] == 1 { return index } index+=1 } return -1 }

題四：有效的字母異位詞

給定兩個字串 s 和 t ，編寫一個函式來判斷 t 是否是 s 的字母異位詞。

注意：若 s 和 t 中每個字元出現的次數都相同，則稱 s 和 t 互為字母異位詞。

示例 1： swift 輸入: s = "anagram", t = "nagaram" 輸出: true 示例 2： swift 輸入: s = "rat", t = "car" 輸出: false

解題思路 雜湊表、排序法

第一種思路：使用雜湊表，解決的形式取決於傾向空間複雜度和時間複雜度哪一種。

第二種思路：使用排序法，有效的字母異位詞排序後，兩個字串是相同的。

解法一：雜湊表，轉成字典集合，判斷相等

把兩個字串都轉成字典，存放每個字元出現的數量。然後再判斷兩個字典是否相等。

時間複雜度：O(n)\ 空間複雜度：O(2n)

程式碼

swift func isAnagram(_ s: String, _ t: String) -> Bool { guard s.count == t.count else { return false } var res = true var sDict = [Character: Int]() var tDict = [Character: Int]() var i = 0 while i < s.count { let sChar = s[s.index(s.startIndex, offsetBy: i)] if sDict[sChar] != nil { sDict[sChar]! += 1 } else { sDict[sChar] = 1 } let tChar = t[t.index(t.startIndex, offsetBy: i)] if tDict[tChar] != nil { tDict[tChar]! += 1 } else { tDict[tChar] = 1 } i+=1 } if sDict != tDict { res = false } return res }

解法二：雜湊表

將其中一個字串轉成雜湊表，雜湊表存放字元的頻次，index: char - "a",  value: count\ 使用另一個字串判斷是否其中的字元在快取中，如果沒有出現，即count == 0，跳出迴圈，如果出現，count-1。

時間複雜度：O(2n)\ 空間複雜度：O(n)

程式碼

swift func isAnagram(_ s: String, _ t: String) -> Bool { var charList = Array<Int>.init(repeating: 0, count: 26) for char in s { let index = (char.asciiValue ?? 0) - (Character("a").asciiValue ?? 0) charList[Int(index)] += 1 } for char in t { let index = (char.asciiValue ?? 0) - (Character("a").asciiValue ?? 0) if charList[Int(index)] == 0 { return false } charList[Int(index)] -= 1 } return true }

解法三：排序法

通過對兩字串進行排序，然後我們再比較兩字串是否相等就可以了。

下篇請看👉《LeetCode 初級演算法之字串>（下），看看你都學會了嗎？》

「」
「」