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

embedded/2024/11/13 15:44:48/

目录

  • 括号匹配问题 (动态规划)
    • 题目
    • 题目分析
    • 代码
  • 子数组最接近某个数 (动态规划)
    • 题目
    • 题目分析
    • 代码
  • 求出数组中缺失的最小正整数 (贪心)
    • 题目
    • 题目分析
    • 代码
  • 恢复二叉搜索树 (二叉树的性质)
    • 题目
    • 题目分析
    • 代码

括号匹配问题 (动态规划)

题目

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

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

题目分析

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

当然这道题也不例外

我们设置一个数组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);}
};

http://www.ppmy.cn/embedded/136937.html

相关文章

【Python】爬虫通过验证码

1、将验证码下载至本地 # 获取验证码界面html url http://www.example.com/a.html resp requests.get(url) soup BeautifulSoup(resp.content.decode(UTF-8), html.parser)#找到验证码图片标签&#xff0c;获取其地址 src soup.select_one(div.captcha-row img)[src]# 验证…

Qt:QPdfDocument渲染PDF文件时的信息丢失问题

背景 Qt自带了QPdfDocument可以用来打开并渲染PDF文件&#xff0c;同时Qt也提供了qtpdf multipage example&#xff0c;可以浏览多页PDF文件&#xff0c;如下图&#xff1a; 问题 但在使用过程中发现&#xff0c;对于某些PDF文件&#xff0c;QPdfDocument在渲染时会丢失部分信…

Golang | Leetcode Golang题解之第542题01矩阵

题目&#xff1a; 题解&#xff1a; type point struct{x, y int }var dirs []point{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}func updateMatrix(mat [][]int) [][]int {var m, n len(mat), len(mat[0])var res make([][]int, m)var visited make([][]bool, m)var queue []poin…

Vivado+Vscode联合打造verilog环境

一、Vivado下载安装 详细参考我另一篇文章&#xff1a; Vivado2022.2下载安装_fpga vivado下载-CSDN博客https://blog.csdn.net/weixin_61081689/article/details/143460790?spm1001.2014.3001.5501 二、Vscode下载安装 详细参考我另一篇文章&#xff1a; VscodeAnacond…

Spring Boot基础教学:Spring Boot 简介

第一部分&#xff1a;Spring Boot 简介 1.1 什么是Spring Boot&#xff1f; Spring框架的简介Spring Boot与Spring框架的关系Spring Boot的优势 1.2 Spring Boot的核心特性 自动配置起步依赖内嵌服务器Spring Boot CLIActuator 1.3 Spring Boot的应用场景 微服务REST API…

(C++11)委托构造函数--C++

文章目录 委托构造函数为什么要有委托构造函数代码解释注意事项 委托构造函数 C11 引入了委托构造的概念&#xff0c;这使得构造函数可以在同一个类中一个构造函数调用另一个构造函 数&#xff0c;从而达到简化代码的目的。 就是委托其他构造函数帮忙构造。 为什么要有委托构…

nacos集群AP架构源码解析

1 心跳检测 核心类&#xff1a;ClientBeatCheckTask 核心方法&#xff1a;run public void run() {try {//1 集群状态下心跳处理if (!getDistroMapper().responsible(service.getName())) {return;}if (!getSwitchDomain().isHealthCheckEnabled()) {return;}List<Instance…

C++ 中的智能指针(Smart Pointer)

C 中的智能指针&#xff08;Smart Pointer&#xff09;是用于管理动态内存分配的工具&#xff0c;它们能够自动管理资源的生命周期&#xff0c;避免内存泄漏。智能指针是 C11 标准引入的&#xff0c;通过模板类封装原生指针&#xff0c;实现资源的自动释放。主要的智能指针包括…