42/2 42%2=0
21/2 21%2=1
10/2 10%2=0
5/2 5%2=1
2/2 2%2=0
1/2 1%2=1
stack: 0,1,0,1,0,1
res: 1 0 1 0 1 0
fn1(){
fn2()
}
fn2(){
fn3()
}
fn3(){}
fn1()
stack:fn1,fn2,fn3
O(1)
,查找O(n)
给定 pushed 和 popped 两个序列,每个序列中的 值都不重复,只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时,返回 true;否则,返回 false 。示例 1:输入:pushed = 1,2,3,4,5, popped = 4,5,3,2,1 输出:true 解释:我们可以按以下顺序执行: push(1), push(2), push(3), push(4), pop() -> 4, push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1 示例 2:输入:pushed = 1,2,3,4,5, popped = 4,3,5,1,2 输出:false 解释:1 不能在 2 之前弹出。提示:1 <= pushed.length <= 1000 0 <= pushedi <= 1000 pushed 的所有元素 互不相同 popped.length == pushed.length popped 是 pushed 的一个排列
index++
,最后判断stack是否为空O(n)
,pushed中的元素入栈出栈一次,空间复杂度O(n)
,栈的大小js:
const validateStackSequences = (pushed, popped) => {
const stack = [];//用栈模拟出栈入栈的过程
let index = 0;
const len = pushed.length;
for (let i = 0; i < len; i++) {
stack.push(pushed[i]);
//当popped中index指向的位置的元素和stack栈顶的元素一致时,出栈 并且 index++
while (popped[index] !== undefined && popped[index] === stack[stack.length - 1]) {
stack.pop();
index++;
}
}
return !stack.length;//最后判断stack是否为空
};
给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。你可以假设除了数字 0 之外,这两个数字都不会以零开头。示例1:
,7 示例2:输入:l1 = 2,4,3, l2 = 5,6,4 输出:8,0,7 示例3:输入:l1 = 0, l2 = 0 输出:0提示:链表的长度范围为 1, 100 0 <= node.val <= 9 输入数据保证链表代表的数字无前导 0进阶:如果输入链表不能翻转该如何解决?
O(max(m,n))
,m,n是两个链表的长度,空间复杂度O(m+n)
js:
var addTwoNumbers = function(l1, l2) {
const stack1 = [];
const stack2 = [];
while (l1 || l2) {//两链表入栈
if (l1) {
stack1.push(l1.val);
l1 = l1.next;
}
if (l2) {
stack2.push(l2.val);
l2 = l2.next;
}
}
let carry = 0;
let ansList = null;
while (stack1.length || stack2.length || carry !== 0) {//不断出栈
const s1 = stack1.length ? stack1.pop() : 0;
const s2 = stack2.length ? stack2.pop() : 0;
let val = s1 + s2 + carry;
carry = parseInt(val / 10);//计算进位
val = val % 10;//计算当前节点的值
const curNode = new ListNode(val);
curNode.next = ansList;//向链表前插入新节点
ansList = curNode;//重新赋值ansList
}
return ansList;
};
你现在是一场采用特殊赛制棒球比赛的记录员。这场比赛由若干回合组成,过去几回合的得分可能会影响以后几回合的得分。比赛开始时,记录是空白的。你会得到一个记录操作的字符串列表 ops,其中 opsi 是你需要记录的第 i 项操作,ops 遵循下述规则:整数 x - 表示本回合新获得分数 x "+" - 表示本回合新获得的得分是前两次得分的总和。题目数据保证记录此操作时前面总是存在两个有效的分数。 "D" - 表示本回合新获得的得分是前一次得分的两倍。题目数据保证记录此操作时前面总是存在一个有效的分数。 "C" - 表示前一次得分无效,将其从记录中移除。题目数据保证记录此操作时前面总是存在一个有效的分数。 请你返回记录中所有得分的总和。示例 1:输入:ops = "5","2","C","D","+" 输出:30 解释: "5" - 记录加 5 ,记录现在是 5 "2" - 记录加 2 ,记录现在是 5, 2 "C" - 使前一次得分的记录无效并将其移除,记录现在是 5. "D" - 记录加 2 * 5 = 10 ,记录现在是 5, 10. "+" - 记录加 5 + 10 = 15 ,记录现在是 5, 10, 15. 所有得分的总和 5 + 10 + 15 = 30 示例 2:输入:ops = "5","-2","4","C","D","9","+","+" 输出:27 解释: "5" - 记录加 5 ,记录现在是 5 "-2" - 记录加 -2 ,记录现在是 5, -2 "4" - 记录加 4 ,记录现在是 5, -2, 4 "C" - 使前一次得分的记录无效并将其移除,记录现在是 5, -2 "D" - 记录加 2 * -2 = -4 ,记录现在是 5, -2, -4 "9" - 记录加 9 ,记录现在是 5, -2, -4, 9 "+" - 记录加 -4 + 9 = 5 ,记录现在是 5, -2, -4, 9, 5 "+" - 记录加 9 + 5 = 14 ,记录现在是 5, -2, -4, 9, 5, 14 所有得分的总和 5 + -2 + -4 + 9 + 5 + 14 = 27 示例 3:输入:ops = "1" 输出:1提示:1 <= ops.length <= 1000 opsi 为 "C"、"D"、"+",或者一个表示整数的字符串。整数范围是 -3 104, 3 104 对于 "+" 操作,题目数据保证记录此操作时前面总是存在两个有效的分数 对于 "C" 和 "D" 操作,题目数据保证记录此操作时前面总是存在一个有效的分数
O(n)
,空间复杂度O(n)
js:
let calPoints = function(ops) {
let res = [];
for(let i = 0; i < ops.length; i++){
switch(ops[i]){
case "C":
res.pop();
break;
case "D":
res.push(+res[res.length - 1] * 2);
break;
case "+":
res.push(+res[res.length - 1] + +res[res.length - 2]);
break;
default:
res.push(+ops[i]);
}
}
return res.reduce((i, j) => i + j, 0);
};
设计一个支持 push ,pop ,top 操作,并能在常数时间内检索到最小元素的栈。实现 MinStack 类:MinStack() 初始化堆栈对象。 void push(int val) 将元素val推入堆栈。 void pop() 删除堆栈顶部的元素。 int top() 获取堆栈顶部的元素。 int getMin() 获取堆栈中的最小元素。示例 1:输入: "MinStack","push","push","push","getMin","pop","top","getMin"[],-2,0,-3,[],[],[],[]]输出: null,null,null,null,-3,null,0,-2解释: MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.getMin(); --> 返回 -2.提示:-231 <= val <= 231 - 1 pop、top 和 getMin 操作总是在 非空栈 上调用 push, pop, top, and getMin最多被调用 3 * 104 次
O(1)
js:
var MinStack = function () {
this.stack = [];
this.min_stack = [Infinity];
};
//stack正常push,min_stack只会push需要入栈和栈顶中较小的元素
MinStack.prototype.push = function (x) {
this.stack.push(x);
this.min_stack.push(Math.min(this.min_stack[this.min_stack.length - 1], x));
};
//stack正常pop,min_stack正常pop
MinStack.prototype.pop = function () {
this.stack.pop();
this.min_stack.pop();
};
//返回stack栈顶元素
MinStack.prototype.top = function () {
return this.stack[this.stack.length - 1];
};
//返回min_stack栈顶元素
MinStack.prototype.getMin = function () {
return this.min_stack[this.min_stack.length - 1];
};
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(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:输入: "MyQueue", "push", "push", "peek", "pop", "empty"[], 1, 2, [], [], []] 输出: null, null, null, 1, 1, false解释: MyQueue myQueue = new MyQueue(); myQueue.push(1); // queue is: 1 myQueue.push(2); // queue is: 1, 2 myQueue.peek(); // return 1 myQueue.pop(); // return 1, queue is 2 myQueue.empty(); // return false提示:1 <= x <= 9 最多调用 100 次 push、pop、peek 和 empty 假设所有操作都是有效的 (例如,一个空的队列不会调用 pop 或者 peek 操作)进阶:你能否实现每个操作均摊时间复杂度为 O(1) 的队列?换句话说,执行 n 个操作的总时间复杂度为 O(n) ,即使其中一个操作可能花费较长时间。
O(1)
,pop时间复杂度为O(n)
,因为pop的时候,输出栈为空,则把输入栈所有的元素加入输出栈。空间复杂度O(n)
,两个栈空间js:
var MyQueue = function() {
//准备两个栈
this.stack1 = [];
this.stack2 = [];
};
MyQueue.prototype.push = function(x) {//push的时候加入输入栈
this.stack1.push(x);
};
MyQueue.prototype.pop = function() {
const size = this.stack2.length;
if(size) {//push的时候判断输出栈是否为空
return this.stack2.pop();//不为空则输出栈出栈
}
while(this.stack1.length) {//输出栈为空,则把输入栈所有的元素加入输出栈
this.stack2.push(this.stack1.pop());
}
return this.stack2.pop();
};
MyQueue.prototype.peek = function() {
const x = this.pop();//查看队头的元素 复用pop方法,然后在让元素push进输出栈
this.stack2.push(x);
return x;
};
MyQueue.prototype.empty = function() {
return !this.stack1.length && !this.stack2.length
};
给定一个只包括 '(',')','{','}','','' 的字符串 s ,判断字符串是否有效。有效字符串需满足:左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 每个右括号都有一个对应的相同类型的左括号。示例 1:输入:s = "()" 输出:true 示例 2:输入:s = "()[]{}" 输出:true 示例 3:输入:s = "(]" 输出:false提示:1 <= s.length <= 104 s 仅由括号 '()[]{}' 组成
O(n)
,空间复杂度O(n)
,n为字符串的长度js:
var isValid = function(s) {
const n = s.length;
if (n % 2 === 1) {//如果字符串能组成有效的括号,则长度一定是偶数
return false;
}
const pairs = new Map([//用栈存储括号对
[')', '('],
[']', '['],
['}', '{']
]);
const stk = [];
for (let ch of s){//循环字符串
if (pairs.has(ch)) {
//遇到右括号则判断右括号是否能和栈顶元素匹配
if (!stk.length || stk[stk.length - 1] !== pairs.get(ch)) {
return false;
}
stk.pop();
} else {
stk.push(ch);//如果遇到左括号入栈
}
};
return !stk.length;//循环结束的时候还要判断栈是否为空
};
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。