Greedy algorithm: 455. Distributing cookies, 376. Swing sequence, 53. Maximum subarray sum

Tips: Live hard and have a happy day

Article directory

455. Distributing cookies
- Problem-solving ideas
- Problems encountered
- Code
- Summary of the question
376. Swing sequence
- Problem-solving ideas
- Problems encountered
- Code
- Summary of the question
53. Maximum subarray sum
- Problem-solving ideas
- Problems encountered
- Code
- Summary of the question
Today’s experience

455. Distributing cookies

Question link: 455. Distributing cookies

Problem-solving ideas

Greedy algorithm: By achieving the local optimal solution, the global optimal solution is achieved. The local optimal solution of this problem is to feed large biscuits to those with big appetites. Make full use of the size of the biscuits to feed one child. The global optimal solution is to feed as many children as possible.
First sort the biscuit array and the children’s array, and then traverse the children’s array from back to front, using large biscuits to satisfy those with big appetites first, and count the number of satisfied children.
An index is used to control the traversal of the biscuit array. When traversing the biscuits, there is no for loop, but a self-decrement method is used. This is also a common technique.

Problems encountered

The traversal is wrong, different ideas traverse differently

Code implementation

Big cookies satisfy big kids

var findContentChildren = function (g, s) {<!-- -->
    //The principle of greed is: use as big biscuits as possible to satisfy children with big appetites
    let result = 0
    //Sort first
    g = g.sort((a, b) => a - b)
    s = s.sort((a, b) => a - b)
    //The serial number of the largest cookie
    let index = s.length - 1
    //Traverse the children - find the child with the biggest appetite first
    for (let i = g.length - 1; i >= 0; i--) {<!-- -->
        //Biscuits need to be bigger than the child's appetite to feed a child
        if (index >= 0 & amp; & amp; g[i] <= s[index]) {<!-- -->
            index--
            result++
        }
    }
    return result
};

Small biscuits satisfy children

var findContentChildren = function (g, s) {<!-- -->
    //The principle of greed is: use as big biscuits as possible to satisfy children with big appetites
    let result = 0
    //Sort first
    g = g.sort((a, b) => a - b)
    s = s.sort((a, b) => a - b)
    //The serial number of the smallest child
    let index = 0
    //Traverse the cookies. If the smallest cookie cannot feed the smallest child, then the cookie + 1 until you find the cookie that can feed the smallest child.
    for (let i = 0; i < s.length; i + + ) {<!-- -->
        //Biscuits need to be bigger than the child's appetite to feed a child
        if (index >= 0 & amp; & amp; s[i] >= g[index]) {<!-- -->
            index++
            result++
        }
    }
    return result
};

Question summary

The big biscuit is eaten first: Traverse the children, starting from the big child and the big biscuit. If the big biscuit cannot feed the big biscuit, the child will become smaller i– until a big biscuit is found. up to the children
Prioritize the children to be fed: Traverse the cookies, starting with small cookies and children. If the child cannot be fed by the small cookies, the cookies will become larger i + + until you find a child that can be fed. of cookies
Think clearly about the local optimum and the global optimum. If you feel that the local optimum can lead to the global optimum, and you can’t think of a counterexample, then give greed a try

376. Swing sequence

Question link: 376. Swing sequence

Problem-solving ideas

A subsequence is obtained by removing some (or optional) elements from the original sequence, leaving the remaining elements in their original order.

Local optimum: Delete the nodes on the monotonic slope (excluding nodes at both ends of the monotonic slope), then this slope can have two local peaks.
Overall optimal: the entire sequence has the most local peaks, thereby achieving the longest swing sequence

In actual operation, you don’t even need to delete the operation, because the question requires the length of the longest swing subsequence, so you only need to count the number of peaks in the array, let the peaks remain as peak as possible, and then Delete nodes on a single slope
There are three situations to consider in this question:
Case 1: There is a flat slope in the uphill and downhill slopes: delete the three 2 rules on the left, then when prediff = 0 & & curdiff < 0, a peak value will also be recorded, because it deletes all the same elements before and leaves The peak value below

Case 2: If there are only 2 elements at the beginning and end of the array, it can be assumed that there is a number at the front of the array, which is the same as the first number
Situation 3: There is a flat slope in the monotonic slope: we need to update prediff when the slope swing changes, so that prediff will not change when there is a flat slope in the monotonic interval, causing our misjudgment

Problems encountered

There is an error in the assignment of prediff

Code implementation

greedy algorithm

var wiggleMaxLength = function (nums) {<!-- -->
    let result = 1
    if (nums.length <= 1) return nums.length
    let prediff = 0
    let curdiff = 0
    for (let i = 0; i < nums.length; i + + ) {<!-- -->
        curdiff = nums[i + 1] - nums[i]
        if (prediff <= 0 & amp; & amp; curdiff > 0 || prediff >= 0 & amp; & amp; curdiff < 0) {<!-- -->
            result++
            prediff = curdiff
        }
    }
    return result
};

Question summary

The essence of the abnormal situation in this question is to consider flat slopes. There are two types of flat slopes, one is a flat slope in the middle of the top and bottom, and the other is monotonous and has a flat slope.

53. Maximum sum of subarrays

Question link: 53. Maximum sum of subarrays

Problem-solving ideas

Local optimum: give up immediately when the current “continuous sum” is a negative number and recalculate the “continuous sum” from the next element, because the “continuous sum” of negative numbers plus the next element will only become smaller and smaller.
Global optimal: choose the largest “continuous sum”
Traverse nums and accumulate with count from the beginning. If count becomes negative once added to nums[i], then count should be accumulated from 0 starting from nums[i + 1], because the count that has become negative will only drag down the count. sum. This is equivalent to constantly adjusting the starting position of the maximum suborder and interval in the brute force solution.
The end position of the interval is actually recorded in time if count reaches the maximum value. if (count > result) result = count;This is equivalent to using result to record the maximum subsequence and interval sum (in disguise, it is adjusting the end position)

Problems encountered

The result value defaults to an infinitesimal value

Code implementation

greedy algorithm

var maxSubArray = function (nums) {<!-- -->
    //Infinitely small numbers
    let result = -Infinity
    let count = 0//accumulate
    for (let i = 0; i < nums.length; i + + ) {<!-- -->
        //Accumulate
        count + = nums[i]
       // Take the cumulative maximum value of the interval (equivalent to continuously determining the end position of the maximum subsequence)
        if (count > result) {<!-- -->
            result = count
        }
        // Equivalent to resetting the starting position of the maximum subsequence, because when encountering a negative number, the sum must be lowered
        if (count < 0) {<!-- -->
            count = 0
        }
    }
    return result
};

Question summary

The code is very simple, but the greedy idea is difficult to think about. It seems like common sense, but it is actually very difficult.

Today’s experience

After a preliminary understanding of the greedy algorithm, I feel that it is to find the optimal solution in daily life. I may have performed the greedy algorithm without realizing it before.