目录实现 Trie (前缀树)全排列子集字符串相乘电话号码的字母组合组合总和括号生成单词搜索分割回文串N 皇后搜索插入位置在排序数组中查找元素的第一个和最后一个位置搜索二维矩阵搜索旋转排序数组寻找旋转排序数组中的最小值实现 Trie (前缀树)解法1set使用unordered_set容器进行储存遍历解法2多叉树根据题目构建出一个26叉树用数组来储存每个节点class Trie // { // public: // unordered_setstring hash; // Trie() // { // } // void insert(string word) // { // hash.insert(word); // } // bool search(string word) // { // return hash.contains(word); // } // bool startsWith(string prefix) // { // for (auto e : hash) // { // int pos 0, i 0; // while (pos e.size() i prefix.size() e[pos] prefix[i]) // { // pos; // i; // } // if (pos e.size() i prefix.size()) // return true; // } // return false; // } // }; class Trie { public: typedef struct Node { struct Node *NodeList[26] {nullptr}; bool end false; } Node; Trie() { _root new Node; } void insert(string word) { Node *cur _root; for (int i 0; i word.size(); i) { int pos word[i] - a; if (cur-NodeList[pos] nullptr) { cur-NodeList[pos] new Node; } cur cur-NodeList[pos]; } cur-end true; // 最后一个字符的下一个节点进行标记 } // 0-找不到 1-精确匹配 2-前缀匹配 int find(const string word) { Node *cur _root; for (int i 0; i word.size(); i) { int pos word[i] - a; if (cur-NodeList[pos] nullptr) return 0; cur cur-NodeList[pos]; } return cur-end true ? 1 : 2; } bool search(string word) { return find(word) 1; } bool startsWith(string prefix) { return find(prefix) ! 0; } private: Node *_root; };全排列解法dfs回溯模板题class Solution { public: vectorvectorint ret; vectorint path; bool vis[7] {false}; // 当前位置进行标记 void dfs(vectorint nums) { if (path.size() nums.size()) { ret.push_back(path); return; } for (int i 0; i nums.size(); i) { if (!vis[i]) { vis[i] true; path.push_back(nums[i]); dfs(nums); path.pop_back(); vis[i] false; } } } vectorvectorint permute(vectorint nums) { dfs(nums); return ret; } };子集解法1dfs从当前位置往后枚举每个数每次递归枚举之前收集结果解法2位运算class Solution { public: vector vectorint ret; vectorint path; void dfs(vectorint nums,int pos) { if(path.size() nums.size()) return; ret.emplace_back(path); for(int i pos;i nums.size();i) { path.push_back(nums[i]); dfs(nums,i 1); path.pop_back(); } } vectorvectorint subsets(vectorint nums) { dfs(nums,0); return ret; } };字符串相乘解法1先把两个字符串翻转遍历其中一个数的每一位于另一个数相乘如果是十位百位要先补0每次得到的结果进行字符串相加...最终结果的string要进行翻转才能得到最终的结果解法2先把两个字符串翻转创建一个数组用来保存每一位与每一位计算的结果之后处理数组时往后进位使用string保存每一位的结果最后string要进行翻转才能得到最终结果class Solution { public: string multiply(string num1, string num2) { int m num1.size(), n num2.size(); vectorint tmp(m n - 1, 0); for (int i 0; i m; i) { for (int j 0; j n; j) { tmp[i j] (num1[i] - 0) * (num2[j] - 0); } } string ret; // tmp的数据写成string类型 int flag 0; for (int i m n - 2; i 0; i--) { int sum tmp[i] flag; ret sum % 10 0; flag sum / 10; cout ret endl; } if (flag ! 0) ret flag 0; reverse(ret.begin(), ret.end()); return ret; } };电话号码的字母组合解法dfs先用一个数组对储存数字映射的字符串下标访问;画决策树设计dfsclass Solution { public: string arr[10] {0, 0, abc, def, ghi, jkl, mno, pqrs, tuv, wxyz}; vectorstring ret; string path; void dfs(string s, int pos) { if (pos s.size()) { ret.push_back(path); return; } for (auto e : arr[s[pos] - 0]) { path e; dfs(s, pos 1); path.pop_back(); } } vectorstring letterCombinations(string digits) { if (digits.size() 0) return ret; dfs(digits, 0); return ret; } };组合总和解法dfs画出决策树每次从当前位置进行往后枚举递归如果当前位置越界或者值大于等于target就要判断是否是答案后进行收集class Solution { public: vectorvectorint ret; vectorint path; int sum 0; void dfs(vectorint candidates, int target, int pos) { if (sum target || pos candidates.size()) { if (sum target) ret.push_back(path); return; } for (int i pos; i candidates.size(); i) { path.push_back(candidates[i]); sum candidates[i]; dfs(candidates, target, i); sum - candidates[i]; path.pop_back(); } } vectorvectorint combinationSum(vectorint candidates, int target) { dfs(candidates, target, 0); return ret; } };括号生成思路1选不不选递归时有两种选要么选择左括号要么选择右括号前提是 当前收集到的左括号 右括号的数量思路2枚举枚举右括号的数量之后添加一个左括号递归时传入两个参数第一个参数递归后填写的位置第二个参数是递归后枚举符合范围的右括号的数量class Solution { public: vectorstring ret; string path; int left 0, right 0, sum; void dfs() { // left个数不符合要求或者左括号数量小于右括号的数量都是不符合题意 if (left sum / 2 || left right) return; if (left right sum) { ret.push_back(path); return; } // 选左 left; path (; dfs(); left--; path.pop_back(); // 选右 right; path ); dfs(); right--; path.pop_back(); } vectorstring generateParenthesis(int n) { sum 2 * n; dfs(); return ret; } }; class Solution { public: vectorstring ret; vectorint left_index; vectorstring generateParenthesis(int n) { auto dfs [](this auto dfs, int pos, int CurrentRightNum) { if (left_index.size() n) { string s(2 * n, )); for (auto i : left_index) s[i] (; ret.push_back(s); return; } // 枚举右括号个数 for (int num 0; num CurrentRightNum; num) { // 根据右括号个数确定放置左括号的坐标 left_index.push_back(pos num); dfs(pos num 1, CurrentRightNum - num 1); // 下次递归的位置与右括号的个数 left_index.pop_back(); } }; dfs(0, 0); return ret; } };单词搜索解法dfs枚举每个位置如果与第一个单词的字符相同就继续上下左右四个方向进行递归class Solution { public: string path; int dx[4] {0, 0, 1, -1}; int dy[4] {1, -1, 0, 0}; bool vis[7][7] {false}; bool exist(vectorvectorchar board, string word) { int n board.size(), m board[0].size(); auto dfs [](this auto dfs, int i, int j, int pos) { if (pos word.size()) return true; for (int k 0; k 4; k) { int x dx[k] i, y dy[k] j; if (x 0 x n y 0 y m !vis[x][y] board[x][y] word[pos]) { vis[x][y] true; if (dfs(x, y, pos 1)) return true; vis[x][y] false; } } return false; }; for (int i 0; i board.size(); i) { for (int j 0; j board[0].size(); j) { if (board[i][j] word[0]) { vis[i][j] true; if (dfs(i, j, 1)) return true; vis[i][j] false; } } } return false; } };分割回文串解法dfs分与不分如果当前位置要进行分割就先判断分割后的字符串是否是回文不是自己向上返回是就从下一个位置递归来分割字符串如果不分就继续找下一个分割位置最后一个位置也就是字符串结尾无论如何都是要进行分割的边界// 分割字符串 class Solution { public: vectorvectorstring ret; vectorstring path; bool IsTrue(string s, int begin, int end) { while (begin end) { if (s[begin] ! s[end--]) return false; } return true; } vectorvectorstring partition(string s) { int n s.size(); // begin:字符串的起始位置 pos:当前位置的前面需不需要分割 auto dfs [](this auto dfs, int begin, int pos) { if (pos n) { ret.push_back(path); return; } if (pos n - 1)// n n-1一定要分 { // 不分 dfs(begin, pos 1); } // 分 if (IsTrue(s, begin, pos)) { path.push_back(s.substr(begin, pos - begin 1)); dfs(pos 1, pos 1); path.pop_back(); } }; dfs(0, 0); return ret; } };N 皇后解法dfs难点怎么处理正斜线与副斜线有无皇后在皇后位置中同一个坐标行列相加后相同证明在同一正斜线在皇后位置中同一个坐标行列相减后相同证明在同一副斜线多个几个空间不然数组会越界class Solution { public: bool row[10], col[10], vis1[20], vis2[20]; vectorstring path; vectorvectorstring ret; vectorvectorstring solveNQueens(int n) { string s; s.resize(n, .); path.resize(n, s); auto dfs [](this auto dfs, int rows) { if (rows n) { ret.push_back(path); return; } for (int j 0; j n; j) { if (path[rows][j] . !row[rows] !col[j] !vis1[rows j] !vis2[rows - j n]) { row[rows] col[j] vis1[rows j] vis2[rows - j n] true; path[rows][j] Q; dfs(rows 1); path[rows][j] .; row[rows] col[j] vis1[rows j] vis2[rows - j n] false; } } }; dfs(0); return ret; } };搜索插入位置解法二分使用朴素二分查找模版class Solution { public: int searchInsert(vectorint nums, int target) { int left 0, right nums.size() - 1; while (left right) { if (nums[left] target) left; else if (nums[right] target) right--; else break; } return left; } };在排序数组中查找元素的第一个和最后一个位置解法二分使用非朴素二分的两个模板进行求解class Solution { public: vectorint searchRange(vectorint nums, int target) { int n nums.size(); if (n 0) return {-1, -1}; // 边界判断 int left 0, right n - 1; // 求左端点 while (left right) { int mid (left right) / 2; if (nums[mid] target) left mid 1; else right mid; } if (nums[left] ! target) return {-1, -1}; // 没找到target直接返回 int tmp left; // 求右端点 left 0, right n - 1; while (left right) { int mid (left right 1) / 2; if (nums[mid] target) right mid - 1; else left mid; } return {tmp, left}; } };搜索二维矩阵解法1二分将二维矩阵转成递增的数组后进行二分解法2排查从第一行的最后一个数开始排查坐标在合法的范围内如果当前值小于目标值则说明当前行都不符合往下一行查询如果当前值大于目标值则说明值可能在当前行往左走等于就直接返回true循环出来后没返回说明找不到返回falseclass Solution { public: bool searchMatrix(vectorvectorint matrix, int target) { int n matrix.size(), m matrix[0].size(); int i 0, j m - 1; while (i n j 0) { if (matrix[i][j] target) i; else if (matrix[i][j] target) j--; else return true; } return false; } };搜索旋转排序数组解法1两次二分找排序数组的终点值分为两个数组进行两次二分找目标值target解法2二分按照 target 在 x中间值的左边进行分类讨论如果等于就返回x下标剩下的就是target在x右边的情况当 target 和 x 都在左半段排序数组时两者都要大于数组最后一个值且target小于x即使数组只有一段它也是降序的可以使用来判断x在右半段排序数组中此时target可以在左半段也可以在右半段class Solution { public: int search(vectorint nums, int target) { int left 0, right nums.size() - 1; while (left right) { int mid (left right) / 2; if (nums[mid] target) return mid; else if ((target nums[right] target nums[mid]) || (nums[mid] nums[right] (target nums[mid] || target nums[right]))) { right mid - 1; } else left mid 1; } return -1; // 两次二分 // int i0,nnums.size(); // while(i1n nums[i]nums[i1]) i; // int left0,righti; // while(leftright) // { // int mid(leftright)/2; // if(nums[mid]target) leftmid1; // else if(nums[mid]target) rightmid-1; // else return mid; // } // lefti1,rightn-1; // while(leftright) // { // int mid(leftright)/2; // if(nums[mid]target) leftmid1; // else if(nums[mid]target) rightmid-1; // else return mid; // } // return -1; } };寻找旋转排序数组中的最小值解法二分使用非朴素二分模板中间位置的值与当前区间的最后一个位置的值进行比较中间值大于最后一个值说明中间值在左半段最小值在右半段剩下的情况说明中间值可能是最小值也可能在中间值的左边但都一定在右半段class Solution { public: int findMin(vectorint nums) { int left 0, right nums.size() - 1; while (left right) { int mid (left right) / 2; if (nums[mid] nums[right]) left mid 1; else right mid; } return nums[left]; } };以上便是全部内容有问题欢迎在评论区指正更新观看