做网站前期需要准备什么,盐城网站建设制作,如何自己开网站,上海建设工程学校网站树形问题 leetcode#xff1a;17 1 字符串的合法性 #xff08;是否包括1#xff0c;*和#号键#xff09; 2 空字符串 3 多个解的顺序 部分源代码如下#xff1a;
在这里插入代码片
#includecstringusing namespace std;private:const string letterMap[1…树形问题 leetcode17 1 字符串的合法性 是否包括1*和#号键 2 空字符串 3 多个解的顺序 部分源代码如下
在这里插入代码片
#includecstringusing namespace std;private:const string letterMap[10]{ ,//0,//1abc,//2def,ghi,jkl,mno,pqrs,tuv,wxyz}void findCombination(const string digits, int index, const string s){if(indexdigits.size()){//保存sreturn; }char c digits[index];assert(c0 c9 c!1);string lettersletterMap[c-0];//找到当前数字对应的阿斯玛值for(int i0; iletters.size();i)findCombinations(digits,index1,sletters[i]);return; }class Solution{public:vectorstring letterCombinations(string digits){}
}; int main(){return 0;
}8-23 递归调用的一个重要特征就是要返回–回溯回溯法是暴力解法的一个主要实现手段
leetcode 93 返回所有合法的ip地址 leetcode 131 返回所有拆分的可能所有拆分的子串都是回文串 回溯算法的应用排列问题 leetcode 46 返回所有元素排列的可能 递归形式如下 部分源代码如下
在这里插入代码片
vectorvectorstringsolveNQueens(int n){}
private:vectorvectorint res;vectorbool used;//来判断数组中第i个元素是否在p中 void generatePermutation(const vectorint nums, int index, vectorint p){if(indexnums.size()){res.push_back(p);return;}for(int i0;inums.size();i)if(!used[i]){//将nums[i]添加在p中p.push_back(nums[i]);used[i]true;generatePermutation(nums,index1,p);p.pop_back();used[i]false; //状态进行回溯 }}
public:vectorvectorint permute(vectorint nums){res.clear();if(nums.size()0)return res;usedvectorbool(nums.size(),false)vectorint p;generatePermutation(nums,0,p)return res; }
思考题leetcode 47 8-45 组合问题 leetcode 77
部分代码如下
在这里插入代码片
private:vectorvectorint res;void generateCombinations(int n, int k, int start, vectorint c){if(c.size()k){res.push_back(c);return;}for(int istart;in;i){c.push_back(i);genenrateCombinations(n,k,i1,c)c.pop_back();}return; vectorvectorint combine(int n, int k){res.clear();if(n0||k0||kn)return res;vectorintc;generateCombinations(n,k,1,c);return res;}
优化思想剪枝 leetcode 39 leetcode 40 leetcode 216 leetcode 78 leetcode 90 leetcode 401 8-67 二维平面上使用回溯法 leetcode79 方向为顺时针方向上右下左 部分代码如下
在这里插入代码片
private:int d[4][2]{{-1,0},{0,1},{1,0},{0,-1}} ;int m,n; vectorvectorbool visited;bool inArea(int x, int y){return x0 xm y0 yn;}//从board[startx][starty]开始寻找word【index...word.size()] bool searchWord(const vectorvectorchar board, const string word, int index,int startx,int starty){if(indexword.size()-1)return board[startx][starty]qord[index];if(board[startx][starty]word[index]){visited[startx][starty]true;//从startxstarty出发向四个方向寻找for(int i0; i4; i){int newxstartxd[i][0];int newystartyd[i][1];if(inArea(newx,newy) !visited[newx][newy] searchWord(board,word,index1,newx,newy)return true;}visited[startx][starty]false; }}bool exsit(vectorvectorchar board, string word){mboard.size();asser(m0);nboard[0].size();visitedvectorvectorbool(m,vectorbool(n,false));for(int i0;iboard.size(); i){for(int j0; jboard[i].size(); j)if(searchWord(board,word,0,i,j))return true;return false;}
}
floodfill算法一类经典问题 leetcode 200 number of islands 从初始点开始来一个深度优先遍历 部分代码如下
在这里插入代码片using namespace std;
class Solution{private:int d[4][2]{{-1,0},{0,1},{1,0},{0,-1}};int m,n; //m,n分别存储陆地的长宽度 vectorvectorbool visited;//标记已经被访问过的陆地 bool inArea(int x, int y){return x0 xm y0 yn;}void dfs(vectorvectorchar grid,int x,int y){visited[x][y]true;for(int i0; i4; i){int newxxd[i][0];int newyyd[i][1];if(inArea(newx,newy) !visited[newx][newy] grid[newx][newy]1)dfs(drid,newx,newy);}return;}public:int numIsLands(vectorvectorchar grid){mgrid.size();if(m0){return 0;}ngrid[0].size();visitedvectorvectorbool(m,vectorbool(n,false));int res0;for(int i0; im;i)for(int j0;jn;j)if(grid[i][j]1 !visited[i][j]){res;dfs(grid,i,j);}}
};int main(){return 0;
}leetcode 130 包围字符 leetcode417
回溯法是经典人工智能的基础 八皇后问题的解 先来看看四皇后问题 快速判断不合法的情况 可以发现每个对角线各个空格元素相加为定值 第二个对角线可以发现相减是一个定值 n皇后的优化问题 leetcode 52 求n皇后问题的所有解的个数
leetcode37 求解数独问题
