【2021-09-18】网易秋招笔试四道编程题

旧城等待， 2022-08-28 13:44 292阅读 0赞

> 通知：最新的秋招笔试编程题题目、思路以及参考代码已经全部整理好放在【TechGuide】了，私信公众号回复【网易】或者【百度】即可获得最实时的笔试题解啦！

> 通知：最新的秋招笔试编程题题目、思路以及参考代码已经全部整理好放在【TechGuide】了，私信公众号回复【网易】或者【百度】即可获得最实时的笔试题解啦！  
> ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAVGVjaEd1aWRl_size_13_color_FFFFFF_t_70_g_se_x_16_pic_center]

【2021-09-04】美团秋招笔试五道编程题（附题目）  
【2021-09-03】贝壳秋招笔试四道编程题（前三道ac）  
【2021-09-01】阿里巴巴秋招笔试两道编程题  
【2021-09-01】华为秋招机试三道编程题（附题目，后两题AC）  
【2021-08-29】美团秋招笔试四道编程题  
【2021-08-29】字节跳动秋招笔试四道编程题  
【2021-08-26】腾讯音乐秋招笔试编程三道题  
【2021-08-25】华为秋招机试三道编程题  
【2021-08-23】阿里巴巴秋招笔试两道编程题  
【2021-08-22】腾讯秋招笔试五道编程题  
【2021-08-22】美团秋招笔试五道编程题（待更新）  
【2021-08-21】网易秋招机试四道编程题（待更新）  
【2021-08-14】荣耀秋招机试三道编程题（已更新）  
【2021-08-18】华为秋招机试三道编程题（已更新）  
【2021-08-18】阿里秋招笔试两道编程题  
【2021-08-15】美团秋招笔试五道编程题（已更新）  
【2021-08-12】携程秋招笔试三道编程题  
【2021-08-11】华为秋招机试三道编程题(已更新)  
【2021-08-09】阿里巴巴秋招笔试两道编程题  
【2021-08-08】拼多多秋招笔试四道编程题  
【2021-08-08】美团秋招笔试五道编程题  
【2021-08-08】好未来秋招三道编程题  
【2021-08-07】网易互娱秋招笔试三道编程题  
【2021-08-04】华为秋招两道编程题

### 文章目录 ###

*  以下题解整理于牛客网，\[链接\](https://www.nowcoder.com/discuss/750297?type=0&order=1&pos=12&page=1&source\_id=discuss\_center\_0\_nctrack&channel=1009&ncTraceId=bad2c21b6dc64535b9129ee2db01582f.204.16320577421069024)已附上，侵删。
 *  第一道：计算个数
 *   *  题目描述
     *  参考代码
 *  第二道：魔法键（100%）
 *   *  题目描述
     *  参考代码：
     *   *  CPP版本
         *  JavaScript版本
 *  第三道：最少个数（100%）
 *   *  题目描述
     *  参考代码
     *   *  CPP版本
         *  JavaScritp版本
 *  第四道：数字迷宫（100%）
 *   *  题目描述
     *  参考代码
     *   *  JavaScript版本

# 以下题解整理于牛客网，[链接][Link 1]已附上，侵删。 #

# 第一道：计算个数 #

## 题目描述 ##

计算某个数x所有位数中能被x整除的数量。

思路是遍历每个位，然后判断是否整除即可。

## 参考代码 ##

const num = parseInt(readline());
    let temp = num;
    let ret = 0;
    while (temp) { 
      const e = temp % 10;
      if (num % e === 0) { 
        ret += 1;
      }
      temp = Math.floor(temp / 10);
    }
    
    console.log(ret);
    // 关注TechGuide！ 大厂笔经面经闪电速递！

# 第二道：魔法键（100%） #

## 题目描述 ##

现在给定一个键盘如下:

![在这里插入图片描述][5104a7063928452e852deb78a531fd27.png]

你需要用它输出一个字符串，输入的规则如下:

1.  初始光标可以在任何位置
2.  按方向键，可以花费一次操作左右移动光标。光标从A向左可以移动到Z从Z向右可以移动到A。可以理解为是一个圈。
3.  按魔法键，可以花费一次操作，使光标移动到任何位置，但魔法键要么一次都不用，要么必须使用m次，并目这些操作必须是连续输入的(中间可以播入确认键的操作)。例如要输出ADDA，m的值为2时，不能同时选择第一步(A移到D)和第三步(D移到A)，只能选择【第一步第二步】或者【第二步第三步】。(具体说明参考样例4)
4.  按确定键，可以花费一次操作输出当前光标所在字母。

现在给你一个字符串和m的值，请问输出该字符串最少需要多少次操作。

**输入描述**  
输入一行字符串S，和一个整数m，  
保证：  
len(S)<10^6  
m<10^5，  
m<len(s)  
输入的字符串一定都是大写字母

ccccc 3

**输出描述**  
输出一个整数X代表最少次数。

## 参考代码： ##

### CPP版本 ###

先把每一步需要的步数计算出来，找到滑动窗口为m时的最多步数，如果这些步数大于魔法键，就用魔法键代替。

#include<iostream>
    #include<string>
    #include<vector>
    #include<numeric>
    #include<math.h>
    #include<algorithm>
    using namespace std;
    int main() { 
     int m;
     string str;
     cin >> str >> m;
    
     int n = str.size();
     long long sum = 0;
     vector<int> nums(n - 1);
     for (int i = 0; i < n - 1; i++) { 
      nums[i] = min(abs(str[i] - str[i + 1]), 26 - abs(str[i] - str[i + 1]));
      sum += nums[i];
     }
    
     //找到滑动窗口大小为m时的最大值
     long long curr=0;
     for (int i = 0; i < m; i++) { 
      curr += nums[i];
     }
     long long maxSteps = curr;
     for (int i = m; i < n-1; i++) { 
      curr = curr - nums[i - m] + nums[i];
      maxSteps = max(maxSteps, curr);
     }
     if (maxSteps > m) { 
      sum = sum - maxSteps + m;
     }
     sum += n;
     cout << sum << endl;
    }
    // 关注TechGuide！ 大厂笔经面经闪电速递！

### JavaScript版本 ###

思路是求前缀和，然后比较区间，选择距离 m 前缀和差最大的区间使用魔法键

# 第三道：最少个数（100%） #

## 题目描述 ##

牛牛真的是很喜欢数学的孩子，现在读初中的牛牛遇到了一个小学奥数题，题目如此描述:"现在拥有若干个大小为整数x1,x2,…xn，可以利用这些整数做2的加减法运算，最少需要多少个形如2^x的整数进行加减法运算后才可以计算出整数s”，请你写代码告诉牛牛应该最少需要多少个整数。

**输入描述**  
输入一个整数s(0<s<10^17)

**输出描述**  
如果存在解则输出一个整数表示最少个数，如果无解输出-1。

**解释**  
1的二进制就是，所以只需要1个20

## 参考代码 ##

### CPP版本 ###

s转化为二进制1100111000，则第一种加法需要的次数就是二进制中1的个数，即=5；第二种减法得到的个数就是【从最高位开始到最后一个1 中间共有几个0】+2，即=4。

#include<iostream>
    #include<string>
    #include<vector>
    #include<numeric>
    #include<math.h>
    #include<algorithm>
    using namespace std;
    int main() { 
     long long s;
     cin >> s;
        if(s==0){ 
            cout<<-1<<endl;
            return 0;
        }
    
     long long curr = s;
     vector<int> nums;
     int ans1 = 0, ans2 = 0;
     //十进制转为二进制
     while (curr) { 
      int t = curr % 2;
      if (t == 1) { 
       ans1++;
       if (ans2 == 0) { 
        ans2 = 2;
       }
      }
      else if (ans2 != 0) { 
       ans2++;
      }
      curr = curr / 2;
      //cout << t << endl;
     }
     //cout << ans1 << " " << ans2 << endl;
     cout << min(ans1, ans2) << endl;
    }
    // 关注TechGuide！ 大厂笔经面经闪电速递！

### JavaScritp版本 ###

全部 2^n 加 或者一个大 2^n 的减很多小的 2^n

即 num = 2^x1 + 2^x2 + 2^x3 + … + 2^xn  
或 num = 2^x1 - 2^x2 - 2^x3 - … - 2^xn  
我们发现等式二可以改写成 num = 2^x1 - (2^x2 + 2^x3 + … + 2^xn)  
因此

例如对 11100 这个二进制数字  
其实可以看成 num = 2^2 + 2^3 + 2^4 其实就是求原先二进制的1的数量  
也可以看成 num = 2^6 - (2^x2 + 2^x3 + … + 2^xn)  
移项，变成 (2^x2 + 2^x3 + … + 2^xn) = 2^6 - num  
因此变成了求左边这个二进制数的 1 的数量

# 第四道：数字迷宫（100%） #

## 题目描述 ##

牛牛困在了数字迷宫里面，该数字迷宫是一个n又n的字符矩车，它由字符“\#”，“.”，“\*”组成。

其中：  
"\#"代表该位置存在障碍，牛牛不能经过它，但是牛牛可以花费a代价消除该障碍。

“.”代表该位置牛牛可以任意移动，无需代价。  
"*"代表传送门，牛牛可以使用它并花费b代价传送到迷宫中另外一个为*的位置。注意传送门是非强制性的，牛牛可以经过它但不便用它。

牛牛每次可以从位置(x,y):  
要么向右移动一格，到(x,y+1)。要么向左移动一格，到(x,y-1)要么向上移动一格，到(x-1,y).要么向下移动一格，到(x+1,y)。当然，牛牛不能走到迷宫外面去。  
牛牛的起点在位置(1,1)，他想知道走到迷宫出口即终点n，n所需的最小代价是多少?

**输入描述**  
第一行输入三个正整数nab，其意义如题意所述。1<a6<10002<n<1000  
接下来n行，每行一个长度为n的字符串，以此来表示nxn的娄字迷宫。注意:  
起点和终点位置不能是\#，但可以是一和!。迷宫中\*的数量要么为0，要么为2。

2 5 10
    *#
    #*

**输出描述**  
输出一行一个整数，表示牛牛走出迷宫所花费的最小代价。

**解释**  
牛牛可以使用传送门直接从(1,1)到(n,n)，但此时要花费10代价。  
花费更少代价的方法是牛牛仅用5代价消除(1,2)或者(2,1)处的障碍，再直接走向终点。

## 参考代码 ##

### JavaScript版本 ###

class Target { 
      constructor(v, i, j) { 
        this.v = v;
        this.i = i;
        this.j = j;
      }
    }
    
    class Heap { 
      constructor(cmp) { 
        this.cmp = cmp;
        this.data = [];
      }
    
      add(value) { 
        this.data.push(value);
        this.siftUp(this.data.length - 1);
      }
    
      size() { 
        return this.data.length;
      }
    
      empty() { 
        return this.data.length === 0;
      }
    
      top() { 
        return this.data[0];
      }
    
      pop() { 
        this.swap(0, this.data.length - 1);
        const value = this.data.pop();
        this.siftDown(0);
        return value;
      }
    
      leftChild(index) { 
        return index * 2 + 1;
      }
      rightChild(index) { 
        return this.leftChild(index) + 1;
      }
      swap(index1, index2) { 
        [this.data[index1], this.data[index2]] = [
          this.data[index2],
          this.data[index1],
        ];
      }
      parent(index) { 
        return Math.floor((index - 1) / 2);
      }
      siftUp(index) { 
        while (
          this.parent(index) >= 0 &&
          this.cmp(this.data[this.parent(index)], this.data[index]) < 0
        ) { 
          this.swap(index, this.parent(index));
          index = this.parent(index);
        }
      }
      siftDown(index) { 
        while (this.leftChild(index) < this.data.length) { 
          const leftChildIndex = this.leftChild(index);
          const rightChildIndex = this.rightChild(index);
          let swapIndex = leftChildIndex;
          if (
            rightChildIndex < this.data.length &&
            this.cmp(this.data[rightChildIndex], this.data[leftChildIndex]) > 0
          ) { 
            swapIndex = rightChildIndex;
          }
          if (this.cmp(this.data[index], this.data[swapIndex]) > 0) { 
            break;
          }
          this.swap(index, swapIndex);
          index = swapIndex;
        }
      }
    }
    
    const heap = new Heap((v1, v2) => v2.v - v1.v);
    
    const nums = readline().split(' ').map(v => parseInt(v));
    const n = nums[0];
    
    const [a, b] = [nums[1], nums[2]];
    
    const lines = [];
    for (let i = 0; i < n; i += 1) { 
        lines.push(readline());
    }
    
    const graph = lines.map((line) => { 
      return [...line];
    });
    const isHere = new Array(1e3 + 10);
    for (let i = 0; i < isHere.length; i += 1) { 
      isHere[i] = new Array(1e3 + 10).fill(false);
    }
    
    let isFirst = true;
    let temp = -1;
    const MOD = 1e3 + 10;
    const map = new Map();
    for (let i = 0; i < graph.length; i += 1) { 
      for (let j = 0; j < graph[0].length; j += 1) { 
        if (graph[i][j] === "*") { 
          if (isFirst) { 
            temp = i * MOD + j;
          } else { 
            map.set(temp, i * MOD + j);
            map.set(i * MOD + j, temp);
          }
          isFirst = false;
        }
      }
    }
    
    heap.add(new Target(0, 0, 0));
    isHere[0][0] = true;
    if (map.has(0)) { 
      const pos = map.get(0);
      const x = Math.floor(pos / MOD);
      const y = pos % MOD;
      map.clear();
      heap.add(new Target(0 + b, x, y));
    }
    
    const dx = [1, 0, -1, 0];
    const dy = [0, 1, 0, -1];
    
    const getValue = (ch) => { 
      if (ch === ".") return 0;
      if (ch === "#") return a;
      if (ch === "*") return 0;
    };
    
    while (!heap.empty()) { 
      const {  i, j, v } = heap.pop();
      if (i === n - 1 && j === n - 1) { 
        console.log(v);
        break;
      }
      for (let k = 0; k < 4; k += 1) { 
        const newX = i + dx[k];
        const newY = j + dy[k];
        if (newX < 0 || newX >= n) continue;
        if (newY < 0 || newY >= n) continue;
        if (isHere[newX][newY]) continue;
    
        isHere[newX][newY] = true;
        const ch = graph[newX][newY];
        const value = newX * MOD + newY;
        if (map.has(value)) { 
          const pos = map.get(value);
          const x = Math.floor(pos / MOD);
          const y = pos % MOD;
          map.clear();
          heap.add(new Target(v + b, x, y));
        }
        heap.add(new Target(v + getValue(ch), newX, newY));
      }
    }
    // 关注TechGuide！ 大厂笔经面经闪电速递！

> 最新的秋招笔试编程题题目、思路以及参考代码已经全部整理好放在【TechGuide】了，私信公众号回复【网易】或者【百度】即可获得最实时的笔试题解啦！

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAVGVjaEd1aWRl_size_13_color_FFFFFF_t_70_g_se_x_16_pic_center]: /images/20220828/6c0a8340717a49f4b7ed1b6c677b76b3.png
[Link 1]: https://www.nowcoder.com/discuss/750297?type=0&order=1&pos=12&page=1&source_id=discuss_center_0_nctrack&channel=1009&ncTraceId=bad2c21b6dc64535b9129ee2db01582f.204.16320577421069024
[5104a7063928452e852deb78a531fd27.png]: /images/20220828/191655cdda7545fb8b12fe488bf9bac5.png