# 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
が含まれているなら,needle
がhaystack
のどの位置から始まるか添字を返せ」という問題です.
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