Neunomizuの日記

俺だけが俺だけじゃない

# LeetCode Easy 557. Reverse Words in a String III

tags: leetcode

問題

イデア

「文字列中にある単語を反転させた文字列を返せ」という問題です.

やるだけです.

解法

空白区切りで分解して,分解後の文字列を反転させます.

計算量

文字列の個数を$N$とし,それぞれの単語の最大の長さを$S$とします.

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

Python

class Solution:
    def reverseWords(self, s: str) -> str:
        return " ".join([word[::-1] for word in s.split()])

# LeetCode Medium 151. Reverse Words in a String

tags: leetcode

問題

イデア

「文字列が与えられるので,空白で区切られた単語を反転させて返せ」という問題です.

最初は完全に問題を勘違いして

" ".join([word[::-1] for word in s.split()])

と書いていました…単語の順番を反転させます.

解法

  • 文字列を空白区切りで分けます.
  • その文字列を配列にして,配列の要素の順番を反転させます.
  • そして,先頭の文字列から空白区切りで連結させます.

計算量

文字列の数を$N$,文字列の最大長を$S$とします.

  • 時間計算量
    • 分割に$O(N)$
    • 順番を反転に$O(N)$
    • 連結に$O(N)$
    • 全て合わせて$O(N)$です.
  • 空間計算量
    • 新しく配列を作るので$O(NS)$です.

Python

class Solution:
    def reverseWords(self, s: str) -> str:
        return " ".join([word for word in s.split()][::-1])

# LeetCode Easy 189. Rotate Array

tags: leetcode

問題

イデア

「1次元配列が与えられた時,kだけ右に要素をずらせ」という問題です.右端から右にずらした場合,左端に行きます.

解法

  • kを,kを配列の大きさで割った余りとします.
    • これは配列の大きさと同じ分だけ右にずらすと元の位置に要素が戻るからです.
  • こうしてできたkに関して
    • 配列の前半kに配列の後半kを加えたものを配列に代入すれば求める配列が得られます.

計算量

要素の数を$N$とします.

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

Python

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        k %= len(nums)
        nums[:] = nums[-k:] + nums[:-k]

# LeetCode Medium 209. Minimum Size Subarray Sum

tags: leetcode

問題

イデア

n個の正の整数の配列を与えられた時,s以上の和を持つ連続した部分列の最小の大きさを探せ」という問題です.ただし,部分列の大きさは最低でも2で,大きさが1のときは0を返します.

全探索をしようとすると計算量のオーダーが$O(N2)$になってしまいます.これだと時間を掛けすぎなので計算量を改善する方法を探します.

ここで,連続した部分列の話をしているので,左端と右端に注目すれば$O(N)$で問題が解けそうだと考えることができます.

解法

  • 右端を和に足していき,和がs以上になったとき,答えの部分列の長さを更新します.
  • そして,左端を取り除き,長さも短くします.

計算量

配列の要素の数を$N$とします.

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

Python

class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        min_len = float('inf')
        left, cur_sum = 0, 0
        for right in range(len(nums)):
            cur_sum += nums[right]
            while cur_sum >= s:
                min_len = min(min_len, right - left + 1)
                cur_sum -= nums[left]
                left += 1
        return min_len if min_len != float('inf') else 0

# LeetCode Easy 28. Implement strStr()

tags: leetcode

問題

イデア

「2つの文字列を与えられた時,片方の文字列haystackに別の文字列needleが含まれているなら,needlehaystackのどの位置から始まるか添字を返せ」という問題です.

needleが空文字のときは0を返します.

愚直に実装すれば良いと思います.

解法

  • 全探索します

計算量

文字列の長さをそれぞれ$N$,$M$とします.

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

Python

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if needle == "":
            return 0
        for start in range(len(haystack) - len(needle) + 1):
            if haystack[start:start+len(needle)] == needle:
                return start
        return -1