循环队列

leetCode

解法

(1) 使用双指针 head 和 tail 标记开头循环队列的头和尾

/**
 * Initialize your data structure here. Set the size of the queue to be k.
 * @param {number} k
 */
var MyCircularQueue = function (k) {
  this.k = k;
  this.tail = -1;
  this.head = -1;
  this.queue = new Array(k);
};

/**
* Insert an element into the circular queue. Return true if the operation is successful. 
* @param {number} value
* @return {boolean}
*/
MyCircularQueue.prototype.enQueue = function (value) {
  if (this.isFull()) {
    return false;
  } else {
    this.tail = ++this.tail % this.k;
    this.queue[this.tail] = value;
    if (this.head === -1) this.head++;
    return true;
  }
};

/**
* Delete an element from the circular queue. Return true if the operation is successful.
* @return {boolean}
*/
MyCircularQueue.prototype.deQueue = function () {
  if (this.tail === -1) {
    return false;
  } else {
    this.queue[this.head] = null;
    this.head = ++this.head % this.k;
    if (this.head >= this.tail) {
      this.head = -1;
      this.tail = -1;
    }
    return true;
  }
};

/**
* Get the front item from the queue.
* @return {number}
*/
MyCircularQueue.prototype.Front = function () {
  return this.queue[this.head] !== undefined ? this.queue[this.head] : -1;
};

/**
* Get the last item from the queue.
* @return {number}
*/
MyCircularQueue.prototype.Rear = function () {
  return this.queue[this.tail] !== undefined ? this.queue[this.tail] : -1;
};

/**
* Checks whether the circular queue is empty or not.
* @return {boolean}
*/
MyCircularQueue.prototype.isEmpty = function () {
  if (this.tail === 0 && this.head === 0) {
    return true;
  } else {
    return false;
  }
};

/**
* Checks whether the circular queue is full or not.
* @return {boolean}
*/
MyCircularQueue.prototype.isFull = function () {
  if ((this.tail + 1) % this.k === this.head) {
    return true;
  } else {
    return false;
  }
};

(2) 合理使用数组的 push() 和 shift() 方法，虽然有些投机取巧，但是很简便。

/**
 * Initialize your data structure here. Set the size of the queue to be k.
 * @param {number} k
 */
var MyCircularQueue = function (k) {
  this.maxLen = k;
  this.arr = [];
}

/**
 * Insert an element into the circular queue. Return true if the operation is successful. 
 * @param {number} value
 * @return {boolean}
 */
MyCircularQueue.prototype.enQueue = function (value) {
  if (this.isFull()) return false;
  return this.arr.push(value), true;
}

/**
 * Delete an element from the circular queue. Return true if the operation is successful.
 * @return {boolean}
 */
MyCircularQueue.prototype.deQueue = function () {
  if (this.isEmpty()) return false;
  return this.arr.shift(), true;
}

/**
 * Get the front item from the queue.
 * @return {number}
 */
MyCircularQueue.prototype.Front = function () {
  if (this.isEmpty()) return -1;
  return this.arr[0];
}

/**
 * Get the last item from the queue.
 * @return {number}
 */
MyCircularQueue.prototype.Rear = function () {
  if (this.isEmpty()) return -1;
  return this.arr[this.arr.length - 1];
}

/**
 * Checks whether the circular queue is empty or not.
 * @return {boolean}
 */
MyCircularQueue.prototype.isEmpty = function () {
  return this.arr.length === 0;
}

/**
 * Checks whether the circular queue is full or not.
 * @return {boolean}
 */
MyCircularQueue.prototype.isFull = function () {
  return this.arr.length === this.maxLen;
};

总结

需要清楚 arr[this.head++] 和 arr[++this.head] 的运算符优先级；
对于代码关键判断相关逻辑，检查队列是空还是满需要考虑的测试边界情况要更多一些，例：这个数组的元素有0个、1个或者2个的情况，检查队列是满还是空是否还可靠？关键的判断逻辑应该保证其健壮，写这一部分的代码，需要多花一些时间。

广度优先搜索算法

leetCode

题目编号：200
岛屿数量

解法

const numIslands = (grid) => {
  let count = 0
  let queue = []
  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[0].length; j++) {
      if (grid[i][j] === '1') {
        count++
        grid[i][j] = '0' // 做标记，避免重复遍历
        queue.push([i, j])
        infect(queue, grid)
      }
    }
  }
  return count
}

function infect(queue, grid) {
  const dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]]
  while (queue.length) {
    const cur = queue.shift()
    for (const dir of dirs) {
      const x = cur[0] + dir[0]
      const y = cur[1] + dir[1]
      if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] !== '1') {
        continue
      }
      grid[x][y] = '0'
      queue.push([x, y])
    }
  }
}

总结

数组上的每个'1'只能属于一块岛屿，所以说被搜索到了之后可以尽管将其变为'0';
每次执行完一次infect() ，相当于找到了一块岛屿；
BFS通常搭配队列数据结构来进行实现。