讲道理的豹子说这不是bug - 个人主页动态 - 牛客网

发布(102) 评论刷题

2023-09-13 17:46

门头沟学院驱动开发

题解 | #合并两个有序的数组#

方法：双指针从数组A、B的最后一个元素开始遍历，比较大小根据规则填充到A数组中。时间复杂度：o(n)空间复杂度：o(1) class Solution { public: void merge(int A[], int m, int B[], int n) { int i = m - 1; int j = n - 1; int idx = m + n - 1; while (i >= 0 && j >= 0) { if (A[i] > B[j]) ...

刷题题解（c++）

0 点赞评论收藏

分享

2023-09-12 21:02

已编辑

门头沟学院驱动开发

题解 | #大数加法#

时间复杂度：o(n)空间复杂度：o(1) class Solution { public: string solve(string s, string t) { // 特殊情况处理 if (s.empty()) return t; if (t.empty()) return s; // 让s为较长的字符串 if (s.length() < t.length()) swap(s, t); // 进位 ...

刷题题解（c++）

0 点赞评论收藏

分享

2023-09-12 20:08

门头沟学院驱动开发

题解 | #验证IP地址#

方法：分割字符串比较1、判断是否为IPv4首先将字符串分割开，遇到‘ . ’字符就进行分割；对分割后的字符串进行判断，需要满足以下条件：（1）分割后的字符串个数为4个；（2）字符串的每个字符都为数字；（3）字符串的数字大小处于0-255之间；（4）字符串的长度大于1时，首个字符不得为0。1、判断是否为IPv6首先将字符串分割开，遇到‘ ：’字符就进行分割；对分割后的字符串进行判断，需要满足以下条件：（1）分割后的字符串个数为8个；（2）字符串的每个字符都为数字或为a-f，A-F的字母；（3）字符串的长度不得超过4且大于0。时间复杂度：o(n)空间复杂度：o(1) class Solution ...

刷题题解（c++）

0 点赞评论收藏

分享

2023-09-11 17:36

已编辑

门头沟学院驱动开发

题解 | #最长公共前缀#

方法：遍历此题较容易，不做讲解时间复杂度：o(n * len)空间复杂度：o(1) class Solution { public: string longestCommonPrefix(vector<string>& strs) { string res; // 特殊情况处理 if (strs.size() == 0) return res; for (int i = 0; i < strs[0].length(); i++) { for (...

刷题题解（c++）

0 点赞评论收藏

分享

2023-09-11 17:13

门头沟学院驱动开发

题解 | #字符串变形#

方法：双逆转具体步骤：（1）先将字符串的小写和大写字母进行反转；（2）将字符串进行翻转；（3）再将单词进行翻转。时间复杂度：o(n)空间复杂度：o(n) class Solution { public: string trans(string s, int n) { string res; // 转换大小写 for (int i = 0; i < n; i++) { if (s[i] >= 'a' && s[i] <= 'z') res += s...

刷题题解（c++）

0 点赞评论收藏

分享

2023-09-08 17:42

门头沟学院驱动开发

题解 | #买卖股票的最好时机(三)#

方法：动态规划创建一个二维数组dp：dp[i][0]表示到第i天为止没有买过股票的最大收益dp[i][1]表示到第i天为止买过一次股票还没有卖出的最大收益dp[i][2]表示到第i天为止买过一次也卖出过一次股票的最大收益dp[i][3]表示到第i天为止买过两次只卖出过一次股票的最大收益dp[i][4]表示到第i天为止买过两次同时也买出过两次股票的最大收益可以得到如下的状态转移方程：dp[i][0] = dp[i - 1][0]; dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);dp[i][2] = max(dp[i - 1][2],...

刷题题解（c++）

0 点赞评论收藏

分享

2023-09-08 16:28

已编辑

门头沟学院驱动开发

题解 | #买卖股票的最好时机(二)#

方法一：动态规划对于第i天可能有两种情况，持有股票和未持有股票。因此创建一个二维数组dp，用于存储第i天持有股票和未持有股票的最大利润。可以得出以下的状态转移方程（1）如果第i天未持有股票： 可能是因为此前从未买过股票或者之前已经卖出，这时dp[i][0] = dp[i - 1][0]； 可能是第i天才卖出，这是dp[i] = dp[i - 1][1] + prices[i - 1]； 所以dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])。（2）如果第i天持有股票： 可能是因为之...

刷题题解（c++）

0 点赞评论收藏

分享

2023-09-08 16:22

已编辑

门头沟学院驱动开发

题解 | #买卖股票的最好时机(一)#

方法一：贪心遍历数组，创建两个int型变量分别用于维护最大的利润和更小的买入价格。时间复杂度：o(n)空间复杂度：o(1) class Solution { public: int maxProfit(vector<int>& prices) { // 特殊情况处理 if (prices.empty()) return 0; // 记录最大利润 int res = 0; // 记录更小的买入价格 int min = prices[0]; ...

刷题题解（c++）

0 点赞评论收藏

分享

2023-09-03 18:57

已编辑

门头沟学院驱动开发

题解 | #打家劫舍(二)#

方法：动态规划创建一个大小为nums.size() + 1的数组dp，dp[i]表示以nums[i - 1]结尾的数组的最大金额，对于dp[i]有两种情况，可以选择偷或者不偷：选择偷：dp[i] = dp[i - 2] + nums[i - 1];选择不偷：dp[i] = dp[i - 1]。选取两个中的最大值即为当前的最大金额。将问题分解为偷第一家和不偷第一家两种情况讨论：偷第一家：dp[1] = nums[0]，函数的输出为dp[nums.size() - 1]不偷第一家：dp[1] = 0，函数的输出为dp[nums.size()]时间复杂度：o(n)空间复杂度：o(n) class S...

刷题题解（c++）

0 点赞评论收藏

分享

2023-09-03 17:20

门头沟学院驱动开发

题解 | #打家劫舍(一)#

方法：动态规划创建一个大小为nums.size() + 1的数组dp，dp[i]表示以nums[i - 1]结尾的数组的最大金额，对于dp[i]有两种情况，可以选择偷或者不偷：选择偷：dp[i] = dp[i - 2] + nums[i - 1];选择不偷：dp[i] = dp[i - 1]。选取两个中的最大值即为当前的最大金额。dp的最后一个元素即为最后的输出时间复杂度：o(n)空间复杂度：o(n) class Solution { public: int rob(vector<int>& nums) { vector<int> dp(...

刷题题解（c++）

0 点赞评论收藏

分享

2023-09-03 16:31

门头沟学院驱动开发

题解 | #最长的括号子串#

方法一：栈遍历字符串，使用栈来存储左括号对应的下标1、对于遇到的每个‘(’ ，将它的下标放入栈中2、对于遇到的每个 ‘)’ ，先弹出栈顶元素表示匹配了当前右括号： （1）、如果栈为空，说明当前的右括号为没有被匹配的右括号，将其下标放入栈中来更新我们之前提到的「最后一个没有被匹配的右括号的下标」 （2）、如果栈不为空，当前右括号的下标减去栈顶元素即为「以该右括号为结尾的最长有效括号的长度」3、从前往后遍历字符串并更新答案即可。需要注意的是，如果一开始栈为空，第一个字符为左括号的时候我们会将其放入栈中，这样就不满足提及的「最后一个没有被匹配的右括号的下标」，为了保持统一，我们在一开始的...

刷题题解（c++）

0 点赞评论收藏

分享

2023-09-02 16:12

门头沟学院驱动开发

题解 | #正则表达式匹配#

方法一：动态规划创建一个bool类型数组dp，大小为（str.length() + 1）* （pattern.length() + 1），用来存储str到pattern是否匹配；dp[i][j] 表示str[i - 1]和pattern[j - 1]是否匹配，可以得到如下的状态转移方程：如果str[i - 1] == pattern[j - 1]或者pattern[j - 1] =='.'(可替代任何字符，等同于相等)，dp[i][j] = dp[i - 1][j - 1]；如果不相等时，只要当pattern[j - 1]为‘*’时，才有可能匹配，可以分三种情况讨论：（1）重复0次：dp[i]...

刷题题解（c++）

0 点赞评论收藏

分享

2023-08-29 11:54

门头沟学院驱动开发

题解 | #编辑距离(一)#

方法：动态规划1、创建数组dp来存储，str1[i]到str[j]所需的最少操作数，可以得到如下的状态转移方程：如果str1[i - 1]和str2[j - 1]相等时，dp[i][j] = dp[i - 1][j - 1]；如果str1[i - 1]和str2[j - 1]不相等时，可能进行三种操作，取三种操作的最小值：替换：dp[i - 1][j -1] + 1删除：dp[i - 1][j] + 1，如果要满足删除可以从str1到str2，那么str1的前一个元素一定要满足转换到str2。所以是dp[i - 1][j] + 1。插入：dp[i][j - 1] + 1，如果要满足插入可以从...

刷题题解（c++）

0 点赞评论收藏

分享

2023-08-28 16:12

已编辑

门头沟学院驱动开发

题解 | #数字字符串转化成IP地址#

方法一：递归+回溯题设可知，IP地址是由四段数字组成的数字序列，中间使用“.”连接起来，每段数字处于[0, 255]之间。所以我们可以将问题分解为：得到上一段数字后，从余下的字符串求剩余几段的数字。1、从字符串的起点开始，得到第一段数字，由题设可知，每一段的数字都不会超过三位数，所以遍历前三个数字；2、下一段数字从上一段数字的后一位开始向后遍历，递归得到所有的可能性。通过对每段数字进行有效性判断，四段数字都满足有效性的是有效的IP地址，存入数组中。时间复杂度：o(3n)空间复杂度：o(n) class Solution { private: // 存储所有可能的IP地址 v...

刷题题解（c++）

0 点赞评论收藏

分享

2023-08-27 21:21

门头沟学院驱动开发

题解 | #最长回文子串#

方法：循环遍历1、遍历数组，以数组每个元素为中心寻找最长的回文子串长度；2、遍历完数组就能得到最长的回文子串。时间复杂度：o(n2)空间复杂度：o(1) class Solution { public: int getLongestPalindrome(string A) { // 特殊情况处理 if (A.length() == 1) return 1; int max_len = 1; for (int i = 0; i < A.length() - 1; i++) { ...

刷题题解（c++）

0 点赞评论收藏

分享

关注他的用户也关注了：

牛客网
牛客企业服务