南昌企业网站设计公司,建设网站要多少页面,做旅游游客产品的网站,深圳做网站的好公司有哪些CONTENTS LeetCode 31. 下一个排列#xff08;中等#xff09;LeetCode 32. 最长有效括号#xff08;困难#xff09;LeetCode 33. 搜索旋转排序数组#xff08;中等#xff09;LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置#xff08;中等#xff09;Lee… CONTENTS LeetCode 31. 下一个排列中等LeetCode 32. 最长有效括号困难LeetCode 33. 搜索旋转排序数组中等LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置中等LeetCode 35. 搜索插入位置简单 LeetCode 31. 下一个排列中等
【题目描述】
整数数组的一个排列就是将其所有成员以序列或线性顺序排列。 例如arr [1,2,3]以下这些都可以视作 arr 的排列[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1]。 整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地如果数组的所有排列根据其字典顺序从小到大排列在一个容器中那么数组的下一个排列就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列那么这个数组必须重排为字典序最小的排列即其元素按升序排列。
例如arr [1,2,3] 的下一个排列是 [1,3,2]。类似地arr [2,3,1] 的下一个排列是 [3,1,2]。而 arr [3,2,1] 的下一个排列是 [1,2,3]因为 [3,2,1] 不存在一个字典序更大的排列。
给你一个整数数组 nums找出 nums 的下一个排列。 必须原地修改只允许使用额外常数空间。
【示例1】
输入nums [1,2,3]
输出[1,3,2]【示例2】
输入nums [3,2,1]
输出[1,2,3]【示例3】
输入nums [1,1,5]
输出[1,5,1]【提示】 1 ≤ n u m s . l e n g t h ≤ 100 1\le nums.length\le 100 1≤nums.length≤100 0 ≤ n u m s [ i ] ≤ 100 0\le nums[i]\le 100 0≤nums[i]≤100
【分析】 产生下一个排列可以使用 next_permutation 函数实现但是我们肯定要讨论手动实现的方式。
我们从后往前找到第一个升序的位置 k k k即 nums[k] nums[k 1]然后从 k 1 k1 k1 开始往后找到大于 nums[k] 的最小的数的位置 t t t即 nums[t] nums[k] nums[t 1] nums[k]然后交换 nums[k] 和 nums[t]最后将从 k 1 k1 k1 开始往后的序列做一个逆序即可。 【代码】
【next_permutation 函数实现】
class Solution {
public:void nextPermutation(vectorint nums) {next_permutation(nums.begin(), nums.end());}
};【手动实现】
class Solution {
public:void nextPermutation(vectorint nums) {int k nums.size() - 2;while (k 0 nums[k] nums[k 1]) k--;if (k 0) reverse(nums.begin(), nums.end()); // 已经是最后一个排列了else{int t k 1;while (t nums.size() nums[t] nums[k]) t;swap(nums[k], nums[t - 1]); // nums[t-1]为大于nums[k]最小的数reverse(nums.begin() k 1, nums.end());}}
};LeetCode 32. 最长有效括号困难
【题目描述】
给你一个只包含 ( 和 ) 的字符串找出最长有效格式正确且连续括号子串的长度。
【示例1】
输入s (()
输出2
解释最长有效括号子串是 ()【示例2】
输入s )()())
输出4
解释最长有效括号子串是 ()()【示例3】
输入s
输出0【提示】 0 ≤ s . l e n g t h ≤ 3 ∗ 1 0 4 0\le s.length\le 3 * 10^4 0≤s.length≤3∗104 s[i] 为 ( 或 )
【分析】 如果忘记了合法括号序列的特性可以回顾一下第22题。本题的思路很难想具有跳跃性。
我们先考虑如何将这个字符串分段从前往后找到第一个满足 ) 数量大于 ( 数量的地方那么我们就当做这边是一个分段点任何合法括号序列都不会横跨这个分段点然后我们从这个点开始同样的继续重新往后找下一个分段点。
之后我们需要找合法括号序列的时候只需要在每一个分段内部找即可每一段中除了最后一个即分段点之外是满足任意前缀的 ( 数量大于等于 ) 数量因此我们可以遍历每一段枚举合法子串的右端点位置求出对应的最靠左的左端点。
我们可以用栈实现这个过程栈中存储每个左括号的下标例如(()(()))算法流程如下
遇到第一个 ) 时下标为 2栈中内容为[0, 1]将栈顶出栈进行匹配后栈顶为 0那么当前的最长合法子串长度为 2 − 0 2 2-02 2−02遇到第二个 ) 时下标为 5栈中内容为[0, 3, 4]将栈顶出栈进行匹配后栈顶为 3那么当前的最长合法子串长度为 5 − 3 2 5-32 5−32遇到第三个 ) 时下标为 6栈中内容为[0, 3]将栈顶出栈进行匹配后栈顶为 0那么当前的最长合法子串长度为 6 − 0 6 6-06 6−06遇到第四个 ) 时下标为 7栈中内容为[0]将栈顶出栈进行匹配后栈为空那么当前的最长合法子串长度为 7 − 0 1 8 7-018 7−018 【代码】
class Solution {
public:int longestValidParentheses(string s) {stackint stk;int res 0;for (int i 0, start 0; i s.size(); i) // start表示每一段的起始点{if (s[i] () stk.push(i); // 左括号直接入栈else if (stk.size()) // 右括号先检查栈里是否有元素没有则说明不合法{stk.pop();if (stk.size()) res max(res, i - stk.top()); // 还没匹配到最左端的左括号else res max(res, i - start 1); // 已经匹配到最左端了}else start i 1; // 右括号已经多于左括号为这一段的分界点更新start从下一段的起点开始}return res;}
};LeetCode 33. 搜索旋转排序数组中等
【题目描述】
整数数组 nums 按升序排列数组中的值互不相同。 在传递给函数之前nums 在预先未知的某个下标 k0 k nums.length上进行了旋转使数组变为 [nums[k], nums[k1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]下标从 0 开始计数。例如[0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2]。 给你旋转后的数组 nums 和一个整数 target如果 nums 中存在这个目标值 target则返回它的下标否则返回 -1。 你必须设计一个时间复杂度为 O ( l o g n ) O(log n) O(logn) 的算法解决此问题。
【示例1】
输入nums [4,5,6,7,0,1,2], target 0
输出4【示例2】
输入nums [4,5,6,7,0,1,2], target 3
输出-1【示例3】
输入nums [1], target 0
输出-1【提示】 1 ≤ n u m s . l e n g t h ≤ 5000 1\le nums.length\le 5000 1≤nums.length≤5000 − 1 0 4 ≤ n u m s [ i ] ≤ 1 0 4 -10^4\le nums[i]\le 10^4 −104≤nums[i]≤104 − 1 0 4 ≤ t a r g e t ≤ 1 0 4 -10^4\le target\le 10^4 −104≤target≤104 nums 中的每个值都独一无二 题目数据保证 nums 在预先未知的某个下标上进行了旋转
【分析】 在一段有序数组里找某个值可以使用二分但是本题将数组旋转后相当于有两个独立的升序数组。因此我们第一步需要先将这两段找出来。
第一段中的所有数都大于 nums[0]而另一段区间中的所有数都小于 nums[0]因此可以利用这个特性二分找出这两段的分界点即大于 nums[0] 的最后一个数。
找到两段的分解点后我们通过 target 与 nums[0] 的大小关系即可知道它是在哪一段中由于两段都是升序的因此我们再通过二分在其中找出 target 即可。 【代码】
class Solution {
public:int search(vectorint nums, int target) {int l 0, r nums.size() - 1;while (l r){int mid l r 1 1;if (nums[mid] nums[0]) l mid;else r mid - 1;}if (target nums[0]) l 0; // 在第一段区间中搜索右端点即为二分出来的边界点relse l r 1, r nums.size() - 1; // 在第二段区间中搜索左右端点都要改while (l r){int mid l r 1;if (nums[mid] target) r mid;else l mid 1;}if (nums[r] ! target) return -1; // 不存在targetelse return r;}
};LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置中等
【题目描述】
给你一个按照非递减顺序排列的整数数组 nums和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 target返回 [-1, -1]。 你必须设计并实现时间复杂度为 O ( l o g n ) O(log n) O(logn) 的算法解决此问题。
【示例1】
输入nums [5,7,7,8,8,10], target 8
输出[3,4]【示例2】
输入nums [5,7,7,8,8,10], target 6
输出[-1,-1]【示例3】
输入nums [], target 0
输出[-1,-1]【提示】 0 ≤ n u m s . l e n g t h ≤ 1 0 5 0\le nums.length\le 10^5 0≤nums.length≤105 − 1 0 9 ≤ n u m s [ i ] ≤ 1 0 9 -10^9\le nums[i]\le 10^9 −109≤nums[i]≤109 − 1 0 9 ≤ t a r g e t ≤ 1 0 9 -10^9\le target\le 10^9 −109≤target≤109 nums 是一个非递减数组
【分析】 同理也是二分查找分别找出大于等于 target 最小的下标以及小于等于 target 最大的下标。 【代码】
class Solution {
public:vectorint searchRange(vectorint nums, int target) {if (nums.empty()) return { -1, -1 }; // 注意需要特判int l 0, r nums.size() - 1, L;while (l r){int mid l r 1;if (nums[mid] target) r mid;else l mid 1;}if (nums[r] ! target) return { -1, -1 };L l, r nums.size() - 1;while (l r){int mid l r 1 1;if (nums[mid] target) l mid;else r mid - 1;}return { L, r };}
};LeetCode 35. 搜索插入位置简单
【题目描述】
给定一个排序数组和一个目标值在数组中找到目标值并返回其索引。如果目标值不存在于数组中返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O ( l o g n ) O(log n) O(logn) 的算法。
【示例1】
输入: nums [1,3,5,6], target 5
输出: 2【示例2】
输入: nums [1,3,5,6], target 2
输出: 1【示例3】
输入: nums [1,3,5,6], target 7
输出: 4【提示】 1 ≤ n u m s . l e n g t h ≤ 1 0 4 1\le nums.length\le 10^4 1≤nums.length≤104 − 1 0 4 ≤ n u m s [ i ] ≤ 1 0 4 -10^4\le nums[i]\le 10^4 −104≤nums[i]≤104 − 1 0 4 ≤ t a r g e t ≤ 1 0 4 -10^4\le target\le 10^4 −104≤target≤104 nums 为无重复元素的升序排列数组
【分析】 简单二分不用过多解释了。 【代码】
class Solution {
public:int searchInsert(vectorint nums, int target) {int l 0, r nums.size(); // 可能会插入到末尾因此r的最大值需要比末尾元素大1while (l r){int mid l r 1;if (nums[mid] target) r mid;else l mid 1;}return r;}
};