leetcode-155-160

leetcode155题160题:

leetcode155题(最小栈):

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

  • push(x) – 将元素 x 推入栈中。
  • pop() – 删除栈顶的元素。
  • top() – 获取栈顶元素。
  • getMin() – 检索栈中的最小元素。
示例:
1
2
3
4
5
6
7
8
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
解答:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
* initialize your data structure here.
*/
var MinStack = function() {
this.stack = [];
this.temp = [];//辅助栈
};

/**
* @param {number} x
* @return {void}
*/
MinStack.prototype.push = function(x) {
this.stack.push(x);
if(this.temp.length==0||this.temp[this.temp.length-1]>=x){//保证辅助栈中,数字的排列从大到小(可相等)
this.temp.push(x);
}
};

/**
* @return {void}
*/
MinStack.prototype.pop = function() {//stack栈一定会pop,对于辅助栈,如果等于栈顶元素,则pop
if(this.stack.pop()==this.temp[this.temp.length-1]){
this.temp.pop();
}
};
/**
* @return {number}
*/
MinStack.prototype.top = function() {//取出栈顶元素
return this.stack[this.stack.length-1];
};

/**
* @return {number}
*/
MinStack.prototype.getMin = function() {//取出辅助栈的栈顶元素
return this.temp[this.temp.length-1];
};

leetcode160题(相交链表):

编写一个程序,找到两个单链表相交的起始节点。

题目

示例:

示例1

示例2

示例3

解答:

采用双指针的方法。

我们可以将a和b两个链表强行串联起来,变成一个8字的形状。

图示

然后我们定义两个指针,一个从a链表头出发,一个从b链表头出发,因为是环形的,最终两个链表会相遇,而相遇的节点就是相交的节点 。

1
2
3
4
5
6
7
8
9
var getIntersectionNode = function(headA, headB) {
var a = headA;
var b = headB;
while(a!=b){
a = (a==null)?headB:a.next;//当a到头的时候,转到headB上去
b = (b==null)?headA:b.next;//当b到头的时候,转到headA上去
}
return a;
};
分享到