复试上机真题历年回顾-2015

组合字符

有3个字母a, b, c:你输入一个数字，要输出所有的组合字符和组合数
输入1
输出a,b,c 3
输入2
输出aa,ab,ac,ba,bb,bc,ca,cb,cc 9

就是个组合问题 dfs+回溯

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
vector<char>v;
int n;
int cnt;
void dfs(int x){
    if(x==n){
        ++cnt;
        for(int i=0;i<v.size();i++)
            cout<<v[i];
        cout<<" ";
        return;
    }
    for(int i=1;i<=3;i++){
        v.push_back('a'-1+i);//入栈
        dfs(x+1);
        v.pop_back();//出栈
    }
}
signed main(){
    cin>>n;
    dfs(0);
    cout<<cnt;
}

最大公共子串

求字符串1与字符串2的最大公共子串的长度及此长度最大公共子串的个数。
输入: abedefg Eebcdfg (最大公共子串:bcd)
输出:3 1
输入: abcdefg abcddefg (最大公共子串为: abcd defg)
输出:4 2

模拟即可

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define x first
#define y second
typedef pair<string,int>pii;
string s1,s2;
vector<pii>v;
signed main(){
    cin>>s1>>s2;
    int len =min(s1.length(),s2.length());
    for(int i=1;i<=len;i++)//枚举公共串长度
        for(int j=0;j<s1.length();j++)
            if(j+i<=s1.length()){//s1子串
                string tmp =s1.substr(j,i);
                int cnt =0;
                for(int k=0;k<s2.length();k++){
                    if(k+i<=s2.length()){//s2子串
                        string t =s2.substr(k,i);
                        if(t==tmp) ++cnt; 
                    }
                }
                if(cnt) v.push_back(make_pair(tmp,cnt));
            }else continue;
    int res=v.back().x.length();
    int count=0;
    for(int i=0;i<v.size();i++){
        if(v[i].x.length()!=res) continue;
        ++count;
    }
    cout<<res<<" "<<count<<endl;

}

去括号

只含加减的式子 去掉括号 比如 (a-(b+c))=a-b-c

从左往右遍历
除了第一个左括号 每个左括号标记一下前边的符号是+还是- 并放入栈中
+标记不变 -记录标记
遍历到+ 观察标记是否为1 为1变-
遍历到- 观察标记是否为1 为1变+
遍历到右括号 回归标记需要将栈中上一次出现的符号取出
取出为+ 标记不变 否则标记变为相反

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define x first 
#define y second
bool flag;
stack<int>s,ss;
signed main(){
    string str;
    cin>>str;
    string tmp=str;
    for(int i=0;tmp[i];i++){
        if(str[i]=='('&&i){
            ss.push(i);
            if(str[i-1]=='+') s.push(0);//记录左括号前的符号
            else if(str[i-1]=='-') {
                s.push(1);
                flag=!flag;
            }
        }else if(str[i]=='+'){
            if(flag) tmp[i]='-';//换符号
        } else if(str[i]=='-'){
            if(flag) tmp[i]='+';//换符号
        }else if(str[i]==')'){
            if(s.size()&&str[ss.top()-1]=='-'){//改标记
                int k=s.top();
                if(k) flag=!flag;
                s.pop();
            }
            ss.pop();
        }

    }
    for(int i=0;tmp[i];i++){
        if(tmp[i]=='('||tmp[i]==')') continue;
        cout<<tmp[i];
    }
    return 0;
}