# LeetCode Medium 54. Spiral Matrix

tags: leetcode

問題

• Explore
• Problems

アイデア

｢m x n行列が与えられたとき，右回りに螺旋状に動いた際に通る要素の配列にして返せ｣という問題です．

螺旋状に動くとは左上→右上→右下→左下→...のように動くことです(直感的には)．

これを如何に実直に実装すればいいのかを考えます．

解法

• visitedというbooleanの値の配列の配列を用意して，この配列を使って一度通ったかどうかを確認します．

計算量

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

Python

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if not matrix:
            return []
    
        max_row, max_col = len(matrix), len(matrix[0])
        visited = [[False] * max_col for _ in matrix]
        res = []
        dir_row = [0, 1, 0, -1]
        dir_col = [1, 0, -1, 0]
        row = col = di = 0
        for _ in range(max_row * max_col):
            res.append(matrix[row][col])
            visited[row][col] = True
            next_row, next_col = row + dir_r[di], col + dir_c[di]
            if 0 <= next_row < max_row and 0 <= next_col < max_col and not visited[next_row][next_col]:
                row, col = next_row, next_col
            else:
                di = (di + 1) % 4
                row, col = row + dir_r[di], col + dir_col[di]
        return res

# LeetCode Medium 498. Diagonal Traverse

tags: leetcode

問題

• Explore
• Problems

アイデア

｢M x Nの行列が与えられたとき，対角線方向にジグザグに動いた時に通る要素を返せ｣という問題です．

このような問題で重要なのは問題を小分けすることで，ここでは最初に右上から左下への対角線方向に進んだ際に通る要素を考え，次にジグザグに動くことを考えます．

解法

• { [0, 0] } -> { [0, 1], [1, 0] } -> { [0, 2], [1, 1], [2, 0] } -> ...という風に進むと考えます
  • この時，ある規則で出現する配列群([0, 1], [1, 0]などの塊)の行と列の添字の和は1ずつ増えていき，最大の和は行列の行と列の和-1です．
  • また，もう一点注目するべきことがあります．3 x 3行列で考えます．
    • 上の例の後に，{ [1, 2], [2, 1] } -> { [2, 2] }となります．
    • つまり，行の添字が行列の行の長さよりも大きくなると数字のパターンが変わります．
• これを考えれば，後は配列群の行と列の添字の和で答えの配列に逆さに加えるかどうかを考えれば良いです．

計算量

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

Python

class Solution:
    def findDiagonalOrder(self, matrix: List[List[int]]) -> List[int]:
        if not matrix or not matrix[0]:
            return []
        height, width = len(matrix), len(matrix[0])
        result = []
        
        for diag in range(height + width - 1):
            tmp = []
            row, col = 0, 0
            if diag < width:
                row, col = 0, diag
            else:
                row, col = diag - width + 1, width - 1
            
            while row < height and col > -1:
                tmp.append(matrix[row][col])
                row += 1
                col -= 1
            
            if diag % 2 == 0:
                result.extend(tmp[::-1])
            else:
                result.extend(tmp)
        return result        

# LeetCode Medium 380. Insert Delete GetRandom O(1)

tags: leetcode

問題

• Explore
• Problems

アイデア

ハッシュ関数を用いたSetを実装する問題です．

解法

• 辞書を使うことで，実装します．

計算量

以下は時間計算量，空間計算量の順です．

• __init__
  • $O(1)$
  • $O(1)$
• insert
  • $O(1)$
  • $O(1)$
• remove
  • $O(1)$
  • $O(1)$
• `getRandom
  • $O(1)$
  • $O(1)$

Python

class RandomizedSet:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.nums = []
        self.idx = {}
        
    def insert(self, val: int) -> bool:
        """
        Inserts a value to the set. Returns true if the set did not already contain the specified element.
        """
        if val in self.idx:
            return False
        
        self.nums.append(val)
        self.idx[val] = len(self.nums) - 1
        return True
        

    def remove(self, val: int) -> bool:
        """
        Removes a value from the set. Returns true if the set contained the specified element.
        """
        if val not in self.idx:
            return False
        
        idx, last = self.idx[val], self.nums[-1]
        self.nums[idx], self.idx[last] = last, idx
        self.nums.pop()
        del self.idx[val]
        return True
        

    def getRandom(self) -> int:
        """
        Get a random element from the set.
        """
        return random.choice(self.nums)


# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()

# LeetCode Medium 347. Top K Frequent Elements

tags: leetcode

問題

• Explore
• Problems

アイデア

空でない整数列が与えられた時，$k$個の最も頻繁に現れる整数を返せという問題です．

整数と登場回数を結びつけるようなデータ構造を使えばいいですね．

解法

• 連想配列を使ってkey=整数，value=登場回数とします．
• 登場回数で降順にソートし，先頭k個を返します．

計算量

numsの大きさを$N$とします．

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

Python

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        num_occur = {}
        for num in nums:
            if num in num_occur:
                num_occur[num] += 1
            else:
                num_occur[num] = 1
                
        res = [key for key, value in sorted(num_occur.items(), key=lambda x: x[1], reverse=True)]
        return res[:k]

# LeetCode Medium 454. 4Sum II

tags: leetcode

問題

• Explore
• Problems

アイデア

整数列A，B，C，Dが与えられるとき，それぞれの要素を1つずつ取り出してその総和が0となるようなものは何通り考えられるかを答えろという問題です．

ナイーブに解こうとすると$O(N⁴)$が必要ですが，連想配列を使うことで答えを記録すれば計算量を落とせそうです．

解法

• AとBの要素の組み合わせを全探索し，その値をkeyとして，登場回数をvalueとする連想配列を作ります．
• 次にCとDの要素の組み合わせを全探索します．
  • a + b + c + dであれば，a + b = -c - dであるので，CとDの要素の和を負にしたものを連想配列がkeyに持つならば，その登場回数を答えに加えれば良いです．

計算量

配列の最大長を$N$とします．

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

Python

class Solution:
    def fourSumCount(self, A: List[int], B: List[int], C: List[int], D: List[int]) -> int:
        complement_dic = {}
        res = 0
        for a in A:
            for b in B :
                if a + b in complement_dic:
                    complement_dic[a+b] += 1
                else :
                    complement_dic[a+b] = 1
        for c in C :
            for d in D :
                if -c - d in complement_dic:
                    res += complement_dic[-c-d]
        return res