数组 Array

1、数组、链表、跳表 - 图1

Array 实战题目

  • 两数之和（近半年内，字节跳动在面试中考查此题达到 152 次）

    1、声明一个map, 遍历数组，如果target - nums[i] 的差值不在map中，将该值存在map中（值为key, 下标为index） 2、如果target - num 在 map中，返回 num 对应的下表和map 中对应key 的index

  1. // 两数之和
  2. const towNum = function(nums, target){
  3.     let numMap = new Map()
  4.   for(let i=0; i<nums.length; i++){
  5.           if(numMap.has(target - nums[i])){
  6.           return [i, numMap.get(target - nums[i])]
  7.       }else{
  8.           numMap.set(nums[i], i)
  9.       }
  10.   }
  11. }
  • 盛最多水的容器（腾讯、百度、字节跳动在近半年内面试常考）

    暴力法 1、双层循环，i 从数组头开始， 在arr.length-1 结尾； j 从数组的i+1开始，在arr.length结尾 2、计算 area = Math.min(num[i], num[j]) * (j-i) 的面积

  1. let maxContainer = function(nums){
  2.     if(nums === null || nums.length <2){return}
  3.   let maxArea = 0;
  4.   for(let i=0; i<nums.length-1; i++){
  5.       for(let j=1; j<nums.length; j++){
  6.             let area = Math.min(nums[i], nums[j]) * (j-i);
  7.           maxArea = Math.max(area, maxArea)
  8.     }
  9.   }
  10.   return maxArea;
  11. }

双指针方法（左右夹逼） 1、数组的左右声明两个指针 2、左右指针未相遇时，每一次移动纵坐标小的那个指针（横坐标距离越远，纵坐标越大面积越大） 3、直到两个指针相遇

  1. let maxContainer = function(nums){
  2.     if(nums === null || nums.length <2){return}
  3.   let i = 0, j=nums.length-1, maxArea = 0;
  4.   while(i<j){
  5.       let area = Math.min(nums[i], num[j]) * (j-i)
  6.     maxArea = Math.max(area, maxArea);
  7.     if(nums[i] < nums[j]){
  8.         i++;
  9.     }else{
  10.         j--;
  11.     }
  12.   }
  13.   return maxArea;
  14. }
  • 移动零（华为、字节跳动在近半年内面试常考）

    快、慢指针 1、 声明一个指针i 慢指针 j 2、遍历数组，如果当前元素不是0，移动到j的位置，j 前进一步 3、直到数组遍历完成

  1. /**
  2.  *           // 初始化 j = 0、i = 0， i不为0，i前进1步
  3. [0,1,0,2]    // i的值非0，和 j 互换位置， j、i 前进1步
  4.  j i
  5. [1,0,0,2]    // i的值为0，不操作，i前进
  6.    j i
  7. [1,0,0,2]    // i的值非0，和 j 互换位置， j、i 前进1步
  8.    j   i
  9. [1,2,0,0]    // 遍历结束
  10. */
  11. /**
  12. [1,0,0,2]
  13.        i
  14.    j
  15.  */
  17. let moveZero = function(nums){
  18.     if(nums === null || nums.length === 0){return }
  19.   let j = 0
  20.   for(let i=0; i<nums.length;i++){
  21.     if(nums[i] !== 0){
  22.         let temp = nums[j];
  23.       nums[j] = nums[i];
  24.       nums[i] = temp;
  25.       j++;
  26.     }
  27.   }
  28. }
  • 爬楼梯（阿里巴巴、腾讯、字节跳动在半年内面试常考）

    1、问题的本质是斐波那契数列 暴力递归法（2 n）

  1. var climbStairs = function(n) {
  2.     if(n<=2){return n}
  3.       return climbStairs(n-1) + climbStairs(n-2)
  4. };

遍历指针移动

三指针移动法 知道前两个指针对应的值，推导第三个 推导第三个后，前两个指针向前移动

  1. var climbStairs = function(n) {
  2.       if(n<=2){return n}
  3.        let a=1, b=2,c;
  4.       for(let i=2; i<n.length;i++){
  5.         c = a + b;
  6.       a = b;
  7.       b = c;
  8.     }
  9.       return c;
  10. };
  • 三数之和（国内、国际大厂历年面试高频老题）

    双指针法 1、排序，遍历数组，左右定义两个指针 j = i+1; k = num.length-1 2、如果三个数的和等于0，两个指针向中间靠近； j++; k— 3、如果三个数的和小于0， j++, 如果三个数的和大于0， k— 4、⚠️ 需要对重复元素去重

  1. let threeNum = function(nums){
  2.     if(nums === null || nums.length<=2 ){return []}
  3.   let threeNumArr = []
  4.   nums.sort((a, b)=>{return a-b})
  5.   for(let i=0; i<nums.length-2; i++){
  6.       if(nums[i]>0) break; // 如果i大于0, 则j、k肯定大于0 无效
  7.     if(i >= 1 && nums[i] === nums[i-1]) continue; // 对i去重
  8.     let j = i+1, k= nums.length-1;
  9.     while(j<k){
  10.           let sum = nums[i] + nums[j] + nums[k]
  11.         if(sum === 0){
  12.           threeNumArr.push([nums[i], nums[j], nums[k]])
  13.                     while(j < k && nums[j] === nums[j+1]) j++; // 对j去重
  14.           while(j < k && nums[k] === nums[k-1]) k--; // 对k去重
  15.           j++;
  16.           k--;
  17.         }else if(sum < 0){
  18.             j++;
  19.         }else {
  20.             k--;
  21.         }
  22.     }
  23.   }
  24.   return threeNumArr;
  25. }

链表 linked list

1、数组、链表、跳表 - 图2

命题规律

1、数组、链表、跳表 - 图3

跳表 skip List

跳表只能应用于元素有序的链表下 对标 平衡树 和 二分查找，插入/删除/搜索 都是O(log n)

如何提高链表查找的效率？
建立索引
时间复杂度：O(log n)
空间复杂度：O(n)

Linked List 实战题目

做题的最大误区

1、做题只做一遍

优化的思想

1、空间换时间
2、一维升二维

做题懵逼的时候

1、暴力解法
2、最基本的问题如何解决：想最简单的问题（找最小重复单元）
计算机只能处理 for while / if else / 递归 recursion

数组常用API总结

API 用法汇总、返回值、对原数组的影响

新增数组

  1. let arr1 = [] // 数组字面量
  2. let arr2 = new Array(3) // 构造函数 [empty × 3] 会创建“稀疏数组”，不推荐
  3. let arr3 = Array.of(3,3,4,5) // [3, 3, 4, 5]
  4. let arr4 = Array.from({length:3}) //将类数组对象转为数组对象(创建给定长度的数组) [undefined, undefined, undefined]
  • 数组字面量
    • let arr1 = []

  • Array( ) / new Array( )

    • 构造函数，会创建“稀疏数组”，不推荐，可以使用Array.of() 代替
      1. new Array(3) // 传入一个参数，指函数的长度 [empty × 3]
      2. new Array(1,2,3) // 当传入的参数大于等于2个时，指传入数组的元素 [1,2,3]

  • Array.from( )

    • 对于不支持ES6的，可以使用 Array.prototype.slice()

    • 将类数组对象（array-like Object）和可遍历对象（包括Set 和 Map）转化为真正的数组

      • 类数组对象: 本质是含有length属性的对象 

        1. let arr4 = Array.from({length:3}) //将类数组对象转为数组对象(创建给定长度的数组) [undefined, undefined, undefined]

      • 可遍历对象：字符串、Set、Map

  • Array.of( )

    • 将一组值，转换为数组
    • 主要是用来替代 Array() / new Array() 传入不同参数导致的重载和行为不统一问题
      1. let arr5 = Array.of(1,2,3); // [1,2,3]

      增

  • push(val, val2)

    • 向数组尾部增加一/n个元素，返回数组的新的长度, 改变原数组

  • unshift(val, val2)

    • 向数组头部增加一/n个元素，返回数组的新的长度, 改变原数组

      删

  • pop()

    • 删除并返回最后一个元素，改变原数组

  • shift()

    • 删除并返回第一个元素，改变原数组

      改

  • splice(index, length, [增加元素1，增加元素2…]): 从index起，删除length个元素，[可选]增加几个元素

    • 返回被删除元素组成的数组
    • 改变原数组
      1. let arr = [1,2,3]
      2. arr.splice(1,2,2.1,2.2) // 返回删除元素组成的数组,即[2,3] 如果没有删除元素，则返回空数组

  • slice(startIndex, endtIndex) 剪切 返回从startIndex开始【包括】到endIndex【不包括】之间的元素组成的数组

    • 返回从startIndex开始到endIndex之间的元素组成的数组（含头不含尾）
    • 不改变原数组
    • 不填写参数，剪切整个数组（copy 数组，不相等）
      1. let arr5 = [1,2,3]
      2. arr5.slice(0,1) // [1]

      查

  • arr [index]

    拼接

  • concat(val, [val, val, [val]])

    • 合并两个或者多个数组，返回新数组
    • 不改变原数组
    • 如果拼接的是数组，会合并到拼接的数组上（只会打开外层的数组）
      1. let arr = [1,2,3]
      2. let newArr = arr.concat(4,[5,6,[7]]) // [1, 2, 3, 4, 5, 6, [7]]

  • join()

    • 用特定的标识符将数组中元素拼接为字符串
    • 返回转换后的字符串
    • 不改变原数组
  • sort()
    • 按ascii码排序
    • 返回排序后的数组
    • 改变原数组
  • reverse()
    • 颠倒数组中元素的顺序
    • 返回颠倒后的数字组成的数组
    • 改变原数组
  • indexOf(元素，startIndex)
    • 从startIndex开始，从头到尾查找元素在数组中的位置
    • 如果存在，返回一个元素位置的下标，否则返回-1
    • 不改变原数组
  • lastIndexOf(元素，startIndex)
    • 从startIndex开始，从尾到头查找元素在数组中的位置
    • 如果存在，返回一个元素位置的下标，否则返回-1
    • 不改变原数组

  • find()

    • 找出数组中第一次满足条件的元素，并返回该元素，如果找不到，返回 undefined
    • 不改变原数组
      1. arr.find(function(ele, index, array){
      2. return ele === 1
      3. })

  • findIndex()

    • 作用同indexOf()， 区别是参数是回调函数
    • 返回第一个满足条件的下标，并停止寻找
    • 不改变原数组
      1. arr.findIndex(function(ele, index, array){
      2. return ele === 2
      3. })

  • includes(元素)

    • 检查数组中是否包含某个元素，返回布尔值
    • 不改变原数组

  • Array.isArray()

    • 判断元素是否是数组

      遍历

  • for

    1. for(let i=0; i<arr.length;i++){
    2.   console.log(i);
    3. console.log(arr[i]);
    4. }

  • for (let item of arr) 

    1. for(let item of arr){
    2. console.log(item) // 数组中的元素
    3. }

  • for (let index in arr) 

    1. for(let index in arr){
    2.   console.log(index) // 数组下标
    3. console.log(arr[index]) // 数组中的元素
    4. }

  • forEach()

    • 遍历整个数组，中途不能中断

  • map()

    • 根据需求格式化原数组，返回「格式化后的」新数组
    • 不改变原数组
      1. let formatArr = arr.map(function(ele, index, array){
      2. return ele + 1;
      3. })

  • some()

    • 对数组中的项目运行给定的函数，若存在一项或者多项符合条件，则返回true，否则返回false（返回布尔值）
    • 不改变原数组
      1. let isSomeBig = arr.some(function(ele, index, array){
      2.    return ele > 3;
      3. })

  • every()

    • 对数组中的每一项运行给定的函数，若每一项都符合，则返回true，否则返回false(返回布尔值)
    • 不改变原数组
      1. let isEveryBig = arr.every(function(ele, index, array){
      2.    return ele > 3;
      3. })

  • reduce()

    • 数组归并方法：利用指定的函数将数组中的两个值化简为一个值，并返回化简后的值
    • 不改变原数组
      1. let arrSum = arr.reduce(function(prev,cur,index,array ){
      2.    // [1] 初始变量（默认为数组的第一个元素，函数执行第一次后的返回值作为函数第二次执行的初始变量，以此类推）
      3.   // [2] 当前变量
      4.  // [3] 当前变量在数组中的索引（从0开始）
      5.  // [4] 原数组对象
      6.  return prev + cur;
      7. })

  • filter()

    • 返回 「数组中满足条件的元素组成的」新数组
    • 不改变原数组
      1. let filterArr = arr.filter(function(ele, index, array){ // ele: 当前元素 index：当前下标 array：原数组对象
      2. return ele < 10;
      3. })

  • flat()

    • 用于将嵌套数组“拉平”
    • 返回一个新数组，不改变原数组
    • 默认只拉平1层，可以通过传入参数拉平多层，传flat(Infinity) 全部拉平
      1. let arr = [1,2,3,[4],[[5]]]
      2. let flatArr = arr.flat(); // [1,2,3,4,[5]]
      3. let flatArr2 = arr.flat(Infinity); // [1,2,3,4,5]

  • flatMap()

    • 对原数组每一个成员执行一个函数（Array.prototype.map()），然后对返回值组成的数组执行flat() 方法
    • 只能展开一层
    • 不改变原数组
      1. let arr = [1,2,3]
      2. let flatMap = [1,2,3].flatMap(x=>[x,x*2]) // [1,2,2,4,3,6]

  • fill()

    • 使用给定的值，填充一个数组
    • 可以接受第二个和第三个参数，用于指定填充的起始位置和结束位置
    • 改变原数组
      1. let arr = ['a','b','c'];
      2. ['a','b','c'].fill('1',1,2) // ['a','1','c'] (含头不含尾)

  • copyWithin()

    • 在当前数组内部，将指定的位置的成员复制到其他的位置（会覆盖原有的成员）

    • 返回当前数组，改变原有数组

      1. Array.prototype.copyWithin(target, start = 0, end = this.length)

    • target（必须）从该位置开始替换

    • start：从该位置开始读取数据
    • end：到该位置停止读取数据
    • 注意: 不会改变数组的长度，只会将元素移动到特定的位置
      1. // 将3号位复制到0号位
      2. [1, 2, 3, 4, 5].copyWithin(0, 3, 4)
      3. // [4, 2, 3, 4, 5]

  • sort(sortFn)

    • 如果省略sortFn，表示按照字符的ASCII码从小到大（升序）进行排序
    • sortFu(a, b) 接收两个参数, a, b代表每次参与排序的两个项目
    • 改变原数组
      1. let arr = [1,2,3]
      2. arr.sort(function(a,b){
      3. console.log('a', a,'-b',b, '--a-b', a-b);
      4. return a-b; // 从小到大
      5. // return b-a; // 从大到小
      6. })
      7. console.log(arr);
      image.png