牛客网——华为题库(61~70)

---

61.放苹果

#include <bits/stdc++.h>

using namespace std;

int process(int m, int n){
    
    if(m < 0 || n < 0){
    
        return 0;
    }
    else if(m == 1 || n == 1){
    
        return 1;
    }
    else {
    
        // 其他情况的时候，我们要计算少一个盘子，和所有盘子拿走一个苹果的情况
        return process(m, n - 1) + process(m - n, n); //
    }
    
}

int main(){
    
    int m = 0, n = 0;
    
    while(cin >> m >> n){
    
        int res = process(m, n);
        
        cout << res << endl;
    }
    
    return 0;
}

62.查找输入整数二进制中1的个数

#include<bits/stdc++.h>

using namespace std;

void process(int num, int& res){
    
    while(num != 0){
    
        res++;
        num = num & (num - 1);
    }
}

int main(){
    
    int num = 0;
    while(cin>>num){
    
        int res = 0;
        process(num, res);
        cout<<res<<endl;
    }
        
    return 0;
}

63.DNA序列

#include <bits/stdc++.h>

using namespace std;

void process(string str, int num, string& res){
    
    vector<string> vec; //保存所有可能的字串
    
    for(int i = 0; i < str.size() - num + 1; i++){
    
        string tmp = str.substr(i, num);
        //cout << tmp << endl;
        vec.push_back(tmp);
    }
    
    int maxLen = INT_MIN;
    for(string s : vec){
    
        int t = 0;
        for(char ch : s){
    
            if(ch == 'C' || ch == 'G'){
    
                t++; //当前字串中C和G的个数
            }
        }
        
        if(t > maxLen){
    
            res = s;
            maxLen = t;
        }
    }
}

int main(){
    
    string str = "";
    cin >> str;
    int n = 0;
    cin >> n;
    
    string res = "";
    process(str, n, res);
    
    cout << res << endl;
    
    return 0;
}

64.MP3光标位置

#include <bits/stdc++.h>

using namespace std;

int main(){
    
    //输入
    int musicNum = 0;
    string command = "";
    cin >> musicNum;
    cin >> command;
    
    //处理命令
    if(musicNum <= 4){
    
        int curMusicPos = 1; //当前光标的一个位置
        for(char ch : command){
    
            if(ch == 'U') curMusicPos--;
            else curMusicPos++;
        }
        
        //输出
        for(int i = 1; i <= musicNum; i++){
    
            cout << i << " ";
        }
        cout << endl;
        // 这里有一点要注意的就是有可能最后的位置超过了musicNum，要取一个模，变到这个范围内
        if(curMusicPos >= 0){
    
            cout << (curMusicPos) % musicNum << endl; //
        }
        else{
    
            cout << (musicNum + curMusicPos + 1) % musicNum << endl;
        }
    }
    
    else{
     //musicNum > 4
        int curMusicPos = 1; //当前光标的一个位置
        int head = 1, end = 4; //head当前列表的头部是哪一首歌曲, end当前列表尾部是哪一首歌曲
        
        for(char ch : command){
    
            if(ch == 'U') {
    
                curMusicPos--;
                //如果光标比第一首歌曲的位置都要小
                if(curMusicPos < 1){
     //跳到最后一页的位置上面
                    curMusicPos = musicNum; //更新光标位置
                    head = musicNum - 4 + 1; //更新列表头部
                    end = musicNum; //更新列表尾部
                }
                else{
     //如果光标没有小于1
                    if(curMusicPos < head){
     //如果当前位置要比当前的列表头还要小，说明要更新列表了
                        head = curMusicPos; //更新列表头部
                        end--; //更新列表尾部
                    }
                }
            }
            // ch == 'D'
            else{
     
                curMusicPos++;
                //如果光标比最后一首歌曲的位置都要大
                if(curMusicPos > musicNum){
     //跳到第一页的位置上面
                    curMusicPos = 1; //更新光标位置
                    head = 1; //更新列表头部
                    end = 4; //更新列表尾部
                }
                else{
     //如果光标没有大于musicNum
                    if(curMusicPos > end){
     //如果当前位置要比当前的列表尾还要大，说明要更新列表了
                        end = curMusicPos; //更新列表尾部
                        head++; //更新列表头部
                    }
                }
            }
           
        }
         
        //输出
        for(int i = head; i <= end; i++){
    
            cout << i << " ";
        }
        cout << endl;
        cout << curMusicPos << endl;
    }
      
    return 0;
}

65.查找两个字符串a,b中的最长公共子串

#include <bits/stdc++.h>

using namespace std;

//dp
//dp[i][j]表示 到s1第i个,到s2第j个为止 的公共子串长度 (其中s1较短)
void longestCommonSubsequence(string s1, string s2, string& res) {
    
    vector<vector<int>> dp(s1.size() + 1, vector<int>(s2.size() + 1, 0));
    int maxLength = INT_MIN, end = 0; //end表示字符串的末位位置 (最大不超过s1的长度)
    
    for(int i = 1; i <= s1.size(); i++){
    
        for(int j = 1; j <= s2.size(); j++){
    
            if(s1[i - 1] == s2[j - 1]){
    
                dp[i][j] = dp[i - 1][j - 1] + 1; //则增加长度
            }
            else{
    
                dp[i][j] = 0; // //该位置为0
            }
            
            if(dp[i][j] > maxLength){
     //更新最大长度
                maxLength = dp[i][j];
                end = i - 1; //
            }
        }
    }

    res = s1.substr(end - maxLength + 1, maxLength);
}

int main(){
    
    string s1 = "";
	string s2 = "";

	getline(cin, s1);
	getline(cin, s2);
    
    if(s1.length() > s2.length()){
    
        swap(s1, s2); //使较小的字符串在前
    } 
            
	string res = "";
	longestCommonSubsequence(s1, s2, res);
	cout << res << endl;
    
    return 0;
}

66.配置文件恢复

#include <bits/stdc++.h>

using namespace std;

vector<pair<string, string>> youXiaoCommand = {
    
    {
    "reset", ""},
    {
    "reset", "board"},
    {
    "board", "add"},
    {
    "board", "delete"},
    {
    "reboot", "backplane"},
    {
    "backplane", "abort"}
};

vector<string> commandRes = {
    
    "reset what",
    "board fault",
    "where to add",
    "no board at all",
    "impossible",
    "install first"
};

int main(){
    
    string str = "";
    while(getline(cin, str)){
    
        stringstream iss(str);
        string key1 = "", key2 = "";
        getline(iss, key1, ' '); //第一个关键字
        getline(iss, key2, ' '); //第二个关键字
        
        string res = "";
        int piPeiCount = 0; //记录匹配的关键字个数 (等于1时即唯一匹配到 即匹配成功)
        for(auto iter = youXiaoCommand.begin(); iter != youXiaoCommand.end(); iter++){
    
            int key1Pos = iter->first.find(key1); //key1在命令的前半部分第一次出现的下标 (为0匹配成功)
            int key2Pos; //key2在命令的前半部分第一次出现的下标 (为0匹配成功)
            
            if(key2 != ""){
     //有key2
                key2Pos = iter->second.find(key2); //key2在命令的前半部分第一次出现的下标
            }
            else if(key2 == "" && iter->second.empty()){
     //特殊情况匹配到命令 {"reset", ""},
                key2Pos = 0;
            }
            else{
     //没匹配到
                key2Pos = -1;
            }
            
            if(key1Pos == 0 && key2Pos == 0){
     //匹配成功
                piPeiCount++; //匹配成功的个数
                res = commandRes[iter - youXiaoCommand.begin()]; //索引位置：iter - youXiaoCommand.begin()
            }
        }
        
        if(piPeiCount == 1){
     //匹配成功且为唯一匹配
            cout << res << endl;
        }
        else{
    //否则就是没有匹配成功，输出"unknown command"
            cout<<"unknown command"<<endl;   
        }
    }
    
    return 0;
}

67.24点游戏算法

#include <bits/stdc++.h>

using namespace std;

double num = 1e-6;
int ANS = 24;
int ADD = 0, SUB = 1, MUL = 2, DIV = 3;

bool process(vector<double>& l){
    
    if(l.size() == 0) return false;
    if(l.size() == 1) return abs(24 - l[0]) < num; //只剩一个数字
    
    int size = l.size(); //
    for(int i = 0; i < size; i++){
    
        for(int j = 0; j < size; j++){
    
            if(i != j){
     //两个索引不能相等
                vector<double> l2;
                for(int k = 0; k < size; k++){
    
                    if(k != i && k != j){
    
                        l2.push_back(l[k]);//先将本轮不做处理的数字放进去
                    }
                }   
                
                //"二合一"
                for(int m = 0; m < 4; m++){
     //四种处理：加减乘除
                    if(m == ADD){
    
                        l2.push_back(l[i] + l[j]);
                    }
                    else if(m == SUB){
    
                        l2.push_back(l[i] - l[j]);
                    }
                    else if(m == MUL){
    
                        l2.push_back(l[i] * l[j]);
                    }
                    else{
    
                        if(abs(l[j]) < num) continue; //除的时候分母不能为0
                        l2.push_back(l[i] / l[j]);
                    }
                    
                    if(process(l2)){
    
                        return true; //
                    }
                    
                    l2.pop_back(); //
                }                                
            }
        }
    }
    return false;
}

int main(){
    
    int a = 0, b = 0, c = 0, d = 0;
    while(cin >> a >> b >> c >> d){
    
        //二合一 + dfs
        vector<double> l1;
        l1.push_back((double)a);
        l1.push_back((double)b);
        l1.push_back((double)c);
        l1.push_back((double)d);
        
        bool res = process(l1);
        
        if(res)
            cout << "true" << endl;
        else
            cout << "false" << endl;
    }
    
    return 0;
}

68.成绩排序

#include <bits/stdc++.h>

using namespace std;

struct cmpJiangXu{
    
  bool operator()(const pair<string, int>& a, const pair<string, int>& b){
    
      return a.second > b.second;
  }  
};

struct cmpShengXu{
    
  bool operator()(const pair<string, int>& a, const pair<string, int>& b){
    
      return a.second < b.second;
  }  
};

int main(){
    
    int n = 0;
    //法一
    /*while(cin >> n){ int sortWay = 0; //排序方式 cin >> sortWay; //输入名字和成绩 vector<pair<string, int>> info; for(int i = 0; i < n; i++){ string name = ""; int score = 0; cin >> name >> score; info.push_back(make_pair(name, score)); } //排序 //stable的函数可保证相等元素的原本相对次序在排序后保持不变 if(sortWay == 0){ //从高到低 降序 stable_sort(info.begin(), info.end(), cmpJiangXu()); } else if(sortWay == 1){ //从低到高 升序 stable_sort(info.begin(), info.end(), cmpShengXu()); } //输出 for(auto iter = info.begin(); iter != info.end(); iter++){ cout << iter->first << " " << iter->second << endl; } }*/
    
    //法二
    while(cin >> n){
    
        int sortWay = 0; //排序方式
        cin >> sortWay;
        //输入名字和成绩
        map<int, vector<string>> info;
        for(int i = 0; i < n; i++){
     //建立成绩和名字的映射
            string name = "";
            int score = 0;
            cin >> name >> score;
            info[score].push_back(name);
        }
        
        //排序
        if(sortWay == 0){
    
            //从高到低 降序
            //逆序遍历 // rbegin rend
            //输出
            for(auto iter = info.rbegin(); iter != info.rend(); iter++){
     //iter++
                for(int i = 0; i < iter->second.size(); i++){
     //成绩相同时，按照输入顺序输出
                    cout << iter->second[i] << " " << iter->first << endl;
                }                
            }
        }
        
        else if(sortWay == 1){
    
            //从低到高 升序
            //顺序遍历
            for(auto iter = info.begin(); iter != info.end(); iter++){
     //iter++
                for(int i = 0; i < iter->second.size(); i++){
    
                    cout << iter->second[i] << " " << iter->first << endl;
                }  
            }
        } 
        
    }
    
    return 0;
}

69.矩阵乘法

#include <bits/stdc++.h>

using namespace std;

int main(){
    
    //输入
    int firstRows = 0;
    int firstCols = 0;
    int secondRows = 0;
    int secondCols = 0;
    cin >> firstRows;
    cin >> firstCols;
    secondRows = firstCols;
    cin >> secondCols;
    
    int num = 0;//矩阵元素
    //输入第一个矩阵
    vector<vector<int>> firstMatrix(firstRows, vector<int>(firstCols, 0));    
    for(int i = 0; i < firstRows; i++){
    
        for(int j = 0; j < firstCols; j++){
    
            cin >> num;
            firstMatrix[i][j] = num;
        }
    }
    //输入第二个矩阵
    vector<vector<int>> secondMatrix(secondRows, vector<int>(secondCols, 0));
    for(int i = 0; i < secondRows; i++){
    
        for(int j = 0; j < secondCols; j++){
    
            cin >> num;
            secondMatrix[i][j] = num;
        }
    }
    
    //计算相乘结果矩阵
    vector<vector<int>> mulRes(firstRows, vector<int>(secondCols, 0));
    for(int i = 0; i < firstRows; i++){
    
        for(int j = 0; j < secondCols; j++){
    
            
            for(int k = 0; k < firstCols; k++){
    
                mulRes[i][j] += firstMatrix[i][k] * secondMatrix[k][j]; //相乘相加
            }
           
        }
    }
    
    //输出
    for(int i = 0; i < firstRows; i++){
    
        for(int j = 0; j < secondCols; j++){
    
            cout << mulRes[i][j] << " ";
        }
        cout << endl; //换行，输出矩阵的下一行元素
    }
    
    return 0;
}

70.矩阵乘法计算量估算

#include <bits/stdc++.h>

using namespace std;

int main(){
    
    int n = 0;
    while(cin >> n){
    
        vector<pair<int, int>> matrixs(n); //行数和列数
        for(int i = 0; i < n; i++){
    
            cin >> matrixs[i].first;
            cin >> matrixs[i].second;
        }
        string s = "";
        cin >> s;
        
        //矩阵乘法 第一行第一列相乘相加
        //A是一个50×10的矩阵，B是10×20的矩阵 则次数为：50×10×20
        int res = 0;
        stack<pair<int, int>> st; //栈存储矩阵的行数和列数
        for(int i = 0; i < s.size(); i++){
     //遍历字符串
            if(s[i] == ')'){
     //如果是右括号，则栈弹出两个元素，并累加乘法次数
                auto y = st.top(); //后面的矩阵
                st.pop();
                auto x = st.top(); //前面的矩阵
                st.pop();
                
                if(x.second == y.first){
    
                    res += x.first * x.second * y.second;
                    st.push({
    x.first, y.second}); // //把形成的新矩阵的行数和列数入栈
                }
                //
                /*else if(y.second == x.first){ res += y.first * y.second * x.second; st.push({y.first, x.second}); //把形成的新矩阵的行数和列数入栈 }*/
            }
            else if(s[i] != '('){
     如果是字符，则直接入栈
            //else if(isalpha(s[i])){ 
                // A是第一个矩阵 它的行数和列数对应matrix[0]
                int t = s[i] - 'A';
                st.push(make_pair(matrixs[t].first, matrixs[t].second));
            }
        }
        
        //输出
        cout << res << endl;
    }
    
    return 0;
}