| 运算符 |
描述 |
例子 |
类似于 |
结果 |
十进制 |
| & |
AND |
5 & 1 |
0101 & 0001 |
0001 |
1 |
| | |
OR |
5 | 1 |
0101 | 0001 |
0101 |
5 |
| ~ |
取反 |
~ 5 |
~ 0101 |
|
-6 |
| ^ |
异或 |
5 ^ 1 |
0101 ^ 0001 |
0100 |
4 |
| << |
左移 |
5 << 1 |
101 << 1 |
1010 |
10 |
| >> |
右移 |
5 >> 1 |
101 >> 1 |
10 |
2 |
| >>> |
无符号右移 |
2 >>> 1 |
0010 >>> 0001 |
0001 |
1 |
二进制
| 二进制 |
十进制 |
计算 |
| 1000 |
8 |
2^3 = 8 |
| 1010 |
10 |
2^3 + 2^1 = 10 |
| 1111 |
15 |
2^3 + 2^2 + 2^1 + 2^0 = 15 |
| 10000 |
16 |
2^4 = 16 |
按位与 &
每一位都为 1，结果才为 1
按位或 |
其中一位为 1，结果就是 1
按位异或 ^
每一位都不同，结果才为 1不进位的加法
1
2
3
4
5
6
7
8
9
| 8 ^ 8 === 0
8 ^ 7 === 15
8 ^ 6 === 14
let a = 102, b = 324
a = a ^ b
b = a ^ b
a = a ^ b
console.log(a, b)
|
左移 <<
公式a * (2 ^ b)
1
2
3
| 3 << 2 === 12
11 << 1 === 22
|
右移 >>
大概公式a / (2 ^ b)
1
2
3
4
5
6
| 10 >> 1 === 5
10 >> 2 === 2
10 >> 3 === 1
11 >> 1 === 5
|
递归
递归 --> 栈 --> 栈溢出stackoverflow
尾递归
在严格模式下, ES6 才实现了尾递归优化
1
2
3
4
5
6
7
8
9
|
function fn() {
console.log('👍')
fn1()
}
function fn() {
console.log('👎')
return fn1() + 1
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
function fn(n) {
if (n === 1) {
return 1
}
return n * fn(n - 1)
}
function fn(n, total = 1) {
if (n === 1) {
return total
}
return fn(n - 1, n * total)
}
|
二分查找
分治法的一种特例减治法
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
| function binarySearch(arr, target) {
function binarySearchEx(start, end) {
if (start > end) return -1
let midIndex = Math.floor((start + end) / 2)
let midValue = arr[midIndex]
if (target < midValue) {
return binarySearchEx(start, midIndex - 1)
} else if (target > midValue) {
return binarySearchEx(midIndex + 1, end)
} else {
return midIndex
}
}
return binarySearchEx(0, arr.length - 1)
}
function binarySearch(arr, target) {
const length = arr.length
let start = 0
let end = length - 1
while (start > end) {
const midIndex = Math.floor((start + end) / 2)
const midValue = arr[midIndex]
if (target < midValue) {
end = midIndex - 1
} else if (target > midValue) {
start = midIndex + 1
} else {
return midIndex
}
}
return -1
}
binarySearch([1, 2, 3, 4, 5, 6, 7, 8, 9], 7)
|
双指针
寻找和为 n 的两个数
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
69
70
71
72
| function findTowNumbers(arr, n) {
const res = []
const length = arr.length
for (let i = 0; i < length - 1; i++) {
const n1 = arr[i]
let flag = false
for (let j = i + 1; j < length; j++) {
const n2 = arr[j]
if (n1 + n2 === n) {
res.push(n1)
res.push(n2)
flag = true
break
}
}
if (flag) break
}
return res
}
function findTowNumbers(arr, n) {
const res = []
const length = arr.length
let i = 0
let j = length - 1
while (i < j) {
const n1 = arr[i]
const n2 = arr[j]
const sum = n1 + n2
if (sum > n) {
j--
} else if (sum < n) {
i++
} else {
res.push(n1)
res.push(n2)
break
}
}
return res
}
function findTowNumbers(arr, n) {
const res = []
const length = arr.length
const map = {}
for (let i = 0; i < length; i++) {
map[arr[i]] = i
}
for (let i = 0; i < length; i++) {
if (map[n - arr[i]]) {
res.push(arr[i], n - arr[i])
break
}
}
return res
}
findTowNumbers([1, 2, 4, 7, 11, 15], 15)
|
移动 0 到数组末尾
将数组中所有的 0 都移动到末尾，例如输入 [1, 0, 3, 0, 11, 0] 输出 [1, 3, 11, 0, 0, 0]
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
| function moveZero(arr) {
const length = arr.length
let i
let j = -1
for (i = 0; i < length; i++) {
if (arr[i] === 0 && j < 0) {
j = i
}
if (arr[i] !== 0 && j >= 0) {
[arr[i], arr[j]] = [arr[j], arr[i]]
j++
}
}
}
function moveZero(arr) {
const length = arr.length
let zeroCount = 0
for (let i = 0; i < length - zeroCount; i++) {
if (arr[i] === 0) {
arr.push(0)
arr.splice(i, 1)
i--
zeroCount++
}
}
}
|
连续最多的字符
给一个字符串，找出连续最多的字符，以及次数
例如字符串 aabbcccddeeee11223 连续最多的是 e 4 次
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
69
70
| function findContinuousChar(str) {
const res = {
char: '',
length: 0
}
const length = str.length
let tempLength = 0
for (let i = 0; i < length; i++) {
tempLength = 0
for (let j = i; j < length; j++) {
if (str[i] === str[j]) {
tempLength++
}
if (str[i] !== str[j] || j === length - 1) {
if (tempLength > res.length) {
res.char = str[i]
res.length = tempLength
}
if (i !== length - 1) {
i = j - 1
}
break
}
}
}
return res
}
function findContinuousChar(str) {
const res = {
char: '',
length: 0
}
const length = str.length
let tempLength = 0
let i = 0
let j = 0
for (; i < length; i++) {
if (str[i] === str[j]) {
tempLength++
}
if (str[i] !== str[j] || i === length - 1) {
if (tempLength > res.length) {
res.char = str[j]
res.length = tempLength
}
tempLength = 0
if (i !== length - 1) {
j = i
i--
}
}
}
return res
}
|
动态规划
青蛙跳台阶
一只青蛙，一次可以跳 1 个台阶，也可以跳 2 个台阶，问青蛙跳上 n 级台阶，总共有多少种方式，也称：爬楼梯问题
f(1) = 1 跳 1 级台阶，只有一种方式f(2) = 2 跳 2 级台阶，有两种方式f(n) = f(n - 1) + f(n - 2) 跳 n 级，可拆分为两个问题
- 第一次跳，要么 1 级，要么 2 级，只有这两种
- 第一次跳 1 级，剩下有
f(n - 1) 种方式
- 第一次跳 2 级，剩下有
f(n - 2) 种方式
1
2
3
4
5
6
7
8
9
| function climbStairs(n) {
const f = []
f[1] = 1
f[2] = 2
for (let i = 3; i <= n; i++) {
f[i] = f[i-2] + f[i-1]
}
return f[n]
}
|
斐波那契数列
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
| function fibonacci(n) {
let arr = [0, 1]
let i = 2
while (i <= n) {
arr[i] = arr[i - 1] + arr[i - 2]
i++
}
return arr[n]
}
function fibonacci(n) {
let n2 = 0, n1 = 1, res = 1
for (let i = 1; i < n; i++) {
res = n2 + n1
n2 = n1
n1 = res
}
return res
}
function fibonacci(n) {
if (n <= 2) return 1
return fibonacci(n - 1) + fibonacci(n - 2)
}
|
最少硬币找零
给出需要找零的钱数，你可以用指定面额的硬币来完成找零，问达成找零所需要的最少硬币个数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| function coinChange(coins, amount) {
const f = []
f[0] = 0
for (let i = 1; i <= amount; i++) {
f[i] = Infinity
for (let j = 0; j < coins.length; j++) {
if (i - coins[j] >= 0) {
f[i] = Math.min(f[i], f[i - coins[j]] + 1)
}
}
}
return f[amount] === Infinity ? : -1 : f[amount]
}
|
微信
