# LeetCode Easy 485. Max Consecutive Ones

tags: leetcode

問題

• Explore
• Problems

アイデア

｢バイナリの配列が与えられたとき，最長の1の列を探して長さを返せ｣という問題です．

解法

最大の長さと現在連続している長さの2つを保持して解きます．

計算量

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

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

Python

class Solution:
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        max_len = 0
        cur_len = 0
        for num in nums:
            if num == 0:
                max_len, cur_len = max(max_len, cur_len), 0
            else:
                cur_len += 1
                
        return max(max_len, cur_len)

# LeetCode Easy 27. Remove Element

tags: leetcode

問題

• Explore
• Problems

アイデア

｢配列と値が与えられた時，新たにメモリを使わずに値と一致する全ての要素を取り除いてできる新たな配列の大きさを返せ｣という問題です．

実装するだけ(？)です．

解法

• どうやら内部だと(意味がわからないが)返した整数個分の配列を参照することになっているらしいです…
  • そのため，valと同じ整数の場合は末尾の要素と交換するのが良いらしいです(？？？)

計算量

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

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

Python

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        start, end = 0, len(nums) - 1
        while start <= end:
            if nums[start] == val:
                nums[start], nums[end] = nums[end], nums[start]
                end -= 1
            else:
                start += 1
        return start

# LeetCode Easy 561. Array Partition I

tags: leetcode

問題

• Explore
• Problems

アイデア

｢2n個($n \in \mathbb{N}$)の整数の配列が与えられた時に，n個のペアを作り，それぞれのペアの小さい方の和を最大にせよ｣という問題です．

最小なものは絶対にこの和に加わるということに気付くと解くことが出来ます

解法

• 配列の中でもっとも小さい要素は他のどんな数とペアになっても和に加わります．
  • そのため，ペアとなるのは残りの要素のうち最小の要素となると和が大きくなります
• これを再帰的に考えると最も小さい要素，3番目に小さい要素…と加えると良いです
• 配列をソートして2つずつ要素を取り出します．

計算量

要素の個数を$N$とします．

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

Python

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        return sum(sorted(nums)[::2])

# LeetCode Easy 14. Longest Common Prefix

tags: leetcode

問題

• Explore
• Problems

アイデア

｢複数の文字列から，共通する最長の接頭辞を探せ｣という問題です．ない場合は空の文字列を返せば良いようです．

2文字列を比較して設備時を探す，これを全ての文字列に対して行うという2つの問題に分割出来ることを使います．

解法

• 2つの文字列を比較して共通する最長の接尾辞を返す関数get_common_prefixを書きます．
• これを配列の全ての要素に左から適用するreduce関数を使います．

計算量

文字列の個数が$N$，文字列の大きさが最小で$S$とします．

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

Python

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        def get_common_prefix(s: str, t: str) -> str:
            common_length = 0

            for  i in range(0, min(len(s), len(t))):
                if s[i] != t[i]:
                    break
                common_length += 1
            
            return s[:common_length]
        
        if not strs:
            return ""
        
        return reduce(get_common_prefix, strs)

# LeetCode Easy 67. Add Binary

tags: leetcode

問題

• Explore
• Problems

アイデア

｢2つの二進数の文字列を与えられたとき，それらの和を二進数で返せ｣という問題です．

普段する計算と同じように文字列の小さい桁から見ていきます．

解法

• a，bの文字列で現在見ている箇所を指すための変数a_posとb_posを用意します．
• これらが0以上のときはその箇所の値をcarryという変数に加え，桁を上げます．
  • 2進数なのでcarryの1桁目(2で割った余り)をresの先頭に加えます．
  • そして，2で割った商を代入します．

計算量

文字列a，bの大きさをそれぞれN，Mとします．

• 時間計算量
  • aとbを走査するので$O(N + M)$
• 空間計算量
  • 答えとなる文字列を格納するのに$O(NM)$

Python

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        a_pos, b_pos = len(a)-1, len(b)-1
        res = ""
        carry = 0

        while a_pos >= 0 or b_pos >= 0 or carry:
            if a_pos >= 0:
                carry += int(a[a_pos])
                a_pos -= 1
            if b_pos >= 0:
                carry += int(b[b_pos])
                b_pos -= 1
            res = str(carry % 2) + res
            carry //= 2
        return res