import Foundation
/*
一般寫算法用c語言來實現(xiàn)，比較能理解整個細節(jié)，因為高級語言都封裝的簡易的操作，
像數(shù)組是動態(tài)的，queue需要維護front和rear指針，stack要維護top指針，
c語言是面向過程的，所以在實現(xiàn)字符串操作相對容易，但在沒有內置的map數(shù)據類型，
所以像實現(xiàn)LRU Cache用到雙向鏈表和hashmap來實現(xiàn)，代碼比較長
*/
//MARK: 53. 最大子數(shù)組和
//動態(tài)轉移方程，就是遞推公式，當前狀態(tài)由上次狀態(tài)轉移，有時可以優(yōu)化用滾動數(shù)組，即用一個變量來維護上一個結果
func maxSubArray(_ nums: [Int]) -> Int {
//f(n) = max{f(n)+n, n}
var pre = 0
var ans = nums[0]
for n in nums {
pre = max(pre + n, n)
ans = max(pre, ans)
}
return ans
}
//MARK: 206. 反轉鏈表
func reverseList(_ head: ListNode?) -> ListNode? {
//頭插法
var pre: ListNode? = nil
var cur = head
while cur != nil {
var next = cur?.next //取出next指針，因為要改變指針方向
cur?.next = pre //翻轉操作
pre = cur //移動cur和next指針
cur = next
}
return pre
}
//遞歸法
func reverseList(_ head: ListNode?) -> ListNode? {
//遞歸出口，當head.next為空，到鏈表最后一個。head == nil是判斷傳的是個nil
if head == nil || head?.next == nil {
return head
}
var newHead = reverseList(head?.next)
head?.next?.next = head //這個里做翻轉操作
head?.next = nil //這里防止出現(xiàn)循環(huán)鏈表，因為最后一個要為nil
return newHead
}
//MARK: 110. 平衡二叉樹
func isBalanced(_ root: TreeNode?) -> Bool {
if (root == nil) {
return true
} else {
//三個條件左右相差1，并且左子樹和右子樹都平衡
return abs(height(root?.left) - height(root?.right)) <= 1 && isBalanced(root?.left) && isBalanced(root?.right)
}
}
//輔助函數(shù)計算高度
func height(_ root: TreeNode?) -> Int {
if root == nil {
return 0
} else {
return max(height(root?.left), height(root?.right)) + 1 //因為高度從1開始計算
}
}
/*
1 2 3
4 5 6
7 8 9
按層模擬: 123, 69, 8, 47, 5
回字形一層一層遍歷
*/
func spiralOrder(_ matrix: [[Int]]) -> [Int] {
guard !matrix.isEmpty else { return [] }
var l = 0
var r = matrix[0].count - 1
var t = 0
var b = matrix.count - 1
var res = Int
while (l <= r && t <= b) {
for i in l...r {
res.append(matrix[t][i]) //把第一行加入到結果數(shù)組
}
//range注意上下界, 或者用stride(from:to:by:)不會有問題, 其他語言是用for來不會有這個問題
if t+1 > b { break }
for i in t+1...b { //上指針下移一個位置
res.append(matrix[i][r]) //把最后一列除了第一個，加入到結果數(shù)組
}
// 邊界縮減了1，所以判斷條件不能<=
if (l < r && t < b) { //因為邊界在++或者--, 右到左，下到上邊界減少1
for i in (l+1..<r).reversed() { //左右縮減1
res.append(matrix[b][i]) //列在變
}
for i in (t+1...b).reversed() {
res.append(matrix[i][l]) //行在變
}
}
//然后下一層
l += 1
r -= 1
t += 1
b -= 1
}
return res
}
/*
1 2 3
4 5 6
7 8 9
*/
//轉圈遍歷 先 123, 69, 87, 5
func spiralOrder(_ matrix: [[Int]]) -> [Int] {
guard !matrix.isEmpty else { return [] }
var l = 0
var r = matrix[0].count - 1
var t = 0
var b = matrix.count - 1
var n = matrix[0].count * matrix.count
var res = Int
while res.count < n {
//to的元素不包含，如果使用range注意上下界， 例如：l...r l > r 會崩潰
for i in stride(from: l, to: r+1, by: 1) where res.count < n {
res.append(matrix[t][i])
}
t += 1
for i in stride(from: t, to: b+1, by: 1) where res.count < n {
res.append(matrix[i][r])
}
r -= 1
for i in stride(from: r, to: l-1, by: -1) where res.count < n {
res.append(matrix[b][i])
}
b -= 1
for i in stride(from: b, to: t-1, by: -1) where res.count < n {
res.append(matrix[i][l])
}
l += 1
}
return res
}
//MARK: 146. LRU 緩存
//哈希表+雙向鏈表
// 靠近頭部最近使用，靠近尾部最久未使用
//通過hashtable實現(xiàn)O(1)插入和查詢
/*
cache: 1 : 1
2 : 2
head -> 2 -> 1 -> tail
<- <- <-
因為用c語言實現(xiàn)hashtable代碼量大，可以使用c語言優(yōu)秀庫uthash底層本身就是用雙向鏈表實現(xiàn)的hash來實現(xiàn)
*/
class DLinkedNode {
var key: Int
var value: Int
var pre: DLinkedNode?
var next: DLinkedNode?
init(_ key: Int, _ val: Int) {
self.key = key
self.value = val
}
}
class LRUCache {
var cache = Int: DLinkedNode
var count: Int = 0
var capacity: Int
let head = DLinkedNode(0, 0)
let tail = DLinkedNode(0, 0)
init(_ capacity: Int) {
self.capacity = capacity
head.next = tail
tail.pre = head
}
func remove(_ key: Int) {
guard count > 0, let node = cache[key] else {
return
}
cache[key] = nil
//雙向斷開連接
node.pre?.next = node.next
node.next?.pre = node.pre
node.pre = nil
node.next = nil
count -= 1
}
//頭插法
func insert(_ node: DLinkedNode) {
cache[node.key] = node
//在頭部插入
//head的下一個連接node
node.next = head.next
head.next?.pre = node
//node連接head
node.pre = head
head.next = node
count += 1
}
func get(_ key: Int) -> Int {
if let node = cache[key] {
// 刪除并插入，相當于移動到頭部
remove(key)
insert(node)
return node.value
}
return -1
}
func put(_ key: Int, _ value: Int) {
if let node = cache[key] {
//如果存在，更新值，并移動到頭部
node.value = value
remove(key)
insert(node)
return
}
let node = DLinkedNode(key, value)
cache[key] = node
//如果已經滿了，移除最后一個node
if count == capacity, let tailKey = tail.pre?.key {
remove(tailKey)
}
//插入到頭部
insert(node)
}
}
//MARK: 102. 二叉樹的層序遍歷
func levelOrder(_ root: TreeNode?) -> [[Int]] {
guard let root = root else {
return []
}
var res = [Int]
var queue: [TreeNode] = [root] //因為上面做了guard守護
while !queue.isEmpty {
var level = Int
for _ in queue { //只要遍歷當前隊列，不需要i，拓展當前層節(jié)點的下層
var node = queue.removeFirst() //出隊，用數(shù)組模擬
level.append(node.val)
if let left = node.left {
queue.append(left)
}
if let right = node.right {
queue.append(right)
}
}
res.append(level)
}
return res
}
class MyQueue {
var inStack = Int
var outStack = Int
// var front = -1 //也可以用一個屬性記錄隊列頭元素
init() {
}
func push(_ x: Int) {
// if inStack.isEmpty {
// front = x
// }
inStack.append(x)
}
func pop() -> Int {
if (outStack.isEmpty) {
while(!inStack.isEmpty) {
outStack.append(inStack.removeLast())
}
}
return outStack.popLast() ?? -1
}
func peek() -> Int {
// return outStack.last ?? inStack.last ?? -1
return outStack.last ?? inStack.first ?? -1 //不用變量就使用這種方式
}
func empty() -> Bool {
return inStack.isEmpty && outStack.isEmpty
}
}
//MARK: 69. Sqrt(x)
func mySqrt(_ x: Int) -> Int {
var l = 0
var r = x
var ans = -1
while l <= r {
let mid = l + (r - l) / 2
if mid * mid <= x {
ans = mid
l = mid + 1 //在右邊
} else {
r = mid - 1 //在左邊
}
}
return ans
}
//如果精確到多少位 swift有類型判斷
func mySqrt(_ x: Double, _ epsilon: Double) -> Double {
var l = 0
var r = x
if (x == 0 || x == 1) {
return x
}
while l < r {
let mid = l + (r - l) / 2
if (abs(mid * mid) - x < epsilon) {
return mid
} else if (mid * mid < x) {
l = mid
} else {
r = mid
}
}
return l
}
//牛頓迭代法 等價于 求 f(x) = x^2 - a 的正根， 因為f'(x) = 2x, 根據斜截式求出x軸交點為 x - f(x)/2x , f(x)代入得
//（x + a/x) / 2
func mySqrt(_ x: Int) -> Int {
var ans = x
while (ans * ans > x) {
ans = (ans + x / ans) / 2
}
return ans
}
//MARK: 排序數(shù)組，歸并排序
func sortArray(_ nums: [Int]) -> [Int] {
guard nums.count > 1 else {return nums}
let m = nums.count / 2
//左右遞歸
let l = sortArray(Array(nums[0..<m]))
let r = sortArray(Array(nums[m..<nums.count]))
//然后再合并
return merge(lPie: l, rPie: r)
}
//重點是合并算法，子問題就是分區(qū)，然后子問題遞歸解決大問題，先遞歸后合并，然后不是原地排序，需要額外臨時數(shù)組
func merge(lPie: [Int], rPie: [Int]) -> [Int] {
var l = 0
var r = 0
var a = [Int]()
while l < lPie.count && r < rPie.count {
if lPie[l] < rPie[r] {
a.append(lPie[l])
l += 1
} else {
a.append(rPie[r])
r += 1
}
}
//還有剩余情況
while l < lPie.count {
a.append(lPie[l])
l += 1
}
while r < rPie.count {
a.append(rPie[r])
r += 1
}
return a
}
//MARK: 快排
func sortArray(_ nums: [Int]) -> [Int] {
var arr = nums;
quickSort(&arr, 0, arr.count - 1)
return arr
}
//重點是分區(qū)算法，子問題就是分區(qū)，然后子問題遞歸解決大問題，先分區(qū)后遞歸，是原地排序
func quickSort(_ nums: inout [Int], _ l: Int, _ r: Int) {
if (l > r) {
return
}
//隨機一個數(shù)交換, 因為如果原來有序的數(shù)組會退化為O(n^2)
let random = Int.random(in: l...r)
(nums[random], nums[r]) = (nums[r], nums[random])
//下面做分區(qū)操作，去r位置的元素作為基準值
var x = nums[r]
// 定義i和j指針，分為三個區(qū)域,0..<i,為小區(qū)，i..<j為大區(qū)，j..<r為未查看
var i = l
for j in l..<r {
if (nums[j] <= x) {
(nums[j], nums[i]) = (nums[i], nums[j])
i += 1
}
}
//把基準的元素放到i的位置
(nums[r], nums[i]) = (nums[i], nums[r])
//遞歸左右區(qū)間
quickSort(&nums, l, i - 1)
quickSort(&nums, i + 1, r)
}
//MARK: 41. 缺失的第一個正數(shù)
// 哈希表法：沒有出現(xiàn)的最小正整數(shù)在[1, N+1]，要么[1, N]或者 N + 1
func firstMissingPositive(_ nums: [Int]) -> Int {
var nums = nums
//將所有負數(shù)改為n+1
let n = nums.count
for i in 0..<n {
if (nums[i] <= 0) {
nums[i] = n + 1
}
}
// 將小于等于n的元素位置變?yōu)樨摂?shù)
for i in 0..<n {
let index = abs(nums[i])
if (index <= n) {
nums[index - 1] = -abs(nums[index - 1])
}
}
//找出第一個大于0的元素，下標+1
for i in 0..<n {
if (nums[i] > 0) {
return i + 1
}
}
return n + 1
}
//swift不好操作字符串，api很繁瑣，不好獲取下標
/*
let name = "King"
let arr = Array(name)
一般采取轉成數(shù)組來操作
*/
//MARK: 14. 最長公共前綴
//參考leetcode國際站，最簡潔的代碼
//縱向每個字符串對比
func longestCommonPrefix(_ strs: [String]) -> String {
if strs.isEmpty { return "" }
var common = strs[0]
for ch in strs {
while !ch.hasPrefix(common) {
common = String(common.dropLast())
}
}
return common
}
//MARK: 160. 相交鏈表
/*
a單獨節(jié)點個數(shù)為a, b單獨節(jié)點個數(shù)為b, a和b共同節(jié)點為c
a + c + b = b + c + a
雙指針把a走完，然后移動到b
把b走完，然后移動到a
然后在交點交匯
*/
func getIntersectionNode(_ headA: ListNode?, _ headB: ListNode?) -> ListNode? {
if headA == nil || headB == nil {
return nil
}
var a: ListNode? = headA
var b: ListNode? = headB
while a !== b { //比較兩個指針需要用!== , !=用來比較值
a = a == nil ? headB : a?.next
b = b == nil ? headA : b?.next
}
return a
}
//MARK: 劍指 Offer 31. 棧的壓入、彈出序列
//用一個棧模擬彈棧，棧頂元素 == 彈出序列的當前元素，如果棧為空則彈出順序合法
func validateStackSequences(_ pushed: [Int], _ popped: [Int]) -> Bool {
var stack = Int
var i = 0
for num in pushed {
stack.append(num)
while !stack.isEmpty && stack.last == popped[i] {
stack.removeLast()
i += 1
}
}
return stack.isEmpty
}
//MARK: 141. 環(huán)形鏈表
//快慢指針，慢指針走一步，快指針走兩步
//注意慢指針在head, 快指針在head.next，因為這樣才能while走起來，
//相當于第一次都在虛節(jié)點出發(fā)，然后慢指針走一步到head，快指針走兩步到head.next
func hasCycle(_ head: ListNode?) -> Bool {
if (head == nil || head?.next == nil) {
return false
}
var slow = head
var fast = head?.next
while (fast !== slow) {
//fast == nil只判斷這個也行，這個是為了節(jié)點單數(shù)，或者雙數(shù)節(jié)點，鏈表走完
if (fast == nil || fast?.next == nil) {
return false
}
slow = slow?.next
fast = fast?.next?.next
}
return true
}
//MARK: 226. 翻轉二叉樹
func invertTree(_ root: TreeNode?) -> TreeNode? {
if (root == nil) {
return nil
}
let left = invertTree(root?.left)
let right = invertTree(root?.right)
root?.left = right
root?.right = left
return root
}
//MARK: 704. 二分查找
func search(_ nums: [Int], _ target: Int) -> Int {
var l = 0
var r = nums.count - 1
while(l <= r) {
let mid = (r - l) / 2 + l
let num = nums[mid]
if (num == target) {
return mid
} else if (num > target) {
r = mid - 1
} else {
l = mid + 1
}
}
return -1
}
//如果右邊界是取不到的， r不能 mid - 1，然后循環(huán)條件是 l < r
func search(_ nums: [Int], _ target: Int) -> Int {
var l = 0
var r = nums.count
while l < r {
let mid = (l + r) / 2
if nums[mid] == target {
return mid
} else if (nums[mid] < target) {
l = mid + 1
} else {
r = mid
}
}
return -1
}
//MARK: 2. 兩數(shù)相加
//因為逆序相加，然后返回也是逆序，所以直接對應位置相加，然后維護一個進位carry
//因為要返回一個鏈表，所以需要維護一個head指針，尾指針tail用來拼接鏈表
//國際站優(yōu)秀遞歸解法
class Solution {
private var anchor = 0
func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
if l1 == nil && l2 == nil && anchor == 0 { return nil }
let sum = (l1?.val ?? 0) + (l2?.val ?? 0) + anchor
anchor = sum / 10
let node: ListNode? = ListNode(sum % 10, addTwoNumbers(l1?.next, l2?.next))
return node
}
}
func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
var l1: ListNode? = l1
var l2: ListNode? = l2
var tail: ListNode? = ListNode(0) //head和tail在虛擬頭節(jié)點
let head = tail
var carry = 0
while l1 != nil || l2 != nil || carry > 0 {
let n1 = l1?.val ?? 0
let n2 = l2?.val ?? 0
let sum = n1 + n2 + carry
carry = sum / 10
tail?.next = ListNode(sum % 10)
tail = tail?.next
l1 = l1?.next
l2 = l2?.next
}
return head?.next //返回下個節(jié)點，head是虛擬頭
}
//MARK: 劍指 Offer 54. 二叉搜索樹的第k大節(jié)點
//利用swift函數(shù)可以嵌套定義，避免用屬性記錄值
//利用中序遍歷逆序，然后返回第k大的元素
class Solution {
func kthLargest(_ root: TreeNode?, _ k: Int) -> Int {
var count = 0
var res = 0
func dfs(_ root: TreeNode?) {
guard let root = root else { return }
dfs(root.right)
count += 1
if count == k {
res = root.val
return
}
dfs(root.left)
}
dfs(root)
return res
}
}
//中序遍歷順序，然后返回第k個元素，但需要額外空間O(n)
class Solution {
func inorder(_ root: TreeNode?, _ res: inout [Int]) {
guard let node = root else { return }
inorder(node.left, &res)
res.append(node.val)
inorder(node.right, &res)
}
func kthLargest(_ root: TreeNode?, _ k: Int) -> Int {
var res: [Int] = []
inorder(root, &res)
return res[res.count - k]
}
}
//MARK: 142. 環(huán)形鏈表 II 返回第一個入環(huán)節(jié)點
//根據歸納計算得出 a = c + (n-1)(b+c) fast和slow指針相遇時，slow指針和從起點出發(fā)的指針ptr在入口相遇
func detectCycle(_ head: ListNode?) -> ListNode? {
var fast = head
var slow = head
while(true) { //fast跑圈，因為可能要跑n圈才能交匯
// fast?.next 表示剛好在尾節(jié)點，下個節(jié)點為空，少循環(huán)一次
if (fast == nil || fast?.next == nil) {
return nil
}
fast = fast?.next?.next
slow = slow?.next
if (fast == slow) {
break
}
}
//重復利用fast指針
fast = head
while (slow != fast) {
slow = slow?.next
fast = fast?.next
}
return fast
}
//簡潔版代碼
func detectCycle(_ head: ListNode?) -> ListNode? {
var fast = head
var slow = head
while fast != nil {
slow = slow?.next
fast = fast?.next?.next
if fast === slow {
fast = head
while fast !== slow {
fast = fast?.next
slow = slow?.next
}
return fast
}
}
return nil
}
//MARK: 3. 無重復字符的最長子串
//滑動窗口,用set來判斷是否有重復字符
//用string的實例方法 contains比較慢
//可以用dict來優(yōu)化查找速度，因為用set操作不方便
func lengthOfLongestSubstring(_ s: String) -> Int {
var map = Character:Int //字典來跟蹤字母的最后一次出現(xiàn)的索引
var result = 0 //記錄結果
var l = -1 //左邊界初始值
for (r, char) in s.enumerated(){
l = max(l, map[char] ?? -1) //更新左邊界
result = max(result, r - l) //計算右減左
map[char] = r //更新字母最新的索引
}
return result
}
//這個運行速度差不多
func lengthOfLongestSubstring2(_ s: String) -> Int {
var maxCount = 0
var array = Character
for char in s {
if let index = array.firstIndex(of: char) {
//從0到i都刪除掉, 不包括i,因為要求連續(xù)的子串
array.removeFirst(index+1) //更新左邊界
}
array.append(char)// 更新右邊界
maxCount = max(maxCount, array.count)
}
return maxCount
}
//MARK: 同構字符串，超時示例，字符串轉字符數(shù)組
func isIsomorphic(_ s: String, _ t: String) -> Bool {
var s2t: [Character: Character] = [:]
var t2s: [Character: Character] = [:]
for (i,_) in s.enumerated() {
// 這種字符串取下標，會導致時間過長。通過轉換成字符串數(shù)組解決
let x = s[s.index(s.startIndex, offsetBy: i)]
let y = t[t.index(t.startIndex, offsetBy: i)]
if (s2t[x] != nil && s2t[x] != y) || (t2s[y] != nil && t2s[y] != x){
return false
}
s2t[x] = y
t2s[y] = x
}
return true
}
//通過轉成字符數(shù)組來解決分割數(shù)組問題
func isIsomorphic1(_ s: String, _ t: String) -> Bool {
let sChars = Array(s)
let tChars = Array(t)
var s2t = Character: Character
for i in 0 ..< sChars.count {
if let char = s2t[sChars[i]] {
if char != tChars[i] {
return false
}
} else {
if s2t.values.contains(tChars[i]) {
return false
}
s2t[sChars[i]] = tChars[i]
}
}
return true
}
//MARK: 1. 兩數(shù)之和
//利用map記錄差值 key為數(shù)組值， value為數(shù)組下標index
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
var dict = Int: Int
for (i, num) in nums.enumerated() {
if (dict[target - num] != nil) {
return [dict[target - num]!, i]
}
dict[num] = i
}
return []
}
//MARK: 合并兩個有序鏈表
//遞歸法，簡潔加上可選綁定簡化了解包
func mergeTwoLists(_ list1: ListNode?, _ list2: ListNode?) -> ListNode? {
guard let list1 = list1 else {return list2}
guard let list2 = list2 else {return list1}
if list1.val < list2.val {
list1.next = mergeTwoLists(list1.next, list2)
return list1
} else {
list2.next = mergeTwoLists(list1, list2.next)
return list2
}
}
//雙指針
func mergeTwoLists(_ list1: ListNode?, _ list2: ListNode?) -> ListNode? {
var l1 = list1
var l2 = list2
var newHead: ListNode? = ListNode(-1) //假的頭結點 注意這里的類型為option
var pre = newHead
while (l1 != nil && l2 != nil) {
if l1!.val <= l2!.val {
pre?.next = l1
l1 = l1?.next
} else {
pre?.next = l2
l2 = l2?.next
}
pre = pre?.next
}
pre?.next = l1 ?? l2
return newHead?.next
}
//MARK: 300. 最長遞增子序列
// dp[i] = max{ dp[j] } + 1 j in 0..<i
func lengthOfLIS(_ nums: [Int]) -> Int {
var dp = [Int]()
//初始化dp數(shù)組為1，因為不像其他語言動態(tài)賦值 dp[i] = 1
dp = (0..<nums.count).map{_ in return 1 }
var ans = 1
for i in 1..<nums.count {
for j in 0..<i {
if nums[j] < nums[i] {
dp[i] = max(dp[i], dp[j] + 1)
}
}
ans = max(ans, dp[i])
}
return ans
}
//方法二： 貪心算法 + 二分查找，優(yōu)化為nlogn
//貪心：如果要上升子序列盡可能小，那每次上升子序列最后加上的數(shù)盡可能小
/*
- 如果 nums[i] > d[len], 則直接加入數(shù)組末尾，并更新len += 1;
- 否則，在d數(shù)組中二分查找，找到第一個比nums[i]小的數(shù)d[k],并更新d[k+1] = nums[i];
以輸入序列 [0, 8, 4, 12, 2] 為例
第一步插入 0，d = [0]
第二步插入 8，d = [0, 8]
第三步插入 4，d = [0, 4]
第四步插入 12，d = [0, 4, 12]
第五步插入 2，d = [0, 2, 12]
*/
func lengthOfLIS(_ nums: [Int]) -> Int {
// 有三種便捷初始化數(shù)組
var tails = (0..<nums.count).map {_ in return 0}
// var tails = [Int](repeating: 0, count: nums.count)
//注意這會初始化為這個 0 --- nums.count
// var tails = Array(0..<nums.count)
var res = 0
for num in nums {
var l = 0
var r = res //這里不用減1，因為有可能是插入數(shù)組末尾
while l < r {
var m = (l + r) / 2
if (tails[m] < num) {
l = m + 1
} else {
r = m
}
}
//二分查找第一個 num比數(shù)組元素小的替換
// l或者r都可以
tails[l] = num
//如果nums[i] > d[len], 則直接加入數(shù)組末尾，并更新len += 1
if (res == r) {
res += 1
}
}
return res
}
//MARK: 415. 字符串相加
//模擬相加,字符串轉成字符數(shù)組比較好處理
func addStrings(_ num1: String, _ num2: String) -> String {
let s1 = Array(num1)
let s2 = Array(num2)
var i = s1.count - 1
var j = s2.count - 1
var add = 0
var ans = Int
//當最后一位還有進位時，還要進入循環(huán)，把進位加上去
// 例如 1 + 9 的情況
while (i >= 0 || j >= 0 || add != 0) {
let x = i >= 0 ? Int(String(s1[i]))! - 0 : 0
let y = j >= 0 ? Int(String(s2[j]))! - 0 : 0
let res = x + y + add
ans.append(res % 10)
add = res / 10
i -= 1
j -= 1
}
//或者當最后一位還有進位時，后面補1
var str = ""
for s in ans.reversed() {
str += "(s)"
}
return str
}
//MARK: 227. 基本計算器 II
//s 由整數(shù)和算符 ('+', '-', '', '/') 組成，中間由一些空格隔開
//思路：利用棧保存乘除的值，遇到乘除與棧頂元素計算并更新棧頂元素，這樣可以優(yōu)先計算乘除，然后處理完乘除后再把棧的元素相加起來（如果是減就加上負數(shù)）
func calculate(_ s: String) -> Int {
var stack = Int
var num = 0
var op = "+"
let count = s.count //這里要把count提前計算，不然會超時，因為count會每次遍歷一次才能得到
for (i,c) in s.enumerated() {
//因為字符可以是連續(xù)的，比如123
if c.isNumber {
num = num * 10 + Int(String(c))!
}
//判斷i == count - 1處理最后一個字符
//注意op為記錄當前數(shù)字的前一個操作符
if !c.isNumber && c != " " || i == count - 1 {
switch op {
case "+":
stack.append(num)
case "-":
stack.append(-num)
case "":
stack.append(stack.removeLast() * num)
default:
stack.append(stack.removeLast() / num)
}
num = 0 //重置下num
op = String(c) //操作符要更新一次
}
}
return stack.reduce(0, +)
}
//MARK: 215. 數(shù)組中的第K個最大元素
func findKthLargest(_ nums: [Int], _ k: Int) -> Int {
var nums = nums
return quickSelect(&nums, 0, nums.count - 1, nums.count - k)
}
func quickSelect(_ nums: inout [Int], _ l: Int, _ r: Int, _ index: Int) -> Int {
//隨機一個數(shù)交換, 因為如果原來有序的數(shù)組會退化為O(n^2)
let random = Int.random(in: l...r)
(nums[random], nums[r]) = (nums[r], nums[random])
//下面做分區(qū)操作，去r位置的元素作為基準值
let x = nums[r]
// 定義i和j指針，分為三個區(qū)域,0..<i,為小區(qū)，i..<j為大區(qū)，j..<r為未查看
var i = l
for j in l..<r {
if (nums[j] <= x) {
(nums[j], nums[i]) = (nums[i], nums[j])
i += 1
}
}
//把基準的元素放到i的位置
(nums[r], nums[i]) = (nums[i], nums[r])
//區(qū)別在于這里，快排提前返回
if (i == index) {
return nums[i]
} else {
return i < index ? quickSelect(&nums, i + 1, r, index) : quickSelect(&nums, l, i - 1, index)
}
}
//MARK: 151. 翻轉字符串里的單詞
//方法一：用系統(tǒng)api
//方法二：自行實現(xiàn)對應的函數(shù)
func reverseWords(_ s: String) -> String {
return s.split(separator: " ").reversed().joined(separator: " ")
}
//MARK: 1143. 最長公共子序列
/*
因為dp[i][j] 長度是+1的
動態(tài)轉移方程 dp[i][j] = dp[i-1][j-1] + 1 text[i-1] = text[j-1]
max{ dp[i-1][j], dp[i][j-1] } text[i-1] != text[j -1]
可以劃個二維的表格表示
/
func longestCommonSubsequence(_ text1: String, _ text2: String) -> Int {
let m = text1.count
let n = text2.count
var dp = Array(repeating: Array(repeating: 0, count: n + 1), count: m + 1)
let s1 = Array(text1)
let s2 = Array(text2)
for i in 1...m {
for j in 1...n {
if s1[i - 1] == s2[j - 1] {
dp[i][j] = dp[i - 1][j - 1] + 1
} else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
}
}
}
return dp[m][n]
}
/
"" b d c
"" 0 0 0 0
a 0 0 0 0
b 0 1 1 1
c 0 1 1 2
每次計算新的一行的時候, 用到的都是上一行或者本行之前算過的數(shù)據（即為左，上，左上), 所以可以優(yōu)化到一維數(shù)組
就是dp取最后一行，降為一維數(shù)組
注意：左上角的數(shù)據會被覆蓋掉，需要用
*/
//優(yōu)化空間為一維
func longestCommonSubsequence(_ text1: String, _ text2: String) -> Int {
let m = text1.count
let n = text2.count
var dp = Array(repeating: 0, count: n + 1)
var temp = 0
var upleft = 0
let s1 = Array(text1)
let s2 = Array(text2)
for i in 1...m {
upleft = dp[0] // 每行開始的時候需要更新下upleft, 這里其實每次都是0
for j in 1...n {
temp = dp[j] // 記錄未被覆蓋之前的dp[j], 它會在計算 j+1的時候作為upLeft用到
if s1[i - 1] == s2[j - 1] {
dp[j] = upleft + 1 //upleft代表左上
} else {
dp[j] = max(dp[j], dp[j - 1]) //j-1代表左側數(shù)據，j代表正上方
}
upleft = temp //更新左上
}
}
return dp[n]
}
//MARK: 交錯字符串
//MARK: 234. 回文鏈表
//方法一: 將鏈表轉換為數(shù)組，然后頭尾雙指針比較
func isPalindrome(_ head: ListNode?) -> Bool {
var arr = Int
var cur: ListNode? = head
while cur != nil {
arr.append(cur!.val)
cur = cur?.next
}
var front = 0
var tail = arr.count - 1
while front < tail { //注意不能用不等于，因為為偶數(shù)時不會交匯
if (arr[front] != arr[tail]) {
return false
}
front += 1
tail -= 1
}
return true
}
//方法二：優(yōu)化O(n)空間，利用快慢指針找到后半部分鏈表，反轉后半部分鏈表，然后對比是否為回文，恢復鏈表，返回結果
//以下為不還原鏈表的方式
func isPalindrome1(_ head: ListNode?) -> Bool {
if head == nil { return true }
let m = findMiddle(head)
var p1 = head
var p2 = reverseList(m)
while p2 != nil {
if p1?.val != p2?.val {
return false
}
p1 = p1?.next
p2 = p2?.next
}
return true
}
func reverseList(_ head: ListNode?) -> ListNode? {
var pre: ListNode? = nil
var cur = head
while(cur != nil) {
let next = cur?.next
cur?.next = pre
pre = cur
cur = next
}
return pre
}
//1-2-2-1
func findMiddle(_ head: ListNode?) -> ListNode? {
var fast = head
var slow = head
while fast?.next != nil {
fast = fast?.next?.next
slow = slow?.next
}
return slow
}
//MARK: 25. K 個一組翻轉鏈表
//官方解法
func reverseKGroup(_ head: ListNode?, _ k: Int) -> ListNode? {
let hair = ListNode(0)
var head: ListNode? = head
hair.next = head
var pre: ListNode? = hair
while (head != nil) {
var tail: ListNode? = pre
for _ in 0..<k {
tail = tail?.next
if tail == nil {
return hair.next
}
}
let next = tail?.next
let reverse = myReverse(head, tail)
head = reverse.0
tail = reverse.1
pre?.next = head
tail?.next = next
pre = tail
head = tail?.next
}
return hair.next
}
func myReverse(_ head: ListNode?, _ tail: ListNode?) -> (ListNode?, ListNode?) {
var pre = tail?.next
// 或者 var pre: ListNode? = nil
var p = head
while (pre !== tail) {
let next = p?.next
p?.next = pre
pre = p
p = next
}
return (tail, head)
//或者 return (pre, head)
}
