LeetCode 初級演算法之字串(上),看看你都學會了嗎?
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 位整數(有符號或無符號)。
解題思路 數學計算(取餘、取商)
- 擷取個位數
- 提取個位數 (取餘的過程
%
) - 整數截掉個位數 (取商的過程
/
)
- 提取個位數 (取餘的過程
- 將個位數新增翻轉結果的尾部
推演:\ 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 初級演算法之陣列(上),看看你都學會了嗎?
- LeetCode 初級演算法之連結串列,看看你都學會了嗎?
- LeetCode 初級演算法之字串(上),看看你都學會了嗎?
- 純程式碼佈局,也可以一樣的簡潔
- UIStackView之一問一答
- 使用UIStackView來簡化iOS的介面佈局
- 夏天來了,iOS開發者們該如何減少App耗電?(上)
- 夏天來了,App開發者們如何看待手機發燙問題?
- 聊聊iOS中UITableView複用的那些事
- 曾經經典的微信打飛機遊戲還有人記得嗎?
- iOS 原生渲染與 Flutter 有什麼區別 (上)
- 瞭解 Mach-O檔案
- CocoaPods中podsepc檔案設定詳解
- iOS 原生渲染與 Flutter 有什麼區別 (下)
- 簡單瞭解 iOS CVPixelBuffer (上)
- 談談 iOS 包瘦身方案
- 播放器重構的探索之路
- 如何使用CocoaPods製作私有庫
- iOS 元件化方案