牛客网——华为题库(31~40)

---

31.单词倒排

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int main(){
    
    string str = "";
    getline(cin, str);
    str += " ";
    vector<string> vec;
    string tmp = "";
    for(char c : str){
    
        if(!isalpha(c)){
    
            if(!tmp.empty()){
    
                vec.push_back(tmp);
                tmp.clear();
            }
        }
        else{
    
            tmp += c;
        }
    }
    
    reverse(vec.begin(), vec.end());
    string res = "";
    for(int i = 0; i < vec.size(); i++){
    
        //cout << vec[i]<<endl;
        res += vec[i];
        res += " ";
    }
    res.pop_back();
    
    cout << res << endl;
    
    return 0;
}

32.密码截取

#include <bits/stdc++.h>

using namespace std;

int getLength(string str, int l, int r){
    
    while(l >= 0 && r < str.size() && str[l] == str[r]){
    
        l--;
        r++;
    }
    
    return r - l - 1;
}

//最大回文子串
void process(string str, int& res){
    
    //dp[i][j]：字符串s在[i, j]范围内最长的回文子串的长度为dp[i][j]。
    int n = str.size();
    vector<vector<bool>> dp(n, vector<bool>(n, false));
    for(int i = 0; i < n; i++){
    
        dp[i][i] = true;//一个字符的回文子序列长度就是1。
    }
    
    for(int i = n - 1; i >= 0; i--){
    
        for(int j = i; j < n; j++){
     //
            if(str[i] == str[j]){
    
                if(j - i <= 2){
    
                    dp[i][j] = true; //
                }
                else{
    
                    dp[i][j] = dp[i + 1][j - 1];
                }
            }
            
            //取最长回文子串
            if(dp[i][j] && j - i + 1 > res){
    
                //s = str.substr(i, j - i + 1);
                res = j - i + 1;
            }
        }
    }
    
    /*//中心扩展法 int n = str.size(); for(int i = 0; i < n; i++){ //ABA int l1 = getLength(str, i, i); //ABBA int l2 = getLength(str, i, i + 1); res = max(res, l1 > l2 ? l1 : l2); }*/
}

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

33.整数与IP地址间的转换

#include <bits/stdc++.h>

using namespace std;

void process(string strIP, long decIP, long& _decIP, string& _strIP){
    
    stringstream iss(strIP);
    string sTmp = "";
    vector<long> nums; //long
    while(getline(iss, sTmp, '.')){
    
        nums.push_back(atol(sTmp.c_str()));
    }
    _decIP = nums[0] << 24 | nums[1] << 16 | nums[2] << 8 | nums[3]; //位运算组装
    
    _strIP += to_string((decIP >> 24) & 0xff); //取第一个八位二进制转换成字符 & 0xff
    _strIP += ".";
    _strIP += to_string((decIP >> 16) & 0xff);
    _strIP += ".";
    _strIP += to_string((decIP >> 8) & 0xff);
    _strIP += ".";
    _strIP += to_string(decIP & 0xff);
}

int main(){
    
    string strIP = "";
    long decIP = 0;
    cin >> strIP;
    cin >> decIP;
    
    long _decIP = 0;
    string _strIP = "";
    process(strIP, decIP, _decIP, _strIP);
    
    cout << _decIP << endl;
    cout << _strIP <<endl;
    
    return 0;
}

34.图片整理

#include <bits/stdc++.h>
#include <iostream>
#include <string>

using namespace std;

struct cmp{
    
    bool operator()(char& a, char& b){
    
        return a < b; //前面小后面大 升序
    }  
};

int main(){
    
    string str = "";
    getline(cin, str);

    sort(str.begin(), str.end(), cmp());
    
    cout << str << endl;
    
    return 0;
}

35.蛇形矩阵

#include <bits/stdc++.h>

using namespace std;

void process(int N){
    
    /*if(N == 0){ cout << "" << endl; }*/
    //第一行最后一个元素 = (N)*(N + 1) / 2;
    //第一行第j列元素 = (j) * (j + 1) / 2;
    //第i行第j列元素 = 第i - 1行j + 1列 - 1;
    //最后一行只有一个元素 = 第一行最后一个元素 - N - 1;
    int num = 1;
    vector<vector<int>> matrix(N, vector<int>(N, 0));
    for(int i = 0; i < N; i++){
    
        for(int j = 0; j <= i; j++){
       
            matrix[i - j][j] = num++; //
        }
    }
    
    for(int i = 0; i < N; i++){
    
        for(int j = 0; j < N - i; j++){
     //
            cout << matrix[i][j] << " ";
        }
        cout << endl;
    }
}

int main(){
    
    int N = 0;
    cin >> N;
    
    process(N);
    
    return 0;
}

36.字符串加密

#include <bits/stdc++.h>

using namespace std;

//encoder
void encoder(string key, string str, string& res){
    
    //如果单词中包含有重复的字母，只保留第1个，将所得结果作为新字母表开头
    vector<char> s; //s[i]对应的便是26个字母中第i个字母的加密结果
    for(int i = 0; i < key.size(); i++){
    
        key[i] = tolower(key[i]); //全部转小写
        if(find(s.begin(), s.end(), key[i]) == s.end()) //如果是第一次加入
            s.push_back(key[i]);
    }
    for(char c = 'a'; c <= 'z'; c++){
    
        if(find(s.begin(), s.end(), c) == s.end()) //如果是第一次加入
            s.push_back(c);
    }
    /*for(char ch : s){ cout << ch; }*/
    
    for(int i = 0; i < str.size(); i++){
    
        if(isupper(str[i])){
    
            res += s[str[i] - 'A'] - 32; //需要在转出来的小写字母基础上减32
        }
        else{
    
            res += s[str[i] - 'a']; //
        }
    }
}

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

37.统计每个月兔子的总数

#include <bits/stdc++.h>

using namespace std;

int process(int n){
    
    return n < 3 ? 1 : process(n - 1) + process(n - 2);
}

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

38.求小球落地5次后所经历的路程和第5次反弹的高度

#include <bits/stdc++.h>

using namespace std;

void process(int num, double& distance, double& high){
    
    double tmp = (double)num;
    for(int i = 0; i < 5; i++){
               
        distance += tmp * 2;
        tmp = tmp / 2;     
    }
    distance = distance - (double)num;
    high = tmp;
}

int main(){
    
    int num = 0;
    cin >> num;
    double distance = 0.0;
    double high = 0.0;
    
    process(num, distance, high);
    
    printf("%lf\n", distance);
    printf("%lf\n", high);
    
    return 0;
}

39.判断两个IP是否属于同一子网

#include <bits/stdc++.h>

using namespace std;

string str2bin(int num){
    
    if(num == 0) return "00000000";
    
    //cout << "num = " << num << endl;
    string binRes = "";
    string help = "0123456789ABCDEF";
    while(num){
    
        binRes += help[num % 2]; //二进制
        num /= 2;
    }
    reverse(binRes.begin(), binRes.end());
    while(binRes.size() < 8){
    
        binRes.insert(binRes.begin(), '0');
    } 
    //cout << "binRes = " << binRes << endl;
    return binRes;
}

bool noLegalYanMa(string zwYanMa){
    
    string res = "";
    stringstream iss(zwYanMa);
    string tmp = "";
    bool isNeg = false;
    while(getline(iss, tmp, '.')){
           
        if(tmp[0] == '-'){
    
            isNeg = true;
            tmp = tmp.substr(1, tmp.size() - 1);
        } 
        //cout << "tmp = " << tmp << endl;
        int size = tmp.size();
        int num = 0;
        for(int i = 0; i < size; i++){
    
            num = num * 10 + (tmp[i] - '0');
        }
        if(isNeg) num = -num;
        
        //cout << "num==" << num << endl;
        if(num < 0 || num > 255) return true;
        
        res += str2bin(num);
    }
    //cout << "res = " << res << endl;
    bool notZero = true;
    for(int j = 0; j < res.size(); j++){
    
        if(res[j] == '0') {
    
            notZero = false;
        }
        else{
    
            if(!notZero){
    
                return true;
            }
            continue;
        }   
    }
    
    return false;
}

string str2binStr(string s){
    
    string res = "";
    stringstream iss(s);
    string tmp = "";
    while(getline(iss, tmp, '.')){
    
        //cout << "tmp = " << tmp << endl; 
        int size = tmp.size();
        int num = 0;
        for(int i = 0; i < size; i++){
    
            num = num * 10 + (tmp[i] - '0');
        }
        //cout << "num==" << num << endl; 
        res += str2bin(num);
    }
    
    return res;
}

bool noLegalIP(string IP){
    
    string res = "";
    stringstream iss(IP);
    string tmp = "";
    bool isNeg = false;
    while(getline(iss, tmp, '.')){
    
        if(tmp[0] == '-'){
    
            isNeg = true;
            tmp = tmp.substr(1, tmp.size() - 1);
        } 
        //cout << "tmp = " << tmp << endl;
        int size = tmp.size();
        int num = 0;
        for(int i = 0; i < size; i++){
    
            num = num * 10 + (tmp[i] - '0');
        }
        if(isNeg) num = -num;
        //cout << "num==" << num << endl; 
        if(num < 0 || num > 255) return true;
    }
    
    return false;
}

string anWeiSum(string zwYanMa, string IP){
    
    string s1 = str2binStr(zwYanMa);
    string s2 = str2binStr(IP);
    cout << s1 << endl;
    cout << s2 << endl;
    
    string res = "";
    int i = s1.size() - 1;
    int j = s2.size() - 1;
    int carry = 0; //进位
    while(i >= 0 || j >= 0){
    
        int digitA = i >= 0 ? (s1[i--] - '0') : 0; //i--
        int digitB = j >= 0 ? (s2[j--] - '0') : 0; //j--
        int sum = digitA + digitB + carry;
        carry = sum >= 2 ? 1 : 0;
        sum = sum >= 2 ? (sum - 2) : sum;
        
        res += to_string(sum);
    }
    if(carry == 1) res += "1";
    reverse(res.begin(), res.end());
    cout << res << endl;
    return res;
}

string anWeiYu(string zwYanMa, string IP){
    
    string s1 = str2binStr(zwYanMa);
    string s2 = str2binStr(IP);
    //cout << s1 << endl;
    //cout << s2 << endl;
    
    string res;
    for(int i = 0; i < 32; i++){
    
        if(s1[i] != s2[i]){
    
            res += "0";
        }
        else if(s1[i] == '0' && s2[i] == '0'){
    
            res += "0";
        }
        else{
     //s1[i] == '1' && s2[i] == '1'
            res += "1";
        }
    }
    //cout << res << endl;
    return res;
}

bool isSameZiWang(string zwYanMa, string firstIP, string secondIP){
    
    if(anWeiYu(zwYanMa, firstIP) == anWeiYu(zwYanMa, secondIP)){
    
        return true;
    }
    return false;
}

void process(string zwYanMa, string firstIP, string secondIP, int& res){
    
    if(noLegalYanMa(zwYanMa) || noLegalIP(firstIP) || noLegalIP(secondIP)){
    
        res = 1;
        return;
    }

    if(isSameZiWang(zwYanMa, firstIP, secondIP)){
    
        res = 0;
    }
    else{
    
        res = 2;
    }
    
    return;
}

int main(){
    
    string zwYanMa = "";
    string firstIP = "";
    string secondIP = "";
    getline(cin, zwYanMa);
    getline(cin, firstIP);
    getline(cin, secondIP);
    int res = 0;

    process(zwYanMa, firstIP, secondIP, res);
    //anWeiYu(zwYanMa, firstIP);
    cout << res << endl;
    return 0;
}

40.统计字符

#include<iostream>
#include<string>

using namespace std;

int main()
{
    
    string str = "";
    while (getline(cin, str))
    {
    
        int alphaNum = 0;
        int spaceNum = 0;
        int digitNum = 0;
        int punctNum = 0;
        
        for(char c : str){
    
            if(isalpha(c)) alphaNum++;
            else if(isspace(c)) spaceNum++;
            else if(isdigit(c)) digitNum++;
            else if(ispunct(c)) punctNum++;
        }
        
        cout << alphaNum << endl << spaceNum << endl << digitNum << endl << punctNum << endl;
    }
    
    return 0;    
}