Code Caprice Algorithm Training Camp 4th Phase 31st Day | Theoretical Basis, 455. Distributing Cookies, 376. Swing Sequence, 53. Maximum Subsequence Sum

theoretical basis

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

To be honest, the greedy algorithm does not have a fixed routine.

455. Distributing cookies

# Let's say you're a great parent and want to give your kids some cookies. However, each child is given no more than one cookie.
# For each child i, there is an appetite value g[i], which is the smallest size of biscuit that can satisfy the child's appetite; and each biscuit j has a size s[j]. If s[j] >= g[i], we can pass this cookie
 # j is assigned to child i, and this child will be satisfied. Your goal is to satisfy as many children as possible and output this maximum value.
#
# Example 1:
# Input: g = [1, 2, 3], s = [1, 1]
# output: 1
 # Explanation:
# You have three children and two biscuits, and the appetite values ​​of the three children are: 1, 2, 3. Although you have two small biscuits, since they both have a size of 1, you can only satisfy a child with an appetite value of 1.
# So you should output 1.
#
# Example 2:
# Input: g = [1, 2], s = [1, 2, 3]
# output: 2
 # Explanation:
# You have two children and three biscuits, and the appetite values ​​of the two children are 1, 2 respectively. You have enough cookies in both quantity and size to keep all the kids satisfied. So you should output 2.
class Solution:
    def findContentChildren(self, g:[int], s:[int]) -> int:
        count = 0
        if not s:
            return count
        s.sort(reverse=True)
        g.sort(reverse=True)
        # The local optimum here is to feed big biscuits to those with big appetites, and make full use of the biscuit size to feed one. The global optimum is to feed as many children as possible
        index = 0
        for i in range(len(g)):
            if index < len(s) and s[index] >= g[i]:
                index += 1
                count += 1
        return count


if __name__ == '__main__':
    g = [1, 2, 3]
    s = [3]
    tmp = Solution()
    res = tmp.findContentChildren(g,s)
    print(res)

376. Wobble Sequence

# A sequence of numbers is called a wiggle sequence if the difference between consecutive numbers strictly alternates between positive and negative. The first difference (if any) may be positive or negative. has only one element or has two unequal elements
 A sequence of # is also considered a wobble sequence.
# For example, [1, 7, 4, 9, 2, 5] is a swing sequence, because the difference (6, -3, 5, -7, 3) is positive and negative alternately.
# On the contrary, [1, 4, 7, 2, 5] and [1, 7, 4, 5, 5] are not swing sequences, the first sequence is because its first two differences are positive numbers, the second sequence because its last difference is zero.
# A subsequence can be obtained by deleting some (or not) elements from the original sequence, and the remaining elements maintain their original order.
#
#Give you an integer array nums, return the length of the longest subsequence in nums as a swing sequence.
#
# Example 1:
# Input: nums = [1, 7, 4, 9, 2, 5]
# output: 6
 # Explanation: The entire sequence is a swing sequence, and the difference between each element is (6, -3, 5, -7, 3).
#
# Example 2:
# Input: nums = [1, 17, 5, 10, 13, 15, 10, 5, 16, 8]
# output: 7
 # Explanation: This sequence contains several length 7 wobble sequences. One of them is [1, 17, 10, 13, 10, 16, 8] and the difference between the elements is (16, -7, 3, -3, 6, -8) .
#
# Example 3:
# Input: nums = [1, 2, 3, 4, 5, 6, 7, 8, 9]
# output: 2
class Solution:
    def wiggleMaxLength(self, nums:[int]) -> int:
        # This is greed
        size = len(nums)
        seq = []
        flag = 1 #Use flag to mark the positive and negative of the previous difference, positive 1 negative 0
        for i in range(1, size):
            tmp = nums[i] - nums[i - 1]
            if tmp == 0: # The requirement in the title is to alternate between positive and negative numbers, so skip 0
                continue
            if seq:
                if flag and tmp < 0:
                    seq.append(tmp)
                    flag = 0
                elif flag == 0 and tmp > 0:
                    seq.append(tmp)
                    flag = 1
            else:
                if tmp < 0: # If the first difference is negative, the flag must be set to False
                    flag = 0
                seq.append(tmp)
        return len(seq)+1

if __name__ == '__main__':
    nums = [1, 7, 4, 9, 2, 5]
    nums = [1, 17, 5, 10, 13, 15, 10, 5, 16, 8]
    nums = [0,0]
    nums = [3,3,3,2,5]
    # nums = [84]
    # nums= [1, 2, 3, 4, 5, 6, 7, 8, 9]
    tmp = Solution()
    res = tmp.wiggleMaxLength(nums)
    print(res)

53. Maximum Subsequence Sum

#Give you an integer array nums, please find a continuous sub-array with the maximum sum (the sub-array contains at least one element), and return its maximum sum.
# A subarray is a contiguous part of an array.
#
# Example 1:
# Input: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
# output: 6
 # Explanation: The sum of consecutive subarrays [4, -1, 2, 1] is the largest, which is 6.
#
# Example 2:
# Input: nums = [1]
# output: 1
#
# Example 3:
# Input: nums = [5, 4, -1, 7, 8]
# Output: 23
class Solution:
    def maxSubArray(self, nums: [int]) -> int:
        res = float('-inf')
        count = 0
        for i in range(len(nums)):
            count += nums[i]
            if count > res: # Take the maximum value accumulated in the interval (equivalent to continuously determining the termination position of the largest subsequence)
                res = count
            if count < 0: # It is equivalent to resetting the starting position of the largest subsequence, because the sum must be lowered when encountering a negative number
                count = 0
        return res

    def maxSubArray2(self, nums: [int]) -> int:
        # dp wording
        if len(nums) == 0:
            return 0
        dp = []
        dp.append(nums[0])
        res = dp[0]
        for i in range(1,len(nums)):
            dp.append(max(dp[i-1]+nums[i],nums[i]))
            if dp[i] > res:
                res = dp[i]
        return res

if __name__ == '__main__':
    nums = [5, 4, -1, 7, 8]
    # nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
    tmp = Solution()
    # res = tmp.maxSubArray(nums)
    res = tmp.maxSubArray2(nums)
    print(res)

Tags: Algorithm Dynamic Programming greedy algorithm

Posted by yhingsmile on Wed, 21 Dec 2022 17:11:06 +0300