程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> Longest Valid Parentheses

Longest Valid Parentheses

編輯:關於C++
Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

z題目是找出最長的匹配括號。

給的提示是用動態規劃,但是我看了網上的,貌似都是沒體現到。


我的解法是這樣的:

1. 對輸入字符串s,開辟int[s.length()]b

2. 從左到右對s進行入棧,當s[i]=='(' push(i)

3.當s[i]==')' b[i]=pop();

這樣子就記錄了所有)對應的(的位置。

4.從右向左掃描s,對i處==‘)’跳到其對應的‘(’處j=b[i],並且看‘(’前面,即j-1是否也是個有匹配的‘)’如果是,則再跳到其匹配的‘(’處,累計長度

5.我比較笨,沒有意識到,在一對匹配的‘(’,‘)’中,他們之間的括號一定是匹配的。

因此,在從右往左計算的時候,遍歷s的指針只需要一直往‘)’所對應的‘(’處跳,而不是要-1來重復工作。

6.上面這個還要計算跳的位置,我對這種算兩個下標之間距離,兩數相減+1一直都容易算錯。

網上還有另一個開辟bool[s.length()] b

對有匹配的括號對其對應的b中是true;

所以最終問題演變成查找b中最長的true串,(因為兩個匹配的括號中間一定是匹配的)

這個方法跟5比起來是一樣的,它的空間比5小,但是5理論上會快一點。


上代碼

package leetcode;

import java.util.Stack;

public class longest_Valid_Parentheses {
	public static int longestValidParentheses(String s) {
		if ("".equals(s))
			return 0;
		Stack st = new Stack();
		int t = 0;
		int[] tmp = new int[s.length()];
		for (int i = 0; i < s.length(); i++) {
			if (s.charAt(i) == '(')
				st.push(i);
			else if (s.charAt(i) == ')' && !st.isEmpty()) {
				tmp[i] = i - st.pop() + 1;
			}
		}
		int max = 0;
		for (int i = tmp.length - 1; i >= 0; i--) {
			if (tmp[i] != 0) {
				max = max > tmp[i] ? max : tmp[i];
				int j=i-tmp[i];
				while (j > 0 && tmp[j] != 0) {

					tmp[i] += (tmp[j]);
					max = max > tmp[i] ? max : tmp[i];
					j = j - tmp[j];

				}
				if(j>0)i=j+1;
			}
		}
		return max;

	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println(longestValidParentheses("(()()()()"));
	}

}




  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved