/**
152.乘积最大子数组
题目
给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
示例 1:
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-product-subarray
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
测试代码
print(maxProduct([2,3,-2,4]))
笔记
这道题的思路和 53.最大子序和 是差不多的
都是一次循环计算最大值
有区别的地方是这道题是要求乘积,而且数组里的元素有负数
所以除了记录最大值外,还要记录最小值
每次都去更新最大值和最小值即可
代码地址
https://github.com/zmfflying/ZMathCode
*/
解题代码
import Foundation
func maxProduct(_ nums: [Int]) -> Int {
if nums.count == 0 {
return 0
}
//这道题的特殊性在于有负数,在乘积中负负为正
//所以除了记录最大值外,还要记录最小值
var maxPro = nums[0]
var res = maxPro
var minPro = maxPro
for i in 1..<nums.count {
let num = nums[i]
//这里需要用变量记录下最大值 maxPro
//不然变化过的最大值 maxPro 参与最小值 minPro 的计算后会导致错误
let tempMax = maxPro
maxPro = max(num, max(tempMax * num, minPro * num))
minPro = min(num, min(minPro * num, tempMax * num))
res = max(maxPro, res)
}
return res
}
/**
121.买卖股票的最佳时机
题目
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
示例 1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
提示：
1 <= prices.length <= 105
0 <= prices[i] <= 104
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
测试代码
print(maxProfit1([7,1,5,3,6,4]))
笔记
这道题的核心是只能买一次卖一次
那么就要在最小值的时候买,在最大差值的时候卖
不断更新最小值,找到最大差值即可
代码地址
https://github.com/zmfflying/ZMathCode
*/
解题代码
import Foundation
//找出最小值
func maxProfit1(_ prices: [Int]) -> Int {
var res: Int = 0
var minP = prices[0]
for i in 1..<prices.count {
let price = prices[i]
//找出最小值
minP = min(minP, price)
//计算最大值
res = max(res, price - minP)
}
return res
}
//利润差转移
func maxProfit2(_ prices: [Int]) -> Int {
var res: Int = 0
var pre: Int = 0
for i in 1..<prices.count {
//计算出当天卖出的利润差
let diff = prices[i] - prices[i-1]
//计算出当天卖出的收益
pre = max(pre + diff, 0)
//计算最大收益
res = max(res, pre)
}
return res
}
//暴力解法 超出时间限制
func maxProfit3(_ prices: [Int]) -> Int {
var res: Int = 0
for i in 0..<prices.count {
let buyPrice = prices[i]
var j = i + 1
while j < prices.count {
let sellPrice = prices[j]
res = max(res, sellPrice - buyPrice)
j += 1
}
}
return res
}
/**
70.爬楼梯
题目
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
- 1 阶 + 1 阶
- 2 阶
示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
- 1 阶 + 1 阶 + 1 阶
- 1 阶 + 2 阶
- 2 阶 + 1 阶
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/climbing-stairs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
测试代码
print(climbStairs(3))
笔记
dp[1] = 1
dp[2] = 2
那么走到dp[3] 的最后一个台阶时,
走了 1 步的方法有 dp[3-1] = dp[2] = 2 种
走了 2 步的方法有 dp[3-2] = dp[1] = 1 种
同理
dp[4] = dp[4-1] + dp[4-2] = dp[3] + dp[2]
所以
dp[i] = dp[i-1] + dp[i-2]
代码地址
https://github.com/zmfflying/ZMathCode
*/
解题代码
import Foundation
func climbStairs(_ n: Int) -> Int {
if n < 3 {
return n
}
var dp = [Int].init(repeating: 0, count: n+1)
dp[1] = 1
dp[2] = 2
for i in 3...n {
//核心公式
dp[i] = dp[i-1] + dp[i-2]
}
return dp[n]
}
网友评论