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 {
    	head = root
  	}
    root.left = nil
    prev?.right = root
    prev = root
    increasingBST(root.right)
    return head
}

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.")
}

法ㄧ: Time elapsed for maximum69Number – 1: 0.0012859106063842773 s.

法二: Time elapsed for maximum69Number – 2: 0.0009620189666748047 s.

法二速度是法ㄧ速度的1.1倍

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/

參考解法:

https://www.youtube.com/watch?v=v3WqNLmmBdk

法ㄧ(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

題目連結: https://leetcode.com/problems/sort-colors/

解法參考: https://leetcode.com/problems/sort-colors/discuss/1918849/100-Fastest-Swift-Solution-time%3A-O(n)-space%3A-O(1).

    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
    		}
    	}
    }