一.算法练习
509.斐波那契数
斐波那契数 (通常用 F(n) 表示)形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是:
F(0) = 0,F(1) = 1
F(n) = F(n - 1) + F(n - 2),其中 n > 1
给定 n ,请计算 F(n) 。
思路:斐波那契数列,算是简单题,可以用普通的递归来做,也可以用dp来做,dp五部曲:1.推断出dp数组以及下标的含义。2.确定递推公式。3.dp数组初始化。4.确定遍历顺序。5.举例推导dp数组。有代码可知一个数是有它的前两个数推导出来的,得出递推公式如下
class Solution {
public:int fib(int n) {if(n<=1){return n;}vector<int> dp(n+1);dp[0]=0;dp[1]=1; for(int i=2;i<=n;i++){dp[i]=dp[i-1]+dp[i-2];}return dp[n];}
};
70.爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
思路:同理, 爬到第i层楼梯,有dp[i]种方法,由于第三层楼梯有dp[1]+dp[2]种方法,所以可以得出递推公式。(和斐波那契数挺像的)
class Solution {
public:int climbStairs(int n) {if(n<=1){return n;}vector<int> dp(n+1);dp[1]=1;dp[2]=2;for(int i=3;i<=n;i++){dp[i]=dp[i-1]+dp[i-2];}return dp[n]; }
};
746.使用最小花费爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
思路:这道题由于前两个楼梯不需要花费体力,所以直接初始化dp数组如下,然后由题意可知,dp[i]:到达第i台阶所花费的最少体力为dp[i]。可以推导出,递推公式是由,dp[i]==dp[i-1]+cost[i-1]和dp[i-2]+cost[i-2]的最小值,这样就可以推导出登顶之后的最小花费了。
class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {//1.确定dp数组的下标和其含义 dp[i]代表此时到达第i个台阶所花费的最少体力vector<int> dp(cost.size()+1);//2.确定递推公式//dp[i]=dp[i-1]+cost dp[1]=0;//因为前两个台阶不需要花费for(int i=2;i<=cost.size();i++){dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);}return dp[cost.size()];}
};
二.四种强制类型转换
1.概念:
-
static_cast:用于基本类型之间的转换,以及具有继承关系的类之间的转换。它可以处理隐式转换和非const转换。但是,它不能用于处理没有继承关系的类之间的转换。
-
dynamic_cast:用于具有继承关系的类指针之间的转换。它在运行时执行类型检查,只能用于处理指针或引用类型。如果转换是合法的,dynamic_cast返回目标类型的指针或引用;如果转换不合法,dynamic_cast返回空指针(对于指针转换)或抛出std::bad_cast异常(对于引用转换)。
-
reinterpret_cast:用于将一个指针或引用转换为另一种类型的指针或引用,甚至可以将一个指针类型转换为整数类型,或者将一个整数类型转换为指针类型。reinterpret_cast是一种非常强大但也非常危险的转换,需要谨慎使用。
-
const_cast:用于去除变量的const属性,可以将const类型转换为非const类型。参数类型必须是指针或引用类型。它通常用于解决函数重载或函数参数类型不匹配的问题。
1.static_cast
static_cast主要用于具有继承关系的类之间的转换,注意,它不能处理没有继承关系的类之间的转换。
三.类的大小与什么有关
1.空类为1
1.局部变量:
定义一个int类型的变量类大小为4
2.函数
可见空函数与类的大小无关,若在函数里定义局部变量呢?
可见,也不影响类的大小。
3.虚函数:
当类前面加上虚函数,类的大小就会加上虚函数表指针的大小8(64位系统),但8+4=12,为什么是16呢,这就要谈到内存对齐了
三.内存对齐
是为了提高内存访问效率和硬件系统的性能,不同的编译器和体系结构可能会有一些差异
如图所示,此时的类大小为24,内存对齐话如图所示