码农乌托邦

楠哥小站

楠哥,理想主义码农,就职于Google,现居纽约。


Valid Parentheses

括号题目是一类经典的算法题目,有很多变形。这类题目乍一看上去没有什么思路,但是实质上就是最近成对括号的匹配问题。常用的方法有记录括号数目和使用栈两种方式。

合法括号的判断问题是指在一串由()[]和{}组成的字符串中,判断括号是否合法。比如{()[]}是一个合法序列,但是(])就是非法的。该题目的解决可以使用栈来完成。当发现一个左括号([{时,将其压入栈中;当扫描到一个右括号时,判断栈顶元素(java中使用peek()函数)是否是与当前元素匹配的括号字符。如果不匹配,则整个字符串不合法;如果匹配,则弹出栈顶元素(java中使用pop())函数。该题目是Leetcode OJ上的题目,其java实现如下。

public class Solution {

	/**
	 * Given a string containing just the characters '(', ')', '{', '}', '[' and
	 * ']', determine if the input string is valid.
	 * 
	 * The brackets must close in the correct order, "()" and "()[]{}" are all
	 * valid but "(]" and "([)]" are not.
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println(new Solution().isValid("[]{}()"));
	}
	
	public boolean isValid(String s) {
        // Start typing your Java solution below
        // DO NOT write main() function
		Stack <Integer> stack = new Stack<Integer>();
		
        for(int i = 0; i < s.length();i++){
        	switch(s.charAt(i)){
        	case '(':
        		stack.push(1);
        		break;
        	case '[':
        		stack.push(2);
        		break;
        	case '{':
        		stack.push(3);
        		break;
        	case ')':
        		if(stack.empty())
        			return false;
        		if(stack.peek() == 1){
        			stack.pop();
        		}
        		else{
        			return false;
        		}
        		break;
        	case ']':
        		if(stack.empty())
        			return false;
        		if(stack.peek() == 2){
        			stack.pop();
        		}
        		else{
        			return false;
        		}
        		break;
        	case '}':
        		if(stack.empty())
        			return false;
        		if(stack.peek() == 3){
        			stack.pop();
        		}
        		else{
        			return false;
        		}
        		break;
        	default:
        			return false;
        	}
        }
        
        if(!stack.empty())
        	return false;
        else
        	return true;
    }

}
最近的文章

Pow(x, n)

指数计算应该是递归程序设计的入门级题目,但是在一场面试中写一个bug-free的代码还是需要多多注意边界条件。首先是底数的正负会影响结果,其次是指数的正负,也会影响结果。因为函数原型是pow(int…

Technical, Career继续阅读
更早的文章

Climbing Stairs

爬楼梯问题是一道典型的递归问题和动态规划问题的入门级题目。题目描述是:给定一个n个台阶楼梯,每次可以上一个或者两个台阶,请问最终可以有多少种方法爬到顶层。使用递归的思路解决是,到达第K个楼梯的方法数目…

Technical, Career继续阅读
comments powered by Disqus