java算法入门之有效的括号删除有序数组中的重复项实现strStr

下面我将详细讲解“java算法入门之有效的括号删除有序数组中的重复项实现strStr”的完整攻略。

1. 题目描述

这个问题由两部分组成。

1.1 删除有效的括号

给定一个括号字符串 s，删除尽可能多的括号，使得 s 合法，并返回删除后的字符串。

输入：s = "lee(t((c)o)de)"
输出："lee(t(c)o)de"
解释："lee(t(co)de)"、"lee(t(c)ode)" 也是一个可行的答案。

输入：s = "a)b(c)d"
输出："ab(c)d"

1.2 删除有序数组中的重复项实现 strStr

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

题目同时要求实现 strStr 函数，输入一个字符串 haystack 和一个子串 needle，在 haystack 字符串中找出 needle 子串出现的第一个位置（从 0 开始）。如果不存在，则返回 -1。

2. 解题思路

2.1 删除有效括号的算法步骤

1. 维护一个栈，用于存储合法字符串的左括号下标；
2. 遍历字符串 s，如果当前字符为左括号，则将其下标入栈；
3. 如果当前字符为右括号，分两种情况：
4. 栈顶为左括号，则直接将栈顶元素出栈；
5. 栈顶不为左括号，则将当前字符下标入栈。
6. 遍历结束后，再次遍历栈中存储的下标，将对应的字符替换为空串。

2.2 删除有序数组中的重复项实现 strStr 的算法步骤

1. 当 nums 数组为空或只有一个元素时，直接返回长度即可；
2. 定义两个指针 i 和 j，分别指向第一个元素和第二个元素；
3. 遍历数组，当 nums[i] 等于 nums[j] 时，j 向右移动一位；
4. 当 nums[i] 不等于 nums[j] 时，将 nums[j] 赋值给 nums[i+1]，然后 i 和 j 都向右移动一位；
5. 遍历结束后，新数组的长度即为 i + 1；
6. 接着实现 strStr 函数：比较 haystack 中的每个子串是否与 needle 相等，如果相等，则返回相应的下标；如果遍历结束后仍没有找到匹配的字符串，则返回 -1。

3. 代码实现

3.1 删除有效括号的代码实现

public String removeInvalidParentheses(String s) {
    Stack<Integer> stack = new Stack<>();
    char[] ch = s.toCharArray();
    for (int i = 0; i < ch.length; i++) {
        if (ch[i] == '(') {
            stack.push(i);
        } else if (ch[i] == ')') {
            if (!stack.isEmpty() && ch[stack.peek()] == '(') {
                stack.pop();
            } else {
                stack.push(i);
            }
        }
    }
    StringBuilder sb = new StringBuilder(s);
    while (!stack.empty()) {
        sb.deleteCharAt(stack.pop());
    }
    return sb.toString();
}

3.2 删除有序数组中的重复项并实现 strStr 的代码实现

public int removeDuplicates(int[] nums, String haystack, String needle) {
    int len = nums.length;
    if (len <= 1) {
        return len;
    }
    int i = 0, j = 1;
    while (j < len) {
        if (nums[i] == nums[j]) {
            j++;
        } else {
            nums[i + 1] = nums[j];
            i++;
            j++;
        }
    }
    // 实现 strStr 函数
    int n = haystack.length();
    int m = needle.length();
    if (m == 0) {
        return 0;
    }
    for (int k = 0; k <= n - m; k++) {
        if (haystack.substring(k, k + m).equals(needle)) {
            return k;
        }
    }
    return -1;
}

4. 示例说明

4.1 示例一：删除有效的括号

输入：s = "lee(t((c)o)de)"
输出："lee(t(c)o)de"

利用上述第 3.1 小节的代码实现可得：

String s = "lee(t((c)o)de)";
String res = removeInvalidParentheses(s);
System.out.println(res); // lee(t(c)o)de

4.2 示例二：删除有序数组中的重复项实现 strStr

输入：nums = [1, 2, 2, 3, 4, 4, 5], haystack = "hello,world", needle = "world"
输出：6

利用上述第 3.2 小节的代码实现可得：

int[] nums = {1, 2, 2, 3, 4, 4, 5};
String haystack = "hello,world";
String needle = "world";
int len = removeDuplicates(nums, haystack, needle);
System.out.println(len); // 7

以上就是本次完整攻略的全部内容，希望对您有所帮助。

阅读剩余 67%