121.买卖股票的最佳时机&70.爬楼梯
- 121.买卖股票的最佳时机
- 70.爬楼梯
- 50.Pow(x,n)
买卖股票的最佳时机
给定一个数组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。
解题思路
暴力法
穷举，实际就是两层循环，时间复杂度为O(n^2)，空间复杂度为O(1)。（会超出时间限制
class Solution {
public:
int maxProfit(vector& prices) {
int length=prices.size();
int rtn=0;
for(int i=0;i 动态规划法
化大为小，总体思路：前i天的最大收益为取最大值{前i-1天的最大收益，第i天的收益}，公式：前i天的最大收益=max{前i-1天的最大收益，第i天的价格-前i-1天中的最小价格}
class Solution {
public:
int maxProfit(vector& prices) {
int length=prices.size();
if(length<=1)return 0;
//维护一个最大收益随时更新，一个i-1天中的最小支出
int beforeMin=prices[0];
int maxprofit=0;
for(int i=1;i 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例1：
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1阶 +1阶
2阶
示例2：
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1阶 + 1阶 + 1阶
1阶 + 2阶
2阶 + 1阶
解题思路
动态规划：
- 要么从第n-1阶台阶，要么从n-2阶台阶跳上第n级台阶，得到递推公式：f(n)=f(n?1)+f(n?2)
- 边界条件：只有一阶台阶的时候有一种方法f(1) = 1f(1)=1；只有两阶台阶的时候有两种方法f(2)=2f(2)=2
class Solution {
public:
int climbStairs(int n) {
int rtn[3]={1,2,3};
if(n<4)return rtn[n-1];
for(int i=3;i矩阵快速幂
以斐波那契数列为例：
https://leetcode-cn.com/problems/fibonacci-number/solution/mian-shi-ti-wen-jin-yi-bu-you-hua-chao-x-aeqe/
https://leetcode-cn.com/problems/fibonacci-number/solution/fei-bo-na-qi-shu-by-leetcode-solution-o4ze/
- 快速幂运算原理：对于求a的n次幂（a可以是数也可以是矩阵），先判断幂次的奇偶性
- 如果是偶数——底数平方，指数除以2
- 如果是奇数——底数平方，指数除以2，再乘一次底数
我们在计算一个数的多次幂时，可以先判断其幂次的奇偶性，然后：
以求 3^10 的结果为例：
3^10=3 * 3 * 3 * 3 * 3 * 3 * 3 * 3 * 3 * 3
=9^5 = 9^4 * 9
=81^2 * 9
=6561 * 9
- 对于以上涉及到 [判断奇偶性] 和 [除以2] 这样的操作。使用系统的位运算比普通运算的效率是高的，因此可以进一步优化：
- 把 power % 2 == 1 变为 (power & 1) == 1
- 把 power = power / 2 变为 power = power >> 1
class Solution {
public:
int fib(int n) {
/*对于n=1和n=2直接返回对应的值*/
if (n < 2) {
return n;
}
vector> q{{1, 1}, {1, 0}};
vector> res = matrix_pow(q, n - 1);//根据上图公式，计算矩阵的n-1次幂
return res[0][0];
}
vector> matrix_pow(vector>& a, int n) {
vector> ret{{1, 0}, {0, 1}};
while (n > 0) {
if (n & 1) {//如果是奇数的话 需要多乘一次底数
ret = matrix_multiply(ret, a);
}
n >>= 1;
a = matrix_multiply(a, a);
}
return ret;
}
/*矩阵相乘的函数*/
vector> matrix_multiply(vector>& a, vector>& b) {
vector> c{{0, 0}, {0, 0}};
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j];
}
}
return c;
}
};
本题代码(官方解答)：
class Solution {
public:
vector> multiply(vector> &a, vector> &b) {
vector> c(2, vector(2));
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j];
}
}
return c;
}
vector> matrixPow(vector> a, int n) {
vector> ret = {{1, 0}, {0, 1}};
while (n > 0) {
if ((n & 1) == 1) {
ret = multiply(ret, a);
}
n >>= 1;
a = multiply(a, a);
}
return ret;
}
int climbStairs(int n) {
vector> ret = {{1, 1}, {1, 0}};
vector> res = matrixPow(ret, n);
return res[0][0];
}
};
关于快速幂次运算见下题：
Pow(x,n)
实现pow(x, n) ，即计算x的n次幂函数（x^n）。
示例1：
输入：x = 2.00000, n = 10
输出：1024.00000
示例2：
输入：x = 2.10000, n = 3
输出：9.26100
示例3：
输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25
解题思路
class Solution {
public:
double myPow(double x, int n) {
double rtn=1.0;
for(int i=n;i!=0;i/=2)
{
if(i&1)rtn*=x;
x*=x;
}
return n<0?1/rtn:rtn;//如果幂次小于0，返回rtn的倒数
}
};