[Swift] [leetcode] Implement strStr ... etc

문제 Implement strStr()

Implement strStr() - LeetCode

 

needle을 찾았다면 찾은 첫 번째 index를 반환, 찾지 못했다면 -1을 반환해야 합니다

 

class Solution {
    func strStr(_ haystack: String, _ needle: String) -> Int {
        if needle.isEmpty { return 0 }
        if !haystack.contains(needle) { return -1 }
        
        var index = 0
        var hs = haystack 
        while !hs.hasPrefix(needle) { 
            index += 1
            hs = String(hs.dropFirst()) 
        }
        return index
    }
}

 

string methods

contains (참고)

: Returns a Boolean value indicating whether the sequence contains the given element

func contains(_ element: Self.Element) -> Bool

요소가 시퀀스 안에 있는지 반환값 Bool로 반환합니다

 

dropFirst (참고)

: Returns a subsequence containing all but the given number of initial elements

func dropFirst(_ k: Int = 1) -> Self.SubSequence

지정된 수의 요소 이후에 시작하는 하위 시퀀스를 반환합니다

 

hasPrefix (참고)

: finding subString

func hasSuffix(_ suffix: String) -> Bool

---

문제 search-insert-position

Search Insert Position - LeetCode

target이 들어가야 하는 index를 반환하면 됩니다.

 

class Solution {
    func searchInsert(_ nums: [Int], _ target: Int) -> Int {
        if let ret = nums.firstIndex(of: target) {
            return ret
        }
        var ret = -1
        for i in nums.indices {
            guard nums[i] < target else {
                ret = i
                break
            }
        }
        return ret == -1 ? nums.count : ret
    }
}

풀이는 index 처음부터 시작해서 값을 비교해서 들어가야 할 위치값을 반환하였습니다만, 이분탐색으로 좀 더 효율이 좋은 코드를 짤 수 있습니다.

---

문제 Sqrt(x)

Sqrt(x) - LeetCode

x의 제곱근의 정수값을 반환하면됩니다, 함수를 사용하지 않아야 합니다

 

class Solution {
    func mySqrt(_ x: Int) -> Int {
        guard x != 0 else { return 0 }
        var left = 1
        var right = (x + 1) / 2
        var ret = 0
        
        while left <= right {
            var mid = left + (right-left)/2
            if mid * mid <= x {
                ret = mid
                left = mid + 1
            } else if mid * mid > x {
                right = mid - 1
            }
        }
        return ret
    }
}

위의 문제에서 언급되었던 이분 탐색이며, 범위를 어떻게 잡는지가 중요합니다

---

문제 Climbing Stairs

Climbing Stairs - LeetCode

계단을 오르는 모든 방법에 대한 갯수를 반환하면 됩니다

피보나치 수열과 동일 합니다

 

class Solution {
    func climbStairs(_ n: Int) -> Int {
        if n == 0 || n == 1 { return 1 }

        var first = 1
        var second = 1
        var third = 0
        
        for _ in 2...n {
            third = first + second
            first = second
            second = third
        }

        return second
    }
}

DP로 풀면 된다고 합니다. 이러한 방식을 기억하려 합니다

---

문제 Convert Sorted Array to Binary Search Tree

Convert Sorted Array to Binary Search Tree - LeetCode

 

이진탐색트리에서 중위값을 가운데로 두는 방식으로

중위수를 가운데로 배치를 해야 하기에 중앙값으로 root를 시작으로 root 보다 작은 중위수, right는 root보다 큰 중위수를 root로 계속 반복을 하면 됩니다.

class Solution {
    func sortedArrayToBST(_ nums: [Int]) -> TreeNode? {
        helper(nums, 0, nums.count - 1)
    }

    private func helper(_ nums: [Int], _ lo: Int, _ hi: Int) -> TreeNode? {
        guard lo <= hi else { return nil }

        let mid = lo + (hi - lo) / 2

        let root = TreeNode(nums[mid])
        root.left = helper(nums, lo, mid - 1)
        root.right = helper(nums, mid + 1, hi)

        return root
    }
}