LeetCode DayGreedy Algorithm Part 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.

Example 1:

Input: g = [1,2,3], s = [1,1]
Output: 1
Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3.
And even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content.
You need to output 1.
Example 2:

Input: g = [1,2], s = [1,2,3]
Output: 2
Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2.
You have 3 cookies and their sizes are big enough to gratify all of the children,
You need to output 2.

Constraints:

1 <= g.length <= 3 * 104
0 <= s.length <= 3 * 104
1 <= g[i], s[j] <= 231 - 1

    public int findContentChildren(int[] g, int[] s) {
        // avoid null pointer
        if(g.length == 0 || s.length ==0){
            return 0;
        }
        // 2 * nlogn
        Arrays.sort(g);
        Arrays.sort(s);

        int i = 0;
        int j = 0;
        int count = 0;
        while(i < g.length && j < s.length){
            if(g[i] <= s[j]){
                i++;
                j++;
                count++;
            } else{
                j++;
            }
        }
        return count;   
    }

time : n`logn

Another version for loop
`
public int findContentChildren(int[] g, int[] s) {
// avoid null pointer
if(g.length == 0 || s.length ==0){
return 0;
}
// 2 * nlogn
Arrays.sort(g);
Arrays.sort(s);

    int j = 0;
    int count = 0;
    for(int i=0; i<s.length && j<g.length; i++){
        if(s[i] >= g[j]){
            j++;
            count++;
        }
    }
    return count;   
}


</p>
<p>`</p>

<h2>
  
  
  376. Wiggle Subsequence
</h2>

<p>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.</p>

<p>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.<br>
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.<br>
A subsequence is obtained by deleting some elements (possibly zero) from the original sequence, leaving the remaining elements in their original order.</p>

<p>Given an integer array nums, return the length of the longest wiggle subsequence of nums.</p>

<p>Example 1:</p>

<p>Input: nums = [1,7,4,9,2,5]<br>
Output: 6<br>
Explanation: The entire sequence is a wiggle sequence with differences (6, -3, 5, -7, 3).<br>
Example 2:</p>

<p>Input: nums = [1,17,5,10,13,15,10,5,16,8]<br>
Output: 7<br>
Explanation: There are several subsequences that achieve this length.<br>
One is [1, 17, 10, 13, 10, 16, 8] with differences (16, -7, 3, -3, 6, -8).<br>
Example 3:</p>

<p>Input: nums = [1,2,3,4,5,6,7,8,9]<br>
Output: 2</p>

<p>Constraints:</p>

<p>1 <= nums.length <= 1000<br>
0 <= nums[i] <= 1000</p>

<p>Follow up: Could you solve this in O(n) time?</p>

<p>`<br>
    public int wiggleMaxLength(int[] nums) {<br>
        if(nums.length == 0){<br>
            return 0;<br>
        }<br>
        int count = 1;<br>
        int preFlag = 0;<br>
        int pre = nums[0];</p>

<pre class="brush:php;toolbar:false">    for(int i=1; i<nums.length; i++){
        if(nums[i]-nums[i-1] != 0){
            int flag = (nums[i]-nums[i-1])/Math.abs(nums[i]-nums[i-1]);

            if(flag == -preFlag || preFlag == 0){
                preFlag = flag;
                count++;
            }
        }
    }
    return count;
}

`

53. Maximum Subarray

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

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.
Example 2:

Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.
Example 3:

Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.

Constraints:

1 <= nums.length <= 105
-104 <= nums[i] <= 104

Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

`
public int maxSubArray(int[] nums) {
if(nums.length == 0){
return 0;
}
int max = Integer.MIN_VALUE;
int sum = Integer.MIN_VALUE;
for(int i=0; i if(nums[i] > 0){
if(sum < 0){
sum = nums[i];
}else{
sum += nums[i];

            }
            max = Math.max(max, sum);
        }else{
            if(sum<0){
                sum = nums[i];
            }else{
            sum += nums[i];
            }
            max = Math.max(max, sum);
        }
    }
    return max;

}

`

improve code
`
public int maxSubArray(int[] nums) {
if(nums.length == 0){
return 0;
}
int max = Integer.MIN_VALUE;
int sum = Integer.MIN_VALUE;
for(int i=0; i if(sum < 0){
sum = nums[i];
}else{
sum += nums[i];

            }
            max = Math.max(max, sum);
    }
    return max;

}

`

Another way for greedy
`
public int maxSubArray(int[] nums) {
if(nums.length == 0){
return 0;
}
int max = Integer.MIN_VALUE;
// int sum = Integer.MIN_VALUE;

    int sum = 0;
    for(int i=0; i<nums.length; i++){
        sum+= nums[i];
        if(max < sum){
            max = sum;
        }
        if(sum <0){
            sum = 0;
        }
            // if(sum < 0){
            //     sum = nums[i];
            // }else{
            //     sum += nums[i];

            // }
            // max = Math.max(max, sum);

    }
    return max;

}

`

The above is the detailed content of LeetCode DayGreedy Algorithm Part 1. For more information, please follow other related articles on the PHP Chinese website!