leetcode 565(구현), 118(구현), 119, 2(구현), 445, 43(구현)

565 https://leetcode.com/problems/array-nesting/

 

S는 A로 만들수 있는 서브배열개념이고.. S를 만드는 방법은 A[i] -> A[A[i]] -> A[A[A[i]]] 이런식으로 위치를 찾아가면서 만들수 있다. 이중 가장 긴 S를 구하는거다. i일때의 그룹을 만들면서 사용한 인덱스들을 set에 저장해둔다. 그리고 그룹이 끝나면 그룹의 길이로 정답을 대체하고 다음거로 넘어간다. 

class Solution:
    def arrayNesting(self, nums: List[int]) -> int:
        i = 0
        used = set()
        ret = []
        while i < len(nums):
            if nums[i] in used:  # nums[i]가 이미 이전의 숫자의 그룹을 만들면서 사용된적이 있으면 이미 했으므로 넘어감.
                i += 1
                continue
            j = i
            group = []
            while nums[j] not in used:  # 그룹을 만드는데 사용되지 않은 숫자들만 대상으로.
                used.add(nums[j])
                group.append(nums[j])
                j = nums[j]
            if len(group) > len(ret):
                ret = group
            #print('group =',group)
            i += 1
        return len(ret)

118 https://leetcode.com/problems/pascals-triangle/, 119 https://leetcode.com/problems/pascals-triangle-ii/

 

파스칼의 삼각형 만드는 구현 문제. 119번은 118번 코드를 매우 조금만 수정하면 되어서 추가로 적진 않는다.

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        ret = [[1]]
        for i in range(1, numRows):
            ret.append([1])  # 시작은 1
            for j in range(i-1):  # 중간 부분은 이전 행의 (j) + (j+1)
                ret[i].append(ret[i-1][j] + ret[i-1][j+1])
            ret[i].append(1)  # 끝은 1로 끝남.
        return ret

2 https://leetcode.com/problems/add-two-numbers/, 445 https://leetcode.com/problems/add-two-numbers-ii/

 

말 그대로 구현한다... 445도 별다를게없어서 그냥 같이 적어놓음.

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        start = cur_node = ListNode(0)
        carry = 0
        while l1 or l2 or carry:
            v1 = v2 = 0
            if l1:
                v1 = l1.val
                l1 = l1.next
            if l2:
                v2 = l2.val
                l2 = l2.next
            cur_val = carry + v1 + v2
            carry = 0
            if cur_val >= 10:
                carry = 1
                cur_val %= 10
            cur_node.next = ListNode(cur_val)
            cur_node = cur_node.next
        return start.next

43 https://leetcode.com/problems/multiply-strings/

 

곱셈을 내부 라이브러리를 사용하지 않고 구현하는 문제이다. 파이썬은 큰 수도 정수로 표현할수 있어서 그냥 str(int(num1) + int(num2)) 하면 되겠지만 이건 당연히 안된다..

class Solution:
    def multiply(self, n1: str, n2: str) -> str:
        ret = 0
        for i in range(len(n2)-1, -1, -1):
            cnt = len(n2)-i-1
            for j in range(len(n1)-1, -1, -1):
                ret += (10**cnt)*int(n2[i])*int(n1[j])
                cnt += 1
        return str(ret)