Web开发面试的那些题-算法篇

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

// JavaScript版本
const selectionSort = (arr) => {
  for (let i = 0; i < arr.length; i++) {
    let minPos = i;
    for (let j = 1 + i; j < arr.length; j++) {
      minPos = arr[minPos] <= arr[j] ? minPos : j;
    }
    swap(arr, i, minPos);
  }
};
const swap = (arr, a, b) => {
  let temp = arr[a];
  arr[a] = arr[b];
  arr[b] = temp;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

const insertionSort = (arr) => {
  for (let i = 1; i < arr.length; i++) {
    let j = i - 1;
    if (arr[i] >= arr[j]) {
      continue;
    }
    while (arr[i] < arr[j]) {
      j--;
      if (j < 0) break;
    }
    let temp = arr[i];
    let tempPos = i;
    while (tempPos !== j + 1) {
      arr[tempPos] = arr[tempPos - 1];
      tempPos--;
    }
    arr[j + 1] = temp;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

const bubbleSort = (arr) => {
  let flag = false; // 一趟排序下来是否存在至少一次交换
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(arr, j, j + 1);
        flag = true;
      }
    }
    if (!flag) break;
  }
};
const swap = (arr, a, b) => {
  let temp = arr[a];
  arr[a] = arr[b];
  arr[b] = temp;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

const mergeSort = (arr, tempArr, leftBegin, rightEnd) => {
  if (leftBegin >= rightEnd) {
    return;
  }
  let center = Math.floor((leftBegin + rightEnd) / 2);
  mergeSort(arr, tempArr, leftBegin, center);
  mergeSort(arr, tempArr, center + 1, rightEnd);
  combine(arr, tempArr, leftBegin, rightEnd);
};
const combine = (arr, tempArr, leftBegin, rightEnd) => {
  let center = Math.floor((leftBegin + rightEnd) / 2);
  let i = leftBegin;
  let j = center + 1;
  let pos = leftBegin;
  while (i !== center + 1 && j !== rightEnd + 1) {
    arr[i] <= arr[j]
      ? (tempArr[pos++] = arr[i++])
      : (tempArr[pos++] = arr[j++]);
  }
  // 归并右边剩下的
  while (j !== rightEnd + 1) {
    tempArr[pos++] = arr[j++];
  }
  // 归并左边剩下的
  while (i !== center + 1) {
    tempArr[pos++] = arr[i++];
  }
  // 转移到原数组
  while (leftBegin !== rightEnd + 1) {
    arr[leftBegin] = tempArr[leftBegin];
    leftBegin++;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

const quickSort = (arr, left, right) => {
  if (left >= right) {
    return; // 边界考虑1
  }
  let pivot = medianThree(arr, left, right);
  if (!pivot) return; // 边界考虑2
  let i = left;
  let j = right - 1;
  for (;;) {
    while (arr[++i] < pivot) {
      continue;
    }
    while (arr[--j] > pivot) {
      continue;
    }
    if (i < j) {
      swap(arr, i, j);
    } else {
      break;
    }
  }
  swap(arr, i, right - 1);
  quickSort(arr, left, i - 1);
  quickSort(arr, i + 1, right);
};

const medianThree = (arr, left, right) => {
  if (left + 1 === right) {
    if (arr[left] > arr[right]) {
      swap(arr, left, right);
    }
    return;
  }
  let center = Math.round((left + right) / 2);
  if (arr[left] > arr[center]) {
    swap(arr, left, center);
  }
  if (arr[left] > arr[right]) {
    swap(arr, left, right);
  }
  if (arr[center] > arr[right]) {
    swap(arr, center, right);
  }
  swap(arr, center, right - 1);
  return arr[right - 1];
};

const swap = (arr, a, b) => {
  let temp = arr[a];
  arr[a] = arr[b];
  arr[b] = temp;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

const getAllPermutations1 = (str) => {
  if (!str.length || str.length === 1) {
    return [str];
  }
  let strArr = Array.from(str);
  let resArr = [];
  strArr.forEach((v, i, arr) => {
    let temp = arr.slice();
    let header = temp.splice(i, 1);
    permutation(temp.join("")).forEach((v) => {
      resArr.push([header, ...v].join(""));
    });
  });
  return resArr;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

const getAllPermutations2 = (str) => {
  const strArr = Array.from(str);
  const resArr = [];
  let temp = strArr.sort();
  resArr.push(temp);
  temp = getNextPermutation(temp);
  while (temp) {
    resArr.push(temp);
    temp = getNextPermutation(temp);
  }
  console.log(resArr.map((item) => item.join("")));
};

// 根据前一个排列获得下一个排列
const getNextPermutation = (perm) => {
  if (perm.length === 0 || perm.length === 1) {
    return;
  }
  let len = perm.length;
  let isFind = null;
  let nextPerm = null;
  while (len > 0) {
    let tempPerm = perm.slice();
    isFind = findAndSwap(tempPerm, len - 2); // 从倒数第二个元素开始，向后找刚好比它大的元素
    if (isFind) {
      nextPerm = sort(tempPerm, len - 1); // 如果找到，交换后将该元素后面的元素升序排列
      return nextPerm;
    }
    len--; // 没找到则向前一个元素，继续找
  }
  return;
};

// 将index及其之后的元素进行升序排列
const sort = (arr, index) => {
  let sortPart = arr.splice(index, arr.length - index).sort();
  return [...arr, ...sortPart];
};

// 从当前数(index)后面找一个刚好比它大的数，并交换位置，找到返回true，找不到false
const findAndSwap = (arr, index) => {
  // 一个元素不需要找，直接false
  if (index < 0) {
    return false;
  }
  let cur = index + 1;
  let nearstIndex = null;
  while (cur !== arr.length) {
    if (arr[cur] > arr[index]) {
      // 第一次直接更新nearstIndex, 之后需要与之前的比较，更小则更新，否则不变
      nearstIndex = !nearstIndex
        ? cur
        : arr[cur] < arr[nearstIndex]
        ? cur
        : nearstIndex;
    }
    cur++;
  }
  if (nearstIndex) {
    let temp = arr[nearstIndex];
    arr[nearstIndex] = arr[index];
    arr[index] = temp;
    return true;
  }
  return false;
};

allPermutations("cbda");