LeetCode 初級演算法之字串(上),看看你都學會了嗎?

語言: CN / TW / HK

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 初級演算法之字串>(下),看看你都學會了嗎?》