【网易互娱模拟笔试】解题记录

野性酷女 2021-11-05 07:04 269阅读 0赞

08-04那天参加了一下网易互娱的模拟笔试，那天状态不太好，再加上调试第一题花了很长时间，心态有点炸了，所以最后完成得并不理想。  
总结：笔试心态还不够稳，手速还不够快，算法还不够熟。

一共 3 道题，题目都很简单，但是自己并没有做完，汗颜羞愧。记录一下。

## 第一题 个税缴纳 ##

新税收政策中，起征点是5000，超过5000的部分，需要进行分级纳税，请根据新纳税表计算个人所得税，题目如图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70]  
**要求：**  
多行输入，每行输入月收入，假设无需缴纳其他费用，请输出计算出所需缴纳的个人所得税，税费四舍五入。

**实现：**

// 计算个人所得税，income: 个人收入， taxs: 汇率表
    int calTax(int income, map<int, double> &taxs){
        
        int len = taxs.size();
        if(income <= 5000){
        
            return 0;
        }
        income  = income - 5000;
        int i   = 0;    // 记录当前为第几个区间
        int res = 0;
        map<int, double>::iterator iter_cur  = taxs.begin();      // 当前区间迭代器
        map<int, double>::iterator iter_next = ++taxs.begin();    // 下一区间迭代器，用于取得下一区间的起始值
        for(; iter_cur != taxs.end(); iter_cur++, iter_next++){
        
            if(income - iter_cur->first <= 0){
        
                break;
            }else{
        
                int range_tax;  // 当前区间所需缴纳的税额
                if(income >= iter_next->first && i < len - 1){
          // 收入大于当前纳税区间的最大值，即大于下一区间的起始值时。并且当前区间不是最后一个区间
                    range_tax = round((iter_next->first - iter_cur->first) * iter_cur->second);  // 直接区间值 * 区间税率
                }else{
        
                    range_tax = round((income - iter_cur->first) * iter_cur->second);            // 收入与区间起始值的差 * 区间税率
                }
                res += range_tax;
                i++;
            }
        }
        return res;
    }
    
    
    int main(){
        
        int T;
        map<int, double> taxs = {
           // 税率表
            {
        0,     0.03},
            {
        3000,  0.1},
            {
        12000, 0.2},
            {
        25000, 0.25},
            {
        35000, 0.3},
            {
        55000, 0.35},
            {
        80000, 0.45}
        };
    
        cin >> T;
        while(T--){
        
            int N;
            int tax;
            cin >> N;
            cout << calTax(N, taxs) << endl;
        }
    	return 0;
    }

AC 100%  
[源码地址][Link 1]

## 第二题 字符串缩写 ##

将4个及4个以上连续字典序的字母转为"首个字母-结束字母"的形式。  
如 “ABCABCDEFGABCD” → “ABCA-GA-D”。字母都为大写字母，没有其他字符。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 1]

**要求：**  
多行输入，每行一个长度不超过5000的字符串。  
输出 缩写后的字符串。

**官方给出的解题思路：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 2]  
算法复杂度是 O(N)

**个人思路实现：**

// 压缩字符串函数，返回缩写后的字符串
    string compressString(string str){
        
        int len = str.size();
        if(len < 4){
        
            return str;
        }
        string res = "";        // 返回结果
        string sub_str = "";    // 用于暂存子串
        int i = 0;
        for(; i < len - 1; i++){
        
            if(str[i] + 1 == str[i + 1]){
        
                sub_str += str[i];
            }else{
        
                if(sub_str.size() >= 3){
        
                    res = res + sub_str[0] +  "-" + str[i];
                }else{
        
                    res = res + sub_str + str[i];
                }
                sub_str = "";   // 初始化
            }
        }
    
        if(sub_str.size() >= 3 && str[i - 1] + 1 == str[i]){
          // 因为 str[len - 1] 尚未遍历，所以还需再判断一次
            res = res + sub_str[0] + "-" + str[i];
        }else{
        
            res = res + sub_str + str[i];
        }
        return res;
    }
    
    
    int main(){
        
        int T;
        cin >> T;
        while(T--){
        
            string s;
            cin >> s;
            cout << compressString(s) << endl;
        }
    	return 0;
    }

[源码地址][Link 2]

## 第三题 ##

由于打字员失误，整数 N 的 X 进制和 Y 进制连在一起输出了，请根据X、Y两个进制连起来的字符串，识别出这个整数 N 的十进制值。数据保证只有一个解。  
![在这里插入图片描述][20190808200059938.png]

**要求：**  
多行输入，每行输入为 X Y Z 的形式，2 <= X, Y <= 16，Z 为 N 的 X 进制及 Y 进制连起来的字符串，请根据 X Y Z 识别出 N，并输出 N 的十进制。10 ~ 15 用大写 A ~ F 表示。0 < N < 2^31 - 1  
如  
输入：13 7 1016  
输出：13

**官方思路：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 4]

**个人思路实现：**

// 进制转换函数， 将 k 机制字符串转换为十进制数
    long long kToDec(int k, string str){
        
       int len = str.size();
       long long res = 0;
       for(int i = 0; i < len; i++){
        
           if(str[i] >= 'A' && str[i] <= 'F'){
        
               res = res * k + (str[i] - 'A') + 10;
           }else{
        
               res = res * k + (str[i] - '0');
           }
       }
       return res;
    }
    
    // 识别数字函数，返回识别结果
    long long identifyNum(int x, int y, string str){
        
       int len  = str.size();
       int left = 0;
       int right = len - 1;
       while(left < right ){
                   // 使用二分法寻找两种进制的“中位数”
           int median = (left + right) / 2;
           long long num1   = kToDec(x, str.substr(0, median + 1)); // 左子串转换成十进制
           long long num2   = kToDec(y, str.substr(median + 1));    // 右子串转换成十进制
           if(num1 < num2){
        
               left = median + 1;
           }else if(num1 > num2){
        
               right = median;
           }else{
        
               return num1;
           }
       }
       return -1;
    }
    
    int main(){
        
       int T;          // 样例数
       cin >> T;
       while(T--){
        
           int X, Y;   // X 进制，Y 进制，
           string Z;   // 为数字字符串
           cin >> X >> Y >> Z;   // 最大输入示例：2 16 11111111111111111111111111111111FFFFFFFF
           cout << identifyNum(X, Y, Z) << endl;
       }
       return 0;
    }

[源码链接][Link 3]

第二、第三题我参考了一个哥们三题全AC的代码，他是用JAVA写的，感兴趣的可以去看看，参考链接：  
[https://www.nowcoder.com/discuss/216766][https_www.nowcoder.com_discuss_216766]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70]: /images/20211104/1ef32b56fcfe4cfd8cf97a3ad933bac5.png
[Link 1]: https://github.com/yohstone/programming-practice/blob/master/netease_simulate_test-1-individual%20income%20tax.cpp
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 1]: /images/20211104/c0852c3a607d4b9aa23986c08c3f35cd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 2]: /images/20211104/274e7bd4736242e8a174d6b17c45fed6.png
[Link 2]: https://github.com/yohstone/programming-practice/blob/master/netease_simulate_test-2-string%20abbreviation.cpp
[20190808200059938.png]: /images/20211104/d9a03a8c3afa4aa4bfa287dfa5a7c96b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 3]: /images/20211104/191926f376f74caf800fc83e7be02b86.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9zdGV2ZS5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 4]: /images/20211104/d9fe9179f3654766825789a1cf3300f1.png
[Link 3]: https://github.com/yohstone/programming-practice/blob/master/netease_simulate_test-3-identify%20num%20of%20diff%20system.cpp
[https_www.nowcoder.com_discuss_216766]: https://www.nowcoder.com/discuss/216766