程序员面试金典

面试题 08.01. 三步问题

class Solution { public: int waysToStep(int n) { vector<int>dp(n+3); dp[0]=0;dp[1]=1;dp[2]=2;dp[3]=4; for(int i=4;i<=n;i++) { dp[i]=((dp[i-3]+dp[i-2])%1000000007+dp[i-1])%1000000007; } return dp[n]; } };

面试题 08.02. 迷路的机器人

class Solution { public: int m,n; vector<vector<int> > path; vector<vector<bool> > visited; int dx[2]={0,1},dy[2]={1,0}; vector<vector<int>> pathWithObstacles(vector<vector<int>>& obstacleGrid) { if(obstacleGrid.empty()||obstacleGrid[0].empty())return path; m = obstacleGrid.size(),n=obstacleGrid[0].size(); visited = vector(m,vector<bool>(n,false)); dfs(obstacleGrid,0,0); return path; } bool dfs(vector<vector<int>>& obstacleGrid,int x,int y){ if(x>=m||y>=n||obstacleGrid[x][y]==1||visited[x][y])return false; if(x==m-1&&y==n-1){ path.push_back({x,y}); return true; } path.push_back({x,y}); visited[x][y]=true; for(int i=0;i<2;++i)if(dfs(obstacleGrid,x+dx[i],y+dy[i]))return true; path.pop_back(); return false; } };

面试题 08.03. 魔术索引

class Solution { public: int findMagicIndex(vector<int>& nums) { int n=nums.size(); for(int i=0;i<n;i++) { if(nums[i]==i) return i; } return -1; } };

面试题 08.04. 幂集

class Solution { public: vector<vector<int>> subsets(vector<int>& nums) { //模拟手动，如数字为3 1初始为[]，插入3,则变为[]、3,插入1，则变为[]、3、1、3 1 vector<vector<int>>res; res.push_back({}); int i=0; while(i<nums.size()) { int size=res.size(); for(int j=0;j<size;j++) { vector<int> ans(res[j].begin(),res[j].end()); ans.push_back(nums[i]); res.push_back(ans); } i++; } return res; } };

面试题 08.05. 递归乘法

class Solution { public: int multiply(int A, int B) { if(B==0) return 0; return multiply(A,B-1)+A; } };