算法内容

1.最长有效括号，题目类型：栈，字符串，比较困难 2.删除有序数组中的重复项，题目类型：数组，双指针，比较简单 3.删除有效括号，题目类型：字符串，优先搜索，比较困难

题目描述

第一题最长有效括号题目描述

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

示例 1：

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

示例 2：

输入：s = ")()())" 输出：4 解释：最长有效括号子串是 "()()"

示例 3：

输入：s = "" 输出：0

提示：

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

以下Java程序实现了这一功能，请你填补空白处内容：

import java.util.*; class Solution { public int longestValidParentheses(String s) { int left = 0, right = 0, max = 0; for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == '(') left++; else right++; if (left == right) max = Math.max(max, left * 2); if (right > left) left = right = 0; } left = 0; right = 0; for (int i = s.length() - 1; i >= 0; i--) { __________________; if (left == right) max = Math.max(max, left * 2); if (right < left) left = right = 0; } return max; } }

Java代码解答如下

if (s.charAt(i) == '(') left++; else right++;

第二题删除有序数组中的重复项题目描述

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。 不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

说明: 为什么返回数值是整数，但输出的答案是数组呢? 请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。 你可以想象内部操作如下: // nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝 int len = removeDuplicates(nums); // 在函数里修改输入数组对于调用者是可见的。 // 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。

for (int i = 0; i < len; i++) {     print(nums[i]); }

示例 1： 输入：nums = [1,1,2] 输出：2, nums = [1,2] 解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

示例 2： 输入：nums = [0,0,1,1,1,2,2,3,3,4] 输出：5, nums = [0,1,2,3,4] 解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

提示： 0 <= nums.length <= 3 * 104 -104 <= nums[i] <= 104 nums 已按升序排列

Java代码解答如下

class Solution { public int removeDuplicates(int[] nums) { if (nums == null || nums.length == 0) { return 0; } int a = 0; for (int b = 1; b < nums.length; b++) { if (nums[a] != nums[b]) { a++; nums[a] = nums[b]; } } return a + 1; } }

第三题 删除有效括号 题目描述

给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。 返回所有可能的结果。答案可以按 任意顺序 返回。

示例 1：

输入：s = "()())()" 输出：["(())()","()()()"]

示例 2：

输入：s = "(a)())()" 输出：["(a())()","(a)()()"]

示例 3：

输入：s = ")(" 输出：[""]

提示：

1 <= s.length <= 25 s 由小写英文字母以及括号 '(' 和 ')' 组成 s 中至多含 20 个括号

Java代码解答如下

public class Solution { private Set<String> set; private String input; private int maxLen = 0; public List<String> removeInvalidParentheses(String s) { set = new HashSet<>(); input = s; removeInvalidParentheses(0, "", 0, 0); return new ArrayList<>(set); } private void removeInvalidParentheses(int index, String valid, int leftCount, int rightCount) { if (leftCount < rightCount) { return; } if (index == input.length()) { if (leftCount == rightCount) { if (maxLen < valid.length()) { maxLen = valid.length(); set.clear(); set.add(valid); } else if (maxLen == valid.length()) { set.add(valid); } } return; } char c = input.charAt(index); if (c == '(') { removeInvalidParentheses(index + 1, valid, leftCount, rightCount); removeInvalidParentheses(index + 1, valid + c, leftCount + 1, rightCount); } else if (c == ')') { removeInvalidParentheses(index + 1, valid, leftCount, rightCount); removeInvalidParentheses(index + 1, valid + c, leftCount, rightCount + 1); } else { removeInvalidParentheses(index + 1, valid + c, leftCount, rightCount); } } }