前端面试之常见算法 前端面试题csdn

1. 不通过中间变量交换两个变量的值

let a = 1, b = 5;
// 第一种方法
b = b - a;
a = a + b;
b = a - b;
// 第二种方法，解构赋值
[a, b] = [b, a]
// 第三种方法，位运算(相同元素异或运算得0，0跟其它元素异或运算得到其它元素)
a = a ^ b;
b = a ^ b; // a ^ b ^ b => a
a = a ^ b; // a ^ b ^ a => b

// 位运算的其它用法
// 1、从1-1000中随机删除一个数，求被删除的那个数。
// 2、判断奇偶数(奇数&1 === 1 偶数&1 === 0)

2. 将json数据转成树形结构

function treeNode(jsonData) {
  let result = [], temp = {}, len = jsonData.length
  for (let i = 0; i < len; i++) {
    // 以id作为索引存储元素，可以无需遍历直接快速定位元素
    temp[jsonData[i]['id']] = jsonData[i]
  }
  for (let i = 0; i < len; i++) {
    const list = jsonData[i]
    const jsonList = temp[list['parentId']]
    if (!jsonList) { // 不存在父元素，意味着当前元素是一级元素
      result.push(list);
    } else {
      jsonList.children = jsonList.children || []
      // result数组中添加的项跟当前的jsonList是对象引用的关系，
      // 所以当前jsonList添加了children，result中的项也添加了children
      jsonList.children.push(list)
    }
  }
  return result;
}

// 执行
treeNode([
  {
    id: 1,
    parentId: null,
    name: "菜单1"
  },
  {
    id: 2,
    parentId: null,
    name: "菜单2"
  },
  {
    id: 3,
    parentId: 1,
    name: "菜单1-1"
  },
  {
    id: 4,
    parentId: 1,
    name: "菜单1-2"
  },
  {
    id: 5,
    parentId: 2,
    name: "菜单2-1"
  },
  {
    id: 6,
    parentId: 5,
    name: "菜单2-1-1"
  }

])

3. 生成斐波那契数组

斐波那契数组：0、1、1、2、3、5、8、13、21、……

function getFibonacci(n) {
  const fibarr = [];
  let i = 0;

  while (i < n) {
    if (i <= 1) {
      fibarr.push(i);
    } else {
      fibarr.push(fibarr[i - 1] + fibarr[i - 2])
    }
    i++;
  }

  return fibarr;
} 

4. 数组去重

//es6去重
Array.from(new Set(arr))

// 函数去重
function unique(arr) {
  let hashTable = {};
  let data = [];
  for (let i = 0, l = arr.length; i < l; i++) {
    if (!hashTable[arr[i]]) {
      hashTable[arr[i]] = true;
      data.push(arr[i]);
    }
  }
  return data
}

5. 数组扁平化

// 第一种方法
function steamroller(arr) {
  let newArr = [];
  for (let i = 0; i < arr.length; i++) {
    if (!Array.isArray(arr[i])) {
      newArr.push(arr[i]);
    } else {
      newArr = newArr.concat(steamroller(arr[i]));
    }
  }
  return newArr;
}

// 第二种方法
function flatten(arr) {
  while (arr.some(item => Array.isArray(item))) {
    arr = [].concat(...arr)
  }
  return arr;
}

// 第三种方法，es6的flat
[1, [2], [3, [[4]]]].flat(Infinity)
// 第四种方法，toString，不过转出来的都是字符串，适合用于数组元素都是字符串的数组扁平化
[1, [2], [3, [[4]]]].toString().split(',') //  ["1", "2", "3", "4"]
['a', ['b'], 'c', [['d']]].toString().split(',') // ["a", "b", "c", "d"]

6. 实现一个函数find(obj, str)，查找对象属性的值

// 例如find(obj, 'a.b.c')得到obj.a.b.c
function find(obj, str) {
  return str.split('.').reduce((target, key) => {
    if (!target) return undefined;
    return target[key]
  }, obj)
}

7. 倒序打印链表的值

// 链表
const node = {
  val: 1,
  next: {
    val: 2,
    next: {
      val: 3,
      next: {
        val: 4
      }
    }
  }
}
// 打印出 4 3 2 1
function reverseConsole(node) {
  if (!node) {
    return
  } else {
    reverseConsole(node.next)
    console.log(node.val)
  }
}

8. 找出字符串中不重复的最长字符串

例如：abacpwwke中中不重复的最长字符串是bacpw

function longSubString(str) {
  let maxStr = '', currentStr = '', len = str.length

  for (let i = 0; i < len; i++) {
    let char = str.charAt(i);
    let index = currentStr.indexOf(char)

    if (index === -1) {
      currentStr += char
      if (maxStr.length < currentStr.length) {
        maxStr = currentStr
      }
    } else {
      currentStr = currentStr.substring(index + 1) + char
    }
  }

  return maxStr
}

9. 冒泡排序

function bubbleSort(arr) {
  for (let i = 0, l = arr.length; i < l - 1; i++) {
    for (let j = i + 1; j < l; j++) {
      if (arr[i] > arr[j]) {
        [arr[i], arr[j]] = [arr[j], arr[i]]
      }
    }
  }
  return arr;
}

10. 插入排序

function insertSort(arr) {
  const len = arr.length
  for (let i = 1; i < len; i++) {
    let preIndex = i - 1;
    let current = arr[i];
    while (preIndex >= 0 && arr[preIndex] > current) {
      arr[preIndex + 1] = arr[preIndex]
      preIndex--
    }
    arr[preIndex + 1] = current
  }
  return arr
}

11. 快速排序

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }

  let leftArr = [];
  let rightArr = [];
  let q = arr[0];

  for (let i = 1, l = arr.length; i < l; i++) {
    if (arr[i] > q) {
      rightArr.push(arr[i]);
    } else {
      leftArr.push(arr[i]);
    }
  }

  return [].concat(quickSort(leftArr), [q], quickSort(rightArr));
}

12. 二分法查找

对已经排好序的数组，查找某个元素在数组中的顺序。

例如数组[1,2,3,4,5,6,7]，查找5的位置

function binarySearch(arr, key) {
  let low = 0, high = arr.length - 1;
  while (low <= high) {
    let mid = parseInt((high + low) / 2);

    if (key == arr[mid]) {
      return mid;
    } else if (key > arr[mid]) {
      low = mid + 1;
    } else if (key < arr[mid]) {
      high = mid - 1;
    }
  }
  return -1;
};