美文网首页
贪心算法:122.买卖股票的最佳时机II、455.分发饼干、39

贪心算法:122.买卖股票的最佳时机II、455.分发饼干、39

作者: zmfflying | 来源:发表于2021-01-08 16:41 被阅读0次

/**

122.买卖股票的最佳时机II

题目

给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。
注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

示例 1:

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

输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票,之后再将它们卖出。
因为这样属于同时参与了多笔交易,你必须在再次购买前出售掉之前的股票。
示例 3:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

提示:
1 <= prices.length <= 3 * 10 ^ 4
0 <= prices[i] <= 10 ^ 4

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

测试代码

print(maxProfit([7,1,5,3,6,4]))

笔记

这道题用 贪心算法 就很方便
等价于每天都只要有收益就买卖
没有收益就不管

代码地址

https://github.com/zmfflying/ZMathCode
*/

解题代码

import Foundation

//贪心算法
func maxProfit(_ prices: [Int]) -> Int {
    var res:Int = 0
    for index in 1..<prices.count {
        res += max(prices[index] - prices[index-1], 0)
    }
    return res
}

/**

455.分发饼干

题目

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

对每个孩子 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 <= g.length <= 3 * 104
0 <= s.length <= 3 * 104
1 <= g[i], s[j] <= 231 - 1

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/assign-cookies
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

测试代码

print(findContentChildren([1,2], [1,2,3]))

笔记

记录大佬的语录
想清楚局部最优,想清楚全局最优,感觉局部最优是可以推出全局最优,并想不出反例,那么就试一试贪心

这道题的思路就是
小的饼干就给胃口小的人吃

代码地址

https://github.com/zmfflying/ZMathCode
*/

解题代码

import Foundation

func findContentChildren(_ g: [Int], _ s: [Int]) -> Int {
    let childArr = g.sorted()
    let foodArr = s.sorted()
    var res = 0
    var foodIndex = 0
    var childIndex = 0
    
    while childIndex < childArr.count && foodIndex < foodArr.count {
        if foodArr[foodIndex] >= childArr[childIndex] {
            foodIndex += 1
            childIndex += 1
            res += 1
        } else {
            foodIndex += 1
        }
    }
    return res
}

/**

392.判断子序列

题目

给定字符串 s 和 t ,判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,"ace"是"abcde"的一个子序列,而"aec"不是)。
进阶:
如果有大量输入的 S,称作 S1, S2, ... , Sk 其中 k >= 10亿,你需要依次检查它们是否为 T 的子序列。在这种情况下,你会怎样改变代码?
致谢:
特别感谢 @pbrother 添加此问题并且创建所有测试用例。

示例 1:

输入:s = "abc", t = "ahbgdc"
输出:true
示例 2:

输入:s = "axc", t = "ahbgdc"
输出:false

提示:

0 <= s.length <= 100
0 <= t.length <= 10^4
两个字符串都只由小写字符组成。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/is-subsequence
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

测试代码

print(isSubsequence("abc", "ahbgdc"))

笔记

这道题的思路和 455.分发饼干 的一样
就每次循环都进行比对 对得上就都后移
对不上就原始字符串后移

代码地址

https://github.com/zmfflying/ZMathCode
*/

解题代码

import Foundation

func isSubsequence(_ s: String, _ t: String) -> Bool {
    let child:[Character] = Array(s)
    let parent:[Character] = Array(t)
    var childIndex: Int = 0
    var parentIndex: Int = 0
    
    while childIndex < child.count && parentIndex < parent.count {
        if child[childIndex] == parent[parentIndex] {
            childIndex += 1
            parentIndex += 1
        } else {
            parentIndex += 1
        }
    }
    
    if childIndex == child.count {
        return true
    }
    return false
}

相关文章

网友评论

      本文标题:贪心算法:122.买卖股票的最佳时机II、455.分发饼干、39

      本文链接:https://www.haomeiwen.com/subject/ktyfaktx.html