面试题 08.01. 三步问题 - 力扣（LeetCode） (leetcode-cn.com)本系列往期文章如下：
【LeetCode 程序员面试金典（第 6 版）】第1-4章题目 01.01 ~ 04.10_lzs_lazy-CSDN博客【LeetCode 程序员面试金典（第 6 版）】第五章题目 05.01 ~ 05.08_lzs_lazy-CSDN博客
三步问题。有个小孩正在上楼梯，楼梯有 n 阶台阶，小孩一次可以上 1 阶、2 阶或 3 阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模 1000000007。
很经典的上台阶问题，思路很简单。
代码中做了详细注释，具体思路参见代码。
class Solution {
public:
enum{MOD = (int)1e9+7};
int waysToStep(int n) {
vectordp(4, 0);
// 赋初值
dp[0] = 1; dp[1] = 1; dp[2] = 2;
// 遍历
for(int i = 3; i <= n; ++i){
// 如果台阶个数为i，有三种情况可以到达i：
//1. 通过第i-1级台阶1步到i
//2. 通过第i-2级台阶2步到i
//3. 通过第i-3级台阶3步到i
// 需注意 因为MOD=1e9+7，所以int类型最多保存两个MOD不溢出。所以对于每次加法运算都要MOD一下。
dp[3] = ( (dp[2] + dp[1]) % MOD + dp[0]) % MOD;
// 为了节省空间，可以通过整体往前移动3位。因为对于第i级台阶方案数来说，最多只需要前3个台阶的方案数。
dp[0] = dp[1];
dp[1] = dp[2];
dp[2] = dp[3];
}
// 如果n < 3 直接输出初始值即可
return n < 3 ? dp[n] : dp[3];
}// end waysToStep
};
面试题 08.02. 迷路的机器人 - 力扣（LeetCode） (leetcode-cn.com)
设想有个机器人坐在一个网格的左上角，网格 r 行 c 列。机器人只能向下或向右移动，但不能走到一些被禁止的网格（有障碍物）。设计一种算法，寻找机器人从左上角移动到右下角的路径。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-gr7gXH9O-1642948367009)(assets/image-20220118141459-wfkiypp.png)]
网格中的障碍物和空位置分别用 1 和 0 来表示。
返回一条可行的路径，路径由经过的网格的行号和列号组成。左上角为 0 行 0 列。如果没有可行的路径，返回空数组。
思路：
由于每个点都可以有两种走法，则每个点最多可以被从两个方向到达。
对于任意可以从(0,0)到达的点(i, j)，它可能存在这样的路径：(0, 0)->(i-1, j)->(i, j) 。也可能存在另一条路径：(0,0)->(i, j-1)->(i, j)。
其中(i-1,j)和(i,j-1)也可以有类似的路径。
可以发现上述描述是个递归的过程，是可以由动态规划处理。
代码中提供了详细解释，具体思路细节可见代码。
class Solution {
public:
typedef pair pss;
vector> pathWithObstacles(vector>& obstacleGrid) {
//真坑呀，起点也不能走
if(obstacleGrid[0][0]) return vector>();
int r = obstacleGrid.size(); int c = obstacleGrid[0].size();
// 开辟 前驱二维数组 , pre[x][y] = (nx, ny) 表示(0,0)->(nx, ny)->(x, y) 是可行的
vector>pre(r, vector(c, pss(-1,-1)));
//标识(0,0)是可以被经过
pre[0][0] = pss(-2, -2);
// 寻找每个点可以经过哪个点到达
for(int i = 0; i < r; ++i){
for(int j = 0; j < c; ++j){
// 障碍物 跳过，所有障碍物的点都不可能从(0,0)到达
if(1 == obstacleGrid[i][j]) continue;
// 从(0, 0)可以到达(i-1,j)，并且从(i-1,j)可以达到(i,j)的条件
// pre[i][j]！=(-1,-1)：两重含义 1. 可以由(0,0)到达。2.(i,j)点不存在障碍物。
if(i && pre[i - 1][j] != pss(-1, -1)){
pre[i][j] = pss(i - 1, j);
}
// 从(0, 0)可以到达(i,j-1)，并且从(i,j-1)可以达到(i,j)的条件
if(j && pre[i][j - 1] != pss(-1, -1)){
pre[i][j] = pss(i, j - 1);
}
}
}
vector>path;
//通过前驱找到路径
int x = r - 1, y = c - 1;
while(pre[x][y].first != -1){
if(0 == x && 0 == y) break;
int nx = pre[x][y].first;
int ny = pre[x][y].second;
path.push_back(vector{x, y});
x = nx; y = ny;
}
// 从终点找到最后都没到起点
if(x != 0 || y != 0) {
path.clear();
return path;
}
path.push_back(vector{0, 0});
//路径翻转
reverse(path.begin(), path.end());
return path;
}
};
面试题 08.03. 魔术索引 - 力扣（LeetCode） (leetcode-cn.com)
魔术索引。 在数组A[0…n-1]中，有所谓的魔术索引，满足条件A[i] = i。给定一个有序整数数组，编写一种方法找出魔术索引，若有的话，在数组A中找出一个魔术索引，如果没有，则返回-1。若有多个魔术索引，返回索引值最小的一个。
直接从小到大遍历即可
class Solution {
public:
int findMagicIndex(vector& nums) {
for(int i = 0; i < nums.size(); ++i) {
if(nums[i] == i) {
return i;
}
}
return -1;
}
};
面试题 08.04. 幂集 - 力扣（LeetCode） (leetcode-cn.com)
幂集。编写一种方法，返回某集合的所有子集。集合中 不包含重复的元素 。
说明：解集不能包含重复的子集。
示例:
输入： nums = [1,2,3]
输出：
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
有两种解法，都要会。
二进制枚举DFS 枚举
方法一：二进制枚举。
如果从包含两个数字的集合中选出子集，总的子集个数为 2 2 = 4 2^2 = 4 22=4 个子集（包括空集）。文字描述这四个子集：空集、只选择第一个数字、只选择第二个数字、两个都选。如果用0和1来表示是否获取某个数字。00：可以表达两个都不选，为空集。01：可以表示选择第一个数字，第二个数字不选。10：可以表示选择第二个数字，第一个数字不选。11：可以表示两个数字都选。为了给出更直观的描述，看0-4的二进制的表示：
0 00
1 01
2 10
3 11结合上述两部分的描述，不难看出如此结论：对于 n 个元素的集合，总的子集个数为 2 n 2^n 2n ， 0 , 1 , 2 , . . . , ( 2 n − 1 ) 0,1,2,...,(2^n-1) 0,1,2,...,(2n−1) 整数的二进制表示，恰好可以表示这 2 n 2^n 2n 个不同的子集。
剩下的就是实现的细节了，代码中有详细的注释。建议下面的模板直接背下来，枚举子集时总可以用到。
class Solution {
public:
vector> subsets(vector& nums) {
// 二进制枚举
// 放入空子集
vector> ans;
// 遍历每一个子集 s。 1 << n 表示 2 ^ n
for(int s = 0; s < 1 << nums.size(); ++s){
vector sub;
// 获取每个子集 s 的元素
for(int pos = 0; pos < nums.size(); ++pos){
// 第 pos 个数字被选择 ，也即 整数 s 的二进制表示中，从右向左第 pos 位是 1 。
if(s >> pos & 1) {
sub.push_back(nums[pos]);
}
}
ans.push_back(sub);
}
return ans;
}
};
解法二：dfs 枚举。
枚举子集的过程，其实就是每个元素都可以取或者不取，每个元素都进行了判定之后，一定会确定一个子集，这本质就是一个搜索问题。
注意：如果对递归还是浑浑噩噩的话，还是建议多找几个实例，多模拟几遍。大家都是如此过来的，什么时候可以脑补递归过程，才算真正入门了递归。这里就不用文字描述了，文字只会加大理解难度。
具体的看代码，代码中给了详细的注释。
class Solution {
public:
//存储所有的子集
vector> ans;
// pos：表示第pos个元素。sub 表示从 0-pos 这些位置上的元素，所有选取的元素集合。nums仅做传值用，不修改。
// 注意 sub 前面的 & 符号，这说明 整个递归过程共享这一个 sub 集合
void dfs(int pos, vector& sub, const vector& nums){
// pos == nums.size() 表示：0-nums.size()-1的nums.size()个元素都进行了判定。
// 每个元素都进行了取舍判定，那么一定出现了一个新的子集
if(pos == nums.size()) {
ans.push_back(sub);
return;
}
// 对于 第pos个元素。
// 1. 选取该元素，第pos个元素需要放入sub集合中。
sub.push_back(nums[pos]);
// 继续判断 第 pos + 1 个元素的取舍情况。
dfs(pos + 1, sub, nums);
// 2. 不选取该元素，由于前面放进去了，此时需要将其取出，而且一定会位于最后的元素（这里如果无法理解，一定要找实例，模拟就明白了）
sub.pop_back();
// 继续判断 第 pos + 1个元素的取舍情况
dfs(pos + 1, sub, nums);
}
vector> subsets(vector& nums) {
vector sub;
dfs(0, sub, nums);
return ans;
}
};
面试题 08.05. 递归乘法 - 力扣（LeetCode） (leetcode-cn.com)
递归乘法。 写一个递归函数，不使用 * 运算符， 实现两个正整数的相乘。可以使用加号、减号、位移，但要吝啬一些。
观察乘法的特点，同时注意题目条件–位移，所以需要留意一下二进制，观察二进制和乘法的关系。
应该能够想到： 2 a ∗ 2 b = 2 a + b 2^a*2^b=2^{a+b} 2a∗2b=2a+b，这个式子中乘法并不会用到乘法，而是用到加法，并且2的次幂可以通过移位来解决。
本题就是利用这个思路来解决。A 和 B 都可以转化为二进制，这样就可以考虑二进制乘法了。
代码中有详细注释。
class Solution {
public:
//遍历 A 的二进制位，A不断右移，而后通过 A & 1获得最后一个二进制位
int binMul(int A, int depth, int B){
// A 最多向右移动 30次
if(depth == 31) {
return 0;
}
// 如果当前 A二进制的第 depth位为1 ，乘法才有值
if(A & 1) {
int ans = 0;
// 遍历 B的所有二进制位
for(int i = 0; i < 31; ++i){
//此时，B 二进制的第i位和A二进制的第depth位都是1，两者相乘为 2^i * 2^{depth} = 2^{i+depth}
//而 2的次幂 可以通过移位来获得
if(B >> i & 1) {
ans += 1 << (i + depth);
}
}
//当前的值 加上后面的二进制的和
return ans + binMul(A >> 1, depth + 1, B);
}
// 如果当前 A二进制的第depth位为0，当前二进制位的乘法值为0，全靠后面的二进制位决定
return binMul(A >> 1, depth + 1, B);
}
int multiply(int A, int B) {
return binMul(A, 0, B);
}
};
【墨鳌】【100%完美满分算法】【标准解法=快速乘】【反向优化=FFT】 - 递归乘法 - 力扣（LeetCode） (leetcode-cn.com)可以学习一波这个题解。可以说思路很像了，但是实现没有那么优雅。
学习一波具体的实现。
class Solution {
public:
int multiply(int A, int B) {
int ans=0;
long long a=max(A,B);
long long b=min(A,B);
while(b){
if(b&1)ans+=a;
b>>=1;
a+=a;
}
return ans;
}
};
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）