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;
}
`
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
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!
![[Web front-end] Node.js quick start](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
