Day 6, C/C++知识点走起~
1
编程题
【剑指Offer】二进制中1的个数
输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。
思路: 我们大家都知道整数在计算机中是以二进制的形式来存储的,因此对于正数或者负数都是0或1的数字组成的。且由于int型为32位,因此我们可以逐一的对每一位进行判断,只需要n & (1<<i)就可以判断第i位是否为1了!
class Solution {
public:
int NumberOf1(int n) {
int count = ;
for(int i = ;i >=; --i){
if(n & ( << i)){
++count;
}
}
return count;
}
};
当然也可以使用STL中的bitset(位图)来直接统计,花里胡哨的写法,只需要一句话!
6};
【剑指Offer】数值的整数次方
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
思路: 首先我们来说一个O(n)的方法,这个题目主要考虑到幂指数为负的情况需要对结果求倒数。
class Solution {
public:
double Power(double base, int exponent) {
double res = ;
if(exponent == )
return ;
if(base == )
return ;
for(int i = ;i < abs(exponent); ++i){
res *= base;
}
if(exponent < ){
res = / res;
}
return res;
}
};
显然,上面的算法一定不会合面试官的胃口的,因此我们可以使用一个快幂算法来进行求解!其实际编程不复杂,但是效率很高的!
假设3^64需要64个乘法运算,但如果这样计算的话:
3^1 = 3 (也就是base) 3^2 = (3^1) * (3^1) 3^4 = (3^2) * (3^2) … 3^64 = (3^32) * (3*32)
这个样子的话,就只算6次乘法,效率提升了很多了!因此我们就可以进行如下编程。
class Solution {
public:
double Power(double base, int exponent) {
if(exponent == ){
return ;
}
if(base == ){
return ;
}
double tmp = base;
double res = ;
int e = abs(exponent);
while(e > ){
if(e & ){ //e & 1相当于e % 2
res *= tmp;
}
e >>= ; // e >> 1相当于e / 2
tmp *= tmp;
}
return (exponent > ) ? res : / res;
}
};
2
概念题
【C/C++】引用传递和值传递的区别
值传递: 编译系统会在调用该函数的地方,把实参复制一份传给函数的形参。因此如果对形参进行修改,其实质是修改实参的副本,而实参本身不发生变化!但这样由于副本拷贝需要系统资源,效率会很低。
引用传递: 编译系统会在调用该函数的地方,直接将实参的内存地址(指针)传给形参。因此形参和实参共同拥有同一块内存,因此在函数中对参数进行修改,实参也会跟着修改。并且引用传递时规定引用不为空,因此需要在使用时对指针进行判断。
C++中参数一般使用引用传递(比如类或者结构体)!
【C/C++】sizeof和strlen的区别有哪些
【C/C++】指针和引用有什么区别呢?
int a=; int *p=&a;
int a=; int &b=a; //b相当于a的别名