31.下一个排列
class Solution {
public:
void nextPermutation(vector<int>& nums) {
/*
in:
k: 驼峰,
t: 驼峰右边第一个比 nums[ k - 1 ] 小的数字
breakthrough:
需要动最右侧第一个驼峰的左边的数字
*/
int k = nums.size() - 1;
while(k > 0 && nums[k - 1] >= nums[k]) k --; // k-1正好是0
if(k <= 0){ // 没有找到
reverse(nums.begin(),nums.end());
}else{
// 找出 t
int t = k;
while(t < nums.size() && nums[t] > nums[ k - 1]) t ++;
swap(nums[t - 1],nums[k - 1]);
reverse(nums.begin() + k,nums.end());
}
}
};
32.最长有效括号
class Solution {
public:
int longestValidParentheses(string s) {
/*
breakthrough:
看视频,看讲解[doge]
*/
stack<int> stk;
int res = 0 ;
for(int i = 0,start = -1; i < s.size(); i ++){
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);
}
}else{
// 更新起点
start = i;
}
}
}
return res;
}
};
33. 搜索旋转排序数组
class Solution {
public:
int search(vector<int>& nums, int target) {
if (nums.empty()) return -1;
// 求驼峰
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;
}
// 判断 target 属于左半段还是右半段
if (target >= nums[0]) l = 0;
else 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;
}
// 找出来了就输出每天找出来,就输出-1
if (nums[r] == target) return r;
return -1;
}
};
34. 在排序数组中查找元素的第一个和最后一个位置
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
if(nums.empty()) return vector<int> {-1,-1};
vector<int>res;
int l = 0,r = nums.size() - 1;
while(l < r){
int mid = l + r >> 1;
if(nums[mid] >= target) r = mid;
else l = mid + 1;
}
// 查看有没有找到,如果找到就进行下一步,没有找到直接输出 -1 -1
if(nums[l] == target){
res.push_back(l);
l = 0,r = nums.size() - 1;
while(l < r){
int mid = l + r + 1 >> 1;
if(nums[mid] <= target) l = mid;
else r = mid - 1;
}
res.push_back(l);
}else return vector<int> {-1,-1};
return res;
}
};
35. 搜索插入位置
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int n = nums.size();
if (target > nums[n - 1]) return n;
int l = 0, r = n - 1;
while (l < r) {
int mid = l + r >> 1;
if (nums[mid] >= target) r = mid;
else l = mid + 1;
}
return r;
}
};