程序员面试金典

面试题 08.11. 硬币

class Solution { public: int waysToChange(int n) { int mask=1e9+7; vector<int>dp(n+1),coins={1,5,10,25}; dp[0]=1; for(int i=0;i<4;i++) { for(int j=coins[i];j<=n;j++) { dp[j]=(dp[j]+dp[j-coins[i]])%mask; } } return dp[n]; } };

面试题 08.12. 八皇后

class Solution { public: vector<vector<string>>res; vector<vector<string>> solveNQueens(int n) { vector<int>pre; dfs(n,0,pre); return res; } void dfs(int n,int id,vector<int>&pre) { if(id==n) { vector<string>ans(n,string(n,'.')); for(int i=0;i<n;i++) { ans[i][pre[i]]='Q'; } res.push_back(ans); return; } for(int i=0;i<n;i++) { if(isvalid(n,id,i,pre)) { pre.push_back(i); dfs(n,id+1,pre); pre.pop_back(); } } } bool isvalid(int n,int id,int num,vector<int>&pre) { int prenum=pre.size(); for(int i=0;i<prenum;i++) { if(num==pre[i]||abs(num-pre[i])==id-i) return false; } return true; } };

面试题 08.13. 堆箱子 最长单调子序列

class Solution { public: int pileBox(vector<vector<int>>& box) { int m=box.size(); if(m==0) return 0; sort(box.begin(),box.end()); vector<int>hi(box.size(),0); int ans=box[0][2]; hi[0]=ans; for(int i=1;i<m;i++) { hi[i]=box[i][2]; for(int j=0;j<i;j++) { if(box[j][0]<box[i][0]&&box[j][1]<box[i][1]&&box[j][2]<box[i][2]) { hi[i]=max(hi[i],hi[j]+box[i][2]); } } ans=max(hi[i],ans); } return ans; } };

面试题 08.14. 布尔运算

class Solution { public: int cnt=0; int countEval(string s, int result) { if(s=="") return 0; int i,j,n=s.size(),len; vector<vector<int>>dp0(n,vector<int>(n,0)); vector<vector<int>>dp1(n,vector<int>(n,0)); for(int i=0;i<n;i+=2) { if(s[i]=='1') dp1[i][i]=1; else dp0[i][i]=1; } for(len = 2; len <= n-1; len += 2) { //按长度递增 for(i = 0; i < n-len; i += 2) { //左端点i for(j = i; j <= i+len-2; j+=2) { //中间端点j if(s[j+1]=='&') { dp1[i][i+len] += dp1[i][j]*dp1[j+2][i+len]; dp0[i][i+len] += dp0[i][j]*dp0[j+2][i+len]+dp1[i][j]*dp0[j+2][i+len]+dp0[i][j]*dp1[j+2][i+len]; } else if(s[j+1]=='|') { dp1[i][i+len] += dp1[i][j]*dp1[j+2][i+len]+dp1[i][j]*dp0[j+2][i+len]+dp0[i][j]*dp1[j+2][i+len]; dp0[i][i+len] += dp0[i][j]*dp0[j+2][i+len]; } else//^ { dp1[i][i+len] += dp1[i][j]*dp0[j+2][i+len]+dp0[i][j]*dp1[j+2][i+len]; dp0[i][i+len] += dp0[i][j]*dp0[j+2][i+len]+dp1[i][j]*dp1[j+2][i+len]; } } } } if(result) return dp1[0][n-1]; return dp0[0][n-1]; } };

面试题 10.01. 合并排序的数组

class Solution { public: void merge(vector<int>& A, int m, vector<int>& B, int n) { int j=m,i=0; int tmp; while(j<m+n&&i<n) { tmp=B[i]; A[j]=tmp; i++; j++; } sort(A.begin(),A.begin()+m+n); } };