几道算法题

2023-04-13 23:06 算法 53 0

1. 队列相关

一、实现一个队列函数，保持最多两个任务同时进行，多余的任务进行排队，待某一个任务完成后再按照顺序执行下一个任务

例如：

addTrack(1000, 1)
addTrack(200, 2)
addTrack(500, 3)
addTrack(900, 4)
// 输出如下结果
// 200ms  后输出 2
// 700ms  后输出 3
// 1000ms 后输出 1
// 1600ms 后输出 4

1
2
3
4
5
6
7
8
9

实现：

let doing = 0 // 正在请求的数量
const wating = [] // 等待请求的数组
let time = Date.now()

function call(element) {
  setTimeout(() => {
    console.log(element.value, Date.now() - time)
    // 正在请求-1
    doing--
    // 如果还有数组长度，取先进来的执行
    if (wating.length > 0) {
      doing++
      call(wating[0])
      // 记得从等待的数组删除
      wating.shift()
    }
  }, element.time);
}
function addTrack(time, value) {
  const element = {
    time,
    value
  }
  // 小于2直接执行
  if (doing < 2) {
    doing++
    call(element)
  } else {
    wating.push(element)
  }
}
addTrack(1000, 1)
addTrack(200, 2)
addTrack(500, 3)
addTrack(900, 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

运行结果

2. 排序相关

一、输入一个数字数组，输出其全部递增元素数组

例如：

increment([1, 5, 4, 7, 8, 4])
increment([5, 4, 3, 7, 8])
increment([5, 4, 3, 2, 1])
// 输出如下结果
// [[1,5], [4,7,8]]
// [[3,7,8]]
// []

1
2
3
4
5
6
7

实现：

function increment(arrIn) {
    let incrementTemp = [] // 缓存比较结果
    const arrOut = [] // 返回结果
    arrIn.forEach((el, index) => {
        // 第一项直接push，不需要比较
        if (index === 0) {
            incrementTemp.push(el)
            return
        }
        const len = incrementTemp.length
        const lastEl = incrementTemp[len - 1]
        // 判断是否比前一个大
        if (el > lastEl) {
            incrementTemp.push(el)
        } else {
            // 判断是否多于两个，是则为递增数列
            if (len > 1) {
                // 不能直接arrOut.push(incrementTemp)，incrementTemp会被后续清空
                arrOut.push([...incrementTemp])
            }
            // 将值的作为下一次比较
            incrementTemp = [el]
        }
    });
    // 循环完毕还需要将incrementTemp放入
    if (incrementTemp.length > 1) {
        arrOut.push([...incrementTemp])
    }
    console.log(JSON.stringify(arrOut));
    return arrOut
}

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

运行结果

二、蛇形矩阵是由1开始的自然数依次排列成的一个矩阵上三角形。

例如

当输入5时，应该输出的三角形为：
1 3 6 10 15
2 5 9 14
4 8 13
7 12
11
当输入4时，应该输出的三角形为：
1 3 6 10
2 5 9
4 8
7

实现

// 观察数字填入规律可知
// 行为递减，列为递增
// 比如输入4，则为
// [0,0] [1,0] [0,1] [2,0] [1,1] [0,2] [3,0] [2,1] [1,2] [0,3]
function func(value) {
  const arr = [] // 矩阵存放
  let n = 1 // 递增值
  for (let i = 0; i < value; i++) {
    for (let j = 0; j <= i; j++) {
      const left = i - j
      const right = j
      if (arr[left]) {
        arr[left][right] = n++
      } else {
        arr[left] = [n++]
      }
    }
  }
  arr.forEach(v => {
    console.log(v.join(' '))
  })
}

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

运行结果

暂无评论，我会出手

说点什么

最多上传8张图片，仅支持jpg，png格式图片，单张大小5MB以内！

用户名：

passerma博客

几道算法题

1. 队列相关

2. 排序相关