链接:https://leetcode.com/tag/recursion/
247 Strobogrammatic Number II (2019年2月22日,谷歌tag)
给了一个 n,给出长度为 n 的所有上下颠倒 180度以后都看起来一样的数字字符串。
题解:dfs,回溯。注意所有的能有pair的序列是 0, 1, 8, 6, 9
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 class Solution { 2 public: 3 vector<string> findStrobogrammatic(int n) { 4 vector<pair<string, string>> digits{{"0", "0"}, {"1", "1"}, {"6", "9"}, {"9", "6"}, {"8", "8"}}; 5 vector<string> res; 6 if (n & 1) { 7 vector<string> list = {"0", "1", "8"}; 8 for (int i = 0; i < 3; ++i) { 9 string s = list[i]; 10 dfs(res, s, digits, n); 11 } 12 } else { 13 string s = ""; 14 dfs(res, s, digits, n); 15 } 16 return res; 17 } 18 void dfs(vector<string>& res, string& s, vector<pair<string, string>>& digits, const int n) { 19 if (s.size() == n) { 20 if (s[0] != '0' || s == "0") { 21 res.push_back(s); 22 } 23 return; 24 } 25 for (auto& p : digits) { 26 string s1 = p.first, s2 = p.second; 27 string oriS = s; 28 s = s1 + s + s2; 29 dfs(res, s, digits, n); 30 s = oriS; 31 } 32 } 33 };
248 Strobogrammatic Number III (2019年1月17日,谷歌高频)
给了两个字符串一个low,一个high,找出 low 和 high 之间所有的 strobogrammatic number 的数量。strobogrammatic number 是说一个数字上下颠倒180度之后看起来一样
题解:找出所有上下颠倒看起来一样的数字。有 0, 1, 8, 69, 和 96, 我们可以用这些number做recursion。每次在两边加上这些数字。就能生成一个上下颠倒后看起来一样的数。
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 class Solution { 2 public: 3 int strobogrammaticInRange(string low, string high) { 4 if (low.size() > high.size() || low.size() == high.size() && low > high) { 5 return 0; 6 } 7 this->low = low, this->high = high; 8 vector<string> start = {"", "1", "8", "0", "69", "96"}; 9 for (auto s : start) { 10 dfs(s); 11 } 12 return ret.size(); 13 } 14 void dfs(string s) { 15 if (check(s)) { 16 ret.insert(s); 17 } 18 if (s.size() <= high.size()) { 19 for (int i = 0; i < model.size(); ++i) { 20 string pre = model[i].first, suff = model[i].second; 21 dfs(pre + s + suff); 22 } 23 } 24 if (s > high) { 25 return; 26 } 27 } 28 bool check(string s) { 29 if (s.empty() || s.size() > 1 && s[0] == '0' ) { 30 return false; 31 } 32 if (low.size() == high.size()) { 33 return s.size() == low.size() && s >= low && s <= high; 34 } else { 35 if (s.size() > low.size() && s.size() < high.size()) { 36 return true; 37 } else if (s.size() == low.size()) { 38 return s >= low; 39 } else if (s.size() == high.size()) { 40 return s <= high; 41 } 42 return false; 43 } 44 return false; 45 } 46 set<string> ret; 47 vector<pair<string, string>> model = {{"6","9"}, {"9","6"}, {"8","8"}, {"1","1"}, {"0","0"}}; 48 string low, high; 49 };
544 Output Contest Matches(2019年2月22日,谷歌tag)
给定一个 n,假设 n 只队伍比赛(n是2的幂),我们每次安排比赛要把最强的队伍和最弱的队伍安排在一起。给出最后比赛的排列字符串。
Input: 8 Output: (((1,8),(4,5)),((2,7),(3,6))) Explanation: First round: (1,8),(2,7),(3,6),(4,5) Second round: ((1,8),(4,5)),((2,7),(3,6)) Third round: (((1,8),(4,5)),((2,7),(3,6))) Since the third round will generate the final winner, you need to output the answer (((1,8),(4,5)),((2,7),(3,6))).
题解:本题看起来比较复杂,但是其实仔细研究一下,我们只需要把所有team的编号放在一个数组里面,把第一个和最后一个组队形成pair,第二个和倒数第二个组队形成pair,生成新的数组,然后调用dfs递归生成即可。
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 class Solution { 2 public: 3 string findContestMatch(int n) { 4 vector<string> pairs(n); 5 for (int i = 0; i < n; ++i) { 6 pairs[i] = to_string(i+1); 7 } 8 dfs(pairs); 9 return pairs[0]; 10 } 11 void dfs(vector<string>& pairs) { 12 if (pairs.size() == 1) {return;} 13 int start = 0, end = pairs.size() - 1; 14 vector<string> newPairs; 15 while (start < end) { 16 string str = "(" + pairs[start++] + "," + pairs[end--] + ")"; 17 newPairs.push_back(str); 18 } 19 pairs = newPairs; 20 dfs(pairs); 21 } 22 };
625 Minimum Factorization(2019年2月22日)
给了一个正整数a,返回一个最小的正整数b,b中所有数位的乘积等于a。
题解:dfs,backtracking. 很慢,本题可以数学方法。
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 class Solution { 2 public: 3 int smallestFactorization(int a) { 4 if (a == 1) {return 1;} 5 string s; 6 dfs(a, s); 7 return hasAns ? res : 0; 8 } 9 bool hasAns = false; 10 int res = INT_MAX; 11 void dfs(int a, string& s) { 12 if (a == 1) { 13 long long temp = stoll(s); 14 if (s.size() <= 10 && temp <= INT_MAX) { 15 hasAns = true; 16 res = min(res, stoi(s)); 17 } 18 return; 19 } 20 for (int i = 9; i > 1; --i) { 21 if (a % i == 0 && s.size() + 1 <= to_string(res).size()) { 22 s.push_back(i + '0'); 23 dfs(a/i, s); 24 s.pop_back(); 25 } 26 } 27 } 28 };
687 Longest Univalue Path
698 Partition to K Equal Sum Subsets (2019年2月24日,谷歌tag)
本题和 544 Output Contest Matches 拼火柴棍的这个题非常类似。基本一模一样。
给了一个数组nums,一个k,问这个数组能不能划分成 k 个总和大小相等的子集。每个数组元素只能用一次,并且必须用掉。
题解:dfs。
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 class Solution { 2 public: 3 bool canPartitionKSubsets(vector<int>& nums, int k) { 4 this->k = k; 5 size = nums.size(); 6 if (size == 0) {return false;} 7 int tot = 0; 8 sort(nums.begin(), nums.end(), greater<int>()); //从大到小排列 9 for (auto& num : nums) { 10 tot += num; 11 } 12 if (tot % k) {return false;} 13 const int length = tot / k; 14 vector<int> visit(size, 0); 15 return dfs(nums, visit, 0, 0, length, 0); 16 } 17 int size = 0, k = 0; 18 bool dfs(const vector<int>& nums, vector<int>& visit, int curLen, int cnt, const int target, int start) { 19 if (cnt == k) {return true;} 20 for (int i = start; i < size; ++i) { 21 if (visit[i]) {continue;} 22 if (curLen + nums[i] > target) {continue;} 23 visit[i] = 1; 24 bool res = false; 25 if (curLen + nums[i] == target) { //如果当前这个子集的元素的和等于target,就去寻找下一个子集。 26 res = dfs(nums, visit, 0, cnt + 1, target, 0); 27 } else if (curLen + nums[i] < target) { 28 res = dfs(nums, visit, curLen + nums[i], cnt, target, i + 1); //如果当前这个子集的元素的和小于target,就继续递归找当前子集的其他元素。 29 } 30 visit[i] = 0; 31 if (res) { 32 return res; 33 } 34 } 35 return false; 36 } 37 };
726 Number of Atoms
761 Special Binary String
779 K-th Symbol in Grammar(2019年2月22日,谷歌tag)(和群主mock的那题非常相似。)
当 N = 1 的时候,字符串为 “0”,每当 N 递增1,就把上一个字符串的 “0” 变成 “01”, 把上一个字符串的“1”变成“10”。返回第N个字符串的第K个字符。
题解:我们这题用递归解。我们先求出当前字符串的第 K 个字符是由前一个字符串的字符是 0 还是 1 生成的,然后根据前一个字符,做一点逻辑判断,判断出当前字符是 0 还是 1。
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 class Solution { 2 public: 3 int kthGrammar(int N, int K) { 4 if (N == 1) {return 0;} 5 int preNumber = kthGrammar(N-1, (K+1)/2); 6 int res = -1; 7 if (preNumber == 0) { //01 8 res = K & 1 ? 0 : 1; 9 } else if (preNumber == 1){ //10 10 res = K & 1 ? 1 : 0; 11 } 12 return res; 13 } 14 };
794 Valid Tic-Tac-Toe State
894 All Possible Full Binary Trees