• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

数据结构和算法躬行记(2)——栈、队列、散列表和位运算

开发技术 开发技术 4周前 (08-30) 24次浏览

一、栈

  栈(stack)是一种操作受限的线性表数据结构,基于后进先出(LIFO)策略的集合类型,例如函数中的临时变量符合后进先出的特性,因此用栈保存最合适。

  在入栈和出栈过程中所需的空间复杂度是 O(1),时间复杂度也是 O(1)。空间复杂度是指运行算法还需要的额外存储空间。

  注意,内存中的堆栈和数据结构中的堆栈不是一个概念,前者是真实存在的物理区,后者是抽象的数据存储结构。

  面试题30 包含min函数的栈。在压栈时,与之前的最小值比较,每次把两者较小的那个值存放到辅助栈中。

  面试题31 栈的压入和弹出序列。如果弹出的数字是栈顶,则弹出;如果弹出的数字不在栈顶,则把还没入栈的数字压入到辅助栈中,直到栈顶是弹出数字为止。

1)括号匹配

  用正确的类型和顺序匹配括号,例如“(”跟“)”匹配,“[”跟“]”匹配,“{”跟“}”匹配。例题:LeetCode的20. 有效的括号

  第一种思路是,当遇到匹配的最小括号对时,将它们从栈中删除(即出栈),如果最后栈为空,那么它是有效的括号,反之不是,代码如下所示

function isValidParentheses(s) {
  const length = s.length;
  let i = 0;
  const stack = [];
  while (i < length) {
    let stackLen = stack.length > 0 ? stack.length - 1 : stack.length;
    if (
      (stack[stackLen] == "(" && s[i] == ")") ||
      (stack[stackLen] == "{" && s[i] == "}") ||
      (stack[stackLen] == "[" && s[i] == "]")
    ) {
      stack.pop();
      i++;
      continue;
    }
    stack.push(s[i]);
    i++;
  }
  return stack.length === 0;
}

  第二种思路是巧妙的利用一张映射表,以右括号为键,左括号为值。先判断当前字符是否是左括号,若是,就入栈,否则匹配当前栈顶元素是否与当前字符匹配。

function isValidParentheses(s) {
  const stack = [],
    map = { "}": "{", "]": "[", ")": "(" };
  for (let i = 0, len = s.length; i < len; i++) {
    let c = s[i];
    if (!map[c]) {
      stack.push(c);
      continue;
    }
    if (stack.length > 0 && map[c] != stack.pop())
      return false;
  }
  return stack.length == 0;
}

2)算术表达式求值

  ( 1 + ( 2 + 3 ) * ( 4 * 5 ) ) 是一个算术表达式,如果将4乘以5,把3加上2,取它们的积然后加1,就得到了101。

  表达式由括号、运算符和操作数(数字)组成,可以用两个栈分别保存运算符和操作数来完成算术求值,处理过程如下所列。

  (1)将操作数压入操作数栈;

  (2)将运算符压入运算符栈;

  (3)忽略左括号;

  (4)在遇到右括号时,弹出一个运算符,弹出所需数量的操作数,并将运算符和操作数的运算结果压入操作数栈。

  源码如下所示。例题:LeetCode的150. 逆波兰表达式求值

function evalExpress(s) {
  const length = s.length;
  let i = 0;
  const ops = [],
    vals = [];
  while (i < length) {
    let word = s[i];
    if (word == "(") {
    } else if (word == "+" || word == "-" || word == "*" || word == "/")
      ops.push(word);
    else if (word == ")") {
      let op = ops.pop(),
        val = vals.pop();
      if (op == "+") val = vals.pop() + val;
      else if (op == "-") val = vals.pop() - val;
      else if (op == "*") val = vals.pop() * val;
      else if (op == "/") val = vals.pop() / val;
      vals.push(val);
    } else
      vals.push(parseInt(word));
    i++;
  }
  return vals.pop();
}

二、队列

  队列(queue)也是一种操作受限的线性表数据结构,基于先进先出(FIFO)策略的集合类型,队列的应用非常广泛,例如循环队列、阻塞队列、并发队列等。

  栈只需一个栈顶指针,而队列需要两个:队首指针和队尾指针。

  面试题9 用两个栈实现队列。先进后出的栈实现先进先出的队列,一系列栈的压入和弹出模拟队列。

  面试题59 窗口滑动的最大值。只把可能成为滑动窗口最大值的数存入一个两端开口的队列(deque)。延伸题:队列的最大值

1)循环队列

  循环队列是首尾相连的队列,这样可避免在出队时进行数据搬移的操作,但需要准确的判断出队空和队满,如下所示。例题:LeetCode的641. 设计循环双端队列

class CircularQueue {
  constructor(capacity) {
    this.items = [];
    this.n = capacity;    //队列大小
    this.head = 0;        //队首指针
    this.tail = 0;        //队尾指针
  }
  enqueue(item) {
    const { head, tail, n } = this;
    //队满
    if ((tail + 1) % n == head) return false;
    this.items[tail] = item;
    //队尾没有存储数据,会浪费一个数组的存储空间
    this.tail = (tail + 1) % n;
    return true;
  }
  dequeue() {
    const { head, tail, n, items } = this;
    //队空
    if (head == tail) return null;
    const result = items[head];
    this.head = (head + 1) % n;
    return result;
  }
}

三、散列表

  散列表(Hash Table)也叫哈希表,一种以空间换时间的方式,是数组的扩展,可根据键(Key)而直接访问内存储存位置的数据结构。

  它通过计算一个关于键值的函数,将所需查询的数据映射到表中一个位置来访问记录,提升查找速度。

  这个映射函数称做散列函数,存放记录的数组称做散列表。

  散列函数的特点如下:

  (1)计算得到的结果是一个非负整数。

  (2)如果 key1 = key2,那 hash(key1) == hash(key2)。

  (3)如果 key1 ≠ key2,那 hash(key1) ≠ hash(key2)。

  但即使是著名的MD5、SHA等散列算法,也不能避免散列冲突。当出现冲突时,可采用拉链法(Chaining)和线性探测法(Linear Probing)。

  所以在散列表中查找数据,最好情况是 O(1),最坏情况是 O(n)。

  LeetCode的242. 有效的字母异位词,除了排序字符之外,还可用散列表记录字符出现的次数。

  LeetCode的1. 两数之和,将数组放入一个散列表中,用总数减去遍历的值,判断差是否可在散列表中查到。复杂度升级后的例题:15. 三数之和18. 四数之和

四、位运算

  位运算就是直接对整数在内存中的二进制进行操作。由于位运算不需要转成十进制,因此处理速度非常快。位运算的总结摘录于《算法面试通关40讲》。

  XOR(异或)的特点如下:

x^0 = x
x^1s = ~x;        //1s是一种全为1的数,即1s = ~0
x^(~x) = 1s;
x^x = 0;
a^b=c => a^c=b, b^c=a        //swap
a^b^c = a^(b^c) = (a^b)^c

  常用的位运算包括:

x&1 == 1 OR == 0    //判断奇偶(x%2==1)。
x = x&(x-1)         //将最低位的 1 清零。
x & -x              //得到最低位的 1。

  更复杂的位运算包括:

x & (~0 << n)                   //将x最右边的n位清零
(x >> n) & 1                    //获取x的第n位值(0或1)
x & (1 << (n-1))                //获取x的第n位的幂值
x | (1 << n)                    //仅将第n位置为1
x & (~(1 << n))                 //仅将第n位置为0
x & ((1 << n) - 1)              //将x最高位至第n位(含)清零
x & (~((1 << (n+1)) - 1))       //将第n位至第0位(含)清零

  LeetCoded的191. 位1的个数,循环执行 x&(x-1),并且记录循环次数,判断条件是x和0是否相同。

  LeetCoded的231. 2的幂,仍然使用 x&(x-1),然后判断x是否等于0。

  LeetCoded的338. 比特位计数,使用递推公式 count[i] = count[i&(i-1)] + 1,只需一遍循环就能得出1的数量。

 


喜欢 (0)