一、分发饼干

题目:

假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。

对每个孩子 i,都有一个胃口值 g[i],这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j,都有一个尺寸 s[j] 。如果 s[j] >= g[i],我们可以将这个饼干 j 分配给孩子 i ,这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子,并输出这个最大数值。

 示例 1:

输入: g = [1,2,3], s = [1,1]
输出: 1
解释: 
你有三个孩子和两块小饼干,3个孩子的胃口值分别是:1,2,3。
虽然你有两块小饼干,由于他们的尺寸都是1,你只能让胃口值是1的孩子满足。
所以你应该输出1。

示例 2:

输入: g = [1,2], s = [1,2,3]
输出: 2
解释: 
你有两个孩子和三块小饼干,2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出2.

思路:

可以采用双指针的方法,先将两数组从小到大排序,判断饼干数组中的值是否大于等于胃口数组的值,如果是结果加1,然后饼干数组向前遍历,继续判断,直到饼干数组全部遍历完毕,输出结果数组

代码:

public int findContentChildren(int[] g, int[] s) {
    // 首先对孩子的胃口数组 g 和饼干的数组 s 进行排序
    Arrays.sort(g); // 排序孩子的胃口数组
    Arrays.sort(s); // 排序饼干数组

    int index = s.length - 1; // 初始化饼干数组的指针,指向最大的饼干
    int result = 0; // 初始化结果,记录满足条件的孩子数量

    // 从胃口最大的孩子开始向前遍历
    for (int i = g.length - 1; i >= 0; i--) {
        // 如果饼干指针有效且当前饼干能够满足当前孩子的胃口
        if (index >= 0 && s[index] >= g[i]) {
            result++; // 记录当前孩子可以被满足
            index--; // 饼干指针向前移动,指向下一个更小的饼干
        }
    }
    return result; // 返回满足条件的孩子数量
}
  1. 排序数组:首先通过 Arrays.sort() 方法对孩子的胃口数组 g 和饼干数组 s 进行排序。排序的目的是为了优化后续的分配过程,使得从胃口最大的孩子开始分配饼干。

  2. 初始化指针和结果

    • index 初始化为 s.length - 1,即指向饼干数组中最大的饼干。这样可以从大到小依次分配饼干。
    • result 初始化为 0,用于记录能够被满足的孩子数量。
  3. 遍历分配饼干

    • 使用 for 循环从胃口最大的孩子开始向前遍历 g 数组。
    • 在每次迭代中,检查当前的饼干指针 index 是否有效(大于等于 0),并且当前指向的饼干 s[index] 是否能够满足当前孩子的胃口 g[i]
    • 如果满足条件,即 s[index] >= g[i],则将 result 自增 1,表示当前孩子可以被满足。
    • 然后将 index 向前移动一位,指向下一个更小的饼干,继续寻找下一个可以满足的孩子。

二、摆动序列

题目:

如果连续数字之间的差严格地在正数和负数之间交替,则数字序列称为 摆动序列 。第一个差(如果存在的话)可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。

  • 例如, [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
解释:这个序列包含几个长度为 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,2,2,4,5)属于单调摆动,这种情况总共只有2个摆动,即为边界的两次摆动,因此采用双指针摆动时不能实时更新两个指针的位置,应为一个指针负责判断差值,当差值存在时才能更新另一个指针的位置

代码:

public int wiggleMaxLength(int[] nums) {
    int prediff = 0; // 上一个数字之间的差值
    int curdiff = 0; // 当前数字之间的差值
    int result = 1; // 初始长度至少为1,因为数组至少有一个元素

    if (nums.length == 1)
        return 1; // 如果数组长度为1,直接返回1作为最大长度

    for (int i = 1; i < nums.length; i++) {
        curdiff = nums[i] - nums[i - 1]; // 计算当前数字与前一个数字的差值

        // 判断是否构成摆动
        if ((prediff >= 0 && curdiff < 0) || (prediff <= 0 && curdiff > 0)) {
            result++; // 如果当前差值和上一个差值方向相反,则增加摆动序列的长度
            prediff = curdiff; // 更新上一个差值为当前差值,用于下一次比较
        }
    }

    return result; // 返回最长摆动子序列的长度
}
  1. 变量说明

    • prediff:存储上一对相邻数字之间的差值。
    • curdiff:存储当前对相邻数字之间的差值。
    • result:记录最长摆动子序列的长度,初始化为1,因为至少可以包含数组中的第一个元素。
  2. 特殊情况处理

    • 如果数组长度为1,直接返回1,因为单个元素本身就构成一个摆动序列。
  3. 遍历数组

    • 从数组的第二个元素开始遍历到最后一个元素。
    • 计算当前相邻元素的差值 curdiff = nums[i] - nums[i - 1]
  4. 判断摆动条件

    • 如果当前差值 curdiff 和上一个差值 prediff 的方向相反(值的正负),则说明这两个数字构成了一个摆动。摆动的条件是:当 prediff >= 0 且 curdiff < 0 或者 prediff <= 0 且 curdiff > 0
    • 如果满足摆动条件,则增加 result 的值,并更新 prediff 为 curdiff,若不满足摆动(即为平坡时),继续移动curdiff,不更新prediff的位置,以便下一轮比较。

三、最大子数组和 

题目:

给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

子数组是数组中的一个连续部分。

示例 1:

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

示例 2:

输入:nums = [1]
输出:1

示例 3:

输入:nums = [5,4,-1,7,8]
输出:23

思路:

判断最大子数组和时,如果子数组总和已经小于0,这时继续相加只会让后面的总值变小,因此当总和小于0时,就不需要继续往下相加,而是以下一个值为起始位置重新统计子数组和,同时记录当前遍历的情况中出现的最大子数组和,最后返回结果

代码:

public int maxSubArray(int[] nums) {
    int result = Integer.MIN_VALUE; // 初始化结果为整型最小值,用于记录最大子数组和
    int count = 0; // 记录当前子数组的和

    for (int i = 0; i < nums.length; i++) {
        count += nums[i]; // 将当前元素加入到当前子数组和中

        if (count > result)
            result = count; // 更新最大子数组和的结果

        if (count < 0)
            count = 0; // 如果当前子数组和为负数,说明当前子数组不可能为最大子数组的前缀,重置为0
    }

    return result; // 返回最大子数组和
}
  1. 变量说明

    • result:用来存储当前找到的最大子数组和,初始值设为整型最小值,确保可以正确比较后续的和。
    • count:记录当前子数组的累积和。
  2. 循环遍历数组

    • 使用 for 循环遍历数组 nums
    • 在每次循环中,将当前元素 nums[i] 加入到 count 中,表示扩展当前子数组。
  3. 更新最大子数组和

    • 每次更新 count 后,通过 if (count > result) 判断当前 count 是否大于 result,如果是,则更新 result
  4. 处理负数子数组

    • 如果 count 小于0,意味着当前累积的子数组和已经为负数,不可能对后续的子数组和有正的贡献,因此将 count 重置为0,表示舍弃当前子数组,重新开始计算新的子数组。
  5. 返回结果

    • 最后返回 result,即为数组中最大的子数组和。

四、买卖股票最佳时机

题目:

给你一个整数数组 prices ,其中 prices[i] 表示某支股票第 i 天的价格。

在每一天,你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买,然后在 同一天 出售。

返回 你能获得的 最大 利润 。

示例 1:

输入:prices = [7,1,5,3,6,4]
输出:7
解释:在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。
随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3。
最大总利润为 4 + 3 = 7 。

示例 2:

输入:prices = [1,2,3,4,5]
输出:4
解释:在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。
最大总利润为 4 。

示例 3:

输入:prices = [7,6,4,3,1]
输出:0
解释:在这种情况下, 交易无法获得正利润,所以不参与交易可以获得最大利润,最大利润为 0。

思路:

关键在于如何寻找这个最小最大值,利用贪心的思维,当局部变量为最优解时,全局变量便等于所有最优的局部变量解之和,因此,我们只需要判断相邻两个数之间的差值,如果为正数,则加入局部的利润中,为负数,则舍去,这样所有的局部正数相加得到的全局总利润即为最优解

代码:

public int maxProfit(int[] prices) {
    int result = 0; // 初始化最大利润为0

    // 遍历股票价格数组
    for (int i = 1; i < prices.length; i++) {
        // 计算相邻两天的价格差
        int profit = prices[i] - prices[i - 1];

        // 如果价格差大于0,表示可以有利润,累加到result中
        if (profit > 0) {
            result += profit;
        }
        // 如果价格差小于等于0,则说明当天卖出的话无法获得利润,跳过此次交易
    }

    return result; // 返回最大利润
}
  1. 变量说明

    • result:用来存储最终的最大利润,初始值为0,因为开始时没有进行任何交易,利润自然为0。
  2. 循环遍历价格数组

    • 使用 for 循环遍历数组 prices,从第二天开始(即 i = 1)到最后一天。
    • 在每次循环中,计算相邻两天的价格差 profit,即 prices[i] - prices[i - 1]
  3. 判断利润是否为正

    • 如果 profit > 0,表示当天卖出股票可以获得利润,将这个利润累加到 result 中。
    • 如果 profit <= 0,表示当天卖出股票无法获得利润(或者可能损失),则跳过此次交易,不对 result 进行累加操作。
  4. 返回结果

    • 最后返回累积的 result,即为股票买卖能够获得的最大利润。

今天的学习就到这里 

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部