当前位置：网站首页>2022-024ARTS：最长有效括号

2022-024ARTS：最长有效括号

2022-07-26 08:08:00 【FlashSu】

ARTS：Algorithm、Review、Tip、Share
Algorithm 算法题
Review 英文文章
Tip 回想一下本周工作中学到的一个小技巧
Share思考一个技术观点、社会热点、一个产品或是一个困惑

Algorithm

32. 最长有效括号

给你一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

示例 1：

输入：s = “(()”
输出：2
解释：最长有效括号子串是 “()”
示例 2：

输入：s = “)()())”
输出：4
解释：最长有效括号子串是 “()()”
示例 3：

输入：s = “”
输出：0

提示：

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-valid-parentheses

解法描述

一道典型的动态规划类型的题目，重点是要找出、定义出状态转移方程，创建一个dp数组，其元素表示：必须包含当前入参字符数组对应下标元素的最长有效括号值。我们只要求出dp数组每个元素的值，找到最大值即为题目所求。

dp值的求解与对应字符有关：如果为开括号，当前肯定不是有效的括号组合，直接跳过；所以我们只处理当前位置为闭括号 “)” 的情况。如果前一个元素为开括号，则比较简单，直接查看 dp[i-2] 元素的值加2就好了，注意需要判断下标。如果 i-1 位置为闭括号 “)”，则需要继续往前看，直到找到有可能存在的对应 i 位置的开括号 “(”，此时 dp[i] = dp[i-1] + dp[i-dp[i-1] - 2] + 2，其中 i-dp[i-1] - 2 为 dp[i-1] 有效长度往前越过开括号的前一个位置，即注释中的x位置。

编码实现

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] == '(') {
    
            // 查看 ( 之前的最长串是否有效
            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;
}

复杂度分析

时间复杂度O(n)
空间复杂度O(n)

Review

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

Tip

校验2个时间戳是否为同一天的问题，需要制定具体的时区进行判断，而校验具体是否为同一天，可以根据Java8中的LocalDate是否

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));
}