数字 `n` 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 **有效的** 括号组合。
**输入：**n = 3
**输出：**["((()))","(()())","(())()","()(())","()()()"]
- 遇到类似生成所有情况的,一般都是直接使用递归(栈和DFS类似)
- 遇到括号匹配的,一般都是用栈
class Solution {
public:
vector<string> generateParenthesis(int n) {
dfs("", n, n);
return res;
}
private:
vector<string> res;
void dfs(const string& str, int left, int right) {
if (left < 0 || left > right) // 出现类似 ()) )) 这种格式都是错误的不用再继续了
return;
if (left == 0 && right == 0) {
res.push_back(str);
return;
}
dfs(str + '(', left - 1, right);
dfs(str + ')', left, right - 1);
}
};
给定一个不含重复数字的数组 `nums` ，返回其 _所有可能的全排列_ 。你可以 **按任意顺序** 返回答案。
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> result;
vector<int> now;
travelArray(result,now,nums);
return result;
}
void travelArray(vector<vector<int>>& result,vector<int>& now,vector<int>& left)
{
int flag=1000;
for(unsigned i=0;i<left.size();i++)
{
if(left[i]!=100)
{
flag=left[i];
now.push_back(left[i]);
left[i]=100;
travelArray(result,now,left);
left[i]=flag;
now.erase(now.end()-1);
}
}
if(flag==1000)
result.push_back(now);
}
};
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
[百度百科](https://baike.baidu.com/item/%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88/8918834?fr=aladdin)中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（**一个节点也可以是它自己的祖先**）。”
在 x 轴上有一个一维的花园。花园长度为 `n`，从点 `0` 开始，到点 `n` 结束。
花园里总共有 `n + 1` 个水龙头，分别位于 `[0, 1, ..., n]` 。
给你一个整数 `n` 和一个长度为 `n + 1` 的整数数组 `ranges` ，其中 `ranges[i]` （下标从 0 开始）表示：如果打开点 `i` 处的水龙头，可以灌溉的区域为 `[i - ranges[i], i + ranges[i]]` 。
请你返回可以灌溉整个花园的 **最少水龙头数目** 。如果花园始终存在无法灌溉到的地方，请你返回 **-1** 。
- 贪心:同一个x,选择最远的y,在这个比y小的所有x1,选取最远的y1,迭代进行
- 动态规划:从前向后
class Solution {
public:
int minTaps(int n, vector<int>& ranges) {
int mindiff=0;
unordered_map<int, int> hashmap;
for (int i=0;i<ranges.size();i++) {
mindiff=min(i-ranges[i],mindiff);
if (hashmap.find(i-ranges[i])!=hashmap.end()) {
hashmap[i-ranges[i]]=max(hashmap[i-ranges[i]],2*ranges[i]);
}else {
hashmap[i-ranges[i]]=2*ranges[i];
}
}
mindiff=-mindiff;
vector<int> dp(ranges.size()+mindiff,INT32_MAX);
for (int i = 0; i < mindiff; i++) {
dp[i]=0;
}
for (int i = 0; i < dp.size(); i++) {
auto self=dp[i];
if (self==INT32_MAX) {
return -1;
}
int val=0;
if (hashmap.find(i-mindiff)!=hashmap.end()) {
val=hashmap[i-mindiff];
}
for (int j = 1; j <= val&&i+j<dp.size(); j++) {
dp[i+j]=min(dp[i+j],self+1);
}
}
return dp[dp.size()-1];
}
}
给一个数n，一个数组A，返回由A中元素组成的小于n的最大数
如n=23121，A={2,4,9| 返回22999
n=23121 A={9} 返回9999
n=23333 A={2,3} 返回23332
n=2222 A={2} 返回222
n=2 A={2} 无解
- 使用贪心加dfs的方法,实际上因为数据量太小,每个位置都尽可能选择最大的一个数字,最后弄不了就回到上一层选择上一层小一点的数字