leetcode 1638(브루트포스), 1387(dp), 35(이분 탐색)

1638 https://leetcode.com/problems/count-substrings-that-differ-by-one-character/
제한조건이 s와 t가 둘다 길이가 100이하이니 그냥 되는대로 구현하면 된다. s의 substring이 t의 substring안에 속하는데 하나만 달라야 한다.

class Solution(object):
    def countSubstrings(self, s, t):
        #s = "aba"
        #t = "baba"
        len_s, len_t = len(s), len(t)
        ret = 0
        for i in range(len_s):
            for j in range(len_t):
                diff, k = 0, 0
                #print i,j
                while k+i < len_s and k+j < len_t:  # k+i는 i의 새로 시작하는 인덱스, k+j는 j의 새로 시작하는 인덱스다.
                    if s[k+i] != t[k+j]:
                        diff += 1
                    if diff == 1:
                        ret += 1
                    if diff > 1:
                        break
                    k += 1
        return ret

1387 https://leetcode.com/problems/sort-integers-by-the-power-value/
오랫만에 보는 dp문제다. 무식하게 매번 전부 구하도록 풀어도 통과는 되는데 미디움정도면 dp를 쓰는게 더 맞는것같다..

class Solution(object):
    def getKth(self, lo, hi, k):
        d = {2**n: n for n in range(1, 10)}  # 미리 저장해둘 사전 캐시. 2의 n승이면 현재 위치에서 n번만 더 가면 된다.
        def getpower(num):
            if num in d:
                return d[num]
            if num % 2 == 0:
                d[num] = getpower(num/2) + 1
            else:
                d[num] = getpower(num*3+1) + 1
            return d[num]
        
        ret = []
        for i in range(lo, hi+1):
            power = getpower(i)
            ret.append([i, power])
        return sorted(ret, key=lambda x:(x[1], x[0]))[k-1][0]

35 https://leetcode.com/problems/search-insert-position/
이진 탐색(이분 탐색)을 구현하는 문제이다. 쉬움 난이도인데 면접때 나올것같은거라서 한번 적으면서 다시 기억해둔다.

class Solution(object):
    def searchInsert(self, nums, target):
        #nums = [1,3,5,6]
        #target = 2
        
        start, end = 0, len(nums)-1
        while start <= end:
            mid = int((start + end)/2)
            #print(start, mid, end)
            if target == nums[mid]:
                return mid
            elif target < nums[mid]:
                end = mid - 1
            else:
                start = mid + 1
        #print('f =',start,mid,end)
        return start