小米 软件开发试卷 编程题 c++实现
第一题,树的中序遍历
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> using namespace std; int len; char s[1111111]; int Find(int l,int r) { int k=0; for(int i=l;i<=r;i++) { if(s[i]=='(') k++; if(s[i]==')') k--; if(k==0&&s[i]==',') return i; } } void dfs(int l,int r) { if(l>r) return; if(l==r) { cout<<s[l]; return; } int pos=Find(l+2,r); dfs(l+2,pos-1); cout<<s[l]; dfs(pos+1,r-1); } int main() { cin>>s; len=strlen(s); dfs(0,len-1); cout<<endl; }
第二题,背包
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<map> using namespace std; int n; int v; int num[11111]; int dp[111111]; int main() { cin>>n; for(int i=0;i<n;i++) cin>>num[i]; cin>>v; memset(dp,-1,sizeof(dp)); dp[0]=0; for(int i=0;i<n;i++) { for(int j=num[i];j<=v;j++) { if(dp[j-num[i]]!=-1) { if(dp[j]==-1) dp[j]=dp[j-num[i]]+1; else dp[j]=min(dp[j],dp[j-num[i]]+1); } } } cout<<dp[v]<<endl; }