算法内容
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);
}
}
}
标签：right,nums,int,练习,括号,算法,valid,数组,left From： https://blog.51cto.com/u_15312559/5785807