面试题 08.05. 递归乘法
源码剖析class Solution {
public:
int multiply(int A, int B) {
int Max = max(A,B);
int Min = min(A,B);
if(Min==0){
return 0;
}
//Min*Max = (Max+1-1)*Min = (Max-1)*Min + Min = multiply(Max-1,Min)+Min
//但这里应当使得Min不断减少，因为递归的出口是Min==0
return multiply(Min-1,Max)+Max;
}
};
这道题让我对递归有了新的认识，同时这里调用函数时要注意，这里不可以使用 Max 来递归，会使得递归执行次数多非常非常多。
2.力扣2119 原题链接2119. 反转两次的数字
源码剖析class Solution {
public:
bool isSameAfterReversals(int num) {
if(num==0) return true;
return num%10;
}
};
其实就是统计原来的数字中有没有尾 0(除去0本身以外)。
3.力扣剑指 Offer 58 - II. 左旋转字符串 原题链接剑指 Offer 58 - II. 左旋转字符串
源码剖析class Solution {
public:
string reverseLeftWords(string s, int n) {
int size = s.size();
string ret = s;
for(int i = 0;i
ret[i] = s[(i+n)%size];
}
return ret;
}
};
这里使用了一个取模运算实现了类似循环队列的效果。
4.力扣面试题 16.07. 最大数值 原题链接面试题 16.07. 最大数值
源码剖析class Solution {
public:
int maximum(int a, int b) {
return a>b?a:b;
}
};
如果使用三元是白给题，不使用任何比较符号的话暂时还解不出来。
解题报告 5.力扣1812 原题链接1812. 判断国际象棋棋盘中一个格子的颜色
源码剖析class Solution {
public:
bool squareIsWhite(string coordinates) {
int x=coordinates[0]-'a';
int y=coordinates[1]-'0';
return !((x+y)&1);
}
};
ascii码的简单应用。
6.力扣136 原题链接136. 只出现一次的数字
源码剖析class Solution {
public:
int singleNumber(vector& nums) {
int ans = nums[0];
for(int i=1;i
ans^=nums[i];
}
return ans;
}
};
异或的性质，任何一个数异或上自己都等于 0 ，而任何一个数异或上 0 都等于本身。
7.力扣268 原题链接268. 丢失的数字
源码剖析class Solution {
public:
int missingNumber(vector& nums) {
int n = nums.size();
int sum = n*(n+1)/2;
for(int i=0;i
sum-=nums[i];
}
return sum;
}
};
直接上等差数列求和公式就可以了。
8.力扣剑指 Offer 53 - II. 0～n-1中缺失的数字 原题链接剑指 Offer 53 - II. 0～n-1中缺失的数字
源码剖析class Solution {
public:
int missingNumber(vector& nums) {
int n = nums.size();
int sum = n*(n+1)/2;
for(int i=0;i
sum-=nums[i];
}
return sum;
}
};
同上。
解题报告 9.力扣1486 原题链接1486. 数组异或操作
源码剖析class Solution {
public:
int xorOperation(int n, int start) {
int ans = 0;
for(int i = 0;i
ans^=(start+2*i);
}
return ans;
}
};
按题目要求实现即可。
10.力扣1009 原题链接1009. 十进制整数的反码
源码剖析class Solution {
public:
int bitwiseComplement(int n) {
if(n==0) return 1;
int num = 1;
while(num<=n){
num=num<<1;
}
return (num-1)^n;
}
};
只要将原来的数异或上与之位数相同的 1 即可。
