[leetcode] 22, 29, 69, 70

shsh·2021년 8월 1일

leetcode

목록 보기

137/161

69. Sqrt(x)

싫어요 수에 놀래서 뒤로 미뤘다가 시간이 부족해서 못풀었읍니다..^^

Solution 1: Accepted (Runtime: 40 ms - 47.15% / Memory Usage: 14.2 MB - 43.27%)

class Solution:
    def mySqrt(self, x: int) -> int:
        ## RC ##
        ## APPROACH : Binary Search ##
        #   1. Any number greater than 1, will have sqrt(n) less than n/2
        #   2. We can check i*i < n till n/2.
        #   3. Can be optimized with binary search, listing all nums till n/2 and check i*i < n
        
        if(x < 4): return 1 if (x!=0) else 0
            
        low = 2
        high = x//2 
        while low <= high:
            mid = low + (high - low)//2
            if mid ** 2 < x:
                low = mid + 1
            
            elif mid ** 2 > x:
                high = mid - 1
            else:
                return mid
                
        return high

여기서도 Binary Search 를...?!

1 보다 큰 숫자들의 제곱근은 모두 n/2 보다 작은 값을 갖기 때문에 high = x//2

따라서 2 ~ x//2 사이에 존재하는 sqrt(x) 찾기

mid 의 제곱이 x 보다 작으면 low 움직이기, 크면 high 움직이기
mid 의 제곱이 x 가 되면 return mid

70. Climbing Stairs

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

My Answer 1: Accepted (Runtime: 32 ms - 54.38% / Memory Usage: 14.2 MB - 72.86%)

class Solution:
    def climbStairs(self, n: int) -> int:
        def func(n):
            if n in dp:
                return dp[n]
            if n == 0:
                return 1
            
            a = 0
            if n-1 >= 0:
                a += func(n-1)
            if n-2 >= 0:
                a += func(n-2)
            return a
        
        dp = {}
        for i in range(1, n+1):
            dp[i] = func(i)
        
        return dp[n]

1 부터 n 까지 숫자들의 조합을 dp 에 저장해서
이미 있는 값들은 dp 값으로 대체

33. Search in Rotated Sorted Array

https://leetcode.com/problems/search-in-rotated-sorted-array/

My Answer 1: Wrong Answer (182 / 195 test cases passed.)

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        lr = 0
        if nums[0] > target:
            lr = 1
        
        l = 0
        r = len(nums)-1
        
        while l < r:
            m = (l+r) // 2
            if nums[m] == target:
                return m
            
            if nums[m] > target:
                if nums[l] > nums[r] and nums[l] > target:
                    l = m+1
                elif nums[l] > nums[r] and nums[r] < target:
                    r = m-1
                elif nums[l] < nums[r]:
                    r = m-1
                else:
                    l = m+1
            else:
                if nums[l] > nums[r] and nums[l] > target:
                    l = m+1
                elif nums[l] > nums[r] and nums[r] < target:
                    r = m-1
                elif nums[l] < nums[r]:
                    l = m+1
                else:
                    r = m-1
                    
        if nums[l] == target:
            return l
        
        return -1

시간을 올인했지만.. 열심히 끼워맞췄는데도 안됐음^^

log N 이라길래 Binary Search 사용

nums[l] > nums[r] 인지 nums[l] < nums[r] 인지 구분해서
경우를 나누려고 했는데 생각보다 넘 복잡..

Solution 1: Accepted (Runtime: 32 ms - 98.22% / Memory Usage: 14.7 MB - 23.45%)

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums)-1
        
        while left <= right:
            mid = left+(right-left) // 2
            
            if nums[mid] == target:
                return mid
                
            if nums[mid] < nums[right]:
                if nums[mid] < target <= nums[right]:
                    left = mid+1
                else:
                    right = mid-1
            else:
                if nums[left] <= target < nums[mid]:
                    right = mid-1
                else:
                    left = mid+1
                    
        return -1

if nums[mid] < nums[right]: 가 포인트 같음

시작 ~ 중간: 1 구역 / 중간 ~ 끝: 2 구역 으로 나뉜다고 가정

mid ~ right 까지 increasing 상태일 때,
2 구역에 target 이 있으면 l = m+1
1 구역에 target 이 있으면 r = m-1

mid ~ right 사이에 꺾이는 부분이 있을 때,
1 구역에 target 이 있으면 r = m-1
2 구역에 target 이 있으면 l = m+1

그냥 외워!!!

34. Find First and Last Position of Element in Sorted Array

https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

시간 없어서 보지도 못했네요..^^

Solution 1: Accepted (Runtime: 84 ms - 73.82% / Memory Usage: 15.4 MB - 82.31%)

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def search(x):
            lo, hi = 0, len(nums)           
            while lo < hi:
                mid = (lo + hi) // 2
                if nums[mid] < x:
                    lo = mid+1
                else:
                    hi = mid                    
            return lo
        
        lo = search(target)
        hi = search(target+1)-1
        
        if lo <= hi:
            return [lo, hi]
                
        return [-1, -1]

Binary Search

lo 는 시작 값을 찾고 hi 는 target+1 의 자리 - 1 해서 마지막 값을 찾음

Binary Search Party Day~