数据结构专项-算法第三周(栈)

660
  1. 682. 棒球比赛
  2. 232. 用栈实现队列
  3. 844. 比较含退格的字符串
  4. 946. 验证栈序列
  5. 20. 有效的括号
  6. 1249. 移除无效的括号
  7. 1021. 删除最外层的括号
  8. 1124. 表现良好的最长时间段
  9. 227. 基本计算器 II
  10. 636. 函数的独占时间

682. 棒球比赛

你现在是一场采用特殊赛制棒球比赛的记录员。这场比赛由若干回合组成，过去几回合的得分可能会影响以后几回合的得分。

比赛开始时，记录是空白的。你会得到一个记录操作的字符串列表 ops，其中 ops[i] 是你需要记录的第 i 项操作，ops 遵循下述规则：
整数 x – 表示本回合新获得分数 x
“+” – 表示本回合新获得的得分是前两次得分的总和。题目数据保证记录此操作时前面总是存在两个有效的分数。
“D” – 表示本回合新获得的得分是前一次得分的两倍。题目数据保证记录此操作时前面总是存在一个有效的分数。
“C” – 表示前一次得分无效，将其从记录中移除。题目数据保证记录此操作时前面总是存在一个有效的分数。
请你返回记录中所有得分的总和。

提示：

1 <= ops.length <= 1000
ops[i] 为 “C”、”D”、”+”，或者一个表示整数的字符串。整数范围是 [-3 * 104, 3 * 104]
对于 “+” 操作，题目数据保证记录此操作时前面总是存在两个有效的分数
对于 “C” 和 “D” 操作，题目数据保证记录此操作时前面总是存在一个有效的分数

题意理解：
给定一个数组，根据特定规则计算得分
可数情况不考虑

  1. 数组中的数据为 符号”+”、字母”D”、字母”C”、和字符串数字组成
  2. 声明一个数字，用来保存每次操作后的结果
  3. 遍历数组，如果为”C”则删除上个元素
  4. 如果为”D” 当前数等于上个数字*2
  5. 如果为”+” 当前数等于前两个数之和
  6. 其他转为数组存储
/**
 * @param {string[]} ops
 * @return {number}
 */
var calPoints = function(ops) {
    const arr=[]
    for(let val of ops){
        if(val==="C"){
            arr.pop()
        }else if(val==="D"){
            arr.push(arr[arr.length-1]*2)
        }else if(val==="+"){
            arr.push(arr[arr.length-1]+arr[arr.length-2])
        }else{
            arr.push(Number(val))
        }
    }
    return arr.reduce((x,y)=>x+y,0)
};
复制代码

232. 用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false
说明：

你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

提示：

1 <= x <= 9
最多调用 100 次 push、pop、peek 和 empty
假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）

提议理解：
使用两个栈模拟队列（栈 先进后出，队列 先进先出）

  1. 要实现入队、出队、判断队列是否为空、返回队首元素的方法
  2. 一个栈用来存储每次入队的操作
  3. 一个栈用来存来存储出队的操作，如果出队的栈为空，则遍历入栈的栈，放进出栈的栈中，如果两个都为空则为空
var MyQueue = function() {
    this.queue=[];
    this.stack=[];
};

/** 
 * @param {number} x
 * @return {void}
 */
MyQueue.prototype.push = function(x) {
    this.stack.push(x)
};

/**
 * @return {number}
 */
MyQueue.prototype.pop = function() {
    if(!this.queue.length){
        while(this.stack.length){
            this.queue.push(this.stack.pop())
        }
    }
    return this.queue.pop()
};

/**
 * @return {number}
 */
MyQueue.prototype.peek = function() {
    if(!this.queue.length){
        while(this.stack.length){
            this.queue.push(this.stack.pop())
        }
    }
    return this.queue[this.queue.length-1]
};

/**
 * @return {boolean}
 */
MyQueue.prototype.empty = function() {
  return !this.queue.length && !this.stack.length
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * var obj = new MyQueue()
 * obj.push(x)
 * var param_2 = obj.pop()
 * var param_3 = obj.peek()
 * var param_4 = obj.empty()
 */
复制代码

844. 比较含退格的字符串

给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。

注意：如果对空文本输入退格字符，文本继续为空。

提示：
1 <= s.length, t.length <= 200
s 和 t 只含有小写字母以及字符 ‘#’

题意理解：
给定一个字符串，出现”#”代表删除前一个字符，判断两个字符串执行操作后是否相等

使用栈进行求解

  1. 声明两个栈来存储两个字符串执行后的最终结果，若果相等则返回true，否则返回false
  2. 遍历单个字符串，如果为#且站不为null则执行出栈曹邹，否则执行入栈操作
/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var backspaceCompare = function (s, t) {
    function stack(str) {
        const arr = []
        for (let i = 0; i < str.length; i++) {
            if (str[i] === "#") {
                if(!arr.length)continue;
                arr.pop()
            } else {
                arr.push(str[i])
            }
        }
        return arr;
    }
    let a = stack(s);
    let b = stack(t);
    while(a.length && b.length){
        if(a.pop()!==b.pop()){
            return false
        }
    }
    return !a.length && !b.length
};
复制代码

字符串操作

  1. 声明变量a和b用来保存s,t操作完成后的值
/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var backspaceCompare = function(s, t) {
    let a="";
    let b="";
    for(let i=0;i<s.length;i++){
        if(s[i]==="#"){
            a=a.slice(0,-1)
        }else{
            a+=s[i]
        }
    }
    for(let i=0;i<t.length;i++){
        if(t[i]==="#"){
            b=b.slice(0,-1)
        }else{
            b+=t[i]
        }
    }
    return a===b;
};
复制代码

946. 验证栈序列

给定 pushed 和 popped 两个序列，每个序列中的 值都不重复，只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回 true；否则，返回 false 。

提示：
1 <= pushed.length <= 1000
0 <= pushed[i] <= 1000
pushed 的所有元素 互不相同
popped.length == pushed.length
popped 是 pushed 的一个排列

题意理解：
判断popped是否为pushed出栈的一种结果

  1. 设置变量i表示popped中第i个数，stack模拟入栈出栈
  2. 遍历pushed，当前值入栈stack， 如果当前值和popped[i]相同，则执行出栈stack，并且i++,遍历栈stack如果栈顶和popped[i]形同，则stack出栈i++
  3. 遍历结束，如果stack为null则返回true，否则返回false
/**
 * @param {number[]} pushed
 * @param {number[]} popped
 * @return {boolean}
 */
var validateStackSequences = function (pushed, popped) {
    const stack = [];
    let i = 0;
    for (const val of pushed) {
        stack.push(val)
        if (popped[i] === val) {
            stack.pop()
            i++;
            while (stack.length && popped[i] === stack[stack.length - 1]) {
                stack.pop()
                i++;
            }
        }
    }
    return !stack.length
};
复制代码

20. 有效的括号

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

有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

提示：
1 <= s.length <= 104
s 仅由括号 ‘()[]{}’ 组成

题意理解：
判断给定的字符串中的括号是否符合闭合条件

  1. 声明一个栈stack用来匹配括号
  2. 如果为左括号，入栈
  3. 否则出栈，判断出栈的括号是否和当前括号匹配，不匹配返回false
  4. 最后如果stack为null则返回true，否则返回false
/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
    const stack = [];
    for (let i = 0; i < s.length; i++) {
        if (s[i] === "(" || s[i] === "[" || s[i] === "{") {
            stack.push(s[i])
        } else {
            const current = stack.pop()
            if (!(current === "(" && s[i] === ")") && !(current === "[" && s[i] === "]") && !(current === "{" && s[i] === "}")) {
                return false
            }
        }
    }
    return !stack.length;
};
复制代码

1249. 移除无效的括号

给你一个由 ‘(‘、’)’ 和小写字母组成的字符串 s。

你需要从字符串中删除最少数目的 ‘(‘ 或者 ‘)’ （可以删除任意位置的括号)，使得剩下的「括号字符串」有效。
请返回任意一个合法字符串。
有效「括号字符串」应当符合以下 任意一条 要求：

空字符串或只包含小写字母的字符串
可以被写作 AB（A 连接 B）的字符串，其中 A 和 B 都是有效「括号字符串」
可以被写作 (A) 的字符串，其中 A 是一个有效的「括号字符串」
提示：
1 <= s.length <= 105
s[i] 可能是 ‘(‘、’)’ 或英文小写字母

题意理解：
输出有效的字符串，及括号可以配对，不匹配的删除掉

  1. 声明两个栈stack保存不匹配的”(“的下标，deleteIndex保存不匹配的”)”的下标
  2. str保存返回值
/**
 * @param {string} s
 * @return {string}
 */
var minRemoveToMakeValid = function (s) {
    const stack = [];
    let deleteIndex = [];
    let str = "";
    for (let i = 0; i < s.length; i++) {
        if (s[i] === "(") {
            stack.push(i)
        } else if (s[i] === ")" && stack.length) {
            stack.pop();
        } else if (s[i] === ")") {
            deleteIndex.push(i)
        }
    }
    deleteIndex=[...deleteIndex,...stack]
    for (let i = 0; i < s.length; i++) {
        if(deleteIndex.includes(i)){
            continue;
        }
        str+=s[i];
    }
    return str;
};
复制代码

1021. 删除最外层的括号

有效括号字符串为空 “”、”(” + A + “)” 或 A + B ，其中 A 和 B 都是有效的括号字符串，+ 代表字符串的连接。

例如，””，”()”，”(())()” 和 “(()(()))” 都是有效的括号字符串。
如果有效字符串 s 非空，且不存在将其拆分为 s = A + B 的方法，我们称其为原语（primitive），其中 A 和 B 都是非空有效括号字符串。

给出一个非空有效字符串 s，考虑将其进行原语化分解，使得：s = P_1 + P_2 + … + P_k，其中 P_i 是有效括号字符串原语。

对 s 进行原语化分解，删除分解中每个原语字符串的最外层括号，返回 s 。
提示：
1 <= s.length <= 105
s[i] 为 ‘(‘ 或 ‘)’
s 是一个有效括号字符串

提议理解：
删除最外层的没对括号(一层)

  1. count左括号数，left起始位置
  2. 当count为0时表示一对凑齐，接着遍历下一个
/**
 * @param {string} s
 * @return {string}
 */
var removeOuterParentheses = function(s) {
    let count=0;
    let left=0;
    let str="";
    for(let i=0;i<s.length;i++){
        if(s[i]==="("){
            count++;
        }else{
            count--;
        }
        if(count===0){
            str+=s.slice(left+1,i)
            left=i+1;
        }
    }
    return str
};
复制代码

1124. 表现良好的最长时间段

给你一份工作时间表 hours，上面记录着某一位员工每天的工作小时数。

我们认为当员工一天中的工作小时数大于 8 小时的时候，那么这一天就是「劳累的一天」。
所谓「表现良好的时间段」，意味在这段时间内，「劳累的天数」是严格 大于「不劳累的天数」。
请你返回「表现良好时间段」的最大长度

提示：
1 <= hours.length <= 104
0 <= hours[i] <= 16

题意理解：
找出一个最长时间段劳累天数大于不劳累天数的总天数

  1. 声明arr用来存储当前天多余劳累的天数
  2. 放最后一个数大于0时表示整体都是劳累的，之间返回数组长度
  3. res存储当前最大劳累天数
  4. 遍历arr,找出当前劳累天数和第一个劳累天数相同的长度的差，及此时的劳累天数
  5. 返回res
/**
 * @param {number[]} hours
 * @return {number}
 */
var longestWPI = function(hours) {
    const arr=[];
    let count=0;
    for(let item of hours){
        if(item>8){
            arr.push(++count)
        }else{
            arr.push(--count)
        }
    }
    if(arr[arr.length-1]>0) return arr.length;
    let res=0;
    let arr1=new Map();
    for(let i=0;i<arr.length;i++){
        if(!arr1.has(arr[i])) arr1.set(arr[i],i);
        if(arr1.has(arr[i]-1)) {
            res=Math.max(res,i-arr1.get(arr[i]-1));
        }
        if(arr[i]>0) res=Math.max(res,i+1);
    }
    return res;
};
复制代码

227. 基本计算器 II

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

整数除法仅保留整数部分。
你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 – 1] 的范围内。
注意：不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

提示：
1 <= ops.length <= 1000
ops[i] 为 “C”、”D”、”+”，或者一个表示整数的字符串。整数范围是 [-3 * 104, 3 * 104]
对于 “+” 操作，题目数据保证记录此操作时前面总是存在两个有效的分数
对于 “C” 和 “D” 操作，题目数据保证记录此操作时前面总是存在一个有效的分数

提议理解：
字符串是一个数学表达式，遍历字符串求出值，不使用内置方法

  1. 初始化栈stack保存当前值，只存在加减乘除
  2. sym表示上个字符默认为+ 正数
  3. num为当前数字，可能有多位
  4. 遍历字符串如果符号位+号则当前数入栈；如果为-号当前数入栈为负数；如果为*出栈数与当前数相乘结果入栈；如果为/号，出栈数/当前数，结果入栈
  5. 出栈数累加就是结果
/**
 * @param {string} s
 * @return {number}
 */
var calculate = function (s) {
    s = s.trim();
    let sym = "+";
    const stack = [];
    let num = 0;
    for (let i = 0; i < s.length; i++) {
        const isNumber = !isNaN(Number(s[i]));
        if (isNumber && s[i] !== " ") {
            num = num * 10 + s[i] * 1
        }
        if (!isNumber || i === s.length - 1) {
            switch (sym) {
                case '+':
                    stack.push(num);
                    break;
                case '-':
                    stack.push(-num);
                    break;
                case '*':
                    stack.push(stack.pop() * num);
                    break;
                default:
                    const cNum = stack.pop();
                    stack.push(cNum > 0 ? Math.floor(cNum / num) : Math.ceil(cNum / num));
                    break;
            }
            num = 0;
            sym = s[i];
        }
    }
    let sum = 0;
    while (stack.length) {
        // 如果换成 shift 超出时间限制
        sum += stack.pop();
    }
    return sum;
};
复制代码

636. 函数的独占时间

有一个 单线程 CPU 正在运行一个含有 n 道函数的程序。每道函数都有一个位于  0 和 n-1 之间的唯一标识符。

函数调用 存储在一个 调用栈 上 ：当一个函数调用开始时，它的标识符将会推入栈中。而当一个函数调用结束时，它的标识符将会从栈中弹出。标识符位于栈顶的函数是 当前正在执行的函数 。每当一个函数开始或者结束时，将会记录一条日志，包括函数标识符、是开始还是结束、以及相应的时间戳。
给你一个由日志组成的列表 logs ，其中 logs[i] 表示第 i 条日志消息，该消息是一个按 “{function_id}:{“start” | “end”}:{timestamp}” 进行格式化的字符串。例如，”0:start:3″ 意味着标识符为 0 的函数调用在时间戳 3 的 起始开始执行 ；而 “1:end:2” 意味着标识符为 1 的函数调用在时间戳 2 的 末尾结束执行。注意，函数可以 调用多次，可能存在递归调用 。
函数的 独占时间 定义是在这个函数在程序所有函数调用中执行时间的总和，调用其他函数花费的时间不算该函数的独占时间。例如，如果一个函数被调用两次，一次调用执行 2 单位时间，另一次调用执行 1 单位时间，那么该函数的 独占时间 为 2 + 1 = 3 。
以数组形式返回每个函数的 独占时间 ，其中第 i 个下标对应的值表示标识符 i 的函数的独占时间。

提示：
1 <= n <= 100
1 <= logs.length <= 500
0 <= function_id < n
0 <= timestamp <= 109
两个开始事件不会在同一时间戳发生
两个结束事件不会在同一时间戳发生
每道函数都有一个对应 “start” 日志的 “end” 日志

提议理解：
分段计算cpu运行各个函数所使用的时间，一个函数可能运行多次

  1. res保存返回数据，stack保存开始的进程
  2. 遍历日志，如果类型为start则入栈，end为出栈，记录前一个进程运行时间，并且对不存在的函数初始化时间

方案二

/**
 * @param {number} n
 * @param {string[]} logs
 * @return {number[]}
 */

var exclusiveTime = function (n, logs) {
      const res = [];
      const stack = [];
      let prev = 0;
      for (let item of logs) {
        let [index, type, value] = item.split(":");
        index *= 1;
        value *= 1;
        if (type === "start") {
          if (res[index] === undefined) {
            res[index] = 0;
          }
          if (stack.length) {
            res[stack[stack.length - 1]] += value - prev - 1;
          }
          stack.push(index)
        } else {
          const currentIndex = stack.pop();
          res[currentIndex] += value - prev + 1;
        }
        prev = value;
      }
      return res
};
复制代码

方案一
通过调试多次测试用例，最后调试出来的方法
第一次没考虑周全

  1. res存储结果
  2. stack存储为结束的进程和上个任务
  3. 如果此次为开始，则入栈，并计算上个任务的时长
  4. 否则出栈，计算时长
/**
 * @param {number} n
 * @param {string[]} logs
 * @return {number[]}
 */

var exclusiveTime = function (n, logs) {
    const res = [];
    const stack = [];
    for (let item of logs) {
        const current = item.split(":");
        if (current[1] === "start") {
            if (res[current[0] * 1] === undefined) {
                res[current[0] * 1] = 0;
            }
            if (stack.length) {
                let pre = stack[stack.length - 1];
                const diff = current[2] * 1 - pre[2] * 1;
                if (pre[1] === "start") {
                    res[pre[0] * 1] += diff;
                } else {
                    pre = stack.pop()
                    pre = stack.length ? stack[stack.length - 1] : pre;
                    res[pre[0] * 1] += diff - 1;
                }
            }
        } else {
            const pre = stack.pop();
            res[current[0] * 1] += current[2] * 1 - pre[2] * 1;
            if (pre[1] === "start") {
                res[current[0] * 1] += 1;
            }
            // 特变注意点 pre[1] !== stack[stack.length - 1][1]
            if (stack.length && pre[1] !== stack[stack.length - 1][1] && stack[stack.length - 1][0] === current[0]) {
                stack.pop();
            }
        }
        stack.push(current)
    }
    return res
};
复制代码
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
前端
喜欢就支持一下吧
点赞0 分享
AI-robot的头像-一一网
asgbookphp ‘index.php’ 跨站脚本攻击漏洞-一一网
asgbookphp ‘index.php’ 跨站脚本攻击漏洞
asgbookphp ‘index.php’ 跨站脚本攻击漏洞
14年前 2.6W+
机器学习之随机森林回归篇（RandomForestRegressor）-一一网
机器学习之随机森林回归篇（RandomForestRegressor）
机器学习之随机森林回归篇（RandomForestRegressor）
4年前 4235
详解数仓中的数据分层：ODS、DWD、DWM、DWS、ADS-一一网
详解数仓中的数据分层：ODS、DWD、DWM、DWS、ADS
详解数仓中的数据分层：ODS、DWD、DWM、DWS、ADS
4年前 3920
DZCP Clanportal ＇Index.PHP＇任意文件上载漏洞-一一网
DZCP Clanportal ＇Index.PHP＇任意文件上载漏洞
DZCP Clanportal ＇Index.PHP＇任意文件上载漏洞
19年前 3843
Wireshark之抓包文件保存-一一网
Wireshark之抓包文件保存
Wireshark之抓包文件保存
4年前 3411
支付宝生活号H5接入支付宝支付流程-一一网
支付宝生活号H5接入支付宝支付流程
支付宝生活号H5接入支付宝支付流程
3年前 3162
相关推荐
支付宝生活号H5接入支付宝支付流程-一一网
支付宝生活号H5接入支付宝支付流程
支付宝生活号H5接入支付宝支付流程
3年前 3162
手摸手教你实现vue的动态路由（addRoute版）-一一网
手摸手教你实现vue的动态路由（addRoute版）
手摸手教你实现vue的动态路由（addRoute版）
4年前 3147
Unity实用功能之使用TextMeshPro组件-一一网
Unity实用功能之使用TextMeshPro组件
Unity实用功能之使用TextMeshPro组件
4年前 3098
vue 项目运行报错：npm ERR! This is probably not a problem with npm. There is likely …-一一网
vue 项目运行报错：npm ERR! This is probably not a problem with npm. There is likely …
vue 项目运行报错：npm ERR! This is probably not a problem with npm. There is likely …...
4年前 2848
Windi CSS 在 Vue3 + Vite 项目中的使用-一一网
Windi CSS 在 Vue3 + Vite 项目中的使用
Windi CSS 在 Vue3 + Vite 项目中的使用
3年前 2747
vue3 使用 qrcode.vue 生成二维码-一一网
vue3 使用 qrcode.vue 生成二维码
vue3 使用 qrcode.vue 生成二维码
4年前 2650
搜索
开启精彩搜索
世界，您好！-一一网
3.7W+人已阅读
世界，您好！
TOP1
番茄社区无限观看+付费视频破解教程-一一网
番茄社区无限观看+付费视频破解教程
5年前3.2W+人已阅读
TOP2
香蕉视频v3.8.3_VIP会员破解教程-一一网
香蕉视频v3.8.3_VIP会员破解教程
5年前3.1W+人已阅读
TOP3
[桜井宁宁]COS和泉纱雾超可爱写真福利集-一一网
密码保护：[桜井宁宁]COS和泉纱雾超可爱写真福利集
5年前2.8W+人已阅读
TOP4
[桜井宁宁] 爆乳奶牛少女cos写真-一一网
密码保护：[桜井宁宁] 爆乳奶牛少女cos写真
5年前2.8W+人已阅读
TOP5
快猫v1.1.7会员破解版_最新快猫vip破解教程大全-一一网
快猫v1.1.7会员破解版_最新快猫vip破解教程大全
5年前2.7W+人已阅读
TOP6
标签云
默认路由黑裙黑群晖麦克风车机鸿蒙系统鸿蒙系统鸿蒙OS鸿蒙驱动软件驱动题库音频剪辑音乐剪辑面板面具静态雷石集群随机阿里云