NeetCode 150 全問の解き方とポイントまとめ Greedy
Greedy
本記事は以下記事の一部です。
NeetCode 150 全問の解き方とポイントまとめ & 感想
GreedyはGreedyで解くと知っている状態で始めたらそんなに難しくない気がする。Greedyで解けるんだと気づけないと最適解に辿り着けない。
77. Maximum Subarray
Link | |
Difficulty (Easy, Medium, Hard) | Medium |
Time Complexity | O (N) |
Space Complexity | O(1) |
The personal need for review (1 ~ 10) | 2 |
Memo | 愚直にやるとO(N^2)になるけど、Kadane's Algorithm を使うとO(N)で解ける。これまでの累積値とそこだけの値を比較して、大きい方に累積値を置き換えつつ、max_totalを随時更新する。Kadane's Algorithmの登場頻度高い。 |
Problem
Given an array of integers
nums
, find the subarray with the largest sum and return the sum.A subarray is a contiguous non-empty sequence of elements within an array.
Example 1:
Input: nums = [2,-3,4,-2,2,1,-1,4] Output: 8
Copy
Explanation: The subarray [4,-2,2,1,-1,4] has the largest sum 8.
Example 2:
Input: nums = [-1] Output: -1
Copy
Constraints:
1 <= nums.length <= 1000
-1000 <= nums[i] <= 1000
Solution
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
total = 0
max_total = -math.inf
for num in nums:
if total + num < num:
total = num
else:
total += num
max_total = max(max_total, total)
return max_total
78. Jump Game
Link | |
Difficulty (Easy, Medium, Hard) | Medium |
Time Complexity | O (N) |
Space Complexity | O(1) |
The personal need for review (1 ~ 10) | 3 |
Memo | Jump Gameはシリーズがあって後半はDPで解く問題になる。1と2はGreedyで解けるので比較的簡単。 もっとも遠い場所がlast indexになるかどうかだけ見てればok。 イテレート中に、現在のindexがfarthestよりも大きくなってれば、もうそこには辿り着けないのでFalseを返す |
Problem
You are given an integer array
nums
where each elementnums[i]
indicates your maximum jump length at that position.Return
true
if you can reach the last index starting from index0
, orfalse
otherwise.Example 1:
Input: nums = [1,2,0,1,0] Output: true
Copy
Explanation: First jump from index 0 to 1, then from index 1 to 3, and lastly from index 3 to 4.
Example 2:
Input: nums = [1,2,1,0,1] Output: false
Copy
Constraints:
1 <= nums.length <= 1000
0 <= nums[i] <= 1000
Solution
class Solution:
def canJump(self, nums: List[int]) -> bool:
farthest = 0
for i, num in enumerate(nums):
if i > farthest:
return False
farthest = max(farthest, i + num)
if farthest >= len(nums) - 1:
return True
return False
79. Jump Game II
Link | |
Difficulty (Easy, Medium, Hard) | Medium |
Time Complexity | O (N) |
Space Complexity | O(1) |
The personal need for review (1 ~ 10) | 4 |
Memo |
|
Problem
You are given an integer array
nums
where each elementnums[i]
indicates your maximum jump length at that position.Return
true
if you can reach the last index starting from index0
, orfalse
otherwise.Example 1:
Input: nums = [1,2,0,1,0] Output: true
Copy
Explanation: First jump from index 0 to 1, then from index 1 to 3, and lastly from index 3 to 4.
Example 2:
Input: nums = [1,2,1,0,1] Output: false
Copy
Constraints:
1 <= nums.length <= 1000
0 <= nums[i] <= 1000
Solution
class Solution:
def jump(self, nums: List[int]) -> int:
if len(nums) <= 1:
return 0
farthest = 0
jumps = 0
current_end = 0
for i, num in enumerate(nums):
if i > farthest:
return -1
farthest = max(farthest, i + num)
if i == current_end:
jumps += 1
current_end = farthest
if current_end == len(nums) - 1:
break
return jumps
80. Gas Station
Link | |
Difficulty (Easy, Medium, Hard) | Medium |
Time Complexity | O (N) |
Space Complexity | O(1) |
The personal need for review (1 ~ 10) | 5 |
Memo |
|
Problem
You are given an integer array
nums
where each elementnums[i]
indicates your maximum jump length at that position.Return
true
if you can reach the last index starting from index0
, orfalse
otherwise.Example 1:
Input: nums = [1,2,0,1,0] Output: true
Copy
Explanation: First jump from index 0 to 1, then from index 1 to 3, and lastly from index 3 to 4.
Example 2:
Input: nums = [1,2,1,0,1] Output: false
Copy
Constraints:
1 <= nums.length <= 1000
0 <= nums[i] <= 1000
Solution
class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
total_gas = 0
total_cost = 0
current_gas = 0
ans_i = 0
for i in range(len(gas)):
total_gas += gas[i]
total_cost += cost[i]
current_gas += gas[i] - cost[i]
if current_gas < 0:
# 次のindexから始める
current_gas = 0
ans_i = i + 1
# 全体を通してgasよりもcostの方が大きければ一周することはできない
if total_cost > total_gas:
return -1
return ans_i
81. Hand of Straights
Link | |
Difficulty (Easy, Medium, Hard) | Medium |
Time Complexity | O (U Log U groupSize) |
Space Complexity | O(U) |
The personal need for review (1 ~ 10) | 7 |
Memo |
Problem
You are given an integer array
hand
wherehand[i]
is the value written on theith
card and an integergroupSize
.You want to rearrange the cards into groups so that each group is of size
groupSize
, and card values are consecutively increasing by1
.Return
true
if it's possible to rearrange the cards in this way, otherwise, returnfalse
.Example 1:
Input: hand = [1,2,4,2,3,5,3,4], groupSize = 4 Output: true
Copy
Explanation: The cards can be rearranged as
[1,2,3,4]
and[2,3,4,5]
.Example 2:
Input: hand = [1,2,3,3,4,5,6,7], groupSize = 4 Output: false
Copy
Explanation: The closest we can get is
[1,2,3,4]
and[3,5,6,7]
, but the cards in the second group are not consecutive.Constraints:
1 <= hand.length <= 1000
0 <= hand[i] <= 1000
1 <= groupSize <= hand.length
Solution
from collections import defaultdict, Counter
class Solution:
def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:
# handのサイズがgroupSizeで割り切れなかったらそもそも分割できないのでFalseを返す
if len(hand) % groupSize != 0:
return False
# hand_count_map
hand_count_map = Counter(hand) # hand -> count of hand
# hand
# put hand if the coiunt of hand is more than 0
min_heap = list(hand_count_map.keys())
heapq.heapify(min_heap)
while min_heap:
# 最小値からloopを回す
min_val = min_heap[0]
for i in range(min_val, min_val + groupSize):
if hand_count_map[i] == 0:
# もしmapに値がなければ穴が空いてるのでFalseを返す
return False
hand_count_map[i] -= 1
if hand_count_map[i] == 0:
top = heapq.heappop(min_heap)
# 最小値から順番になくなっていかなきゃいけない
if i != top:
return False
return True
82. Merge Triplets to Form Target Triplet
Link | |
Difficulty (Easy, Medium, Hard) | Medium |
Time Complexity | O(N) |
Space Complexity | O(1) |
The personal need for review (1 ~ 10) | 5 |
Memo |
|
Problem
You are given a 2D array of integers
triplets
, wheretriplets[i] = [ai, bi, ci]
represents theith
triplet. You are also given an array of integerstarget = [x, y, z]
which is the triplet we want to obtain.To obtain
target
, you may apply the following operation ontriplets
zero or more times:Choose two different triplets
triplets[i]
andtriplets[j]
and updatetriplets[j]
to become[max(ai, aj), max(bi, bj), max(ci, cj)]
.
* E.g. iftriplets[i] = [1, 3, 1]
andtriplets[j] = [2, 1, 2]
,triplets[j]
will be updated to[max(1, 2), max(3, 1), max(1, 2)] = [2, 3, 2]
.Return
true
if it is possible to obtaintarget
as an element oftriplets
, orfalse
otherwise.Example 1:
Input: triplets = [[1,2,3],[7,1,1]], target = [7,2,3] Output: true
Copy
Explanation:
Choose the first and second triplets, update the second triplet to be [max(1, 7), max(2, 1), max(3, 1)] = [7, 2, 3].Example 2:
Input: triplets = [[2,5,6],[1,4,4],[5,7,5]], target = [5,4,6] Output: false
Copy
Constraints:
1 <= triplets.length <= 1000
1 <= ai, bi, ci, x, y, z <= 100
Solution
class Solution:
def mergeTriplets(self, triplets: List[List[int]], target: List[int]) -> bool:
goods = set() # index
for ai, bi, ci in triplets:
if ai > target[0] or bi > target[1] or ci > target[2]:
continue
if ai == target[0]:
goods.add(0)
if bi == target[1]:
goods.add(1)
if ci == target[2]:
goods.add(2)
return len(goods) == 3
83. Merge Triplets to Form Target
Link | |
Difficulty (Easy, Medium, Hard) | Medium |
Time Complexity | O(N) |
Space Complexity | O(1) |
The personal need for review (1 ~ 10) | 5 |
Memo |
Problem
You are given a 2D array of integers
triplets
, wheretriplets[i] = [ai, bi, ci]
represents theith
triplet. You are also given an array of integerstarget = [x, y, z]
which is the triplet we want to obtain.To obtain
target
, you may apply the following operation ontriplets
zero or more times:Choose two different triplets
triplets[i]
andtriplets[j]
and updatetriplets[j]
to become[max(ai, aj), max(bi, bj), max(ci, cj)]
.
* E.g. iftriplets[i] = [1, 3, 1]
andtriplets[j] = [2, 1, 2]
,triplets[j]
will be updated to[max(1, 2), max(3, 1), max(1, 2)] = [2, 3, 2]
.Return
true
if it is possible to obtaintarget
as an element oftriplets
, orfalse
otherwise.Example 1:
Input: triplets = [[1,2,3],[7,1,1]], target = [7,2,3] Output: true
Copy
Explanation:
Choose the first and second triplets, update the second triplet to be [max(1, 7), max(2, 1), max(3, 1)] = [7, 2, 3].Example 2:
Input: triplets = [[2,5,6],[1,4,4],[5,7,5]], target = [5,4,6] Output: false
Copy
Constraints:
1 <= triplets.length <= 1000
1 <= ai, bi, ci, x, y, z <= 100
Solution
class Solution:
def mergeTriplets(self, triplets: List[List[int]], target: List[int]) -> bool:
goods = set() # index
for ai, bi, ci in triplets:
if ai > target[0] or bi > target[1] or ci > target[2]:
continue
if ai == target[0]:
goods.add(0)
if bi == target[1]:
goods.add(1)
if ci == target[2]:
goods.add(2)
return len(goods) == 3
84. Partition Labels
Link | |
Difficulty (Easy, Medium, Hard) | Medium |
Time Complexity | O(N) |
Space Complexity | O(N) |
The personal need for review (1 ~ 10) | 5 |
Memo |
|
Problem
You are given a string
s
consisting of lowercase english letters.We want to split the string into as many substrings as possible, while ensuring that each letter appears in at most one substring.
Return a list of integers representing the size of these substrings in the order they appear in the string.
Example 1:
Input: s = "xyxxyzbzbbisl" Output: [5, 5, 1, 1, 1]
Copy
Explanation: The string can be split into
["xyxxy", "zbzbb", "i", "s", "l"]
.Example 2:
Input: s = "abcabc" Output: [6]
Copy
Constraints:
1 <= s.length <= 100
Solution
class Solution:
def partitionLabels(self, s: str) -> List[int]:
# character -> index of the char last appears
char_lasti_map = {}
for i, c in enumerate(s):
char_lasti_map[c] = i
res = []
starti = 0
lasti = -1
for i, c in enumerate(s):
lasti = max(lasti, char_lasti_map[c])
if i == lasti:
res.append(i - starti + 1)
starti = i + 1
return res
85. Valid Parenthesis String
Link | |
Difficulty (Easy, Medium, Hard) | Medium |
Time Complexity | O(N) |
Space Complexity | O(N) |
The personal need for review (1 ~ 10) | 5 |
Memo |
|
Problem
You are given a string
s
consisting of lowercase english letters.We want to split the string into as many substrings as possible, while ensuring that each letter appears in at most one substring.
Return a list of integers representing the size of these substrings in the order they appear in the string.
Example 1:
Input: s = "xyxxyzbzbbisl" Output: [5, 5, 1, 1, 1]
Copy
Explanation: The string can be split into
["xyxxy", "zbzbb", "i", "s", "l"]
.Example 2:
Input: s = "abcabc" Output: [6]
Copy
Constraints:
1 <= s.length <= 100
Solution
class Solution:
def checkValidString(self, s: str) -> bool:
left_stack = [] # (index)
star_stack = [] # (index)
for i, c in enumerate(s):
if c == ')':
if left_stack:
left_stack.pop()
elif star_stack:
star_stack.pop()
else:
return False
elif c == '(':
left_stack.append(i)
else:
star_stack.append(i)
while left_stack and star_stack and left_stack[-1] < star_stack[-1]:
left_stack.pop()
star_stack.pop()
return not left_stack