牛客网——华为题库(41~50)

41.称砝码

#include <bits/stdc++.h>

using namespace std;

int main(){
    int typeNum = 0;
    cin >> typeNum;
    vector<int> weight(typeNum, 0);
    for(int i = 0; i < typeNum; i++){
        int tmp = 0;
        cin >> tmp;
        weight[i] = tmp;
    }
    vector<int> nums(typeNum, 0);
    for(int i = 0; i < typeNum; i++){
        int tmp = 0;
        cin >> tmp;
        nums[i] = tmp;
    }
    
    unordered_set<int> s;
    s.insert(0); //
    for(int i = 0; i < typeNum; i++){//对于每一种砝码
        for(int j = 0; j < nums[i]; j++){//用完当前砝码的数量之前
            unordered_set<int> tmp(s);
            for(auto iter = tmp.begin(); iter != tmp.end(); iter++){//当前集合每个都可以加一次
                s.insert(*iter + weight[i]);
            }
        }
    }
    
    cout << s.size() << endl;
    
    return 0;
}

42.学英语

#include <bits/stdc++.h>

using namespace std;

vector<string> ones = { "zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine" };
vector<string> tens = { "ten","eleven","twelve","thirteen","fourteen","fifteen","sixteen","seventeen","eighteen","nineteen" };
vector<string> twenties = { "zero","ten","twenty","thirty","forty","fifty","sixty","seventy","eighty","ninety" };
vector<string> hundreds = { "hundred", "thousand", "million", "billion" };
const int ihundreds[] = {(int)1e2, (int)1e3, (int)1e6, (int)1e9, (int)1e12 }; //用来划分数字的范围

string process(long long num){
    if(num <= 9) return ones[num];
    else if(num < 20) return tens[num % 10];
    else if(num < 1e2) return twenties[num / 10] + (num % 10 == 0 ? "" : " " + ones[num % 10]);
    else{
        for(int i = 0; i < 4; i++){ //大于100
            if(num < ihundreds[i + 1]){ //(i == 0 ? " and" : " ") 因为百位数和十位数之间要加and
                return process(num / ihundreds[i]) + " " 
                    + hundreds[i] 
                    + (num % ihundreds[i] ? (i == 0 ? " and " : " ") + process(num % ihundreds[i]) : "");
            }
        }
    }
    
    return "";
}

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

43.迷宫问题

#include <bits/stdc++.h>

using namespace std;

int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1};
vector<pair<int, int>> res;

void dfs(vector<vector<int>>& matrix, int m, int n, int x, int y, vector<pair<int, int>>& paths){
    //一定要先压 后判断终止条件
    paths.push_back(make_pair(x, y)); //压入路径
    matrix[x][y] = 1; //标记为 已经访问过
    
    if(x == m - 1 && y == n - 1){
        res = paths;
        return;
    }

    //四个方向
    for(int i = 0; i < 4; i++){
        int mx = x + dx[i]; int my = y + dy[i];
        if(mx >= 0 && mx < m && my >= 0 && my < n && matrix[mx][my] == 0){
            dfs(matrix, m, n, mx, my, paths);
            paths.pop_back(); //回溯          
        }
    }
    matrix[x][y] = 0;
    return;  
}

int main(){
    int m = 0, n = 0;
    while(cin >> m >> n){
        vector<vector<int>> matrix(m, vector<int>(n, 0)); //
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                cin >> matrix[i][j];
            }
        }
        
        vector<pair<int, int>> paths;//记录临时路径
        //dfs
        dfs(matrix, m, n, 0, 0, paths);
        
        for(int i = 0; i < res.size(); i++){
            cout << "(" << res[i].first << "," << res[i].second << ")" << endl;
        }
        
    }
    
    return 0;
}

44.Sudoku

#include <bits/stdc++.h>

/*
从左上角开始去遍历这个数独。

对于没有填入的格子（即格子数值为0），我们去枚举1～9每个数字填入，
然后根据数独的性质（同行、同列、同一个九宫格不能有相同数字）去判断填入。
如果可以成功填完所有格子那么就是找到了答案。
找到答案后可以用一个bool变量，然后注意在回溯的地方根据这个变量及时的return，
防止已经找到答案后又回溯为0。

对于初始化就有值的格子，我们往右走（列数值加一），
那么因为一行只有9个，所以当列走到头的时候，列的值变成0，行的值加1（其实就是换到了下一行的开头）。
*/

using namespace std;

const int N = 15;
int mp[N][N];//存储数独
bool findAnswerOk = false; //是否找到答案

//检验在当前位置填入val后，满足要求与否
bool check(int row, int col, int val){
    //同行
    for(int j = 0; j < 9; j++){
        if(mp[row][j] == val) return false;
    }
    
    //同列
    for(int i = 0; i < 9; i++){
        if(mp[i][col] == val) return false;
    }
    
    //同一个九宫格
    int rowLimit = (row / 3) * 3 + 3; //九宫格行的终点(1--9) //
    int colLimit = (col / 3) * 3 + 3; //九宫格列的终点(1--9) //
    for(int i = rowLimit - 3; i < rowLimit; i++){ //
        for(int j = colLimit - 3; j < colLimit; j++){ //
            if(mp[i][j] == val) return false;
        }
    }
    
    return true;
}

//dfs 当前行、列
void dfs(int row, int col){
    if(col == 9){//当前行结束(最多为8)
        row++; //下一行
        col = 0;
    }
    
    //终止条件 (遍历完了整个矩阵)
    if(row == 9 && col == 0){
        findAnswerOk = true; //找到了答案
        return;
    }
    
    if(mp[row][col] == 0){ //该位置还没填充数字
        for(int i = 1; i <= 9; i++){ //遍历检查数字是否能填充
            if(check(row, col, i)){
                mp[row][col] = i; //进行填充
                dfs(row, col + 1); //下一个
                
                if(findAnswerOk) return; //已经找到了答案，直接返回
                
                mp[row][col] = 0; //没有找到答案，回溯
            }
        }
    }
    else{
        dfs(row, col + 1); //已填充，直接下一个数字
    }
}

int main(){
    for(int i = 0; i < 9; i++) {
        for(int j = 0; j < 9; j++) {
            cin >> mp[i][j];
        }
    }
    
    dfs(0, 0);//起点坐标（0，0）
    
    for(int i = 0; i < 9; i++) {
        for(int j = 0; j < 9; j++) {
            cout << mp[i][j] << ' ';
        }
        cout << endl;
    }
    
    return 0;
}

45.名字的漂亮度

#include <bits/stdc++.h>

using namespace std;

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

void process(string s, int& ans){
    //cout << s << endl;
    unordered_map<int, int> m;
    for(int ch : s){
        m[ch - 'a']++;
    }
    vector<pair<int, int>> vec;
    for(auto item = m.begin(); item != m.end(); item++){
        vec.push_back(make_pair(item->first, item->second));
    }
    sort(vec.begin(), vec.end(), cmp());
    
    int n = 26;
    for(int i = 0; i < vec.size(); i++){
        //cout << vec[i].first << " " << vec[i].second << endl;
        ans += vec[i].second * n;
        n--;
    }  
}

int main(){
    int num = 0;
    while(cin >> num){
        vector<int> res(num, 0);
        for(int i = 0; i < num; i++){
            string s = "";
            cin >> s;
            int ans = 0;
            process(s, ans);
            res[i] = ans;
        }
        
        for(int i = 0; i < num; i++){
            cout << res[i] << endl;
        }
    }
    
    return 0;
}

46.截取字符串

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

using namespace std;

int main(){
    string str = "";
    getline(cin, str);
    int num = 0;
    cin >> num;
    
    string res = "";
    for(char c : str){  
        if(num == 0) break;
        res += c;
        num--;
    }
    
    cout << res << endl;
    
    return 0;
}

48.从单向链表中删除指定值的节点

#include <bits/stdc++.h>

using namespace std;

struct ListNode{
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr){};
    ListNode(int x) : val(x), next(nullptr){};
};

int main(){
    int nodeNum = 0;
    int headVal = 0;
    while(cin >> nodeNum >> headVal){
        /*//法一：用数组模拟链表
        vector<int> array;
        array.push_back(headVal);
        for(int i = 1; i < nodeNum; i++){
            int num = 0, posNum = 0;
            cin >> num >> posNum; //输入要插入的数和它要插入哪个数字后面
            auto iter = find(array.begin(), array.end(), posNum); //找到要插入数字后面的那个位置
            if(iter == array.end()){
                array.push_back(num); //结尾
            }
            else{
                array.insert(iter + 1, num); //iter + 1
            }
        }
        //移除数字
        int removeNum = 0;
        cin >> removeNum;
        auto it = find(array.begin(), array.end(), removeNum); //找到要移除的数字的位置
        array.erase(it); //移除
        
        for(int i = 0; i < array.size(); i++){
            cout << array[i] << " ";//输出
        }            
        cout << endl;*/
        
        //法二：构建链表
        ListNode* head = new ListNode(headVal); //头结点
        for(int i = 1; i < nodeNum; i++){
            int preNodeNum = 0, curNodeNum = 0;
            cin >> curNodeNum >> preNodeNum;
            ListNode* curNode = new ListNode(curNodeNum); //添加这个结点
            
            ListNode* cur = head;
            while(cur != nullptr && cur->val != preNodeNum){ //找到前序结点
                cur = cur->next;
            }
            //插入节点
            curNode->next = cur->next;
            cur->next = curNode;
        }
        //移除数字
        int removeNum = 0;
        cin >> removeNum;
        ListNode* cur = head;
        /*while(cur != nullptr){
            if(cur->val != removeNum) { //不输出removeNum，其他都输出            
                cout << cur->val << " ";
            }
            cur = cur->next;
        }
        cout << endl;*/
        while(cur->next != nullptr && cur->next->val != removeNum){ //找到要移除的结点
           cur = cur->next;
        }     
        
        //移除节点
        ListNode* tmp = cur->next;
        cur->next = cur->next->next;
        delete tmp;
        
        ListNode* output = head;
        while(output != nullptr){
            cout << output->val << " ";//输出
            output = output->next;
        }            
        cout << endl;
    }
    
    return 0;
}

50.四则运算

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

using namespace std;

string changeKuohao(string& s){
    for(int i = 0; i < s.size(); i++){
        if(s[i] == '{' || s[i] == '['){
            s[i] = '(';
        }
        if(s[i] == '}' || s[i] == ']'){
            s[i] = ')';
        }
    }
    //cout<<s<<endl;
    return s;
}

int calculate(int a, int b, char c){
    switch(c){
        case '+':
            return a + b;
            break;
        case '-':
            return a - b;
            break;
        case '*':
            return a * b;
            break;
        case '/':
            return a / b;
            break;
        default:
            return 0;
            break;
    }
}

int process(string s){
    int flag = 0; //正负号标志，0为无正负号，1为正号，2为负号
    stack<int> numst; //数字栈
    stack<char> symbolst; //符号栈
    
    for(int i = 0; i < s.size(); i++){
        if(isdigit(s[i])){
            int num = 0; //数字的值
            int j = i;
            while(i + 1 < s.size() && isdigit(s[i + 1])) i++;
            string tmp = s.substr(j, i - j + 1);
            
            for(int k = 0; k < tmp.size(); k++){
                num = num * 10 + (tmp[k] - '0');
            }
            if(flag == 2) num = 0 - num;
            
            flag = 0; //复位
            numst.push(num); //入栈
        }  
        else if(s[i] == '*' || s[i] == '/' || s[i] == '('){//为乘除时
            symbolst.push(s[i]);
        }
        else if(s[i] == '+' || s[i] == '-'){//为加减时
            //处理负号
            if(i == 0 || s[i - 1] == '('){
                if(s[i] == '+'){
                    flag = 1;
                }
                else{
                    flag = 2;
                }
            }     
            //堆栈非空时，符号栈弹出符号，并结合数字栈计算
            while(!flag && !symbolst.empty() && symbolst.top() != '('){
                int b = 0, a = 0; char sym_tmp;
                b = numst.top(); numst.pop();
                a = numst.top(); numst.pop();
                sym_tmp = symbolst.top(); symbolst.pop();
                numst.push(calculate(a, b, sym_tmp));//计算结果入栈
            }
            if(!flag) symbolst.push(s[i]); //
        }
        else if(s[i] == ')'){//为右括号时
            while(symbolst.top() != '('){
                int b = 0, a = 0; char sym_tmp;
                b = numst.top(); numst.pop();
                a = numst.top(); numst.pop();
                sym_tmp = symbolst.top(); symbolst.pop();
                numst.push(calculate(a, b, sym_tmp));//计算结果入栈
            }
            symbolst.pop();
        }
        else{
            cout<<"error!"<<endl;
        }
    }

    //循环结束后把剩下的符号弹出，并结合数字栈计算
    while(!symbolst.empty()){
        int b = 0, a = 0; char sym_tmp;
        b = numst.top(); numst.pop();
        a = numst.top(); numst.pop();
        sym_tmp = symbolst.top(); symbolst.pop();
        numst.push(calculate(a, b, sym_tmp));//计算结果入栈
    }
    
    return numst.top();
}

int main(){
    string str = "";
    while(cin>>str){
        str = changeKuohao(str); //将大括号和中括号转成小括号
        int res = process(str);
        cout << res << endl;
    }
    
    return 0;
}