Greedy

本記事は以下記事の一部です。

NeetCode 150 全問の解き方とポイントまとめ & 感想

GreedyはGreedyで解くと知っている状態で始めたらそんなに難しくない気がする。Greedyで解けるんだと気づけないと最適解に辿り着けない。

77. Maximum Subarray

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

Problem

You are given an integer array nums where each element nums[i] indicates your maximum jump length at that position.

Return true if you can reach the last index starting from index 0, or false 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

Problem

You are given an integer array nums where each element nums[i] indicates your maximum jump length at that position.

Return true if you can reach the last index starting from index 0, or false 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

Problem

You are given an integer array nums where each element nums[i] indicates your maximum jump length at that position.

Return true if you can reach the last index starting from index 0, or false 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

Problem

You are given an integer array hand where hand[i] is the value written on the ith card and an integer groupSize.

You want to rearrange the cards into groups so that each group is of size groupSize, and card values are consecutively increasing by 1.

Return true if it's possible to rearrange the cards in this way, otherwise, return false.

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

Problem

You are given a 2D array of integers triplets, where triplets[i] = [ai, bi, ci] represents the ith triplet. You are also given an array of integers target = [x, y, z] which is the triplet we want to obtain.

To obtain target, you may apply the following operation on triplets zero or more times:

Choose two different triplets triplets[i] and triplets[j] and update triplets[j] to become [max(ai, aj), max(bi, bj), max(ci, cj)].
* E.g. if triplets[i] = [1, 3, 1] and triplets[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 obtain target as an element of triplets, or false 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

Problem

You are given a 2D array of integers triplets, where triplets[i] = [ai, bi, ci] represents the ith triplet. You are also given an array of integers target = [x, y, z] which is the triplet we want to obtain.

To obtain target, you may apply the following operation on triplets zero or more times:

Choose two different triplets triplets[i] and triplets[j] and update triplets[j] to become [max(ai, aj), max(bi, bj), max(ci, cj)].
* E.g. if triplets[i] = [1, 3, 1] and triplets[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 obtain target as an element of triplets, or false 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

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

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