算法

用递归算法实现,数组长度为5且元素的随机数在2-32之间不重复的值

1
let arr = giveRandomNumber([], 5, 32, 2)
2
console.log('arr:', arr)
3
4
function giveRandomNumber(arr, length, max, min) {
5
const random = Math.floor(Math.random() * (max - min) + 1) + min
6
!arr.includes(random) && arr.push(random)
7
return arr.length === length ? arr : giveRandomNumber(arr, length, max, min)
8
}
Copied!

写一个方法去掉空格

方法一 Regex:
1
string.replace(/\s/g, '')
Copied!
方法二 Split:
1
const a = (str) => str.split(' ').join('')
Copied!

二分查找

很简单,就是控制好左侧和右侧的指针,然后使用中间的跟 target 对比。如果一致 就是当前中间值,如果小 则说把左侧指针移动到中间指针后一个,继续前面的操作

递归

1
let data = [12, 24, 32, 43, 52, 61, 74]
2
function splitFind(arr, target) {
3
const time = arr.length / 2
4
const first = arr[time]
5
6
for (let i = 0; i < arr.length; i++) {
7
8
}
9
}
10
11
console.log('result:', splitFind(data, 61))
Copied!

循环

1
var search = function(nums, target) {
2
let left = 0
3
let right = nums.length - 1
4
5
while (left <= right) {
6
let half = left + Math.floor((right - left) / 2)
7
let cur = nums[half]
8
9
if (cur === target) return half
10
if (cur > target) {
11
right = half - 1;
12
} else if (cur < target) {
13
left = half + 1
14
}
15
}
16
17
return -1
18
}
Copied!

找出数组中连续重复的元素的起始索引

1
var arr = [1,2,3,9,9,9,9,6,7,8,10,10,10,15]
2
var dic = {}
3
for (k in arr){
4
if (!dic[arr[k]]){dic[arr[k]] = [k]}
5
else{dic[arr[k]][1] = k}
6
}
7
for (k in dic){if (dic[k].length==1){delete(dic[k])}}
8
9
console.log(dic)
10
// { '9': [ '3', '6' ], '10': [ '10', '12' ] }
Copied!

斐波那契数列

简单实现(极其容易内存溢出)
1
function Fibonacci(n) {
2
if (n <= 1) { return n }
3
return Fibonacci(n-2) + Fibonacci(n-1)
4
}
Copied!
尾递归实现(简单,安全)
1
function Fibonacci(n, ac1 = 1, ac2 = 1) {
2
if (n <= 1) { return ac2 }
3
return Fibonacci(n - 1, ac2, ac1 + ac2)
4
}
Copied!
循环实现
1
function Fibonacci(n) {
2
let ac1 = 1, ac2 = 1
3
4
for (let i = 2; i < n; i++) {
5
[ac1, ac2] = [ac2, ac1 + ac2]
6
}
7
8
return ac2
9
}
Copied!
yield 实现
1
function* FibonacciGenerator() {
2
let ac1 = 1, ac2 = 1
3
while(true) {
4
[ac1, ac2] = [ac2, ac1 + ac2]
5
yield ac2
6
}
7
}
8
9
function Fibonacci(n) {
10
if (n === 1 || n === 2) return 1
11
12
let res = 0
13
const generator = FibonacciGenerator()
14
15
for (let i = 2; i < n; i ++) {
16
res = generator.next()
17
}
18
return res.value
19
}
Copied!
1
if (curX < n || curY < m) {
2
if (flag) {
3
if (curY === 0) {
4
flag = false
5
curX += 1
6
} else {
7
curX += 1
8
curY -= 1
9
}
10
} else {
11
if (curX === 0) {
12
flag = true
13
curY += 1
14
} else {
15
curX -= 1
16
curY += 1
17
}
18
}
19
} else {
20
if (flag) {
21
if ()
22
}
23
}
Copied!

动态规划

动态规划可以看作是与递归相反的技术
递归:从顶部开始将问题分解,通过解决掉所有分解出的小问题的方式,来解决整个问题 动态规划:从底部开始解决问题,将所有的小问题解决掉,然后合并成一个解决方案,从而解决掉大问题
动态规划解决找零问题:
1
const coinChange = (coins, amount) => {
2
// 初始化备忘录,用Infinity填满备忘录,Infinity说明该值不可以用硬币凑出来
3
const dp = new Array(amount + 1).fill(Infinity)
4
5
// 设置初始条件为 0
6
dp[0] = 0
7
8
for (var i = 1; i <= amount; i++) {
9
for (const coin of coins) {
10
// 根据动态转移方程求出最小值
11
if (coin <= i) {
12
dp[i] = Math.min(dp[i], dp[i - coin] + 1)
13
}
14
}
15
}
16
17
// 如果 `dp[amount] === Infinity`说明没有最优解返回-1,否则返回最优解
18
return dp[amount] === Infinity ? -1 : dp[amount]
19
}
Copied!
输入: coins = [1, 2, 5], amount = 11 输出: 3 解释: 11 = 5 + 5 + 1
Last modified 1yr ago