LeetCode Day 31 Greedy Algorithm (1/6)

Begin Greedy Algorithm Practice !

1. Basis of the greedy algorithm

The essence of greediness is to select the local optimum at each stage so as to achieve the global optimum.

1.1 When to use greedy algorithm

There is no fixed routine for greedy, when a problem can be deduced from a local optimum to an overall optimum, then greedy can be used.

1.2 General steps of greedy algorithm

The greedy algorithm is generally divided into the following four steps:

• Decompose the problem into several sub-problems
• Find a suitable greedy strategy
• Solve the optimal solution of each subproblem
• Stack the local optimal solutions into a global optimal solution.

The steps are a bit trivial, so you won’t have to think about them in detail in practice.

Practice Questions

Question 1

455. Assign Cookies

Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie.

Each child i has a greed factor g[i], which is the minimum size of a cookie that the child will be content with; and each cookie j has a size s[j]. If s[j] >= g[i], we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.

Large biscuits can satisfy both greedy high and low children, but small biscuits can only satisfy greedy low children, so it is important to prioritise distributing the large ones to greedy high children to avoid wasting large biscuits.

So it is necessary to traverse the biscuits and children from back to front.

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g.sort()  
        s.sort() 
        index = len(s) - 1  
        result = 0  
        for i in range(len(g)-1, -1, -1):  
            if index >= 0 and s[index] >= g[i]:  
                result += 1
                index -= 1
        return result

Question 2

376. Wiggle Subsequence

A wiggle sequence is a sequence where the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with one element and a sequence with two non-equal elements are trivially wiggle sequences.

• For example, [1, 7, 4, 9, 2, 5] is a wiggle sequence because the differences (6, -3, 5, -7, 3) alternate between positive and negative.
• In contrast, [1, 4, 7, 2, 5] and [1, 7, 4, 5, 5] are not wiggle sequences. The first is not because its first two differences are positive, and the second is not because its last difference is zero.

A subsequence is obtained by deleting some elements (possibly zero) from the original sequence, leaving the remaining elements in their original order.

Given an integer array nums, return the length of the longest wiggle subsequence of nums.

At first glance it looks troublesome, because it is necessary to eliminate extraneous elements and to find the maximum length that meets the conditions. But in fact there is no need to perform any in place operations on the array, just count the lengths that meet the requirements.

Two variables, curDiff and preDiff, can be used to calculate the difference between the number of elements in the current array and the number before and after.

class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        if len(nums)<= 1:
            return len(nums)
        curDiff = 0  # current
        preDiff = 0  # previous 
        result = 1  
        for i in range(len(nums) - 1):
            curDiff = nums[i + 1] - nums[i]  
            if (preDiff <= 0 and curDiff > 0) or (preDiff >= 0 and curDiff < 0):
                result += 1  
                preDiff = curDiff  
        return result

Question 3

53. Maximum Subarray

Given an integer array nums, find the subarray with the largest sum, and return its sum.

First set an infinite small number as a starting point, and then constantly accumulate the number of the list, while comparing, encountered a relatively large number on the RESULT was given, when the accumulation of the end of this time, the value of the value becomes negative on the reset to 0, to avoid the impact on the results.

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        result = float('-inf')
        count = 0
        for i in range(len(nums)):
            count += nums[i]
            if count > result:
                result = count
            if count <= 0:
                count = 0
        return result