【秋招笔经】大厂笔试题1

问题1

给你一个由n个正整数组成的数组nums。
你可以对数组的任意元素执行任意次数的两类操作:
(1)如果元素是偶数，除以2

例如，如果数组是[1,2,3,4] ,那么你可以对最后-个元素执行此操作，使其变成[1,2,3,2]

(2)如果元素是奇数，乘上2

例如，如果数组是[1,2,3,4] ，那么你可以对第一个元素执行此操作， 使其变成[2,2,3,4]

数组的偏移量是数组中任意两个元素之间的最大差值。

结果是：返回数组在执行某些操作之后可以拥有的最小偏移量。

示例1：
输入：nums=[1，2，3，4]
输出：1
解释:你可以将数组转换为[1，2，3，2]， 然后转换成[2，2，3，2]， 偏移量是3-2=1

示例2：
输入：nums=[4，1，5，20，3]
输出：3
解释:两次操作后，你可以将数组转换为[4，2，5，5，3]， 偏移量是5- 2=3

思路：我们可以同时增大数组，将所有的奇数都变成最大偶数，这样之后的操作就只能用除法，每次操作都用最大值区做除法，拉近最大值和最小值之间的差值，这样我们想要的偏移量就能达到最小。

       //排序
     function sort(arr) {
            return arr.sort((a, b) => {
                return a - b;
            })
        }
        function minmumDeviation(arr) {
            //先放大数组（将里面的奇数值都乘以2）
            let maxArr = arr.map(item => {
                    return item = item % 2 === 0 ? item : item * 2;
                })
                //进行排序
            sort(maxArr);

            let maxVal = maxArr[maxArr.length - 1];
            let minVal = maxArr[0];
            //diff用来判断最大偏移量
            let diff = maxVal - minVal;
            while (maxArr % 2 === 0) {
                // 出队最大元素(先出队做除法操作以后再入队)
                let temp = maxArr.pop();
                // 缩小最大元素
                let tempVal = temp / 2;
                // 放入数组
                maxArr.push(tempVal);
                // 排序
                sort(maxArr);
                // 最小差值（）
                let tempDiff = Math.min(diff, maxArr[maxArr.length - 1] - maxArr[0]);
                if (tempDiff < 0) break;
                diff = tempDiff;
                // 重新获取最大值
                maxVal = maxArr[maxArr.length - 1];
            }
            return diff;
        }

        let nums = [1, 2, 3, 4];
        console.log(minmumDeviation(nums));
'
运行
运行

问题2

小红想知道，n的阶乘十进制表示总共有多少个‘0’？
思路：先求n的阶乘，然后遍历将数字转化为字符串，遍历0的个数即可。

    var sum = 1;
        var n = prompt('请输入n');
        for (let i = 1; i <= n; i++) {
            sum *= i;
        }
        var s = sum.toString();
        var count = 0;
        for (i in s) {
            if (s.charAt(i) === '0') {
                count++;
            }
        }
        console.log(count);

问题3

动态回文：小红拿到一个字符串，她准备删除其中一段区间，使得剩下的部分是回文。小红希望得到的字符串的长度尽可能的大，你能求出这个长度吗？

示例1：
输入：abca
输出：3
解释：删除区间[2,2]，形成字符串aca是回文的

示例2：
输入：cbcbacabb
输出：3
解释：删除区间[4，9]，形成字符串cbc是回文的，可以证明，无法得到更长的回文串

这个问题我们可以分成两部分来解决：1.切区间 2.判断回文

         // 动态回文
        // 先切割字符串
        function cutString(str) {
            let arr = str;
            let maxlen = 0;
            for (let i = 0; i < arr.length; i++) {
                for (let j = i; j < arr.length; j++) {
                    let cut = arr.split('');
                    cut.splice(i, j);
                    if (judgmentpPalindrome(cut)) {
                        maxlen = Math.max(maxlen, cut.length);
                    }
                }
            }
            return maxlen;
        }

        //判断回文
        function judgmentpPalindrome(arr) {
            let i = 0;
            let j = arr.length - 1;
            while (i < j) {
                if (arr[i] !== arr[j]) {
                    return false;
                }
                i++;
                j--;
            }
            return true;
        }

        let str = "cbcbacabb";
        console.log(cutString(str));
'
运行
运行

零件组装

小明管理了一家工厂，该工厂生产一种大型机械，需要由四种零件组装完成。我们不妨称这四种零件为A，B，C，D
由于生产机械需要保证产品的质量，工厂对每个零件会进行检测，量化出每个零件的评分，评分当然有一个合格的分数(我们不妨假设它是x)，当零件评分大于x的时候，该零件才是合格的。
四个分别合格的零件A，B，C，D可以组装成一个合格的大型机械。现在小明想如道当前产出的这些零件一共可以组装成多少合格的大型机械?
请注意:每个零件至多只能用于一个大型机械的组装，不能反复组装。
输入描述：
第一行五个正整数，前四个正整数a1，a2，a3，a4分别表示有a1个零件A，a2个零件B，a3个零件C，a4个零件D，第五个正整数x表示合格的零件评分需要大于x。
接下来4行:
第二行有a1个空格分开的数字，分别表示这a1个零件A的评分。
第三行有a2个空格分开的数字，分别表示这a2个零件B的评分。
第四行有a3个空格分开的数字，分别表示这a3个零件C的评分。
第五行有a4个空格分开的数字，分别表示这a4个零件D的评分。
输出描述：
输出一个数，表示可以组装成的大型机械的数量。

样例输入：
1 2 2 1 2
4
7 7
6 6
8
样例输出：
1

这个题的思路就是求数组中，数组元素大于这个标准的x的个数，求出来之后，找到最小值就可以了

let stardand=read_line.split("").map(v=>parseInt(v));
let A=stardand[0];
let B=stardand[1];
let C=stardand[2];
let D=stardand[3];
let x=stardand[4];
let line
let arr=[];
while((line=read_line())!=''){
let input =line.split(" ").map(v=>parseInt(v));
arr.push(input);
}
let obj = {};
for (let i = 0; i < arr.length; i++) {
 let count = 0;
 for (let j = 0; j < arr[i].length; j++) {
 //找到数组里面的元素，判断是否合格，合格就+1
   if (arr[i][j] > x) {
     count++;
   }
 }
 obj[i] = count;
}

let res = Object.values(obj); //返回一个给定对象自身的所有可枚举属性值的数组
//最后判断这个数组里面的最小值，这个最小值就是合格的大型机械数
let t = Math.min(...res);
console.log(t);

支配数

小A认为如果在数组中有一个数出现了至少k次且这个数是该数组的众数(即出现次数最多的数之一)那么这个数组被该数所支配。显然，当k比较大的时候有些数组不被任何数所支配。现在小A想知道她所拥有的数组A中有多少个区间是被某个数所支配的。

输入描述：
第一行有两个正整数n，k(2<=k<=n<=100000)。n代表小A所拥有的数组A的长度，k代表问题描述中的参数。
第二行有n个正整数，代表A中元素的值。值的范围在1到n之间。

输出描述：
一个非负整数，代表所求的答案。

样例输入：
6 2
1 2 1 3 2 3
样例输出：
8
提示：
输入中[1，2，1] 、[1，2，1，3] 、[1，2，1，3，2] 、[1，2，1，3，2，3]、[2，1，3，2] 、[2，1，3，2，3] 、[1，3，2，3] 、[3，2，3] 这8个区间均被某些数所支配

思路：如果小区间存在这个可支配的数，那就不需要在遍历了，后面扩展的大区间是一定符合的，直接返回剩余可以扩展的长度就好了

let n = 6;
let k = 2;
let res = 0;
let arr = [1, 2, 1, 3, 2, 3];
function hasKing(nums, k) {
  let map = new Map();
  for (let i of nums) {
    map.set(i, map.has(i) ? map.get(i) + 1 : 1);
   // set() 方法为 Map 对象添加或更新一个指定了键（key）和值（value）的（新）键值对。
  }
  
  let keys = map.keys();
  let max = map.get(nums[0]);
  for (let i of keys) {
    if (map.get(i) > max)   max = map.get(i);
  }
  return max >= k;
}
for (let i = 0; i < n; i++) {
  for (let j = k + i; j < n; j++) {
    let temp = arr.slice(i, j + 1);
    if (hasKing(temp, k)) {
      // 这里有一个思想就是 如果在小区间已经找到了，那就没有必要往大区间遍历，直接计算剩余长度就好了
      res = res + n - j;
      break;
    }
  }
}
console.log(res);
'
运行
运行