2022-024arts: Longest valid bracket

ARTS：Algorithm、Review、Tip、Share

• Algorithm Algorithm problem
• Review English articles
• Tip Think back to a small skill learned at work this week
• Share Think about a technical point of view 、 Social hot spots 、 A product or a puzzle

Algorithm

32. Longest valid bracket

Give you one that only contains ‘(’ and ‘)’ String , Find the longest effective （ The format is correct and continuous ） The length of the bracket substring .

Example 1：

Input ：s = “(()”
Output ：2
explain ： The longest valid bracket substring is “()”
Example 2：

Input ：s = “)()())”
Output ：4
explain ： The longest valid bracket substring is “()()”
Example 3：

Input ：s = “”
Output ：0

Tips ：

0 <= s.length <= 3 * 104
s[i] by ‘(’ or ‘)’

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/longest-valid-parentheses

Solution description

A typical topic of dynamic programming , The point is to find out 、 Define the state transition equation , Create a dp Array , Its elements represent ： Must contain the subscript element corresponding to the current input character array The longest valid bracket value of . We just need to find out dp The value of each element of the array , Finding the maximum value is the goal of the topic .

dp The solution of the value is related to the corresponding character ： If it is an open bracket , Currently, it is definitely not a valid bracket combination , Just skip ; So we only deal with closed parentheses in the current position “)” The situation of . If the previous element is an open bracket , It's simpler , Direct view dp[i-2] Add the value of the element 2 Just fine , Pay attention to the need to judge the subscript . If i-1 The position is closed parenthesis “)”, You need to keep looking forward , Until we find the possible correspondence i Open bracket of position “(”, here dp[i] = dp[i-1] + dp[i-dp[i-1] - 2] + 2, among i-dp[i-1] - 2 by dp[i-1] The effective length goes forward past the previous position of the open bracket , That is x Location .

coded

public int longestValidParentheses(String s) {
    
    if (s == null || s.length() == 0) {
    
        return 0;
    }

    int max = 0;
    int[] dp = new int[s.length()];
    char[] chars = s.toCharArray();
    for (int i = 1; i < chars.length; i++) {
    
        if (chars[i] != ')') {
    
            continue;
        }

        if (chars[i - 1] == '(') {
    
            //  see  (  Whether the previous longest string is valid 
            dp[i] = i >= 2 && dp[i - 2] >= 0 ? dp[i - 2] + 2 : 2;
        } else if (dp[i - 1] > 0 && (i - dp[i - 1] - 1) >= 0 && chars[i - dp[i - 1] - 1] == '(') {
    
            // ↓
            // x((……))
            dp[i] = dp[i-1] + (i-dp[i-1]-2 >= 0 ? dp[i-dp[i-1]-2] : 0) + 2;
        }
        max = Math.max(max, dp[i]);
    }
    return max;
}

Complexity analysis

Time complexity O(n)
Spatial complexity O(n)

Review

Spring 5 source code analysis series (4) — initialization of IOC container (2)

Tip

check 2 Whether the timestamps are the same day , It is necessary to formulate a specific time zone for judgment , And check whether it is the same day , According to Java8 Medium LocalDate whether

public static void main(String[] args) {
    
    ZoneId swissZone = ZoneId.of("Asia/Shanghai");
    ZoneId numZone = ZoneId.of("UTC+08:00");
    System.out.println(swissZone.equals(numZone));

    Instant instant = Instant.now();
    ZonedDateTime time1 = instant.atZone(swissZone);

    ZonedDateTime time2 = Instant.ofEpochMilli(System.currentTimeMillis()).atZone(numZone);
    System.out.println("is same date? " + time1.toLocalDate().isEqual(time2.toLocalDate()));
    System.out.println("is same date, use equals? " + time1.toLocalDate().equals(time2.toLocalDate()));
    System.out.println("time is equals? " + time1.isEqual(time2));
}

Share

I've seen it recently 《 The courage to be hated 》 This book , It mainly introduces some viewpoints in Adler's Psychology , The book is described in the form of several dialogues between young people and philosophers , Explained freedom 、 Happiness 、 The meaning of life 、 Attitude to life these problems , I believe this is a topic that many people will think about , My own words , There will always be some vague understanding , The ideas given in this book are simple 、 Much more direct , But it is worth repeatedly understanding and thinking ……