力扣hot100——第6天：32最长有效括号、33搜索旋转排序数组、34在排序数组中查找元素的第一个和最后一个位置

1.32最长有效括号

参考：力扣题目链接；题解1，题解2

1.1.题目

1.2.解答

这道题目官方的题解讲解的就非常清除了，现在摘录如下：

注意：注意dp数组的定义，dp[i]一定是以i为结尾的字符子串，也就是必须包含s[i]。

尤其注意第二种情况，也就是s[i-1] = ')'的时候，此时当前的s[i] = ')'无法跟s[i-1]匹配直接构成一个有效的字符子串，所以s[i]需要到前面去寻找，看是否有和它匹配的(。所以问题就变成，我该去前面的什么位置寻找呢？肯定不能随便选一个(的位置就和他匹配，因为这样会导致这个匹配的(和当前的s[i]之间的字符串不一定是合法的括号字符子串。

所以我们寻找之前的(的前提就是先让中间的字符串是一个合法的字符子串。也就是先去考虑s[i-1]的')'，因为他已经在上一步经过计算了，不管以它结尾的字符子串是不是一个合法的括号字符子串，都可以找到它对应的字符串的头字符。那么我们分两种情况假设：

• 假设以它结尾的字符和之前的某个头(构成了一个合法的括号字符子串，也就是上面题解中说的sub_s。所以这个sub_s对应的头字符串的位置就是i-1 - dp[i-1] + 1，其中i-1是s[i-1]的位置，dp[i-1]是以s[i-1]=')'为结尾的合法括号字符子串的长度，最后再+1是因为我们要找到s[i-1]对应的头字符(。比如长度是2的子串，当前尾巴-2之后位置是头字符串的前一个位置，所以我们要再+1移动到后面的一个位置，才是头字符(的位置。但是实际上最后我们想找的位置是s[i]对应的头位置，所以最后还需要再-1向前移动一位，因此最后和s[i]对应的头(的位置就是i-1 - dp[i-1]。
• 假设以它结尾的字符没有和之前的某个(构成一个合法的括号字符子串，也就是dp[i-1] = 0。那么和s[i]对应的头(的位置就是i-1 - dp[i-1] = i-1，很显然此时结果就是s[i-1] = ')'，不是(，所以不满足要求。但是不影响我们后面的计算。

在找到了s[i]对应的有可能合法的最前面的头字符之后，我们就要判断：

• 如果这个位置的字符是(，即s[i-1-dp[i-1]] = '('，那么当前的s[i]可以和这个字符构成有效括号字符子串，所以此时从i-1-dp[i-1]到i位置的子串就构成了一个有效的字符子串。但是此时注意：以i-1-dp[i-1]-1的子串也有可能仍旧可以构成有效的子串，所以最后以i结尾的有效子串的长度 = i-1-dp[i-1]到i的长度 + 以i-1-dp[i-1]-1为结尾的子串的长度。

• 如果这个位置的字符是)，那么前面一顿计算都白费了，此时s[i] = ')'不能和这个位置的)构成有效的子串，所以dp[i] = 0。

最后给出代码如下，其实并不是很难。关键是要注意，计算了当前结尾的子串的长度之后，不要忘了加上i-1-dp[i-1]-1结尾的子串的长度。

int longestValidParentheses(string s)
{
    // 定义dp数组，并且全部初始化成0
    vector<int> dp(s.size(), 0);  // string.length()和string.size()结果是一样的，不存在任何区别
    int result = 0;   // 记录最长的长度

    // 开始遍历，执行动态规划
    for(int i = 1; i < s.size(); i++)   // i = 0的位置不管是什么子串，肯定都不是有效括号，所以直接跳过即可
    {
        if(s[i] == ')')  // 只有)需要处理，因为以(结尾的子串一定不能构成有效的子串
        {
            // 前一个是(，则i和i-1直接可以构成一个()，所以有效子串长度就是i-2结尾的有效子串长度+2
            if(s[i-1] == '(')
            {
                if(i >= 2)  // 防止数组索引越界
                    dp[i] = dp[i-2] + 2;
                else
                    dp[i] = 2;
            }   
            // 前一个是)，则需要判断i-1结尾的有效子串
            else
            {
                // i-1结尾的子串长度是0，说明i-1结尾的就无法构成子串，由于i结尾的一定包含i-1，
                // 所以也无法构成子串。因此这里我们只需要考虑构成子串的情况，即dp[i-1] > 0
                if(dp[i-1] == 0)
                {
                    dp[i] = 0;   // 可省略，由初始化赋值
                }
                else
                {
                    // 当前)和前面的(构成匹配，同时要注意防止数组索引越界，比如())这种情况
                    if(i-1-dp[i-1] >= 0 && s[i-1-dp[i-1]] == '(')  
                    {
                        // i-1-dp[i-1]-1结尾的有效子串长度 + i-1结尾的有效子串长度 + 2
                        if(i-1-dp[i-1]-1 >= 0)   // 防止数组索引越界
                            dp[i] = dp[i-1-dp[i-1]-1] + dp[i-1] + 2;
                        else
                            dp[i] = dp[i-1] + 2;
                    }
                    else
                    {
                        dp[i] = 0;
                    }
                }
            }
        }
        else
        {
            dp[i] = 0;   // 可省略，由初始化赋值
        }

        result = max(result, dp[i]);
    }

    return result;
}
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

上述代码可以发现非常繁杂，主要是把dp[i] = 0的情况也写出来了， 实际上这个不用写用初始化赋值的0也可以。另一个就是在访问数组元素的时候需要时刻判断防止越界，这个问题可以通过增加判断和三元运算符来解决，因此简化代码如下：

int longestValidParentheses(string s)
{
    // 定义dp数组，并且全部初始化成0
    vector<int> dp(s.size(), 0);  // string.length()和string.size()结果是一样的，不存在任何区别
    int result = 0;   // 记录最长的长度

    for(int i = 1; i < s.size(); i++)
    {
        if(s[i] == ')')
        {
            if(s[i-1] == '(')
                dp[i] = (i >= 2 ? dp[i-2] : 0) + 2;
            else
            {
                if(i-1-dp[i-1] >= 0 && s[i-1-dp[i-1]] == '(')
                    dp[i] = (i-1-dp[i-1]-1 >= 0 ? dp[i-1-dp[i-1]-1] : 0) + dp[i-1] + 2;
            }
        }

        result = max(result, dp[i]);
    }

    return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

2.33搜索旋转排序数组

参考：力扣题目链接；题解1，题解2

2.1.题目

2.2.解答

题解1和题解2给出的解答都比较好，这里摘录题解1的讲解如下，其中说了一句二分的本质就是根据是否满足性质进行二分。

最后给出代码如下：

int search(vector<int> &nums, int target)
{
    if(nums.empty())
        return -1;
    if(nums.size() == 1)
        return (nums[0] == target ? 0 : -1);

    // [left, right] 二分数组，以mid划分数组为[left, mid-1], middle, [mid+1, right]
    // 三种情况：左升序、右无序；左升序、右升序；左无序、右升序
    int left = 0;
    int right = nums.size() - 1;
    while (left <= right)
    {
        int middle = left + (right - left)/2;
        if(nums[middle] == target)
            return middle;
        else
        {
            // 左升序，则应该用左区间去判断边界
            // 注意一定要<=，比如[3,1]中寻找1这种情况。主要就是数组长度为2时，由于/2是向下取整，
            // 所以结果是left = middle。
            if(nums[left] <= nums[middle])   
            {
                // 结果不在左区间中
                if(target < nums[left] || target > nums[middle])   
                    left = middle + 1;
                else    // 结果在左区间中
                    right = middle - 1;     
            }
            else   // 右升序
            {
                // 结果不在右区间中
                if(target < nums[middle] || target > nums[right])  
                    right = middle - 1;
                else
                    left = middle + 1;
            }
        }
    }

    return -1;  // 实际执行不到这里
}
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

注意：代码中的if(nums[left] <= nums[middle])必须是<=，而不能是<，这样的话有一个测试用例[3, 1]中寻找1会输出索引为-1，也就是没找到，这样是错误的。具体自己还没想明白为什么会这样。。。

3.34在排序数组中查找元素的第一个和最后一个位置【代码随想录已刷】

参考：力扣题目链接；自己的博客总结