javascript 常见的面试题---数组 && 算法

小咪咪 2021-09-29 23:02 300阅读 0赞

网上汇总而来的题目。

### 第一题： ###

用 JavaScript 写一个函数，输入 int 型（正整数），返回整数逆序后的字符串。如：输入整型 1234，返回字符串“4321”。

要求必须使用递归函数调用，不能用全局变量，输入函数必须只有一个参数传入，必须返回字符串。

查看代码

1 // 推荐方法
     2 function format(num) {
     3   const num1 = num / 10;
     4   const num2 = num % 10;
     5   if (num1 < 1) {
     6     return `${num}`;
     7   } else {
     8     num = parseInt(num1);
     9     return `${num2}${format(num)}`;
    10   }
    11 }
    12 // 其他实现方法
    13 function format(num) {
    14   return `${num}`.length === 1 ? `${num}` : `${num}`.slice(-1) + format(`${num}`.slice(0, -1));
    15 }
    16 function format(num) {
        // 不符合题意，就当顺便复习下这些api吧 emmmm....
    17   return num < 10 ? `${num}` : `${num}`.split('').reverse().join('');
    18 }
    19 // 方法1简写
    20 function format(num) {
    21   return num / 10 < 1 ? `${num}` : `${num % 10}${format(parseInt(num / 10))}`;
    22 }

--------------------

###  第二题： ###

给定两个数组，写一个方法来计算它们的交集。

例如：给定 nums1 = \[1, 2, 2, 1\]，nums2 = \[2, 2\]，返回 \[2, 2\]。

查看代码

巨佬的总结：算法题，求两个数组的最长公共子序列。

思路1：空间换时间。建个表，存放其中一个数组的值和该值出现的次数。此处遍历n次，n为数组的长度。

接着遍历另外一个数组。如果数组的值出现在表的键里，则把值push进result数组。该键对应的值减一。此处遍历m次，m为数组的长度。时间复杂度O(m+n)。

代码实现：

1 function myIntersection(arr1, arr2) {
     2   const result = [];
     3   const map = {};
     4 
     5   for (let val of arr1) {
     6     if (!!map[val]) {
     7       map[val]++;
     8     } else {
     9       map[val] = 1;
    10     }
    11   }
    12 
    13   arr2.forEach(val => {
    14     if (!!map[val]) {
    15       result.push(val);
    16       map[val]--;      
    17     }
    18   });
    19   return result;
    20 }

思路2：时间换空间。遍历其中一个数组，判断另外一个数组中是否包含该值，有则push进result数组，并在另外一个数组中删除该值。

代码实现：

1 function myIntersection(arr1, arr2) {
     2   const _arr2 = [...arr2];
     3   return arr1.filter(val => {
     4     const idx = _arr2.indexOf(val);
     5     if (idx > -1) {
     6       _arr2.splice(idx, 1);
     7       return true;
     8     }
     9     return false;
    10   });
    11 }

这里直接filter方法返回数组，需要注意的是splice方法会改变原数组。

--------------------

###  第三题： ###

冒泡排序如何实现，时间复杂度是多少， 还可以如何改进？

查看代码

1 function myBubbleSort(arr, cb = (x, y) => x - y) {
     2   const res = cb(1, 2);
     3   
     4   let i, j, len = arr.length;
     5   if (res < 0) {
         // 升序
     6     for (i = 0; i < len; i++) {
     7       for(j = 0; j < len - i - 1; j++) {
     8         if (arr[j] > arr[j + 1]) {
     9           [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
    10         }
    11       }
    12     }
    13   } else {
         // 降序
    14     for (i = 0; i < len; i++) {
    15       for(j = len - 1; j > i; j--) {
    16         if (arr[j] > arr[j - 1]) {
    17           [arr[j], arr[j - 1]] = [arr[j - 1], arr[j]];
    18         }
    19       }
    20     }
    21   }
    22 }

时间复杂度O(n^2)。简单改进：

思路是把可能出现的好的情况挑出来。注意以上都直接改变了原数组。

--------------------

###  第四题： ###

某公司 1 到 12 月份的销售额存在一个对象里面。

如下：\{1:222, 2:123, 5:888\}，请把数据处理为如下结构：\[222, 123, null, null, 888, null, null, null, null, null, null, null\]

查看代码

1 function format(origin) {
    2   const res = [];
    3   for (let i = 0; i < 12; i++) {
    4     res[i] = origin[i + 1] || null;
    5   }
    6   return res;
    7 }

或者

1 function format(origin) {
    2   return Array.from(new Array(12)).map((_, i) => origin[i + 1] || null);
    3 }

--------------------

### 第五题： ###

使用 sort() 对数组 \[3, 15, 8, 29, 102, 22\] 进行排序，输出结果

查看代码

1 [3, 15, 8, 29, 102, 22].sort();

输出结果是：\[102, 15, 22, 29, 3, 8\]。

sort方法在不传回调函数的情况下。默认将值转化成字符串，然后按照字符串字符的utf-16编码比较大小。

先比较首字符。如果首字符相同，则比较第二个字符，以此类推。升序。

js查看字符串字符utf-16编码对应api是String.prototype.charCodeAt();

--------------------

### 第六题： ###

两个数组合并成一个数组

请把两个数组 \['A1', 'A2', 'B1', 'B2', 'C1', 'C2', 'D1', 'D2'\] 和 \['A', 'B', 'C', 'D'\]，合并为 \['A1', 'A2', 'A', 'B1', 'B2', 'B', 'C1', 'C2', 'C', 'D1', 'D2', 'D'\]。

查看代码

就这题而言：

1 const arr1 = ['A1', 'A2', 'B1', 'B2', 'C1', 'C2', 'D1', 'D2'];
    2 const arr2 = ['A', 'B', 'C', 'D'];
    3 const _arr = arr1.concat(arr2.map(val => `${val}3`));
    4 const newArr = _arr.sort().map(val => val.includes('3') ? val.replace('3', '') :
    5 val);

或者：

1 const newArr = arr2.reduce((cur, next) => [...cur, ...arr1.filter(val => val.startsWith(next)), next], []);

--------------------

### 第七题： ###

已知如下数组：

var arr = \[ \[1, 2, 2\], \[3, 4, 5, 5\], \[6, 7, 8, 9, \[11, 12, \[12, 13, \[14\] \] \] \], 10\];

编写一个程序将数组扁平化去并除其中重复部分数据，最终得到一个升序且不重复的数组

查看代码

方法1：

const arr3 = [ [1, 2, 2], [3, 4, 5, 5], [6, 7, 8, 9, [11, 12, [12, 13, [14] ] ] ], 10];
    const arr5 = [...new Set(arr3.flat(Infinity))].sort((x, y) => x - y);

flat方法可以将数组拍扁。Set构造函数去重，sort方法排序。

方法2：

const arr3 = [ [1, 2, 2], [3, 4, 5, 5], [6, 7, 8, 9, [11, 12, [12, 13, [14] ] ] ], 10];
    const arr6 = Array.from(new Set(arr3.join(',').split(',').map(Number).sort((x, y) => x - y)));

set构造函数去重，join方法把数组拍扁，由于值变成了字符串，split方法转成数组后，map方法加Number转成数字。sort方法排序。

方法3：

function format(arr) {
      return arr.reduce((acc, val) => Array.isArray(val) ? acc.concat(format(val)) : acc.concat(val), []);
    }

const arr3 = \[ \[1, 2, 2\], \[3, 4, 5, 5\], \[6, 7, 8, 9, \[11, 12, \[12, 13, \[14\] \] \] \], \[10\]\];

const arr4 = \[...new Set(format(arr3))\].sort((x, y) => x - y);

reduce、concat方法加递归把数组拍扁。Set构造函数去重。sort方法排序。

方法4：

1 function format(arr) {
     2   const res = [];
     3   const stack = [...arr];
     4   while (stack.length) {
     5     const next = stack.pop();
     6     if (Array.isArray(next)) {
     7       stack.push(...next);
     8     } else {
     9       res.push(next);
    10     }
    11   }
    12   return [...new Set(res)].sort((x, y) => x - y);
    13 }

栈方法把数组拍扁。使用数组的push、pop方法实现后进先出。

--------------------

### 第八题： ###

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

示例:

输入: [0,1,0,3,12]
    输出: [1,3,12,0,0]

说明:

1.  必须在原数组上操作，不能拷贝额外的数组。
2.  尽量减少操作次数。

查看代码

方法1：冒泡排序的思路。比较相邻两个值，若为0，交换位置。代码演示：

1 function format(arr) {
     2   let len = arr.length - 1;
     3 
     4   while (len) {
     5     let pos = 0;
     6 
     7     for (let i = 0; i < len; i++) {
     8       if (arr[i] === 0) {
     9         [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
    10         pos = i;
    11       }
    12     }
    13     
    14     len = pos;
    15   }
    16 }

方法2：数组的push方法实现0的移动，splice方法保持顺序不变。代码演示：

验证：

1 function format(arr) {
     2   let i, len = arr.length;
     3   for (i = 0; i < len; i++) {
     4     if (arr[i] === 0) {
     5       arr.push(0);
     6       arr.splice(arr.indexOf(0), 1);
     7       i--;
     8       len--;
     9     }
    10   }
    11 }

push0进数组后，遍历长度需要减1。0无需在遍历。删除数组当前项后，i需减1

const arr = [5, 0, 0, 0, 3, 0, 12, 0];
    format(arr);
    console.log(arr);

![1716959-20190716201632604-333573899.png][]

--------------------

### 第九题： ###

打印出 1 - 10000 之间的所有对称数

例如：121、1331 等

查看代码

方法1：对称数反过来也是原来那个数，利用这个特点。

function printNum() {
      return [...Array(10000).keys()].filter(val => val > 10 && `${val}`.split('').reverse().join('') == val);
    }

不管三七二十一循环10000次，每个值先转成字符串再拆成数组在反转在转化成字符串，最后利用隐式转换与原值比较，判断是否相等。

方法2：

1 function printNum() {
     2   let i, _i, res = [];
     3   for (i = 1; i < 10; i++) {
     4     res.push(i * 11);
     5     _i = 0;
     6     while (_i < 10) {
     7       res.push(i * 101 + _i * 10);
     8       res.push(i * 1001 + _i * 110);
     9       _i++;
    10     }
    11   }
    12   return res;
    13 }

利用对称数的特点，用数学的方式实现。外层循环9层，1-9。内层10次。总共90次。

--------------------

### 第十题： ###

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

![1716959-20190716233843871-652628345.png][]

查看代码

方法1：pop、unshift方法实现从尾到头。

1 function carousel(arr, k = 0) {
    2   let  i, len = arr.length;
    3   for (i = 0; i < k % len; i++) {
    4     arr.unshift(arr.pop(len - 1));
    5   }
    6 }

k值有可能大于数组长度，取余可以避免不必要的循环。

方法2：

function carousel([...arr], k = 0) {
      return arr.splice(-k % arr.length).concat(arr);
    }

k值有可能大于数组长度，对数组长度取余，余数为需要旋转的个数。利用splice方法第一个参数为负数时，值为数组长度+负值。

截取需要旋转的部分，然后再和原数组拼接。

有错误的地方欢迎指出。

转载于:https://www.cnblogs.com/caimuguodexiaohongmao/p/11180479.html

[1716959-20190716201632604-333573899.png]: /images/20210725/d3c891a542ac478d9d02693c26042300.png
[1716959-20190716233843871-652628345.png]: /images/20210725/d006daa6720340cab9c39ef349820b12.png