[队列 & 栈]

[Linjiayu6]

增加或删除

// 增加: push / unshift / splice
array.push(1)
array.unshift(1)
array.splice(增加位置, 0, 55,  66, 77)

// 删除: pop / shift / splice
array.pop()
array.shift()
array.splice(删除位置,  删除几个)

# 增加: append / insert(位置, 值)
# 删除: pop(index)

截取或拼接

// 拼接 浅拷贝 类似 python [1] + [2] 
concat()

// 截取
slice(startindex, endIndex(不包含))

var array = [1,2,3,4]
var slicedata = array.slice(1, 3) // [2, 3] 类似python array[1: 3] 
var slicedata = array.slice(3,4) // [4]

# 拼接: array1 + array2
# 截取: array[1: 4] 从位置1 到位置3 (不包含4)

排序 / 字符串 / 值判断

array.reverse()
array.sort()
array.join('&')
array.indexOf(888) // [2, 888, 1] 888是否在数组中, 返回index

# 排序: sort() reverse()
# 连接: str.join(array)  例如 '&'.join(array)

[Linjiayu6]

1 - 622. 设计循环队列

设计思路

[Linjiayu6]

2 - 有效的括号 🔥 🔥 🔥 🔥 🔥 🔥

var isValid = function(s) {
  var stack = []
  var obj = {
    '(': ')',
    '{': '}',
    '[': ']'
  }

  for (_s of s) {
    if (obj[_s]) { // 如果有匹配
      stack.push(obj[_s]) // 将待匹配值放入栈中
    } else {
      var pop_s = stack.pop() // 将内容从栈顶pop出来
      if (pop_s !== _s) return false // 不匹配说明并不相同
    }
  }
  return stack.length === 0
};

[Linjiayu6]

3 - 1047. 删除字符串中的所有相邻重复项

1 - 硬计算

var removeDuplicates = function(S) {
  if (S.length === 0 || S.length === 1) return S
  var A = S.split('')
  var i = 0
  while (i < A.length) {
    // 最后一个值了, 不能继续下去了, 直接返回
    if (i + 1 === A.length) return A.join('')
    // 相同
    if (A[i] === A[i + 1]) {
      A.splice(i, 2)
      i = i > 0 ? i - 1 : i
    } else {
      i += 1 // 继续
    }
  }

  return A.join('')
};

2 - 🔥 利用栈

/**
 * "abbaca"
 * 利用栈 stack = []
 * - stack = ['a'], 出栈 'a' 和 'b' 比较, 不同, 则 再放进去 stack = ['a', 'b']
 * - stack = ['a', 'b'], 出栈 'b' 和 'b' 比较, 相同, 则继续
 * return stack.join('')
 */
var removeDuplicates = function(S) {
  if (S.length === 0 || S.length === 1) return S
  var stack = [S[0]]
  for (let i = 1; i < S.length; i++) {
    var prev = stack.pop(), curr = S[i]
    if (prev !== curr) {
      stack.push(prev)
      stack.push(curr)
    }
  }
  return stack.join('')
};

[Linjiayu6]

4 - 剑指 Offer 50. 第一个只出现一次的字符

var firstUniqChar = function(s) {
  var map = new Map()
  for (let _s of s) {
    map.set(_s, map.has(_s) ? map.get(_s) + 1: 1)
  }

  for ([key, val] of map) {
    if (val === 1) return key
  }
  return ' '
};

/**
 * @param {string} s
 * @return {character}
 */
var firstUniqChar = function(s) {
    if (s === '') return ' '
    var map = new Map()
    for(let i = 0; i < s.length; i++) {
        if (map.has(s[i])) {
            map.set(s[i], map.get(s[i]) + 1)
        } else {
            map.set(s[i], 1)
        }
    }
    // [ 'l', 2 ]
    for ([key, value] of map) if (value === 1) return key
    return ' '
};

[Linjiayu6]

5 - 380. 常数时间插入、删除和获取随机元素

/**
 * Initialize your data structure here.
 */
var RandomizedSet = function() {
  this.set = new Set()
};

/**
 * Inserts a value to the set. Returns true if the set did not already contain the specified element. 
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.insert = function(val) {
  if (!this.set.has(val)) {
    this.set.add(val)
    return true
  }
  return false
};

/**
 * Removes a value from the set. Returns true if the set contained the specified element. 
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.remove = function(val) {
  if (this.set.has(val)) {
    this.set.delete(val)
    return true
  }
  return false
};

/**
 * Get a random element from the set.
 * @return {number}
 */
RandomizedSet.prototype.getRandom = function() {
  var index = parseInt(Math.random() * this.set.size)
  return Array.from(this.set)[index]
};

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * var obj = new RandomizedSet()
 * var param_1 = obj.insert(val)
 * var param_2 = obj.remove(val)
 * var param_3 = obj.getRandom()
 */

[Linjiayu6]

88. 合并两个有序数组

/**
 * case1
 * nums1 = [7,8,9,0,0,0], m = 3
 * nums2 = [2,5,6],       n = 3
 *
 * case2
 * [0] 0
 * [1] 1
 */
var merge = function(nums1, m, nums2, n) {
  var i = m - 1, j = n - 1, tail = m + n - 1

  while (j >= 0) { // nums2 用尽
    if (i < 0) { // 将nums2 值赋值到nums1上去
      nums1[tail--] = nums2[j--] // 本身nums1 就是空的情况, 无需理会nums1比较, 直接将nums2值附上去
      continue
    }
    if (nums1[i] < nums2[j]) { // nums2 更大, 插入到 nums1 中
      nums1[tail--] = nums2[j--]
    } else { // nums1 更大, 就插入到nums1 指针位置
      nums1[tail--] = nums1[i--] // 先赋值, 再--
      // tail -= 1
      // i -= 1
    }
  }
  return nums1
};