20题：有效的括号

题目：

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。
    示例 1：
    输入：s = “()”
    输出：true
    示例 2：
    输入：s = “()[]{}”
    输出：true
    示例 3：
    输入：s = “(]”
    输出：false
    示例 4：
    输入：s = “([])”
    输出：true
    示例 5：
    输入：s = “([)]”
    输出：false
    提示：
  • 1 <= s.length <= 104
  • s 仅由括号 '()[]{}' 组成

分析：

该题目只有3中括号类型：() [] {}
如果一个括号是正确且相邻的，那就把它删去，只判断其它的就可以了，
例如：()[]{}([{])
其实相当于判断([{])，其它的都没用。
这种类型一定是错的，问题是怎么使用编程表达出来。
只要循环删除相邻的括号即可，如果有括号不相邻，无法删去，那就一定是错误的，比如:([{}])(])({)
第一次删除得到([])(])({)
第二次删除得到()(])({)
第三次删除得到(])({)
然后就删不下去了，只要里面的无法删除，就说明里面的括号有不相邻的，外面的即使可以配对，整个也是错误的，所以整个题目只需要从头开始循环，然后一点点删除相邻的括号，直到删不动了为止，最后如果是空的，就是正确的，如果还有没有删掉的，就是错误的。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <string>
using namespace std;
class Solution {
public:
	bool isValid(string s) {
		while (true) {
			int len = s.size();
			for (int i = 0; i < s.size(); i++) {
				if ((s[i] == '(' && s[i + 1] == ')') ||
					(s[i] == '[' && s[i + 1] == ']') ||
					(s[i] == '{' && s[i + 1] == '}')) {
					s.erase(i, 2);//删除后需要重新开始
					break;
				}
			}
			if (len == s.size()) {
				break;//说明没有可以替换的括号了，结束循环
			}
		}
		return s.empty();
	}
};

它的时间复杂度是$O(n^{2})$
另一种是栈的方法，推荐的方法也是栈，它的时间复杂度是$O(n)$，但是目前还没有学到栈，所以先只把代码放到这里。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <string>
#include <stack>
#include <unordered_map>
class Solution {
public:
    bool isValid(string s) {
        stack<char> st;  // 创建一个栈，用于存储遇到的左括号

        // 建立右括号到左括号的映射表
        unordered_map<char, char> pairs = {
            {')', '('},  // 右括号')'对应左括号'('
            {']', '['},  // 右括号']'对应左括号'['
            {'}', '{'}   // 右括号'}'对应左括号'{'
        };

        // 遍历字符串中的每一个字符
        for (char c : s) {
            if (c == '(' || c == '[' || c == '{') {
                // 如果是左括号，压入栈中
                st.push(c);
            }
            else {
                // 如果是右括号
                // 情况1：栈为空，说明前面没有左括号与之匹配
                // 情况2：栈顶的左括号与当前右括号不匹配
                if (st.empty() || st.top() != pairs[c]) {
                    return false;
                }
                // 匹配成功，弹出栈顶的左括号
                st.pop();
            }
        }

        // 遍历完字符串后
        // 栈为空：所有括号都正确匹配
        // 栈不为空：有多余的左括号没有匹配
        return st.empty();
    }
};

26题：删除有序数组中的重复项

通过这道题目学习了双指针法，27题也同样适用。

题目：

给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
考虑 nums 的唯一元素的数量为 k。去重后，返回唯一元素的数量 k。
nums 的前 k 个元素应包含 排序后 的唯一数字。下标 k - 1 之后的剩余元素可以忽略。

判题标准:
系统会用下面的代码来测试你的题解:

1
2
3
4
5
6
7
8
9
int[] nums = [...]; // 输入数组
int[] expectedNums = [...]; // 长度正确的期望答案

int k = removeDuplicates(nums); // 调用

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[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 。不需要考虑数组中超出新长度后面的元素。

提示：

  • 1 <= nums.length <= 3 * 104
  • -100 <= nums[i] <= 100
  • nums 已按 非递减 顺序排列。

分析：

利用数组是有序的这个特点，直接使用双指针法，i和j都用来作下标，题目让我原地改，就是直接改这个数组，不能再重新开一个数组（重新开也可以用双指针）。
两个指针的分工是这样的：i用来复制元素，j用来探路。

开始时候i和j都是1，指向第2个元素，然后判断nums[i-1]和num[j]是否相等，如果相等，说明就重复了，只把j++，继续“探路”，i则留在原地，等待找到不同的元素后改变i所指位置的值，然后i++。

下面给出代码

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
    int removeDuplicates(std::vector<int>& nums) {
        //由于数组是有序的，所以使用双指针法
        //令j为快指针，i为慢指针
        //首先排除数组为空的情况
        if (nums.empty()) {
            return 0;
        }
        //双指针法
        int i = 1;
        int j = 1;//因为如果数组不为空，那么至少有一个不同的元素，所以从第二个元素开始覆盖即可，即下标为1的元素
        for (j = 1; j < nums.size(); j++) {
            if (nums[i - 1] != nums[j]) {
                nums[i] = nums[j];//不相等则说明找到了新的元素，进行覆盖
                i++;
            }
        }
        return i;//结束后j溢出，i所在的位置即不同元素个数
    }
};

27题：移除元素

这道题和上一道基本一样，只是多了一种优化的双指针

题目：

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

  • 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
  • 返回 k。

用户评测：
评测机将使用以下代码测试您的解决方案：

1
2
3
4
5
6
7
8
9
10
11
12
13

int[] nums = [...]; // 输入数组
int val = ...; // 要移除的值
int[] expectedNums = [...]; // 长度正确的预期答案。
                            // 它以不等于 val 的值排序。

int k = removeElement(nums, val); // 调用你的实现

assert k == expectedNums.length;
sort(nums, 0, k); // 排序 nums 的前 k 个元素
for (int i = 0; i < actualLength; i++) {
    assert nums[i] == expectedNums[i];
}

如果所有的断言都通过，你的解决方案将会 通过。

示例 1：
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2,_,_]
解释：你的函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

示例 2：
输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3,_,_,_]
解释：你的函数应该返回 k = 5，并且 nums 中的前五个元素为 0,0,1,3,4。
注意这五个元素可以任意顺序返回。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

分析：

这道题依然是双指针，分为两种：
1.普通双指针
i和j开始都指向0，如果某个地方j指向的值为val，那么i不动，j向后移一位，用于探路，直到找到一个不等于val的值，i改变当前位置的值并向后移一位。
这种做法最糟糕的情况最多遍历数组两边，i和j各一遍，例如一个没有val的数组。
2.优化双指针
换一种思路，j确实是用来探路的，但是完全可以从右侧开始探路，i从左向右，j从右向左，分别取名为left和right。
这种情况，只要让left向后移动即可，直到有值等于val，让right所指的值进行覆盖，但是right指的也可能是val，但是没有关系，我们先进行覆盖，让right向左移动，同时判断left所指的值是否还等于val，如果还等于，那就left--，下次循环还在这个位置。当然，如果不使用for循环，而是使用while(left<right)的话，就不用考虑left--了，因为left不会自增

能使用这种思路的关键是题目不要求返回的值还是原来的顺序。
这种方式最多遍历一次数组（实际上也肯定得遍历一次）

除了双指针法，还有暴力解法，虽然26题学习了双指针法，但是刚写这道题的时候还是没想到
下面大概说一下暴力法的思路：
暴力法：
遍历数组，找到某个位置的值等于val后，直接删除，就是把后面的都往前移一位，但是为了排除最后一位是val的情况，首先要判断最后一位是不是val，然后赋值为val+1，以免复制了好几个val
下面给出代码。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
    //双指针法
    int guanfang1_removeElement(vector<int>& nums, int val) {
        int n = nums.size();
        int left = 0;
        for (int right = 0; right < n; right++) {
            if (nums[right] != val) {
                nums[left] = nums[right];
                left++;
            }
        }
        return left;
    }
    //双指针优化
    int guanfang2_removeElement(vector<int>& nums, int val) {
        int left = 0, right = nums.size();
        while (left < right) {
            if (nums[left] == val) {
                nums[left] = nums[right - 1];
                right--;
            }
            else {
                left++;
            }
        }
        return left;
    }

    int removeElement(vector<int>& nums, int val) {
        //我的暴力解法
        //思路：只要找到和val相同的元素就把它删掉，后面的元素都往前移动一个位置，同时用count记录删除了多少个元素，返回num,size()-count
        //首先排除nums为空的情况
        if (nums.empty()) {
            return 0;
        }
        int i = 0;
        int count = 0;
        //为了避免最后一个元素删不掉的情况，先判断该元素是否=val
        if (nums[nums.size() - 1] == val) {
            count++;
            nums[nums.size() - 1] = val+1;//改为不等于val的值
        }
        //下面可以正常进行判断
        for (i = 0; i < nums.size(); i++) {
            if (nums[i] == val) {
                count++;
                for (int j = i; j < nums.size()-1; j++) {
                    nums[j] = nums[j + 1];
                }
                i--;//解决连续出现val的情况
            }
        }
        return nums.size() - count;
    }
};

28题：找出字符串中第一个匹配项的下标

这个题目比较简单，我很快就写出来了，这种情况很少见，这个题目就不过多分析了。
普通的解法时间复杂度是$O(n \times m)$，空间复杂度是$O(1)$
不过也有非常复杂的解法，KMP算法，时间复杂度是$O(n + m)$，空间复杂度是$O(n)$，KMP不作解释，因为我没看懂

题目：

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回  -1 。

示例 1：
输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。

示例 2：
输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在"leetcode" 中出现，所以返回 -1 。

提示：

  • 1 <= haystack.length, needle.length <= 104
  • haystack 和 needle 仅由小写英文字符组成

分析：

只返回第一个下标即可，使用暴力法。
先排除一些特殊情况，比如haystack.size()=0，needle.length.size()=0或者haystack.size()<needle.length.size()，如果出现以上情况，直接返回-1

这个方法关键就是怎么尽力少匹配一些，首先就是先找到needle的第一个字符，和haystack中的元素依次匹配，(当然可以使用substr(size_t pos = 0, size_t len = npos)依次进行匹配，但是我没学过，所以也没用)
如果第一个字符匹配，再进行下面的匹配，一旦出现不符的情况，立刻break，如果循环进行结束，也就是匹配成功，就返回下标。
其它的我唯一能想到的能减少匹配次数的方法，是不完全循环haystack，而是循环到haystack.size()-needle.size()，往后字符数就不够了，也就不用循环了。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <iostream>
#include <string>
#include <vector>
using namespace std;

//我的暴力匹配
class Solution {
public:
    int strStr(string haystack, string needle) {
        //思路：如果要匹配，那就得一个个字符作比较，且都必须相等，最后要返回的是相等的地方的第一个下标

        //先排除特殊情况
        //首先排除haystack为空的情况，而且因为要从haystack中找needle，所以haystack的长度一定>=needle
        if (haystack.empty() || needle.empty() || haystack.size() < needle.size()) {
            return -1;
        }
        //朴素的思想，先找相同的第一个下标，找到了再往后循环，时间复杂度应该是O(n*m)或者说O(n^2)
        int i = 0;
        int j = 0;
        for (i = 0; i <= haystack.size()-needle.size(); i++) {  //循环到haystack.size()-needle.size()就停，因为后面地方不够了，肯定不匹配
            if (haystack[i] == needle[0]) {
                //第一个字母相同，可以向后循环
                for (j = 1; j < needle.size(); j++) {
                    if (haystack[i + j] != needle[j]) {
                        break;
                    }
                }//循环如果正常进行，说明找到了
                if (j == needle.size()) {
                    return i;
                }
            }
        }
        return -1;
    }
};

//KMP算法，看着就很难，先放着
class Solution1 {
public:
    int strStr(string haystack, string needle) {
        int n = haystack.size(), m = needle.size();
        if (m == 0) {
            return 0;
        }
        vector<int> pi(m);
        for (int i = 1, j = 0; i < m; i++) {
            while (j > 0 && needle[i] != needle[j]) {
                j = pi[j - 1];
            }
            if (needle[i] == needle[j]) {
                j++;
            }
            pi[i] = j;
        }
        for (int i = 0, j = 0; i < n; i++) {
            while (j > 0 && haystack[i] != needle[j]) {
                j = pi[j - 1];
            }
            if (haystack[i] == needle[j]) {
                j++;
            }
            if (j == m) {
                return i - m + 1;
            }
        }
        return -1;
    }
};