LeetCode Day 贪心算法 第 1 部分

455. 分配 Cookie

假设您是一位很棒的父母，想给您的孩子一些饼干。但是，您最多应该给每个孩子一块饼干。

每个孩子 i 都有一个贪婪因子 g[i]，这是孩子会满意的 cookie 的最小大小；每个 cookie j 的大小为 s[j]。如果 s[j] >= g[i]，我们可以将 cookie j 分配给子 i，并且子 i 将是内容。您的目标是最大化内容子级的数量并输出最大数量。

示例1：

输入：g = [1,2,3], s = [1,1]
输出：1
说明：您有 3 个孩子和 2 个饼干。 3个孩子的贪婪因子分别是1,2,3。
即使你有 2 个饼干，由于它们的大小都是 1，所以你只能制作贪婪因子为 1 的孩子的内容。
您需要输出 1.
示例2：

输入：g = [1,2], s = [1,2,3]
输出：2
说明：您有 2 个孩子和 3 个饼干。 2个孩子的贪婪因子是1, 2。
你有 3 块饼干，它们的大小足以满足所有孩子的需求，
你需要输出2。

限制：

1 0 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;   
    }

时间：n`logn

另一个版本的for循环
`
public int findContentChildren(int[] g, int[] s) {
// 避免空指针
if(g.length == 0 || s.length ==0){
返回 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;   
}

`

376. 摆动子序列

摆动序列是连续数字之间的差异严格在正负之间交替的序列。第一个差异（如果存在）可以是正值，也可以是负值。包含一个元素的序列和包含两个不相等元素的序列是简单的摆动序列。

例如，[1, 7, 4, 9, 2, 5] 是一个摆动序列，因为差值 (6, -3, 5, -7, 3) 在正负之间交替。
相反，[1,4,7,2,5]和[1,7,4,5,5]不是摆动序列。第一个不是因为它的前两个差值为正，第二个不是因为它的最后一个差值为零。
子序列是通过从原始序列中删除一些元素（可能为零）而获得的，而其余元素仍保持原始顺序。

给定一个整数数组 nums，返回 nums 的最长摆动子序列的长度。

示例1：

输入：nums = [1,7,4,9,2,5]
输出：6
解释：整个序列是一个有差异的摆动序列 (6, -3, 5, -7, 3)。
示例2：

输入：nums = [1,17,5,10,13,15,10,5,16,8]
输出：7
解释：有几个子序列可以达到这个长度。
一个是 [1, 17, 10, 13, 10, 16, 8]，有差异 (16, -7, 3, -3, 6, -8)。
示例 3：

输入：nums = [1,2,3,4,5,6,7,8,9]
输出：2

限制：

1 0

跟进：你能在 O(n) 时间内解决这个问题吗？

`
public int wiggleMaxLength(int[] nums) {
if(nums.length == 0){
返回 0;
}
整数计数 = 1;
int preFlag = 0;
int pre = nums[0];

    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. 最大子数组

给定一个整数数组 nums，找到
子数组
最大的和，并返回其和。

示例1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：子数组 [4,-1,2,1] 的和最大为 6。
示例2：

输入：nums = [1]
输出：1
解释：子数组 [1] 的和最大为 1。
示例 3：

输入：nums = [5,4,-1,7,8]
输出：23
解释：子数组 [5,4,-1,7,8] 的和最大为 23。

限制：

1 -104

后续：如果您已经找到了 O(n) 解决方案，请尝试使用分而治之的方法编写另一个解决方案，这种方法更微妙。

`
public int maxSubArray(int[] nums) {
if(nums.length == 0){
返回 0;
}
int max = Integer.MIN_VALUE;
int sum = Integer.MIN_VALUE;
for(int i=0;我 if(nums[i] > 0){
if(总和 sum = nums[i];
}其他{
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;

}

`

以上是LeetCode Day 贪心算法 第 1 部分的详细内容。更多信息请关注PHP中文网其他相关文章！