华为笔试题库之中等--难度

题记：若立志投身算法研究，可精研理论算法：动态规划、递归、深度搜索等；若以解决问题为目的，主要为了工作内容，当尝试快而简单的方法，这该是学习的本意。

// 题目来源：华为机试——牛客HJ16——购物单
#include 
#include 
using namespace std;

int main() {
    int N, m;
    cin >> N >> m;
    // 由于价格是10的整数倍，处理一下以降低空间/时间复杂度
    N /= 10;
    vector > prices(61, vector(3, 0));        // 价格
    vector > priceMultiplyPriority(61, vector(3, 0));      // 重要程度
    for (int i = 1; i <= m; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        a /= 10; b *= a;
        if (c == 0) {
            prices[i][0] = a; priceMultiplyPriority[i][0] = b;
        } else {
            if (prices[c][1] == 0) {
                prices[c][1] = a; priceMultiplyPriority[c][1] = b;
            } else {
                prices[c][2] = a; priceMultiplyPriority[c][2] = b;
            }
        }
    }
    // 使用分组背包
    vector > dp(m+1, vector(N+1, 0));
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= N; ++j) {
            int a = prices[i][0], b = priceMultiplyPriority[i][0];
            int c = prices[i][1], d = priceMultiplyPriority[i][1];
            int e = prices[i][2], f = priceMultiplyPriority[i][2];
            dp[i][j] = j >= a ? max(dp[i-1][j-a] + b, dp[i-1][j]) : dp[i-1][j];
            dp[i][j] = j >= (a+c) ? max(dp[i-1][j-a-c] + b + d, dp[i][j]) : dp[i][j];
            dp[i][j] = j >= (a+e) ? max(dp[i-1][j-a-e] + b + f, dp[i][j]) : dp[i][j];
            dp[i][j] = j >= (a+c+e) ? max(dp[i-1][j-a-c-e] + b + d + f, dp[i][j]) : dp[i][j];
        }
    }
    cout << dp[m][N] * 10 << endl;
}

#include 
using namespace std;

//正则表达式
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    string s,t;
    while(getline(cin,s)) {
        stringstream ss(s);
        pair p(0,0);
        while(getline(ss,t,';')) {
            if(t.empty())
                continue;
            string _ = t.substr(1);
            if(regex_match(_,regex("[0-9]*"))) {
                switch(t[0]) {
                    case 'A': p.first -= stoi(_); break; //左移
                    case 'D': p.first += stoi(_); break; //右移
                    case 'W': p.second += stoi(_); break; //上移
                    case 'S': p.second -= stoi(_); break; //下移
                    default: break; //无效
                }           
            }
        }
        cout << p.first << "," << p.second << endl;
    }
    return 0;
}

//非正则表达式
bool isNum(string s){
    int len=s.size();
    for(int i=0;i
        if('0'<=s[i]&&s[i]<='9')continue;
        else return false;
    }
    return true;
}
int main(){
    string s;
    pairp(0,0);
   while(getline(cin, s, ';')){
       if(s.empty())continue;
          string s1=s.substr(1);
          
       if(isNum(s1)){
           switch(s[0]){
               case 'A':
                   p.first-=stoi(s1);
                   break;
               case 'D':
                   p.first+=stoi(s1);
                   break;
               case 'W':
                   p.second+=stoi(s1);
                   break;
               case 'S':
                   p.second-=stoi(s1);
                   break;
               default:
                   break;
           }
       }
   }
        cout< 
3.密码验证合格程序 
 
#include
#include
#include
using namespace std;

int main () {
    string s;
    while (getline(cin, s)) {
        // 要求1
        int len = s.size();
        if (len <= 8) {
            cout << "NG" << endl;
            continue;
        }
        // 要求2
        unordered_set set;
        for (int i = 0; i < len; ++i) {
            if (s[i] >= 'A' && s[i] <= 'Z')
                set.insert(1);
            else if (s[i] >= 'a' && s[i] <= 'z')
                set.insert(2);
            else if (s[i] >= '0' && s[i] <= '9')
                set.insert(3);
            else
                set.insert(4);
        }
        if (set.size() < 3) {
            cout << "NG" << endl;
            continue;
        }
        // 要求3
        int flag = 0;
        for (int i = 0; i < len - 3; ++i) {
            for (int j = i + 1; j < len - 2; ++j) {
                if (s.substr(i, 3) == s.substr(j, 3)) {
                    flag = 1;
                    break;
                }
            }
            if (flag == 1)
                break;
        }
        if (flag == 1) {
            cout << "NG" << endl;
            continue;
        }

        cout << "OK" << endl;

    }


    return 0;
}
 
4.查找兄弟单词 
 
#include 
#include 
#include 

using namespace std;

bool isBrotherWord(string s1, string s2) {
    if (s1 == s2) {
        return false;
    }
    sort(s1.begin(), s1.end());
    sort(s2.begin(), s2.end());
    if (s1 == s2) {
        return true;
    } else {
        return false;
    }
}

int main() {
    int n;
    cin >> n;
    multiset str_set;
    while(n > 0) {
        string s;
        cin >> s;
        str_set.insert(s);
        n--;
    }
    string x;
    cin >> x;
    int k;
    cin >> k;
    int count = 0;
    string res;
    for(auto s : str_set) {
        if (isBrotherWord(s, x)) {
            count++;
            k--;
            if (k == 0) {
                res = s; 
            }
        }
    }

    cout << count << endl;
    if (!res.empty()) {
        cout << res << endl;
    }

    return 0;
}
 
5.字符串加解密 
 
#include
using namespace std;
int main() {
    int i=0;        //用于区分是原文还是密文
    string oritext;        //存放输入字符串
    vector> vec;    //利用pair记录加密解密规则
    vector>::iterator it;    //迭代器
    for(int i=0;i<26;i++) {    //将规则写入vector容器中
        if(i==25) {
            vec.push_back(make_pair('Z', 'a'));
            vec.push_back(make_pair('z', 'A'));
            continue;
        }
        vec.push_back(make_pair('A'+i, 'b'+i));
        vec.push_back(make_pair('a'+i, 'B'+i));
    }
    for(int i=0;i<10;i++) {
        if(i==9) {
            vec.push_back(make_pair('9', '0'));
            continue;
        }
        vec.push_back(make_pair('0'+i, '1'+i));
    }
    while(getline(cin, oritext)) {    //按照规则对输入字符串进行加密解密
        i++;    //每获取到一个字符串，i++
        if(i%2) {    //奇数为原文,进行加密操作
            for(int i=0;i
                for(it=vec.begin();it!=vec.end();it++) {
                    if(oritext[i]==it->first) {
                        oritext[i] = it->second;
                        break;
                    }
                }
            }
            cout<    //偶数为密文，进行解密操作
            for(int i=0;i
                for(it=vec.begin();it!=vec.end();it++) {
                    if(oritext[i]==it->second) {
                        oritext[i] = it->first;
                        break;
                    }
                }
            }
            cout< 
6.迷宫问题 

 
 
#include
#include
using namespace std;

int n,m;
vector>maze;
vector>best_path;
vector>temp_path;
void dfs(int i,int j)
{
    if(i<0|i>=n||j<0||j>=m||maze[i][j]==1)
    {
        return;
    }
    maze[i][j]=1;
    temp_path.push_back({i,j});
    if(i==n-1&&j==m-1)
    {
        best_path=temp_path;
    }
    dfs(i-1,j);
    dfs(i+1,j);
    dfs(i,j-1);
    dfs(i,j+1);
    maze[i][j]=0;
    temp_path.pop_back();
}
int main()
{
    while(cin>>n>>m)
    {
        maze=vector>(n,vector(m,0));
        best_path.clear();
        temp_path.clear();
        for(int i=0;i
            for(int j=0;j
                cin>>maze[i][j];
            }
        }
        dfs(0,0);
        for(int i=0;i
            vectorv=best_path.at(i);
            cout<<'('< 
7.从单向链表中删除指定值的节点 

 
 
#include
using namespace std;

int main() {
    int n,head;
    cin>>n>>head;    //输入结点数和头结点的值
    forward_list linklist;    //创建一个单向链表
    linklist.push_front(head);    //初始化头结点
    for(int i=1;i
        int front,back;
        cin>>back>>front;
        auto it=find(linklist.begin(), linklist.end(), front);
        linklist.insert_after(it, back);    //逐个插入结点
    }
    int last;
    cin>>last;    //输入要删除的结点值
    linklist.remove(last);    //移除具有该值的节点
    for(auto it=linklist.begin();it!=linklist.end();it++) {
        cout<<*it<<" ";    //从头到尾输出链表的值
    }
    cout< 
8. 查找两个字符串a,b中的最长公共子串 
 
#include
#include
using namespace std;

void FindSubString(string str1, int length1,string str2)
{
     for(int i=length1; i>0; i--)
     {
         for(int j=0; j<=length1-i;j++)
         {
             string sub = str1.substr(j,i);
             if(str2.find(sub)!=str2.npos)
             {
                 cout<
    string str1,str2;
    int length1,length2;
    while(cin>>str1>>str2)
    {
        length1 = str1.length();
        length2 = str2.length();
        //如果str1为短串
        if(length1 <= length2)
        {
            //从长往短找
            FindSubString(str1, length1, str2);
        }
        else
        {
            //从长往短找
            FindSubString(str2, length2,str1);
        }
    }

    return 0;
}
 
9. 24点 
 
#include
#include
using namespace std;
bool check(vector n, double a)
{
    if(n.empty())return a == 24;
    for(int i = 0; i < n.size(); i++)
    {
        vector r(n);//r=n
        r.erase(r.begin() + i);
        if(check(r,a+n[i])||check(r,a-n[i])||check(r,a*n[i])||check(r,a/n[i]))
            return true;
    }
    return false;
}
int main()
{
    vector nums(4); 
    while(cin >> nums[0] >> nums[1] >> nums[2] >> nums[3])
        if(check(nums, 0))cout << "true" << endl;
        else cout << "false" << endl;
}
 
10.合法IP 
 
#include
#include
using namespace std;


//使用正则表达式
int main()
{
    string str;
    cin>>str;
    regex r("(\d+).(\d+).(\d+).(\d+)");
    smatch m;
    bool is_ok=true;
    if(regex_match(str,m,r)==false)
        is_ok=false;
    
    for(int i=1;i
          //cout<255 ||(m[i].str()[0]=='0' && m[i].str().length()>1))
              is_ok= false;
    }
    if(is_ok)
      cout<<"YES"< 
11.求解立方根
 
 
#include 
#include 

using namespace std;
const double delta = 1e-3;

int main() {
    double x;
    int flag = 1;
    scanf("%lf", &x);
    if(x < 0) flag = -1, x = -x;
    double lb = 0, mid, rb = x;
    if(x < 1) rb = 1;
    
    while(lb <= rb) {
        mid = (lb + rb) / 2;
        double tmp = mid * mid * mid;
        if(abs(tmp - x) < delta) break;
        else if(tmp > x) {
            rb = mid - 0.01;
        } else {
            lb = mid + 0.01;
        }
    }
    
    printf("%.1lf", mid * flag);
    
    return 0;
}
 
12. 在字符串中找出连续最长的数字串 
 
#include
using namespace std;
vector a;
int main(void)
{
    int count=0,m=0;
    string str,temp;
    
    cin>>str;
    str.insert(str.begin(),'c');
    for(int i=0;i
         if(str[i]>='0'&&str[i]<='9')
         {
           count++;
            if(count>m)
                m = count;
         }
        else count = 0;
    }
    for(int i=0;i
        if(str[i]>='0'&&str[i]<='9')
        {
            count++;
            temp.push_back(str[i]);
            if(count==m)
            a.push_back(temp);
        }
        else{
           temp.clear();
            count = 0;
        }
    }
    for(int i=0;i
        cout<