每日一题之LeetCode 栈简单题集合496,682,232,225,155,844,20

496 下一个最大的元素
方法1 :自己瞎写的 没有考虑到栈的特性
class Solution:
def nextGreaterElement(self, nums1, nums2):

     L=[]
    for i in nums1:
         k=nums2.index(i)
         lenth2=len(nums2)
        if k==lenth2-1:
           L.append(-1)
         for j in range(k+1,lenth2):
             if nums2[j]>i:
                 L.append(nums2[j])
                 break

             if j==lenth2-1:
                 L.append(-1)
    return L  

方法2:网上大神写的 很膜拜
class Solution:
def nextGreaterElement(self, nums1, nums2):

                    d = {}
                    st = []
                    ans = []

                    for x in nums2:
                        while len(st) and st[-1] < x:
                            d[st.pop()] = x
                        st.append(x)

                    for x in nums1:
                        ans.append(d.get(x, -1))

                    return ans

682.棒球比赛
注:好久前写的,后面再吧栈的写出来
ops= ["35","-32","C","39","+","-48","C","5","88","-52","+","C","D","D","100","C","+","-74","53","59"]
L=[]
sum=[]
lenth=len(ops)
for i in range(0,lenth):
if i==0:
sum.append(int(ops[i]))
else:

   if ops[i]==‘C‘:

            sum.insert(0,0)

            sum.insert(1,0)

            sum.pop()

   elif  ops[i]==‘D‘:
    sum.append(sum[i-1]*2)

   elif ops[i]==‘+‘:
    sum.append(sum[i-1]+sum[i-2])
   else :

        sum.append(int(ops[i]))

score=0
for j in sum:
score=score+j
print(score)
232.用栈实现队列
方法1:网上的,用两个list来实现
class MyQueue:

def __init__(self):
    """
    Initialize your data structure here.
    """
    self.stact=[]
    self.queue=[]
    self.len=0

def push(self, x):
    """
    Push element x to the back of queue.
    :type x: int
    :rtype: void
    """
    self.stact.append(x)
    self.len=self.len+1

def pop(self):
    """
    Removes the element from in front of queue and returns that element.
    :rtype: int
    """

    while len(self.stact)!=0:
        self.queue.append(self.stact.pop())

    x = self.queue.pop()

    while len(self.queue)!= 0:
       self.stact.append(self.queue.pop())

    self.len -=1
    return x

def peek(self):
    """
    Get the front element.
    :rtype: int
    """

    while len(self.stact)!=0:
        self.queue.append(self.stact.pop())

    x = self.queue.pop()
    self.queue.append(x)
    while len(self.queue)!= 0:
       self.stact.append(self.queue.pop())

    return x

def empty(self):
    """
    Returns whether the queue is empty.
    :rtype: bool
    """

    if self.len==0:
        return False

方法2:用一个list来实现,比较简单
class MyQueue:

def __init__(self):
    """
    Initialize your data structure here.
    """
    self.queue = []

def push(self, x):
    """
    Push element x to the back of queue.
    :type x: int
    :rtype: void
    """
    self.queue.append(x)

def pop(self):
    """
    Removes the element from in front of queue and returns that element.
    :rtype: int
    """
    if len(self.queue)>0:
       print( self.queue.pop(0))

def peek(self):
    """
    Get the front element.
    :rtype: int
    """
    if len(self.queue)>0:
        print( self.queue[0])

def empty(self):
    """
    Returns whether the queue is empty.
    :rtype: bool
    """
    if len(self.queue)>0:
        return False
    else:
        return True
def shuchu(self):
     for i in self.queue:
         print(i)

235,用队列来实现栈
注:与上面异曲同工
class MyStack:

def __init__(self):
    """
    Initialize your data structure here.
    """
    self.queue = []

def push(self, x):
    """
    Push element x to the back of queue.
    :type x: int
    :rtype: void
    """
    self.queue.append(x)

def pop(self):
    """
    Removes the element from in front of queue and returns that element.
    :rtype: int
    """
    if len(self.queue)>0:
        return self.queue.pop()
        #len(self.queue)-=1

def top(self):
    """
    Get the front element.
    :rtype: int
    """
    if len(self.queue)>0:
        return self.queue[-1]

def empty(self):
    """
    Returns whether the queue is empty.
    :rtype: bool
    """
    if len(self.queue)>0:
        return False
    else:
        return True

155,最小栈
注:可以使用深复制在里面找出来最小值,但会超时,很慢很慢
方法1:用min 函数,较慢,因为每次都执行
class MinStack:

def __init__(self):
    """
    initialize your data structure here.
    """
    self.queue = []
    self.min=None
def push(self, x):
    """
    :type x: int
    :rtype: void
    """
    self.queue.append(x)
    self.min=min(self.queue)

def pop(self):
    """
    :rtype: void
    """
    if len(self.queue)>0:
       self.queue.pop()
       self.min=min(self.queue)
       return self.queue
def top(self):
    """
    :rtype: int
    """
    if len(self.queue)>0:
        return self.queue[-1]

def getMin(self):
    """
    :rtype: int
    """
    return self.min

方法2:判断,比较快
class MinStack(object):
def init(self):
"""
initialize your data structure here.
"""
self.stack = []
self.min = None

def push(self, x):
    """
    :type x: int
    :rtype: void
    """
    self.stack.append(x)
    if self.min == None or self.min > x:
        self.min = x

def pop(self):
    """
    :rtype: void
    """

    popItem = self.stack.pop()
    if len(self.stack) == 0:
        self.min = None
        return popItem

    if popItem == self.min:
        self.min = self.stack[0]
        for i in self.stack:
            if i < self.min:
                self.min = i
    return popItem

def top(self):
    """
    :rtype: int
    """
    return self.stack[-1]

def getMin(self):
    """
    :rtype: int
    """
    return self.min

844.比较含退格的字符串
注:注意遇到‘#’时,字符串长度为0时的处理,以及两个“#”,字符串长度为0时的处理。PS,这是老子自己写出来运行最快的代码了,代码也简洁,写了半个小时吧,有一丢丢自豪。还学会了在类里调用函数。一个类里不能函数调用函数。
class Solution:

def backspaceCompare(self, S, T):
    """
    :type S: str
    :type T: str
    :rtype: bool
    """

    S1=back(S)
    T1=back(T)
    if S1==T1:
        return True
    else:
        return False

def back(L):
K=[]
for i in L:
if i==‘#‘ and len(K)!=0:

               K.pop()
        elif  i==‘#‘ and len(K)==0:
               pass
        else:
            K.append(i)
    return K

20,有效的括号
注:好久前写的了,也是在学栈之前写的,后面把栈的写出来。
class Solution:
def isValid(self, s):

    a=list(s)
    b=[]                            #存放左括号的栈  qc:list当做栈
    c={‘(‘:‘)‘,‘[‘:‘]‘,‘{‘:‘}‘}     #字典存储     qc;key:value 键:值
    for i in a:
        if i==‘‘:
            return True
        elif i in c: #如果是字典中的键,即左括号,放进栈
            b.append(i)
        else:
            if len(b)==0: #先判断是否有左括号存在
                return False
            else:
                 #字典得到该键的值==栈顶值对应的右括号
                if c.get(b[-1])!=i:
                    return False
                else:
                    del b[-1]      #删除栈顶元素
    if len(b)!=0:  #若还存在左括号,此时已没有右括号,出错
        return False
    return True

PS.写这么一些题还是有用的,至少遇到一些题知道其实是采用了栈的思想,以前都是瞎写。编程还是要有思维。

原文地址:http://blog.51cto.com/13930723/2327301

时间: 12-06

每日一题之LeetCode 栈简单题集合496,682,232,225,155,844,20的相关文章

LeetCode 第 73 题 (Set Matrix Zeroes)

LeetCode 第 73 题 (Set Matrix Zeroes) Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place. Follow up: Did you use extra space? A straight forward solution using O(mn) space is probably a bad idea. A simple impro

leetcode中第一题twosum问题解答算法的可行性证明

leetcode中第一题twosum问题解答算法的可行性证明 一.引入 关于leetcode中第一题twosum问题,网上已有不少高人做出过解答,并提出了切实可行的算法实现.我在解答该题时参考了博客http://www.zixue7.com/article-9576-1.html的解答.为让读者更直观地阅读和理解本文,先简要摘录以上博客的内容如下: 题目还原 Two Sum Given an array of integers, find two numbers such that they a

leetcode第9题-Palindrom Number

这是leetcode的第九题,相对来说比较简单,目的很简单,就是判断一个int型的数是不是回文数.但是有几点需要考虑: 负数应该没有回文数,要加判断!要注意额外的空间申请问题.判断是否是回文数势必要对一个数进行反转,反转的时候就要考虑溢出的问题.实现的代码如下: #include<stdio.h> bool isPalindrom(int x) { if(x<0) return false; else { int tmp=x; int sum=0; while(tmp) { sum=su

LeetCode 第 342 题(Power of Four)

LeetCode 第 342 题(Power of Four) Given an integer (signed 32 bits), write a function to check whether it is a power of 4. Example: Given num = 16, return true. Given num = 5, return false. Follow up: Could you solve it without loops/recursion? 题目很简单,

Leetcode第五题_Longest Palindromic Substring

Longest Palindromic Substring Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring. Leetcode第5题,题目大概意思是给一个字符串,从中找出最长的回文串,所谓回文串,就是

LeetCode 第三题,Longest Substring Without Repeating Characters

题目: Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest s

poj2105 IP Address(简单题)

题目链接:http://poj.org/problem?id=2105 Description Suppose you are reading byte streams from any device, representing IP addresses. Your task is to convert a 32 characters long sequence of '1s' and '0s' (bits) to a dotted decimal format. A dotted decima

poj 3270 Cow Sorting 置换群 简单题

假设初始状态为 a:2 3 1 5 4 6 则目标状态为 b:1 2 3 4 5 6且下标为初始状态中的3 1 2 4 5 6(a[3],a[1]...) 将置换群写成循环的形式 (2,3,1),(5,4),6就不用移动了. 移动方式2种 1:选循环内最小的数和其他len-1个数交换 2:选整个序列最小的数和循环内最小的数交换,转到1,再换回来. #include<cstdio> #include<queue> #include<algorithm> #include&

数论 --- 简单题

吃糖果 Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)Total Submission(s): 22376    Accepted Submission(s): 6396 Problem Description HOHO, 终于从Speakless手上赢走了所有的糖果,是Gardon吃糖果时有个特殊的癖好,就是不喜欢将一样的糖果放在一起吃,喜欢先吃一种,下一次吃另一 种,这样:

BZOJ 2683 简单题 ——CDQ分治

简单题 #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define F(i,j,k) for (int i=j;i<=k;++i) #define D(i,j,k) for (int i=j;i>=k;--i) #define maxn 2000005 int sum[maxn]; void a