JS►data constructor

data constructor

数据结构

逻辑结构

定义：数据之间的关系，分成两种：线性结构、非线性结构

线性：是一个有序数据元素的集合。元素之间的关系是一对一的，除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的

  • 常见：栈，队列，链表，线性表

非线性：各个数据元素不再保持在一个线性序列中，每个数据元素可能与零个或者多个其他数据元素发生联系

  • 常见：二维数组，树

物理结构

物理结构：指数据的逻辑结构在计算机中的存储形式，如何把数据元素存储到计算机的存储器中

两种：

顺序存储结构：是把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的

链式存储结构：是把数据元素存放在任意的存储单元里，存储单元可连续也可不连续。数据元素的存储关系并不能反映其逻辑关系，需要用一个指针存放数据元素的地址

队列

队列

特性

  • FIFO（先进先出）

  • 插入元素 始终被添加在队列的末尾, 删除元素 只能移除第一个元素

缺点

  • 在插入和删除时, 每个元素都要依次向前或向后移动指针, 导致队头之前的位置空出来, 浪费空间

循环队列

特性

  • 先入先出

  • 插入元素 始终被添加在队列的末尾, 删除元素 只能移除第一个元素

优点

  • 循环队列好处是我们可以利用这个队列之前用过的空间

应用

当你想要按顺序处理元素时，使用队列可能是一个很好的选择。

实现代码

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
/**循环队列 */
class MyCircularQueue {
    /**初始化队列容量 */
    constructor(capacity) {
        /**队列容量 */
        this.cap = capacity;
        /**队列头部 */
        this.head = -1;
        /**队列尾部 */
        this.tail = -1;
        /**数据 */
        this.arr = [];
    }
    /**向循环队列插入一个元素 */
    enQueue(value) {
        if(this.isFull()){
            return false;
        }
        if (this.isEmpty()) {
            this.head = 0;
        }
        // 精髓代码,头指针和尾指针都是从-1开始,不断增加取余数.添加时的位置关系.和删除时的位置关系总是顺序相关的
        this.tail = (this.tail + 1) % this.cap;
        this.arr[this.tail] = value;
        return true;
    }
    /**从循环队列中删除一个元素 */
    deQueue() {
        if(this.isEmpty()){
            return false;
        }
        if(this.head == this.tail){
            this.head = this.tail = -1;
        }else{
            // 按顺序从最开始删除
            this.head = (this.head + 1) % this.cap;
        }
        return true;
    }
    /**从队首获取元素 */
    Front() {
        if (this.isEmpty()) {
            return -1;
        }
        return this.arr[this.head];
    }
    /**从队尾获取元素 */
    Rear() {
        if (this.isEmpty()) {
            return -1;
        }
        return this.arr[this.tail];
    }
    /**队列是否为空 */
    isEmpty() {
        return this.head == -1;
    }
    /**队列是否已满 */
    isFull() {
        return this.head == (this.tail + 1) % this.cap;
    }
}

队列和广度优先搜索（BFS）

BFS 广度优先搜索, 利用队列先入先出的特性

寻找树A到G的最短路径问题

1
2
3
4
5
6
7
进队【A】
出队第一个元素A，子节点入队【B,C,D】
出队B，子节点入队【C,D,G】
出队C，子节点入队 【D,G,E,F】(同一节点去重)
出队D，子节点入队【G,E,F】
出队G，没有子节点,到达终点,此时最小步
出队其他节点

例题1

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

示例 1:

1
2
3
输入: n = 12
输出: 3 
解释: 12 = 4 + 4 + 4.

示例 2:

1
2
3
输入: n = 13
输出: 2
解释: 13 = 4 + 9.

解题思路:

给定一个N元树，其中每个节点表示数字n的余数减去一个完全平方数的组合，在树中找到一个节点，该节点满足两个条件：

(1) 节点的值（即余数）也是一个完全平方数。
(2) 在满足条件（1）的所有节点中，节点和根之间的距离应该最小。
(3) 当遇到第一个平方根数时,结束并返回步数

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
var numSquares = function(n) {
  let square = []
  // 计算n以下的所有平方数值
  for (let m = 1;;m++) {
    if (m * m <= n) {
      square.push(m * m)
    } else {
      break;
    }
  }

  // 数值本身是平方根时,直接返回
  if (square.includes(n)) return 1

  let list = []
  list.push(n)
  let step = 0

  // 每一个子节点都要去重,并入队
  let has = new Set()

  // 结束前list队列里总是有值保持循环体成立并执行
  while (list.length > 0) {
    const len = list.length
    step++
    has = new Set()
    // 每一个level级别的子节点遍历,(去重后的数据)
    for (let i = 1; i <= len; i ++) {
      const item = list.shift()
      // 小于n的所有平方数的list, 针对同level下的每一个节点的子节点,
      // 首先判断是否是平方数,是则可以结束,
      // 其次是过滤掉大于该节点的平方根数,因为子节点是当前节点减去小于自己的所有平方数的余数集合
      // 最后,不符合上面条件的数值,去重,入队,赋值给list.while循环体,进入下一层level的遍历
      for (let z = 0; z < square.length; z++) {
        if (item === square[z]) {
          list = []
          return step
        } else if (item < square[z]) {
          break
        } else {
          has.add(item - square[z])
        }
      }
    }
    list = Array.from(has)
  }
}

例题2

给你一个 m * n 的网格，其中每个单元格不是 0（空）就是 1（障碍物）。每一步，您都可以在空白单元格中上、下、左、右移动。
如果您 最多 可以消除 k 个障碍物，请找出从左上角 (0, 0) 到右下角 (m-1, n-1) 的最短路径，并返回通过该路径所需的步数。如果找不到这样的路径，则返回 -1。

示例1

1
2
3
4
5
6
7
8
9
10
输入： 
grid = 
[[0,0,0],
 [1,1,0],
 [0,0,0],
 [0,1,1],
 [0,0,0]], 
k = 1

输出：6

不消除任何障碍的最短路径是 10。消除位置 (3,2) 处的障碍后，最短路径是 6 。

该路径是 (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (3,2) -> (4,2)

示例2

1
2
3
4
5
6
7
输入
grid = 
[[0,1,1],
 [1,1,1],
 [1,0,0]], 
k = 1
输出：-1

解题思路:

  • 二维网格中的最短路问题，我们一般可以使用广度优先搜索 + 队列的方法解决

  • 最短路中经过同一位置不会超过一次，因此最多消除k个障碍物等价于最多经过 k 个障碍物

  • 假定一个三元组[x, y, rest]表示一个状态，x,y表示位置，rest表示经过rest个障碍物，值必须为非负整数

  • 对于当前的状态[x, y, rest]，可以向最多四个新状态进行搜索，let position = [[-1, 0], [1, 0], [0, -1], [0, 1]]

  • 假如向右移动一个,如果新位置为障碍物(1)，那么新的状态为[x+1, y, rest - 1]，否则新的状态为[x+1, y, rest]

  • 我们从初始状态 [0, 0, k] 开始搜索，当我们第一次到达状态[m - 1, n - 1, k’]，就得到了从左上角[0, 0]到右下角[m - 1, n - 1],且最多经过 k 个障碍物的最短路径

  • 格子布局无障碍最小路径是 m + n - 2 步,直接走两条边线即是最短

  • 最短路径上, 障碍物可以有m + n - 3个点位可能为障碍物,所以k不能超过这个值,超过该值,则最短路径为m + n - 2

  • 如示例1[1,1]其实属于四个位置的子节点([1,0],[0,1],[1,0],[2,1],[1,2]),当对这四个节点操作时,他们的子节点又都包含[1,1],所以说如果不去重复状态,这里逻辑就无法走下去,形成死循环

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
var shortestPath = function(grid, k) {
    let n = grid.length
    let m = grid[0].length
    if (m === 1 && n === 1) return 0
    // 格子布局无障碍最小路径是 m + n - 2 步,
    // 最短路径上, 障碍物可以有m + n - 3个点位可能为障碍物,所以k不能超过这个值
    if (k > m + n - 3) return (m + n - 2)
    k = Math.min(k, m + n - 3)
    let queue = [[0, 0, k]]
    // 每一个状态不能重复, k的变化也会导致状态变化,[0,0,1]和[0,0,0]位置相同,但是状态不同,第二是消除了一次障碍物的节点
    let visit = {
      ['0-0-' + k]: 1
    }
    let step = 0
    // 左右上下四个点位
    let position = [[-1, 0], [1, 0], [0, -1], [0, 1]]
    while (queue.length) {
        step++
        let len = queue.length
        // 遍历当前level入队的节点,并搜索该level节点下的所有子节点
        for (var i = 0; i < len; i++) {
            let current = queue.shift()
            let newk = current[2]
            if (current[0] === m && current[1] === n) {
                queue = []
                break
            }
            // 遍历每个节点的四个位置
            for (let key in position) {
                  let newx = current[0] + position[key][0]
                  let newy = current[1] + position[key][1]
                  // 新的节点必须是不存在状态
                if (newx >= 0 && newx < m && newy >= 0 && newy < n) {
                    if (grid[newy][newx] === 0 && !visit[[newx, newy, newk].join('-')]) {
                        if (newx === m - 1 && newy === n - 1) {
                            queue = []
                            return step
                        }
                        queue.push([newx, newy, newk])
                        visit[[newx, newy, newk].join('-')] = 1
                    } else if (grid[newy][newx] === 1 && newk > 0 && !visit[[newx, newy, newk - 1].join('-')]) {
                        queue.push([newx, newy, newk - 1])
                        visit[[newx, newy, newk - 1].join('-')] = 1
                    }
                }
            }
        }
    }
    return -1
};

栈

LIFO (后入先出)

  • 栈的末尾添加一个新元素

  • 删除，退栈 pop 将删除栈中最后一个元素

例题1

有效的括号

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效

返回
顶部