左神课堂开始

2024-01-05 03:08

文章标签 课堂左神

本文主要是介绍左神课堂开始，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这些都是左神（左程云）课堂里讲的例子，写下自己的理解。

1、已知一个字符串都是由左括号(和右括号)组成，判断该字符串是否是有效的括号组合。

例子：

有效的括号组合:()()(())(()())

无效的括号组合:(())(()()(()

这题比较简单，

1,可以先定义一个状态 int status ==0 ，当遇到“)”这个状态就改变：--status;

2,当遇到“(”也改变其其状态：status++;

3,当遇到其他的字符就直接返回 false;

public static boolean isValid(String str){if (str == null || str.equals("")){return false;}char[] chas = str.toCharArray();int status = 0;for (int i = 0; i < chas.length; i++){if (chas[i] != ')' && chas[i] != '('){return false;}if (chas[i] == ')' && --status < 0){return false;}if (chas[i] == '('){status++;}}return status == 0;}

2、题目进阶：

已知一个字符串都是由左括号(和右括号)组成，返回最长有效括号子串的长度。

该题：其实也很简单，但是是在左神讲完了之后，我才觉得的。

(())(()(()))

可以定义一个数组 int[] dp = new int[chas.length];长度就是上面字符串的长度。该数组就是为了保存每个位置上最大子串的长度。看下表：

i 0 1 2 3 4 5 6 7

chas ( ) ( ( ) ( ) )

dp 0 2 0 0 2 0 4 8

从上表可以看出。

dp的值，只有在“)”上计算才有意义。

当i = 6 时:最大子串是"前面最大子串"的长度 +2（只要出现一对，最少+2);

而然，"前面的最大子串"怎么去获得呢？

需要通过 pre = i - dp[i-1]-1 ;比如：i = 7时，pre = 7-4-1 = 2;

然后，还需要注意前面是否还存在成对符号“()”所以就需要加上 dp[pre-1]。这样 i= 7的时候，结果dp[7] = 8;

for (int i = 1; i < chas.length; i++){if (chas[i] == ')'){pre = i - dp[i - 1] - 1;if (pre >= 0 && chas[pre] == '('){dp[i] = dp[i - 1] + 2 + (pre > 0 ? dp[pre - 1] : 0);}}res = Math.max(res, dp[i]);}

完整代码：

public class Problem_01_ParenthesesProblem
{public static boolean isValid(String str){if (str == null || str.equals("")){return false;}char[] chas = str.toCharArray();int status = 0;for (int i = 0; i < chas.length; i++){if (chas[i] != ')' && chas[i] != '('){return false;}if (chas[i] == ')' && --status < 0){return false;}if (chas[i] == '('){status++;}}return status == 0;}public static int maxLength(String str){if (str == null || str.equals("")){return 0;}char[] chas = str.toCharArray();int[] dp = new int[chas.length];int pre = 0;int res = 0;for (int i = 1; i < chas.length; i++){if (chas[i] == ')'){pre = i - dp[i - 1] - 1;if (pre >= 0 && chas[pre] == '('){dp[i] = dp[i - 1] + 2 + (pre > 0 ? dp[pre - 1] : 0);}}res = Math.max(res, dp[i]);}return res;}public static void main(String[] args){String str1 = "((())())";System.out.println(isValid(str1));System.out.println(maxLength(str1));String str2 = "(())(()(()))";System.out.println(isValid(str2));System.out.println(maxLength(str2));String str3 = "()(()())";System.out.println(isValid(str3));System.out.println(maxLength(str3));}
}

左神：语录

记住：看到子串，子数组一般都是以每个位置开头，以每个位置结尾。几乎可以解决70%。

但是，子序列却不是这样的。