# LeetCode Medium 279. Perfect Squares

tags: leetcode

問題

• Explore
• Problems

アイデア

｢正整数 $n$ が与えられた時， $n$ を平方数の和だけで表した時に，使うのに必要な最小の平方数の数を返せ｣という問題です．

よくわからない…

解法

動的計画法でした(完)

配列を

dp[i番目までの数] = iを平方数の和で表したときの最小の平方数の個数

として，後は各平方数ごとに配列を更新する．

計算量

• 時間計算量
  • $O(n \sqrt{n})$
• 空間計算量
  • $O(n)$

Python

class Solution:
    def numSquares(self, n: int) -> int:
        dp = [float('inf')] * (n + 1)
        dp[0] = 0
        for i in range(1, int(math.sqrt(n)) + 1):
            square_num = i * i
            for j in range(square_num, len(dp)):
                dp[j] = min(dp[j], 1 + dp[j - square_num])
        return dp[n]

# LeetCode Medium 138. Copy List with Random Pointer

tags: leetcode

問題

• Explore
• Problems

アイデア

｢ランダムな位置のノードを指すポインタを持つ単方向連結リストをdeep copyせよ，つまり完全にコピーせよ｣という問題です．

やるだけですね(出来なかった並感)．

解法

連想配列を使ってコピーします．

• 最初に全てのノードをコピーします．
• 次に，全てのノードのnextとrandomをコピーします．

非常に簡単なのに気付けなかった…どうかしている．

計算量

ノードの数を$N$とします．

• 時間計算量
  • $O(N)$
• 空間計算量
  • $O(N)$

Python

"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head:
            return head
        
        node_hash = {}
        node = head
        while node:
            node_hash[node] = Node(node.val, None, None)
            node = node.next
        
        node = head
        for key in node_hash:
            if key.next:
                node_hash[key].next = node_hash[key.next]
            if key.random:
                node_hash[key].random = node_hash[key.random]
            node = node.next
            
        return node_hash[head]

# LeetCode Medium 61. Rotate List

tags: leetcode

問題

• Explore
• Problems

アイデア

｢単方向連結リストを右向きにkだけ回転させろ｣という問題です．

解法

• 先頭のノードへのポインタを2つ作ります．(1つはノードの数を数え，最後のノードを先頭に繋げるp，1つは位置をずらす際に使うp)
• ノードを最後まで探索して，探索したノードの数を数えます．
• こうして，探索し終わったノードを先頭のノードに繋げます．
• そして，cnt - k - 1回(kはcntで割ったあまり)qを次のポインタのノードにします．
• こうすることで，qを先頭にしたいノードの前のノードにすることができ，qの次のノードを答えにし，qの次のポインタをNULLにすることで，連結リストを循環しないようにすることが出来ます．

計算量

ノードの数を$N$とします．

• 時間計算量
  • $O(N)$
• 空間計算量
  • $O(1)$

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def rotateRight(self, head: ListNode, k: int) -> ListNode:
        if not head:
            return None
        p = q = head
        cnt = 1
        while p.next:
            p = p.next
            cnt += 1
        p.next = head
        k %= cnt
        for _ in range(cnt-k-1):
            q = q.next
        ans = q.next
        q.next = None
        return ans

# LeetCode Medium 430. Flatten a Multilevel Doubly Linked List

tags: leetcode

問題

• Explore
• Problems

アイデア

｢前後ポインタだけでなく，子リストへのポインタも持つ連結リストが与えられる．この複数層連結リストを単層化しろ｣という問題です．

与えられる連結リストのheadは最も上の層のもので，DFSをしろということです．DFSならばあるデータ構造を使うのが楽ですね．

解法

• 次にたどるノードをスタックで管理します．
  • これによってDFSをが可能になります．
• next，child があればスタックに積みます．
  • nextを先に積むことで，後で積まれたchildノードから探索されます．

計算量

ノードの数を$N$をとする．

• 時間計算量
  • $O(N)$
• 空間計算量
  • $O(N)$

Python

"""
# Definition for a Node.
class Node:
    def __init__(self, val, prev, next, child):
        self.val = val
        self.prev = prev
        self.next = next
        self.child = child
"""

class Solution:
    def flatten(self, head: 'Node') -> 'Node':
        if not head:
            return
        
        stk = [head]
        prev = Node(0)
        while stk:
            cur = stk.pop()
            cur.prev = prev
            prev.next = cur
            prev = cur
            if cur.next:
                stk.append(cur.next)
            if cur.child:
                stk.append(cur.child)
                cur.child = None
                
        head.prev = None
        return head

# LeetCode Medium 2. Add Two Numbers

tags: leetcode

問題

• Explore
• Problems

アイデア

｢空でない2つの非負整数を表現する連結リストが与えられる．それらの桁は反対順に入れられており，それぞれ単一の桁を持つ．2つの数を足した値を連結リストで返せ｣という問題です．

問題なのは桁上がりくらいですかね．実装するだけです．

解法

リストの要素を最初から見て，最初の要素から足していけば良さそうです．

計算量

連結リストのノード数を$N$とします．

• 時間計算量
  • $O(N)$
• 空間計算量
  • $O(1)$

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        p, q = l1, l2
        cur= res = ListNode(0)
        carry = 0
        while p or q:
            l1_val = p.val if p else 0
            l2_val = q.val if q else 0
            cur_num = carry + l1_val + l2_val
            carry = cur_num // 10
            cur.next = ListNode(cur_num % 10)
            cur = cur.next
            if p:
                p = p.next
            if q:
                q = q.next
        if carry:
            cur.next = ListNode(carry)
        return res.next