Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

发现数据结构之美-栈 #208

Open
FrankKai opened this issue Apr 10, 2020 · 3 comments
Open

发现数据结构之美-栈 #208

FrankKai opened this issue Apr 10, 2020 · 3 comments

Comments

@FrankKai
Copy link
Owner

FrankKai commented Apr 10, 2020

image

在代码的世界中,无论是什么语言,栈其实都是一种非常重要的数据结构。
全球闻名的代码提问社区stack overflow就以栈(stack)溢出作为网站名的一个部分。
在写代码或者是debug的过程中,相信你已经感受到了在函数调用栈的世界蹦蹦跳跳的快乐了。
在学校里刷oj,刷LeetCode,进入社会参加笔试面试的过程中,相信你也感受到了栈的强大和易用。

这篇博文非常适合数据结构基础非常薄弱的同学食用,也欢迎基础扎实的同学指正和交流。
如果从未感受过stack的美妙和强大,这篇博文将非常适合你~

  • 什么是栈?
    • 数据结构图
    • 入栈出栈图
  • JavaScript中的栈
    • 在js中,如何发现出栈LIFO的特性?
    • 如何实现一个最小栈?
    • 图解函数调用栈
  • leetcode 栈 解法题目
    • 20.有效的括号(easy)
    • 67.二进制求和(easy)
    • 905.按奇偶排序数组(easy)
    • 56.合并区间(medium)
    • 75.颜色分类(medium)
    • 228.汇总区间(medium)
    • 739.每日温度(medium)
  • 面试题 栈 解法题目
    • 实现一个BigInt
@FrankKai
Copy link
Owner Author

FrankKai commented Apr 10, 2020

什么是栈?

  • 栈是一种后入先出(LIFO)的数据结构
  • 栈通常使用DFS(Depth First Search)遍历
  • 通常可以通过top/bottom来代表栈的顶部和底部

数据结构图

image

入栈出栈图

image

JavaScript中的栈

在js中,如何发现出栈LIFO的特性?

下面这个结构大家都熟悉,瞬间体现出栈LIFO的特性。

// 定义一个栈
let stack = [1,2,3];
// 入栈
stack.push(4); // stack [1,2,3,4]
// 出栈
stack.pop(); // 4 stack [1,2,3]

如何实现一个最小栈?

设计一个支持 push ,pop ,top 操作,并能在常数时间内检索到最小元素的栈。

push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。
var MinStack = function() {
  this.stack = [];
};
MinStack.prototype.push = function(x) {
  this.stack.push(x);
};
MinStack.prototype.pop = function() {
  return this.stack.pop();
};
MinStack.prototype.top = function() {
  return this.stack[this.stack.length - 1];
};
MinStack.prototype.getMin = function() {
  return Math.min(...this.stack);
};

题目:https://leetcode-cn.com/problems/min-stack/
解法:https://github.com/FrankKai/leetcode-js/blob/master/155.Min_Stack.js

图解函数调用栈

image

从frames stack中调用函数。

function foo(){
    let a = 10;
    return a + b + 11
}
function bar(x){
    let y = 3;
    return foo(x*y);
}
console.log(bar(7)); // 返回42

过程拆解:

  • 调用bar时,包含bar的arguments和本地变量的第一个frame创建了
  • 当bar调用foo时,包含了foo的arguments和本地变量的第二个frame创建成功,并且将其推入顶部
  • 当foo返回时,顶部的frame element会从stack中pop出来(留下bar在栈中)
  • 当bar返回时,stack清空

可视化拆解:

image

image

image

@FrankKai
Copy link
Owner Author

FrankKai commented Apr 10, 2020

leetcode 栈 解法题目

  • 20.有效的括号(easy)
  • 67.二进制求和(easy)
  • 905.按奇偶排序数组(easy)
  • 56.合并区间(medium)
  • 75.颜色分类(medium)
  • 228.汇总区间(medium)
  • 739.每日温度(medium)

20.有效的括号(easy)

题目:https://leetcode-cn.com/problems/valid-parentheses/
题解:https://github.com/FrankKai/leetcode-js/blob/master/20.Valid_Parentheses.js

/**
   * 解法2:栈
   * 1.构建一个栈
   * 2.依次入栈所有开括号
   * 3.遇到闭括号时与栈顶的开括号匹配
   *   3.1若匹配上,出栈并继续
   *   3.2匹配不上,return false
   * 4.遍历结束后的栈应该为空,否则为无效括号
   */
var isValid = function(s) {
  var bracketsMap = {
    "(": ")",
    "{": "}",
    "[": "]"
  };
  var openBrackets = Object.keys(bracketsMap);
  var closeBrackets = Object.values(bracketsMap);
  var stack = [];
  var sArr = s.split("");
  for (var i = 0; i < sArr.length; i++) {
    if (openBrackets.indexOf(sArr[i]) !== -1) {
      stack.push(sArr[i]);
    } else if (closeBrackets.indexOf(sArr[i]) !== -1) {
      var top = stack[stack.length - 1];
      if (sArr[i] === bracketsMap[top]) {
        stack.pop();
      } else {
        return false;
      }
    }
  }
  return stack.length === 0;
}

67.二进制求和(easy)

/**
 * @param {string} a
 * @param {string} b
 * @return {string}
 */
var addBinary = function (a, b) {
    /**
     * 解法2:栈
     * 时间复杂度:O(n)
     * 性能:56ms, 35.5MB
     */
    let aArr = a.split("");
    let bArr = b.split("");
    let stack = [];
    let count = 0;
    while (aArr.length !== 0 || bArr.length !== 0) {
        let aPop = aArr.pop() || 0;
        let bPop = bArr.pop() || 0;
        let stackBottom = 0;
        if (stack.length > count) {
            stackBottom = stack.shift() || 0;
        }
        let sum = parseInt(aPop) + parseInt(bPop) + parseInt(stackBottom)
        if (sum <= 1) {
            stack.unshift(sum);
        } else {
            stack.unshift(sum - 2);
            stack.unshift(1);
        }
        count++;
    }
    return stack.join("");
};

905.按奇偶排序数组(easy)

题目:https://leetcode-cn.com/problems/sort-array-by-parity/
题解:https://github.com/FrankKai/leetcode-js/blob/master/905.Sort_Array_By_Parity.js

/**
 * @param {number[]} A
 * @return {number[]}
 */
var sortArrayByParity = function (A) {
  /**
   * 栈头栈尾解法即可
   * 偶数栈底推入unshift
   * 奇数栈顶推入push
   */
  var stack = [];
  for (var i = 0; i < A.length; i++) {
    if (A[i] % 2 === 0) {
      stack.unshift(A[i]);
    } else {
      stack.push(A[i]);
    }
  }
  return stack;
};

56.合并区间(medium)

题目:https://leetcode-cn.com/problems/merge-intervals/
题解:https://github.com/FrankKai/leetcode-js/blob/master/56.Merge_Intervals.js

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function (intervals) {
  /**
   * 解法1:排序 + 栈
   * 性能:88ms 36.3MB
   * 思路:
   * 推入区间 空栈 或者 arr[0]大于栈最后一个区间闭
   * 覆盖重叠 arr[0]小于栈最后一个区间闭
   *  */
  intervals.sort((a, b) => a[0] - b[0]);
  let stack = [];
  for (let i = 0; i < intervals.length; i++) {
    let currrentInterval = intervals[i];
    let stackLastItem = stack[stack.length - 1];
    if (stack.length === 0 || currrentInterval[0] > stackLastItem[1]) {
      stack.push(currrentInterval);
    } else if (currrentInterval[0] <= stackLastItem[1]) {
      stackLastItem[1] = Math.max(stackLastItem[1], currrentInterval[1]);
    }
  }
  return stack;
};

75. 颜色分类(medium)

题目:https://leetcode-cn.com/problems/sort-colors/
题解:https://github.com/FrankKai/leetcode-js/blob/master/75.Sort_Colors.js

var sortColors = function (nums) {
  /**
   * 解法1:递归 栈
   * 性能:64ms 35.1MB
   */
  var length = nums.length;
  var countHead = arguments[1] || 0;
  var countTail = arguments[2] || 0;
  for (var i = countHead || 0; i < length - countTail; i++) {
    if (nums[i] === 0) {
      countHead++;
      nums.unshift(nums.splice(i, 1)); // 增加if(i!==0)会降低10ms性能
      return sortColors(nums, countHead, countTail);
    } else if (nums[i] === 2) {
      countTail++;
      nums.push(nums.splice(i, 1));
      return sortColors(nums, countHead, countTail);
    }
  }
  return nums;
}

228.汇总区间(medium)

题目:https://leetcode-cn.com/problems/summary-ranges/
题解:https://github.com/FrankKai/leetcode-js/blob/master/228.Summary_Ranges.js

/**
 * @param {number[]} nums
 * @return {string[]}
 */
var summaryRanges = function (nums) {
  /**
   * 解法1:排序 + 栈
   * 性能:52ms 33.7MB
   */
  nums.sort((a, b) => a - b);
  let stack = [];
  let result = [];
  for (let i = 0; i < nums.length; i++) {
    if (stack.length === 0 || nums[i] - stack[stack.length - 1] === 1) {
      stack.push(nums[i]);
    } else {
      stackToResult();
      stack = [];
      stack.push(nums[i]);
    }
    if (i === nums.length - 1) {
      stackToResult();
    }
  }
  function stackToResult() {
    if (stack.length > 1) {
      result.push(`${stack[0]}->${stack[stack.length - 1]}`);
    } else {
      result.push(`${stack[0]}`);
    }
  }
  return result;
};

739.每日温度(medium)

题目:https://leetcode-cn.com/problems/daily-temperatures/
题解:https://github.com/FrankKai/leetcode-js/blob/master/739.Daily_Temperatures.js

  /**
   * 解法2:栈 + 递归 1132ms 19.96% 59.2MB 11.76%
   * 思路:
   * 1.通过shift取出栈底元素
   * 2.遍历剩余温度栈内温度
   *     若温度出现比栈底温度大者
   *         存储i+1
   *         递归进行下一次入栈
   *     若温度小于等于栈底温度
   *         若遍历到最后一个都没有出现更大的
   *              存储 0
   *              进行下一次入栈
   * 3.最后一个温度无论如何都肯定是0
   */
var dailyTemperatures = function(T) {
  if (T.length < 1 || T.length > 30000) return false;
  var result = arguments[1] || [];
  var bottom = T.shift();
  for (var i = 0; i < T.length; i++) {
    var t = T[i];
    if (t > bottom) {
      result.push(i + 1);
      return dailyTemperatures(T, result);
    } else {
      if (i === T.length - 1) {
        result.push(0);
        return dailyTemperatures(T, result);
      }
    }
  }
  result.push(0);
  return result;
}

@FrankKai FrankKai changed the title 发现数据结构的美-栈 发现数据结构之美-栈 Apr 13, 2020
@FrankKai
Copy link
Owner Author

FrankKai commented May 21, 2020

面试题 栈 解法题目

实现一个BigInt

实现大整数相加,大于 Number.MAX_VALUE,不能直接使用 BigInt。

/**
* 请通过代码实现大整数(可能比Number.MAX_VALUE大)相加运算
// your code goes here
var bigint1 = new BigInt('1231230');
var bigint2 = new BigInt('12323123999999999999999999999999999999999999999999999991');
console.log(bigint1.plus(bigint2))
*/
function BigInt(value) {
  this.value = value;
}

BigInt.prototype.plus = function (bigint) {
  let aArr = this.value.split("");
  let bArr = bigint.value.split("");
  let stack = [];
  let count = 0;
  while (aArr.length !== 0 || bArr.length !== 0) {
    let aPop = aArr.pop() || 0;
    let bPop = bArr.pop() || 0;
    let stackBottom = 0;
    if (stack.length > count) {
      stackBottom = stack.shift();
    }
    let sum = parseInt(aPop) + parseInt(bPop) + parseInt(stackBottom);
    if (sum < 10) {
      stack.unshift(sum);
    } else if (sum >= 10) {
      stack.unshift(sum - 10);
      stack.unshift(1);
    }
    count++;
  }
  return stack.join("");
};

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant