【C++ 算法进阶】算法提升十四

括号匹配问题 （动态规划）

题目

现在给你一串括号字符串 请问这串括号字符串中最长的有效括号子串是多少

有效括号子串： 每个左右括号都有与其匹配的位置

题目分析

一般来说我们看到 “子串” “子数组” 等字眼 我们就要考虑到以末尾位置讨论的动态规划

当然这道题也不例外

我们设置一个数组dp dp[i]的含义是 以i位置结尾的时候有效括号的数目是多少

当然 每次遍历到左括号的时候dp的答案肯定是0

所以说我们每次只在匹配到右括号的时候计算

每次找到有效的右括号则dp值加上2

当然 我们还要考虑到的是 在当前位置括号匹配上了 前面位置是否还有有效括号 如果有我们加上

代码

int process(vector<char> s1) {
	int ans = 0;
	int pre = 0;
	vector<int> dp(s1.size(), 0);

	for (int i = 0; i < s1.size(); i++) {
		int count = 0;
		if (s1[i] == ')') {
			count = 2 + dp[i - 1];
			if (i - dp[i-1] - 2 >= 0) {
				count += dp[i - dp[i-1] - 2];
			}
			dp[i] = count;
			ans = max(ans, count);
		}
	}


	return ans;
}

子数组最接近某个数 （动态规划）

题目

给定一个数组 要你求出该子数组中 小于等于某个数 K 的最大值

题目分析

这道题其实只要我们稍微转换一下就非常简单

我们可以先求出以当前位置结尾的前缀和 之后在set中找出之前前缀和中大于等于 总和 - K 的元素

之后相减 就能得出最终答案

代码

int process(vector<int> v1 , int k) {
	int ans = 0;
	set<int> set1;
	set1.insert(0);
	vector<int> dp(v1.size(), 0);
	dp[0] = v1[0];
	for (int i = 1; i < v1.size(); i++) {
		dp[i] = dp[i - 1] + v1[i];

		if (set1.lower_bound(dp[i] - k) == set1.end()) {
			ans = max(ans, dp[i]);
		}
	}

	return ans;
}

求出数组中缺失的最小正整数 （贪心）

题目

给定你一个数组 这个数组中的数可能有正数负数和零 现在要求你求出在这个数组中 确实的最小正整数

比如说这个数组中是 23456 … 那么缺失的最小正整数就是1

时间复杂度为N 空间复杂度为1

题目分析

本题为字节面试原题 难度为hard

由于时间和空间复杂度的限制 我们不能使用排序 或者借助额外数组等手段

这也是这道题的主要难点

其实遇到这种不能借助额外空间的题目 我们首先要想到的就是建立有效区和无效区

那么我们希望有效区是什么样子呢？

最好是 i 位置 填写 i + 1 的数值 比如说0位置填1 1位置填2 …

这样子我们最后只需要根据有效区的大小就能确定最后需要的数字是多少了

之后所有的数字都丢进无效区

需要注意的是 我们这里的期望数字是会有一个最大结果的 这个最大结果就是这个数组中所有数都是正整数并且是 0 1 2 … N 的格式

而恰巧 我们可以用右数组的边界来表示期望数字的最大结果 每次右数组往左扩的时候这个结果都减小

代码

int process(vector<int> v1) {
	int L = 0;
	int R = v1.size();
	while (L != R) 
	{
		if (v1[L] == L + 1)
		{
			L++;
		}
		else if (v1[L] <= L || v1[L] > R || v1[L] == v1[v1[L] - 1]) {
			swap(v1[L], v1[--R]);
		}
		else
		{
			swap(v1[L], v1[v1[L] - 1]);
		}
	}

	return L + 1;
}

恢复二叉搜索树 （二叉树的性质）

题目

本题为LC原题目 题目如下

题目分析

本题其实就是利用了二叉搜索树的性质 就是中序遍历的话 遍历出来的结果是有序的

如果说其中有逆序对 那么这个逆序对中的数字就是我们要修改的结果了

1. 如果只有一个逆序对 那么这个逆序对的两个数字就是我们要修改的结果
2. 如果有两个逆序对 那么第一个逆序对的第一个数字和第二个逆序对的第二个数字就是我们要修改的结果

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void inorder(TreeNode* root, vector<int>& nums) {
        if (root == nullptr) {
            return;
        }
        inorder(root->left, nums);
        nums.push_back(root->val);
        inorder(root->right, nums);
    }

    pair<int,int> findTwoSwapped(vector<int>& nums) {
        int n = nums.size();
        int index1 = -1, index2 = -1;
        for (int i = 0; i < n - 1; ++i) {
            if (nums[i + 1] < nums[i]) {
                index2 = i + 1;
                if (index1 == -1) {
                    index1 = i;
                } else {
                    break;
                }
            }
        }
        int x = nums[index1], y = nums[index2];
        return {x, y};
    }
    
    void recover(TreeNode* r, int count, int x, int y) {
        if (r != nullptr) {
            if (r->val == x || r->val == y) {
                r->val = r->val == x ? y : x;
                if (--count == 0) {
                    return;
                }
            }
            recover(r->left, count, x, y);
            recover(r->right, count, x, y);
        }
    }

    void recoverTree(TreeNode* root) {
        vector<int> nums;
        inorder(root, nums);
        pair<int,int> swapped= findTwoSwapped(nums);
        recover(root, 2, swapped.first, swapped.second);
    }
};