leetcode 67(합 구현), 415, 350(구현), 1002(구현), 202(구현), 258(숫자근 digit root)

67 https://leetcode.com/problems/add-binary/, 415 https://leetcode.com/problems/add-strings/

1. 작은 자리의 수를 큰 자리의 수와 길이가 맞게 0으로 채워준다.

2. 더하면서 carry가 생기면 다음에 추가해준다.

415는 아래 코드에서 10진수 개념으로만 보고 조금만 바꿔주면되어서 따로 안적는다

class Solution(object):
    def addBinary(self, a, b):
        if len(b) > len(a):
            a,b = b,a
        for i in xrange(len(a)-len(b)):
            b = '0' + b

        ret = ''
        carry = 0
        for i in xrange(len(a)-1, -1, -1):
            s = carry + int(a[i]) + int(b[i])
            carry = 0
            if s > 1:
                s %= 2
                carry = 1
            ret = str(s) + ret
        if carry == 1:
            ret = '1' + ret
        return ret

350 https://leetcode.com/problems/intersection-of-two-arrays-ii/

시키는대로 구현한다..

class Solution(object):
    def intersect(self, nums1, nums2):
        if len(nums2) > len(nums1):
            nums1,nums2 = nums2,nums1
        n1_dict, n2_dict = {}, {}
        for n in nums1:
            n1_dict[n] = n1_dict.get(n, 0) + 1
        for n in nums2:
            n2_dict[n] = n2_dict.get(n, 0) + 1
        
        ret = []
        for k,v in n2_dict.iteritems():
            ret += [k]*min(v, n1_dict.get(k, 0))
        return ret

1002 https://leetcode.com/problems/find-common-characters/

class Solution(object):
    def commonChars(self, A):
        A = [{aa:a.count(aa) for aa in a} for a in A]  # A를 다시 만드는데 각각의 원소가 각각의 단어의 카운트를 저장해놓은 딕셔너리로 만듬
        A = sorted(A, key=lambda x:len(x))  # 길이로 정렬
        
        ret = []
        for k,v in A[0].iteritems():  # 가장 짧은 길이의 단어의 알파벳으로 돌림.
            ret += [k]*min([v] + map(lambda x: x.get(k, 0), A[1:]))
        return ret

202 https://leetcode.com/problems/happy-number/

class Solution(object):
    def isHappy(self, n):
        history = set([n])
        while True:
            n = sum(map(lambda x: int(x)**2, list(str(n))))
            if n == 1:
                return True
            if n in history:
                return False
            history.add(n)

258 https://leetcode.com/problems/add-digits/

구현 자체는 쉬운데 이게 숫자근(digit root)이라고 따로 이론이 있는 문제였나보다..

https://leetcode.com/problems/add-digits/discuss/68580/Accepted-C%2B%2B-O(1)-time-O(1)-space-1-Line-Solution-with-Detail-Explanations 를 읽어보자.

파이썬 코드 : https://leetcode.com/problems/add-digits/discuss/68732/No-looprecursion-O(1)-runtime-just-one-line-python-code