难度中等655
实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须
原地
修改，只允许使用额外常数空间。
以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
1,2,3
→
1,3,2
3,2,1
→
1,2,3
1,1,5
→
1,5,1
void nextPermutation(vector<int>& nums) {
int i=0;
for (i=nums.size()-2; i >= 0; -- i) { // 从后往前找到第一个相邻升序对
if (nums[i] < nums[i+1]) break;
}
if (i == -1) reverse(nums.begin(),nums.end()); // 无相邻升序对，必定为非递减序列
else {
for (int j=nums.size()-1; j >= i+1; -- j) { // 从后往前[i+1,end)找第一个大于a[i+1]的值
if (nums[i] < nums[j]) {
swap(nums[i],nums[j]); // 交换二者
reverse(nums.begin()+i+1,nums.end()); // 反转[i+1,end)，变成升序
break;
}
}
}
}难度困难957
给定一个只包含
'('
和
')'
的字符串，找出最长的包含有效括号的子串的长度。
示例 1:
输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"
示例 2:
输入: ")()())" 输出: 4 解释: 最长有效括号子串为"()()"
解题思路一：常规
对于这种括号匹配问题，一般都是使用栈
我们先找到所有可以匹配的索引号，然后找出最长连续数列！
例如：s = )(()())，我们用栈可以找到，
位置 2 和位置 3 匹配，
位置 4 和位置 5 匹配，
位置 1 和位置 6 匹配，
这个数组为：2,3,4,5,1,6 这是通过栈找到的，我们按递增排序！1,2,3,4,5,6
找出该数组的最长连续数列的长度就是最长有效括号长度！
所以时间复杂度来自排序：O(nlogn)。
接下来我们思考，是否可以省略排序的过程,在弹栈时候进行操作呢?
直接看代码理解!所以时间复杂度为：O(n)。
解题思路二：dp 方法
我们用 dp[i] 表示以 i 结尾的最长有效括号；
当 s[i] 为 (,dp[i] 必然等于 0，因为不可能组成有效的括号；
那么 s[i] 为 )
2.1 当 s[i-1] 为 (，那么 dp[i] = dp[i-2] + 2；
2.2 当 s[i-1] 为 ) 并且 s[i-dp[i-1] - 1] 为 (，那么 dp[i] = dp[i-1] + 2 + dp[i-dp[i-1]-2]；
时间复杂度：O(n)
作者：powcai
链接：https://leetcode-cn.com/problems/longest-valid-parentheses/solution/zui-chang-you-xiao-gua-hao-by-powcai/
来源：力扣（LeetCode）
不怎么会，一会儿再说呜呜呜呜难度中等941
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组
[0,1,2,4,5,6,7]
可能变为
[4,5,6,7,0,1,2]
)。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回
-1
。
你可以假设数组中不存在重复的元素。
你的算法时间复杂度必须是
O
(log
n
) 级别。
示例 1:
输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4
示例 2:
输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1
一看复杂度就是二分查找啊
//题目要求用二分
class Solution {
public:
int search(vector<int>& nums, int target) {
int n=nums.size();
if(n==0) return -1;
if(n==1) return nums[0]==target?0:-1;
int l=0,r=n-1;
while(l<=r){
int mid=(l+r)/2;
if(nums[mid]==target) return mid;
if(nums[l]<=nums[mid]){
//说明l-mid是有序的
if(nums[l]<=target&&target<=nums[mid]) r=mid-1;
else l=mid+1;
}else{
//说明mid-r是有序的。
if(nums[mid]<=target&&target<=nums[r]) l=mid+1;
else r=mid-1;
}
}
return -1;
}
};难度中等584
给定一个按照升序排列的整数数组
nums
，和一个目标值
target
。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是
O
(log
n
) 级别。
如果数组中不存在目标值，返回
[-1, -1]
。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]
等待...难度简单678
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 1:
输入: [1,3,5,6], 5 输出: 2
示例 2:
输入: [1,3,5,6], 2 输出: 1
示例 3:
输入: [1,3,5,6], 7 输出: 4
示例 4:
输入: [1,3,5,6], 0 输出: 0
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int l=0,r=nums.size();
while(l<r){
int mid=(l+r)/2;
if(nums[mid]==target) return mid;
else if(nums[mid]>target) r=mid;
else l=mid+1;
}
return r;
}
};
// 0,3->1 nums[1]=3->l=0,r=1->nums[0]=1<2->l=0,r=1
// 0,4->2 nums[2]=5,l=0,r=2->nums[1]=3,l=0,r=1->nums[0]=1,l=0,r=1 此处修改为l=1难度中等416
判断一个 9×9 的数独是否有效。只需要
根据以下规则
，验证已经填入的数字是否有效即可。
-
数字
1-9
在每一行只能出现一次。 -
数字
1-9
在每一列只能出现一次。 -
数字
1-9
在每一个以粗实线分隔的
3x3
宫内只能出现一次。
上图是一个部分填充的有效的数独。
数独部分空格内已填入了数字，空白格用
'.'
表示。
示例 1:
输入: [ ["5","3",".",".","7",".",".",".","."], ["6",".",".","1","9","5",".",".","."], [".","9","8",".",".",".",".","6","."], ["8",".",".",".","6",".",".",".","3"], ["4",".",".","8",".","3",".",".","1"], ["7",".",".",".","2",".",".",".","6"], [".","6",".",".",".",".","2","8","."], [".",".",".","4","1","9",".",".","5"], [".",".",".",".","8",".",".","7","9"] ] 输出: true
示例 2:
输入:
[
["8","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]
]
输出: false
解释: 除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。
但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。
说明:
- 一个有效的数独（部分已被填充）不一定是可解的。
- 只需要根据以上规则，验证已经填入的数字是否有效即可。
-
给定数独序列只包含数字
1-9
和字符
'.'
。 -
给定数独永远是
9x9
形式的。
待续...难度简单545
给定一个正整数
n
（1 ≤
n
≤ 30），输出外观数列的第
n
项。
注意：整数序列中的每一项将表示为一个字符串。
「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。前五项如下：
1. 1 2. 11 3. 21 4. 1211 5. 111221
第一项是数字 1
描述前一项，这个数是
1
即 “一个 1 ”，记作
11
描述前一项，这个数是
11
即 “两个 1 ” ，记作
21
描述前一项，这个数是
21
即 “一个 2 一个 1 ” ，记作
1211
描述前一项，这个数是
1211
即 “一个 1 一个 2 两个 1 ” ，记作
111221
class Solution {
public:
string countAndSay(int n) {
string x="1";
string next=x;n--;
while(n--){
int cnt=1;
x=next+"#";next="";
for(int i=1;i<x.size();i++){
if(x[i]!=x[i-1]){
next+=to_string(cnt)+x[i-1];cnt=1;
}else
cnt++;
}
}
return next;
}
};难度中等934
给定一个
无重复元素
的数组
candidates
和一个目标数
target
，找出
candidates
中所有可以使数字和为
target
的组合。
candidates
中的数字可以无限制重复被选取。
说明：
-
所有数字（包括
target
）都是正整数。 - 解集不能包含重复的组合。
示例 1：
输入：candidates =[2,3,6,7],target =7, 所求解集为： [ [7], [2,2,3] ]
示例 2：
输入：candidates = [2,3,5], target = 8,
所求解集为：
[
[2,2,2,2],
[2,3,3],
[3,5]
]
class Solution {
public:
vector<int> tmp;
void get(int index,int sum,int target,vector<int>& candidates,vector<vector<int>>& ans){
if(sum==target){
ans.push_back(tmp);
return;
}
if(index>candidates.size()-1||sum>target) return;
if(sum+candidates[index]<=target){
tmp.push_back(candidates[index]);
get(index,sum+candidates[index],target,candidates,ans);
tmp.pop_back();
}
get(index+1,sum,target,candidates,ans);
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> ans;
get(0,0,target,candidates,ans);
return ans;
}
};背包+字典
思路分析：
不考虑输出结果要求，初看题目和零钱兑换问题很相似。
但是“零钱兑换”问题输出为凑成总金额所需的最少硬币个数。此问题需输出所有可行解，可考虑用字典dp[n]存储和为n(candidate<=n<=target)时的每一个组合，代码如下。
vector<vector<int>> combinationSum(vector<int>& candidates, int target){
vector<vector<int>> dp[target+1];vector<int> zero;
dp[0].push_back(zero);
for(int num:candidates){
for(int i=num;i<=target;i++){
if(dp[i-num].size()>0){
for(auto tmp:dp[i-num]){
tmp.push_back(num);
dp[i].push_back(tmp);
}
}
}
}
return dp[target];
}
作者：gsp_leetcode
链接：https://leetcode-cn.com/problems/combination-sum/solution/bei-bao-wen-ti-zi-dian-by-gsp_leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。难度中等401
给定一个数组
candidates
和一个目标数
target
，找出
candidates
中所有可以使数字和为
target
的组合。
candidates
中的每个数字在每个组合中只能使用一次。
说明：
- 所有数字（包括目标数）都是正整数。
- 解集不能包含重复的组合。
示例 1:
输入: candidates =[10,1,2,7,6,1,5], target =8, 所求解集为: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ]
示例 2:
输入: candidates = [2,5,2,1,2], target = 5, 所求解集为: [ [1,2,2], [5] ]
解释语句: if cur > begin and candidates[cur-1] == candidates[cur] 是如何避免重复的。
这个避免重复当思想是在是太重要了。
这个方法最重要的作用是，可以让同一层级，不出现相同的元素。即
1
/ \
2 2 这种情况不会发生 但是却允许了不同层级之间的重复即：
/ \
5 5
例2
1
/
2 这种情况确是允许的
/
2
为何会有这种神奇的效果呢？
首先 cur-1 == cur 是用于判定当前元素是否和之前元素相同的语句。这个语句就能砍掉例1。
可是问题来了，如果把所有当前与之前一个元素相同的都砍掉，那么例二的情况也会消失。
因为当第二个2出现的时候，他就和前一个2相同了。
那么如何保留例2呢？
那么就用cur > begin 来避免这种情况，你发现例1中的两个2是处在同一个层级上的，
例2的两个2是处在不同层级上的。
在一个for循环中，所有被遍历到的数都是属于一个层级的。我们要让一个层级中，
必须出现且只出现一个2，那么就放过第一个出现重复的2，但不放过后面出现的2。
第一个出现的2的特点就是 cur == begin. 第二个出现的2 特点是cur > begin.// author:rmokerone
#include <iostream>
#include <vector>
using namespace std;
class Solution {
private:
vector<int> candidates;
vector<vector<int>> res;
vector<int> path;
public:
void DFS(int start, int target) {
if (target == 0) {
res.push_back(path);
return;
}
for (int i = start; i < candidates.size() && target - candidates[i] >= 0; i++) {
if (i > start && candidates[i] == candidates[i - 1])
continue;
path.push_back(candidates[i]);
// 元素不可重复利用，使用下一个即i+1
DFS(i + 1, target - candidates[i]);
path.pop_back();
}
}
vector<vector<int>> combinationSum2(vector<int> &candidates, int target) {
sort(candidates.begin(), candidates.end());
this->candidates = candidates;
DFS(0, target);
return res;
}
};
作者：liweiwei1419
链接：https://leetcode-cn.com/problems/combination-sum-ii/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-m-3/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。