冲刺之路(常见算法)

位运算

十进制转二进制,二进制转十进制的计算方式

  • 十进制 33 可以看成是 32 + 1 ,并且 33 应该是六位二进制的(因为 33 近似 32,而 32 是 2 的五次方,所以是六位),那么 十进制 33 就是 100001 ,只要是 2 的次方,那么就是 1否则都为 0
  • 那么二进制 100001 同理,首位是 2^5 ,末位是 2^0 ,相加得出 33

左移 <<

1
10 << 1 // -> 20

左移就是将二进制全部往左移动,10 在二进制中表示为 1010 ,左移一位后变成 10100 ,转换为十进制也就是 20,所以基本可以把左移看成以下公式 a * (2 ^ b)

算数右移 >>

1
10 >> 1 // -> 5

算数右移就是将二进制全部往右移动并去除多余的右边,10 在二进制中表示为 1010 ,右移一位后变成 101 ,转换为十进制也就是 5,所以基本可以把右移看成以下公式 int v = a / (2 ^ b)

右移很好用,比如可以用在二分算法中取中间值

13 >> 1 // -> 6

按位操作

按位与

每一位都为 1,结果才为 1

1
2
8 & 7 // -> 0
// 1000 & 0111 -> 0000 -> 0

按位或

其中一位为 1,结果就是 1

1
2
8 | 7 // -> 15
// 1000 | 0111 -> 1111 -> 15

按位异或

每一位都不同,结果才为 1

1
2
3
4
8 ^ 7 // -> 15
8 ^ 8 // -> 0
// 1000 ^ 0111 -> 1111 -> 15
// 1000 ^ 1000 -> 0000 -> 0

从以上代码中可以发现按位异或就是不进位加法

面试题:两个数不使用四则运算得出和

这道题中可以按位异或,因为按位异或就是不进位加法,8 ^ 8 = 0 如果进位了,就是 16 了,所以我们只需要将两个数进行异或操作,然后进位。那么也就是说两个二进制都是 1 的位置,左边应该有一个进位 1,所以可以得出以下公式 a + b = (a ^ b) + ((a & b) << 1) ,然后通过迭代的方式模拟加法

1
2
3
4
5
6
7
function sum(a, b) {
if (a == 0) return b
if (b == 0) return a
let newA = a ^ b
let newB = (a & b) << 1
return sum(newA, newB)
}

排序

以下两个函数是排序中会用到的通用函数,就不一一写了

1
2
3
4
5
6
7
8
function checkArray(array) {
return Array.isArray(array)
}
function swap(array, left, right) {
let rightValue = array[right]
array[right] = array[left]
array[left] = rightValue
}

冒泡排序

冒泡排序的原理如下,从第一个元素开始,把当前元素和下一个索引元素进行比较。如果当前元素大,那么就交换位置,重复操作直到比较到最后一个元素,那么此时最后一个元素就是该数组中最大的数。下一轮重复以上操作,但是此时最后一个元素已经是最大数了,所以不需要再比较最后一个元素,只需要比较到 length - 2 的位置。

1
2
3
4
5
6
7
8
9
10
function bubble(array) {
checkArray(array);
for (let i = array.length - 1; i > 0; i--) {
// 从 0 到 `length - 1` 遍历
for (let j = 0; j < i; j++) {
if (array[j] > array[j + 1]) swap(array, j, j + 1)
}
}
return array;
}

该算法的操作次数是一个等差数列 n + (n - 1) + (n - 2) + 1 ,去掉常数项以后得出时间复杂度是 O(n * n)

插入排序

插入排序的原理如下。第一个元素默认是已排序元素,取出下一个元素和当前元素比较,如果当前元素大就交换位置。那么此时第一个元素就是当前的最小数,所以下次取出操作从第三个元素开始,向前对比,重复之前的操作。

1
2
3
4
5
6
7
8
function insertion(array) {
if (!checkArray(array)) return
for (let i = 1; i < array.length; i++) {
for (let j = i - 1; j >= 0 && array[j] > array[j + 1]; j--)
swap(array, j, j + 1);
}
return array;
}

该算法的操作次数是一个等差数列 n + (n - 1) + (n - 2) + 1 ,去掉常数项以后得出时间复杂度是 O(n * n)

选择排序

选择排序的原理如下。遍历数组,设置最小值的索引为 0,如果取出的值比当前最小值小,就替换最小值索引,遍历完成后,将第一个元素和最小值索引上的值交换。如上操作后,第一个元素就是数组中的最小值,下次遍历就可以从索引 1 开始重复上述操作。

1
2
3
4
5
6
7
8
9
10
11
function selection(array) {
if (!checkArray(array)) return
for (let i = 0; i < array.length - 1; i++) {
let minIndex = i;
for (let j = i + 1; j < array.length; j++) {
minIndex = array[j] < array[minIndex] ? j : minIndex;
}
swap(array, i, minIndex);
}
return array;
}

该算法的操作次数是一个等差数列 n + (n - 1) + (n - 2) + 1 ,去掉常数项以后得出时间复杂度是 O(n * n)

归并排序

归并排序的原理如下。递归的将数组两两分开直到最多包含两个元素,然后将数组排序合并,最终合并为排序好的数组。假设我有一组数组 [3, 1, 2, 8, 9, 7, 6],中间数索引是 3,先排序数组 [3, 1, 2, 8] 。在这个左边数组上,继续拆分直到变成数组包含两个元素(如果数组长度是奇数的话,会有一个拆分数组只包含一个元素)。然后排序数组 [3, 1] 和 [2, 8] ,然后再排序数组 [1, 3, 2, 8] ,这样左边数组就排序完成,然后按照以上思路排序右边数组,最后将数组 [1, 2, 3, 8] 和 [6, 7, 9] 排序。

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

//归并排序
function mergeSort(arr){
var len = arr.length;
if(len < 2){
return arr;
}
//首先将无序数组划分为两个数组
var mid = Math.floor(len / 2);
var left = arr.slice(0,mid);
var right = arr.slice(mid,len);
return merge(mergeSort(left),mergeSort(right));//递归分别对左右两部分数组进行排序合并
}
//合并
function merge(left,right){
var result = [];
while(left.length>0 && right.length>0){
if(left[0]<=right[0]){
//如果左边的数据小于右边的数据,将左边数据取出,放在新数组中
result.push(left.shift());
}else{
result.push(right.shift());
}
}
while(left.length){
result.push(left.shift());
}
while(right.length){
result.push(right.shift());
}
return result;
}
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
function sort(array) {
if (!checkArray(array)) return
mergeSort(array, 0, array.length - 1);
return array;
}

function mergeSort(array, left, right) {
// 左右索引相同说明已经只有一个数
if (left === right) return;
// 等同于 `left + (right - left) / 2`
// 相比 `(left + right) / 2` 来说更加安全,不会溢出
// 使用位运算是因为位运算比四则运算快
let mid = parseInt(left + ((right - left) >> 1));
mergeSort(array, left, mid);
mergeSort(array, mid + 1, right);

let help = [];
let i = 0;
let p1 = left;
let p2 = mid + 1;
while (p1 <= mid && p2 <= right) {
help[i++] = array[p1] < array[p2] ? array[p1++] : array[p2++];
}
while (p1 <= mid) {
help[i++] = array[p1++];
}
while (p2 <= right) {
help[i++] = array[p2++];
}
for (let i = 0; i < help.length; i++) {
array[left + i] = help[i];
}
return array;
}

以上算法使用了递归的思想。递归的本质就是压栈,每递归执行一次函数,就将该函数的信息(比如参数,内部的变量,执行到的行数)压栈,直到遇到终止条件,然后出栈并继续执行函数。对于以上递归函数的调用轨迹如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
mergeSort(data, 0, 6) // mid = 3
mergeSort(data, 0, 3) // mid = 1
mergeSort(data, 0, 1) // mid = 0
mergeSort(data, 0, 0) // 遇到终止,回退到上一步
mergeSort(data, 1, 1) // 遇到终止,回退到上一步
// 排序 p1 = 0, p2 = mid + 1 = 1
// 回退到 `mergeSort(data, 0, 3)` 执行下一个递归
mergeSort(2, 3) // mid = 2
mergeSort(3, 3) // 遇到终止,回退到上一步
// 排序 p1 = 2, p2 = mid + 1 = 3
// 回退到 `mergeSort(data, 0, 3)` 执行合并逻辑
// 排序 p1 = 0, p2 = mid + 1 = 2
// 执行完毕回退
// 左边数组排序完毕,右边也是如上轨迹

该算法的操作次数是可以这样计算:递归了两次,每次数据量是数组的一半,并且最后把整个数组迭代了一次,所以得出表达式 2T(N / 2) + T(N) (T 代表时间,N 代表数据量)。时间复杂度为 O(N * logN)

快排

快排的原理如下。随机选取一个数组中的值作为基准值,从左至右取值与基准值对比大小。比基准值小的放数组左边,大的放右边,对比完成后将基准值和第一个比基准值大的值交换位置。然后将数组以基准值的位置分为两部分,继续递归以上操作。

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
// 快速排序入口
function quickSort(arr, left = 0, right = arr.length - 1) {
// 定义递归边界,若子数组只有一个元素,则没有排序必要
if(arr.length > 1) {
// 计算当前数组的基准值
const nextPivot = partition(arr, left, right)
// 如果左边子数组的长度不小于1,则递归快排这个子数组
if(left < nextPivot-1) {
quickSort(arr, left, nextPivot-1)
}
// 如果右边子数组的长度不小于1,则递归快排这个子数组
if(nextPivot<right) {
quickSort(arr, nextPivot, right)
}
}
return arr
}
// 寻找基准值的过程
function partition(arr, left, right) {
// 基准值默认取中间位置的元素
let pivotValue = arr[Math.floor(left + (right-left)/2)]
// 初始化左右指针
let i = left
let j = right
// 当左右指针不越界时,循环执行以下逻辑
while(i<=j) {
// 左指针所指元素若不大于基准值,则右移左指针
while(arr[i] < pivotValue) {
i++
}
// 右指针所指元素若不小于基准值,则左移右指针
while(arr[j]>pivotValue) {
j--
}

// 若i<=j,则意味着基准值左边存在较大元素或右边存在较小元素,交换两个元素确保左右两侧有序
if(i<=j) {
swap(arr, i, j)
i++
j--
}

}
// 返回左指针索引作为下一个基准值的索引
return i
}

// 快速排序中使用 swap 的地方比较多,我们提取成一个独立的函数
function swap(arr, i, j) {
[arr[i], arr[j]] = [arr[j], arr[i]]
}

编码复盘——快速排序的时间复杂度分析

快速排序的时间复杂度的好坏,是由基准值来决定的。

  • 最好时间复杂度:它对应的是这种情况——我们每次选择基准值,都刚好是当前子数组的中间数。这时,可以确保每一次分割都能将数组分为两半,进而只需要递归 log(n) 次。这时,快速排序的时间复杂度分析思路和归并排序相似,最后结果也是 O(nlog(n))。
  • 最坏时间复杂度:每次划分取到的都是当前数组中的最大值/最小值。大家可以尝试把这种情况代入快排的思路中,你会发现此时快排已经退化为了冒泡排序,对应的时间复杂度是 O(n^2)。
  • 平均时间复杂度: O(nlog(n))

面试题题目需要找出数组中第 K 大的元素,这问题也可以使用快排的思路。并且因为是找出第 K 大元素,所以在分离数组的过程中,可以找出需要的元素在哪边,然后只需要排序相应的一边数组就好。

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
var findKthLargest = function(nums, k) {
let l = 0
let r = nums.length - 1
// 得出第 K 大元素的索引位置
k = nums.length - k
while (l < r) {
// 分离数组后获得比基准树大的第一个元素索引
let index = part(nums, l, r)
// 判断该索引和 k 的大小
if (index < k) {
l = index + 1
} else if (index > k) {
r = index - 1
} else {
break
}
}
return nums[k]
};
function part(array, left, right) {
let less = left - 1;
let more = right;
while (left < more) {
if (array[left] < array[right]) {
++less;
++left;
} else if (array[left] > array[right]) {
swap(array, --more, left);
} else {
left++;
}
}
swap(array, right, more);
return more;
}

动态规划

动态规划背后的基本思想非常简单。就是将一个问题拆分为子问题,一般来说这些子问题都是非常相似的,那么我们可以通过只解决一次每个子问题来达到减少计算量的目的。

一旦得出每个子问题的解,就存储该结果以便下次使用。

斐波那契数列

斐波那契数列就是从 0 和 1 开始,后面的数都是前两个数之和

0,1,1,2,3,5,8,13,21,34,55,89….

那么显然易见,我们可以通过递归的方式来完成求解斐波那契数列

1
2
3
4
5
function fib(n) {
if (n < 2 && n >= 0) return n
return fib(n - 1) + fib(n - 2)
}
fib(10)

以上代码已经可以完美的解决问题。但是以上解法却存在很严重的性能问题,当 n 越大的时候,需要的时间是指数增长的,这时候就可以通过动态规划来解决这个问题。

动态规划的本质其实就是两点

  1. 自底向上分解子问题
  2. 通过变量存储已经计算过的解

根据上面两点,我们的斐波那契数列的动态规划思路也就出来了

  1. 斐波那契数列从 0 和 1 开始,那么这就是这个子问题的最底层
  2. 通过数组来存储每一位所对应的斐波那契数列的值
1
2
3
4
5
6
7
8
9
10
function fib(n) {
let array = new Array(n + 1).fill(null)
array[0] = 0
array[1] = 1
for (let i = 2; i <= n; i++) {
array[i] = array[i - 1] + array[i - 2]
}
return array[n]
}
fib(10)

0 - 1背包问题

看这个

最长递增子序列

0%