网站备案部门,建设厅焊工证什么样子,asp网站怎么安装,上海市工程建设协会网站暴力--二进制 采用与#xff1a;力扣---子集---回溯#xff08;子集型回溯#xff09;---递归-CSDN博客 中二进制求解一样的思路#xff0c;即遍历0~-1#xff08;从二进制去考虑#xff09;#xff0c;如果这个数的第 i 位为0#xff0c;则括号的第 i 位为‘#xff…
暴力--二进制 采用与力扣---子集---回溯子集型回溯---递归-CSDN博客 中二进制求解一样的思路即遍历0~-1从二进制去考虑如果这个数的第 i 位为0则括号的第 i 位为‘ ’为1代表‘ ’。依次求出所有括号的可能性总共种可能再对每种情况进行判别。 代码
C
class Solution {
public:bool check(string temp,int n){stackchar s;int num2*n;for(int i0;inum;i){//先判断是否配对if(temp[i](){s.push(temp[i]);}else{if(s.empty()){return false;}else{s.pop();}}}if(s.empty()){return true;}else{return false;}}vectorstring generateParenthesis(int n) {vectorstring res;int temp2*n;for(int i0;i(1temp);i){ //0代表(1代表)string s;for(int j0;jtemp;j){if(i (1j)){s);}else{s(;}}//coutsendl;if(check(s,n)){res.push_back(s);}}return res;}
};
Python
class Solution:def generateParenthesis(self, n: int) - List[str]:def check(temp:str,n:int) - bool:sdeque()num2*nfor i in range(num):if temp[i](:s.append(temp[i])else:if len(s)0:return Falseelse:s.pop()if len(s)0:return Trueelse:return Falseres[]temp2*ntemp_1tempfor i in range(temp_):sfor j in range(temp):if i (1j):s)else:s(if check(s,n):res.append(s)return res
注意len(s)用于查看队列/栈中元素的个数string在Python中的写法为strPython中栈和队列都可以用deque来实现。dequefrom collections import deque
暴力--回溯dfs 采用与力扣---子集---回溯子集型回溯---递归-CSDN博客 中递归法一样的思路分为三个步骤第一步骤为特殊情况的判别即个位置已经填满对其进行判别。第二步骤为第 i 为设置为‘(’进行递归调用注意保护现场。第三步骤为第 i 为设置为‘ ’进行递归调用注意保护现场。 代码
C
class Solution {
public:bool check(string temp,int n){stackchar s;int num2*n;for(int i0;inum;i){//先判断是否配对if(temp[i](){s.push(temp[i]);}else{if(s.empty()){return false;}else{s.pop();}}}if(s.empty()){return true;}else{return false;}}void dfs(int i,vectorstring res,string temp,int n){if(i2*n){if(check(temp,n)){res.push_back(temp);}return;}//将(加入temptemp(;dfs(i1,res,temp,n);temp.pop_back();//将)加入temptemp);dfs(i1,res,temp,n);temp.pop_back();}vectorstring generateParenthesis(int n) {vectorstring res;string temp;dfs(0,res,temp,n);return res;}
};
Python class Solution:def generateParenthesis(self, n: int) - List[str]:def check(temp:str,n:int) - bool:sdeque()num2*nfor i in range(num):if temp[i](:s.append(temp[i])else:if len(s)0:return Falseelse:s.pop()if len(s)0:return Trueelse:return Falsedef dfs(i:int,res:List[str],temp:str,n:int):if i2*n:if check(temp,n):res.append(temp)returntemp(dfs(i1,res,temp,n)temptemp[0:len(temp)-1]temp)dfs(i1,res,temp,n)temptemp[0:len(temp)-1]res[]tempdfs(0,res,temp,n)return res
对第二种写法的优化 我们需要认识到一个点遍历到第 i 位即要确定第 i 位是左括号还是右括号时前 i-1 位的左括号数量一定大于右括号的数量第 i 位才可能是‘ ’。所以我们可以在这部分进行改进 //将)加入temp
temp);
dfs(i1,res,temp,n);
temp.pop_back(); 同时对特殊情况的判断也可以变为对左括号数量和对右括号数量的判断。 代码
C
class Solution {
public://左括号数右括号数才能加右括号void dfs(int i,vectorstring res,string temp,int n,int left,int right){if(i2*n){if(leftright){res.push_back(temp);}return;}//将(加入temptemp(;dfs(i1,res,temp,n,left1,right);temp.pop_back();//将)加入tempif(leftright){temp);dfs(i1,res,temp,n,left,right1);temp.pop_back();}}vectorstring generateParenthesis(int n) {vectorstring res;string temp;dfs(0,res,temp,n,0,0);return res;}
};
Python
class Solution:def generateParenthesis(self, n: int) - List[str]:def dfs(i:int,res:List[str],temp:str,n:int,left:int,right:int):if i2*n:if leftright:res.append(temp)returntemp(dfs(i1,res,temp,n,left1,right)temptemp[0:len(temp)-1]if leftright:temp)dfs(i1,res,temp,n,left,right1)temptemp[0:len(temp)-1]res[]tempdfs(0,res,temp,n,0,0)return res
