# LeetCode – 897. Increasing Order Search Tree

### 題目連結:

https://leetcode.com/problems/increasing-order-search-tree/

### 參考解法:

https://leetcode.com/problems/increasing-order-search-tree/discuss/244939/Swift-88ms

### 法ㄧ(Two pointers with in-order traversal)

``````var head: TreeNode?
var prev: TreeNode?
func increasingBST(_ root: TreeNode?) -> TreeNode? {
guard let root = root else { return nil }
increasingBST(root.left)
if head == nil {
}
root.left = nil
prev?.right = root
prev = root
increasingBST(root.right)
}``````

# LeetCode – 942. DI String Match

### 題目連結:

https://leetcode.com/problems/di-string-match/

### 參考解法:

https://leetcode.com/problems/di-string-match/discuss/755754/Swift-Simple-Solution

### 法ㄧ(Time complexity: O(n), Space complexity: O(n) note: s is the length of s)

``````    func diStringMatch(_ s: String) -> [Int] {
guard s.count > 0 else { return [] }
let sArr = Array(s)
var arr = Array(repeating: 0, count: s.count)
var low = 0
var high = s.count
var index = 0
for c in s {
if c == "D" {
arr[index] = high
high -= 1
} else {
arr[index] = low
low += 1
}
index += 1
}
arr.append(high) // note: arr.append(low) also works
return arr
}``````

### 延伸題（印出所有可能的permutation):

``````    func diStringMatch(_ s: String) -> [[Int]] {
guard s.count > 0 else { return [] }
let sArr = Array(s)
var arr = Array(repeating: 0, count: s.count + 1)
for i in 0 ..< arr.count {
arr[i] = i
}

var result: [[Int]] = []
helper(arr, sArr, &result, 0, [])
return result
}

func helper(_ arr: [Int], _ sArr: [Character] ,_ result: inout [[Int]], _ curStep: Int, _ curPerm: [Int]) {
if curPerm.count == sArr.count + 1 {
result.append(curPerm)
return
}

var tmpArr = arr
for i in 0 ..< tmpArr.count {
let val = tmpArr.remove(at: i)
if curStep == 0 || isValidNum(curPerm.last, val, sArr[curStep - 1]) {
helper(tmpArr, sArr, &result, curStep + 1, curPerm + [val])
}
tmpArr.insert(val, at: i)
}
}

func isValidNum(_ a: Int?, _ b: Int, _ op: Character) -> Bool {
guard let a = a else { return true }
if op == "D" {
return a > b
} else {
return a < b
}
}``````

# LeetCode – 392. Is Subsequence

### 題目連結:

https://leetcode.com/problems/is-subsequence/

### 參考解法：

https://leetcode.com/problems/is-subsequence/discuss/394509/Swift-solution-32ms-100-very-simple

### Test cases:

// s: “", t: “a"
// s: “a", t: “"
// s: “abc", t: “abc"
// s: “abc", t: “abdce" note: 多字
// s: “abc", t: “adc" note: 少字
// s: “abbc",t: “abcb" note: 順序錯

### 法ㄧ

Time complexity: O(mn) 、Space complexity: O(n)

Note: m is the length of s, n is the length of t

``````    func isSubsequence(_ s: String, _ t: String) -> Bool {
if s.isEmpty { return true }
else if !s.isEmpty && t.isEmpty { return false }
else if s == t { return true }
else {
let tArr = Array(t)
var lastPos = 0
for c in s {
var found = false
for i in lastPos ..< tArr.count {
if c == tArr[i] {
if i < lastPos {
return false
}
found = true
lastPos = i + 1
break
}
}
if !found { return false }
}
return true
}
}``````

### 法二

Time complexity: O(m) 、Space complexity: O(n+m)

Note: m is the length of s, n is the length of t

``````    func isSubsequence(_ s: String, _ t: String) -> Bool {
let sArr = Array(s)
let tArr = Array(t)
var sIndex = 0
var tIndex = 0
while sIndex < sArr.count && tIndex < tArr.count {
if sArr[sIndex] == tArr[tIndex] {
sIndex += 1
}
tIndex += 1
}
return sIndex == s.count
}``````

# LeetCode – 1827. Minimum Operations to Make the Array Increasing

### 題目連結:

https://leetcode.com/problems/minimum-operations-to-make-the-array-increasing/

### 參考解法：

https://leetcode.com/problems/minimum-operations-to-make-the-array-increasing/discuss/1502527/Swift-Simple-solution

### 法ㄧ(Time complexity: O(n) 、Space complexity: O(n) )

``````    func minOperations(_ nums: [Int]) -> Int {
var i = 0
var result = 0
var arr = nums
while i < nums.count - 1 {
if arr[i+1] <= arr[i] {
result += arr[i] - arr[i+1] + 1
arr[i+1] = arr[i] + 1
}
i += 1
}
return result
}``````

### 法二(Time complexity: O(n) 、Space complexity: O(1) )

``````    func minOperations(_ nums: [Int]) -> Int {
var result = 0
var lastNum = 0
for i in 0 ..< nums.count {
if i != 0 && nums[i] <= lastNum {
result += (lastNum - nums[i] + 1)
lastNum = lastNum + 1
} else {
lastNum = nums[i]
}
}
return result
}``````

# LeetCode – 1323. Maximum 69 Number

### 題目連結:

https://leetcode.com/problems/maximum-69-number/

### 參考解法:

https://leetcode.com/problems/maximum-69-number/discuss/929925/Swift-faster-than-100

### 法ㄧ(自己的解法):

``````func maximum69Number (_ num: Int) -> Int {
var arr: [Int] = []
var tmp = num
while tmp > 0 {
let val = tmp % 10
tmp = tmp / 10
arr.append(val)
}

var result = 0
var isReplaced = false
for i in (0 ..< arr.count).reversed() {
if !isReplaced && arr[i] == 6 {
arr[i] = 9
isReplaced = true
}
result = result * 10 + arr[i]
}

return result
}
``````

### 法二(別人的解法):

``````func maximum69Number (_ num: Int) -> Int {
var charArr: [Character] = String(num).map { Character("\(\$0)") }
if let idx = charArr.firstIndex(of: "6") {
charArr[idx] = "9"
return Int(charArr.reduce("") {\$0 + String(\$1)})!
}
return num
}

``````

### 比較法ㄧ和法二performance差異:

``````//利用這個function去評估performance
func printTimeElapsedWhenRunningCode(title:String, operation:()->()) {
let startTime = CFAbsoluteTimeGetCurrent()
operation()
let timeElapsed = CFAbsoluteTimeGetCurrent() - startTime
print("Time elapsed for \(title): \(timeElapsed) s.")
}``````

# LeetCode – 1221. Split a String in Balanced Strings

### 題目連結:

https://leetcode.com/problems/split-a-string-in-balanced-strings/

### 參考解法:

https://leetcode.com/problems/split-a-string-in-balanced-strings/discuss/573442/Swift

### 法ㄧ(自己的解法):

``````    func balancedStringSplit(_ s: String) -> Int {
var rCount = 0
var lCount = 0
var result = 0
for c in s {
if c == "R" {
rCount += 1
} else {
lCount += 1
}

if rCount != 0 && lCount != 0 && rCount == lCount {
result += 1
rCount = 0
lCount = 0
}
}
return result
}``````

### 法二(別人的解法):

``````    func balancedStringSplit(_ s: String) -> Int {
var sum = 0
var result = 0
for c in s {
if c == "R" {
sum += 1
} else {
sum -= 1
}

if sum == 0 {
result += 1
}
}
return result
}``````

# LeetCode – 746. Min Cost Climbing Stairs￼￼

### 題目連結:

https://leetcode.com/problems/min-cost-climbing-stairs/

### 法ㄧ(Recursive version):

``````var dp: [Int] = []
func minCostClimbingStairs(_ cost: [Int]) -> Int {
dp = Array(repeating: -1, count: cost.count + 1)
return helper(cost, cost.count)
}

func helper(_ cost: [Int], _ steps: Int) -> Int {
if steps <= 1 {
return 0
} else if dp[steps] != -1 {
return dp[steps]
} else {
dp[steps] = min(helper(cost, steps - 1) + cost[steps - 1], helper(cost, steps - 2) + cost[steps - 2])
return dp[steps]
}
}``````

### 法二(Iterative version):

``````func minCostClimbingStairs(_ cost: [Int]) -> Int {
if cost.count == 0 || cost.count == 1 {
return 0
} else {
var dp = Array(repeating: -1, count: cost.count + 1)
dp[0] = 0
dp[1] = 0
for i in 2 ... cost.count {
dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
}
return dp[cost.count]
}
}``````

# LeetCode – 2160. Minimum Sum of Four Digit Number After Splitting Digits￼￼

### 題目連結:

https://leetcode.com/problems/minimum-sum-of-four-digit-number-after-splitting-digits/

### 參考解法:

https://blog.csdn.net/qq_45124566/article/details/124070992

``````    func minimumSum(_ num: Int) -> Int {
var arr: [Int] = []
var tmp = num
while tmp > 0 {
let val = tmp % 10
arr.append(val)
tmp = tmp / 10
}

arr.sort(by: <)

return (arr[0] + arr[1]) * 10 + (arr[2] + arr[3])
}``````

# LeetCode – 75. Sort Colors

``````    func sortColors(_ nums: inout [Int]) {
var zeroIndex = 0
var twoIndex = nums.count - 1
var i = 0
while i <= twoIndex {
if nums[i] == 0, i > zeroIndex {
nums.swapAt(i, zeroIndex)
zeroIndex += 1
} else if nums[i] == 2, i < twoIndex {
nums.swapAt(i, twoIndex)
twoIndex -= 1
} else {
i += 1
}
}
}``````