活动地址： 牛客春招刷题训练营 - 编程打卡活动

简单题：求int型正整数在内存中存储时1的个数

一种做法是直接模拟进制转换

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int cnt = 0;
    while(n) {
        cnt += (n % 2);
        n /= 2;
    }
    cout << cnt << endl;
    return 0;
}

另一种做法是直接调用C++的内置函数__builtin_popcount。

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    cout << __builtin_popcount(n) << endl;
    return 0;
}

中等题：整数与IP地址间的转换

和简单题一样，其实本质就是一个进制转换题，只不过这题是256进制（因为每一位是0~255）。

第一问是256进制转10进制，用字符串读入处理一下就行。

第二问是10进制转256进制，需要注意的是256^4-1的值超过了int范围，所以需要用long long来存。

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

int main() {
    string s;
    ll n;
    cin >> s >> n;
    ll t = 0, res = 0;
    for(auto c: s) {
        if(c == '.') {
            res = res * 256 + t;
            t = 0;
        } else {
            t = t * 10 + c - '0';
        }
    }
    res = res * 256 + t;
    vector<int> ip;
    while(n) {
        ip.push_back(n % 256);
        n /= 256;
    }
    cout << res << endl;
    while(!ip.empty()) {
        cout << ip.back();
        ip.pop_back();
        if(ip.size() != 0) cout << ".";
    }
    return 0;
}

困难题：字符串通配符

这道题是前一天的困难题（计算字符串的编辑距离）的加强版吧。

其实本质思想是一模一样的。为什么这么说呢？

因为“可以匹配得到”是不是也可以看作是编辑距离为0。

所以这道题就是有通配符的字符串编辑距离计算。

实际写起来细节比较多，不过仔细分类讨论一下就行了。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    string s, p;
    cin >> s >> p;
    int ls = s.size(), lp = p.size();
    vector<vector<int>> dp(ls+1, vector<int>(lp+1));
    for(int i=0; i<=ls; i++) {
        if(i >= 1 && s[i-1] == '*') {
            dp[i][0] = dp[i-1][0];
        } else {
            if(i >= 1) dp[i][0] = dp[i-1][0] + 1;
            else dp[i][0] = 0;
        }
        
    }
    for(int j=0; j<=lp; j++)
        dp[0][j] = j;
    auto check = [&](char x) {
        if(x >= '0' && x <= '9') return 1;
        if(x >= 'A' && x <= 'Z') return 2;
        if(x >= 'a' && x <= 'z') return 3;
        return 0;
    };
    for(int i=1; i<=ls; i++) {
        for(int j=1; j<=lp; j++) {
            if(s[i-1] == p[j-1]) dp[i][j] = dp[i-1][j-1];
            else {
                if(check(s[i-1]) + check(p[i-1]) == 5 && abs(s[i-1]-p[j-1]) == 32) {
                   dp[i][j] = dp[i-1][j-1];
                } else if(check(s[i-1])) {
                    dp[i][j] = 1;
                } else if(check(p[j-1])) {
                    if(s[i-1] == '*') {
                        dp[i][j] = min(dp[i-1][j], dp[i][j-1]);
                        dp[i][j] = min(dp[i][j], dp[i-1][j-1]);
                    } else if(s[i-1] == '?') {
                        dp[i][j] = dp[i-1][j-1];
                    } 
                } else {
                    dp[i][j] = 1;
                }
            }
        }
    }
    if(dp[ls][lp] == 0) cout << "true" << endl;
    else cout << "false" << endl;
    return 0;
}