鏈接：https://leetcode.com/tag/recursion/

?

247 Strobogrammatic Number II (2019年2月22日，谷歌tag)

給了一個 n，給出長度為 n 的所有上下顛倒 180度以后都看起來一樣的數字字符串。

題解：dfs，回溯。注意所有的能有pair的序列是 0， 1， 8， 6， 9

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 }; View Code

?

248 Strobogrammatic Number III （2019年1月17日，谷歌高頻）

給了兩個字符串一個low，一個high，找出 low 和 high 之間所有的 strobogrammatic number 的數量。strobogrammatic number 是說一個數字上下顛倒180度之后看起來一樣

題解：找出所有上下顛倒看起來一樣的數字。有 0， 1， 8， 69， 和 96， 我們可以用這些number做recursion。每次在兩邊加上這些數字。就能生成一個上下顛倒后看起來一樣的數。

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 }; View Code

?

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遞歸生成即可。

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 }; View Code

?

625 Minimum Factorization（2019年2月22日）

給了一個正整數a，返回一個最小的正整數b，b中所有數位的乘積等于a。

題解：dfs，backtracking. 很慢，本題可以數學方法。

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 }; View Code

?

687 Longest Univalue Path

698 Partition to K Equal Sum Subsets （2019年2月24日，谷歌tag）

本題和?544 Output Contest Matches 拼火柴棍的這個題非常類似。基本一模一樣。

給了一個數組nums，一個k，問這個數組能不能劃分成 k 個總和大小相等的子集。每個數組元素只能用一次，并且必須用掉。

題解：dfs。

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 }; View Code

?

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。

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 }; View Code

?

794 Valid Tic-Tac-Toe State

894 All Possible Full Binary Trees

轉載于:https://www.cnblogs.com/zhangwanying/p/10284615.html

總結

以上是生活随笔為你收集整理的【LeetCode】Recursion（共11题）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。