锐客网

  1. 首页 > 睿知 > it技术 > >

Leetcode 20有效的括号（附JAVA Deque 和LinkedList用法）

IT知识leetcodelinkedlist

不操千曲而后晓声，观千剑而后识器。这篇文章主要讲述Leetcode 20有效的括号（附JAVA Deque 和LinkedList用法）相关的知识，希望能为你提供帮助。


方法一：利用栈

思路：（1）创建一个栈，在栈里依次加入字符串的括号，如果遇到的是右括号，那么将左括号入栈，如果是右括号，则将出栈一个元素，判断出栈元素，是不是刚好是当前即将入栈的匹配右元素
python版本

class Solution(object):
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""

# The stack to keep track of opening brackets.
stack = []

# Hash map for keeping track of mappings. This keeps the code very clean.
# Also makes adding more types of parenthesis easier
mapping = ")": "(", "": "", "]": "["

# For every bracket in the expression.
for char in s:

# If the character is an closing bracket
if char in mapping:

# Pop the topmost element from the stack, if it is non empty
# Otherwise assign a dummy value of # to the top_element variable
top_element = stack.pop() if stack else #

# The mapping for the opening bracket in our hash and the top
# element of the stack dont match, return False
if mapping[char] != top_element:
return False
else:
# We have an opening bracket, simply push it onto the stack.
stack.append(char)

# In the end, if the stack is empty, then we have a valid expression.
# The stack wont be empty for cases like ((()
return not stack

java版本
class Solution
public boolean isValid(String s)
int n = s.length();
if (n % 2 == 1)
return false;


Map< Character, Character> pairs = new HashMap< Character, Character> ()
put(), ();
put(], [);
put(, );
;
Deque< Character> stack = new LinkedList< Character> ();
for (int i = 0; i < n; i++)
char ch = s.charAt(i);
if (pairs.containsKey(ch))
if (stack.isEmpty() || stack.peek() != pairs.get(ch))
return false;

stack.pop();
else
stack.push(ch);


return stack.isEmpty();


如果括号只有??()??样式，那么判断有效的括号可以用下面的方式
def vaild(input_str):
tmp = []
for i in input_str:

if i == ")" and tmp[-1] == "(":
print(tmp[-1])
tmp.pop()
else:
tmp.append(i)

if tmp == []:
return True
else:
return False

print(vaild("(()())"))

扩展，关于Java的双端队列Deque和LinkedList相关知识
一个是peek和pop的用法
???peek()??? 返回队头元素，但不删除该元素。
???pop()?? 返回队头元素，并删除该元素。
示例代码如下
import java.util.LinkedList;
class LinkedListPopDemo

public static void main(String[] args)

// Create a LinkedList of Strings
LinkedList< String> list = new LinkedList< String> ();

// Add few Elements
list.add("Jack");
list.add("Robert");
list.add("Chaitanya");
list.add("kate");

// Display LinkList elements
System.out.println("LinkedList before: "+list);

// pop Element from list and display it
System.out.println("Element removed: "+list.pop());

// Display after pop operation
System.out.println("LinkedList after: "+list);


LinkedList before: [Jack, Robert, Chaitanya, kate]
Element removed: Jack
LinkedList after: [Robert, Chaitanya, kate]

总结一下：
当我们只需要取出栈顶的元素进行处理（或者说我们需要先对栈顶的数据进行处理例如比较）然后根据处理的结果进行决定是否要pop()，这种情况下，我们可以先使用peek()方法，取出栈顶的值。
补充总结一下栈中的其他常用的方法：
empty( )——如果堆栈是空的，则返回true，当堆栈包含元素时，返回false；
一个是add和push的用法区别
Java LinkedList add 是加在list尾部，LinkedList push 施加在list头部，等同于addFirst
【Leetcode 20有效的括号（附JAVA Deque 和LinkedList用法）】示例代码1
import java.util.LinkedList;
class LinkedListExample

public static void main(String[] args)

// Create a LinkedList of Strings
LinkedList< String> list = new LinkedList< String> ();

// Add few Elements
list.add("Jack");
list.add("Robert");
list.add("Chaitanya");
list.add("kate");

// Display LinkList elements
System.out.println("LinkedList contains: "+list);

// push Element the list
list.push("NEW ELEMENT");

// Display after push operation
System.out.println(

    推荐阅读


    上一篇：投稿|狂奔的极兔，摔了一跤

    下一篇：Go Web 编程入门（验证器）