中文亚洲精品无码_熟女乱子伦免费_人人超碰人人爱国产_亚洲熟妇女综合网

當前位置: 首頁 > news >正文

宣傳類的網(wǎng)站怎么做/廣告軟文代理平臺

宣傳類的網(wǎng)站怎么做,廣告軟文代理平臺,網(wǎng)站建設ppt方案,建設政府網(wǎng)站來源0x3f:https://space.bilibili.com/206214 回溯分為【子集型回溯】【組合型回溯】【排列型回溯】 文章目錄回溯基本概念[17. 電話號碼的字母組合](https://leetcode.cn/problems/letter-combinations-of-a-phone-number/)子集型回溯(分割問題也可以看…

來源0x3f:https://space.bilibili.com/206214

回溯分為【子集型回溯】【組合型回溯】【排列型回溯】

文章目錄

  • 回溯基本概念
    • [17. 電話號碼的字母組合](https://leetcode.cn/problems/letter-combinations-of-a-phone-number/)
  • 子集型回溯(分割問題也可以看作枚舉分割點==>子集型)
    • [78. 子集](https://leetcode.cn/problems/subsets/)
      • 方法一:輸入的視角(每個節(jié)點可以選擇選和不選)
      • 方法二:答案的角度(枚舉第一個數(shù)選誰、第二個數(shù)選誰)
    • [131. 分割回文串](https://leetcode.cn/problems/palindrome-partitioning/)
      • 思路:設每兩個相鄰字符間有逗號,枚舉每個逗號結束位置。這樣就變成了[78. 子集]問題
    • [784. 字母大小寫全排列](https://leetcode.cn/problems/letter-case-permutation/)
    • [93. 復原 IP 地址](https://leetcode.cn/problems/restore-ip-addresses/)
  • 組合型回溯(剪枝技巧)
    • [77. 組合](https://leetcode.cn/problems/combinations/)
    • [216. 組合總和 III](https://leetcode.cn/problems/combination-sum-iii/)
    • [22. 括號生成](https://leetcode.cn/problems/generate-parentheses/)
  • 排列型回溯(棋盤問題也是排列型回溯)
    • [46. 全排列](https://leetcode.cn/problems/permutations/)
    • [51. N 皇后](https://leetcode.cn/problems/n-queens/)

回溯基本概念

回溯三問:

1、當前操作?

2、子問題?

3、下一個子問題?

void backtracking(參數(shù)) {if (終止條件) {存放結果;return;}for (選擇:本層集合中元素(樹中節(jié)點孩子的數(shù)量就是集合的大小)) {處理節(jié)點;backtracking(路徑,選擇列表); // 遞歸回溯,撤銷處理結果}
}

17. 電話號碼的字母組合

難度中等2314

給定一個僅包含數(shù)字 2-9 的字符串,返回所有它能表示的字母組合。答案可以按 任意順序 返回。

給出數(shù)字到字母的映射如下(與電話按鍵相同)。注意 1 不對應任何字母。

img

示例 1:

輸入:digits = "23"
輸出:["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2:

輸入:digits = ""
輸出:[]

示例 3:

輸入:digits = "2"
輸出:["a","b","c"]

提示:

  • 0 <= digits.length <= 4
  • digits[i] 是范圍 ['2', '9'] 的一個數(shù)字。

回溯三問:

1、當前操作? 枚舉 path[i] 要填入的字母

2、子問題? 構造字符串>=i 的部分

3、下一個子問題? 構造字符串>= i+1 的部分

class Solution {private static final String[] arr = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};List<String> res = new ArrayList<>();public List<String> letterCombinations(String digits) {if(digits.equals("")) return res;dfs(digits, 0, new StringBuilder());return res;}public void dfs(String digits, int i, StringBuilder sb){if(i == digits.length()){res.add(sb.toString());return;}String str = arr[digits.charAt(i) - '0'];for(int j = 0; j < str.length(); j++){sb.append(str.charAt(j));dfs(digits, i+1, sb);sb.deleteCharAt(sb.length()-1);}}
}

子集型回溯(分割問題也可以看作枚舉分割點==>子集型)

子集型回溯:每個元素都可以選和不選

回溯三問:

**1、當前操作?**枚舉第 i 個數(shù)選/不選

2、子問題? 從下標 >=i 的數(shù)字中構造子集

3、下一個子問題? 從下標 >=i+1 的數(shù)字中構造子集


78. 子集

難度中等1931

給你一個整數(shù)數(shù)組 nums ,數(shù)組中的元素 互不相同 。返回該數(shù)組所有可能的子集(冪集)。

解集 不能 包含重復的子集。你可以按 任意順序 返回解集。

示例 1:

輸入:nums = [1,2,3]
輸出:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2:

輸入:nums = [0]
輸出:[[],[0]]

提示:

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10
  • nums 中的所有元素 互不相同

題解:

方法一:輸入的視角(每個節(jié)點可以選擇選和不選)

class Solution {List<List<Integer>> res = new ArrayList<>();List<Integer> cur;public List<List<Integer>> subsets(int[] nums) {cur = new ArrayList<>();dfs(nums, 0);return res;}// 每個節(jié)點可以選擇選和不選public void dfs(int[] nums, int i){if(i == nums.length){res.add(new ArrayList<>(cur));return;}dfs(nums, i+1);cur.add(nums[i]);dfs(nums, i+1);cur.remove(cur.size()-1);}
}

方法二:答案的角度(枚舉第一個數(shù)選誰、第二個數(shù)選誰)

class Solution {List<List<Integer>> res = new ArrayList<>();List<Integer> cur;public List<List<Integer>> subsets(int[] nums) {cur = new ArrayList<>();dfs(nums, 0);return res;}// 每個節(jié)點可以選擇選和不選public void dfs(int[] nums, int i){// 關鍵在這里, 遞歸入口每次記錄答案res.add(new ArrayList<>(cur));if(i == nums.length){return;}for(int j = i; j < nums.length; j++){cur.add(nums[j]);dfs(nums, j+1);cur.remove(cur.size()-1);}}
}

131. 分割回文串

難度中等1387

給你一個字符串 s,請你將 s 分割成一些子串,使每個子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正著讀和反著讀都一樣的字符串。

示例 1:

輸入:s = "aab"
輸出:[["a","a","b"],["aa","b"]]

示例 2:

輸入:s = "a"
輸出:[["a"]]

提示:

  • 1 <= s.length <= 16
  • s 僅由小寫英文字母組成

思路:設每兩個相鄰字符間有逗號,枚舉每個逗號結束位置。這樣就變成了[78. 子集]問題

方法二:答案的角度(枚舉字串結束位置)

class Solution {List<List<String>> res = new ArrayList<>();List<String> cur;public List<List<String>> partition(String s) {cur = new ArrayList<>();dfs(s, 0);return res;}public void dfs(String s, int i){if(i == s.length()){res.add(new ArrayList<>(cur));return;}//枚舉字串結束位置(設以j結尾是否符合要求)for(int j = i; j < s.length(); j++){//判斷一下[i, j] 部分是否為回文串String str = s.substring(i, j+1);if(isrev(str)){cur.add(str);dfs(s, j+1);cur.remove(cur.size()-1);}}}public boolean isrev(String str){int left = 0, right = str.length()-1;while(left < right){if(str.charAt(left) != str.charAt(right))return false;left++; right--;}return true;}
}

784. 字母大小寫全排列

難度中等515

給定一個字符串 s ,通過將字符串 s 中的每個字母轉變大小寫,我們可以獲得一個新的字符串。

返回 所有可能得到的字符串集合 。以 任意順序 返回輸出。

示例 1:

輸入:s = "a1b2"
輸出:["a1b2", "a1B2", "A1b2", "A1B2"]

示例 2:

輸入: s = "3z4"
輸出: ["3z4","3Z4"]

提示:

  • 1 <= s.length <= 12
  • s 由小寫英文字母、大寫英文字母和數(shù)字組成

題解:

DFS 回溯 看到題目要求組合或者集合,馬上想到可以用回溯法:

回溯法本來是說對于每個元素都先考慮放它的情況,再考慮不放它的情況;

放在這道題的背景里就是,對于每個字母,先考慮放它,再考慮放它的另一種大小寫形式。

class Solution {List<String> res = new ArrayList<>();public List<String> letterCasePermutation(String s) {dfs(s, 0, new StringBuilder());return res;}public void dfs(String s, int i, StringBuilder sb){if(i == s.length()){res.add(new String(sb.toString()));return;}// 不改sb.append(s.charAt(i));dfs(s, i+1, sb);sb.deleteCharAt(sb.length()-1);//改if(s.charAt(i) >= 'a' && s.charAt(i) <= 'z'){sb.append((char)(s.charAt(i) - 32));dfs(s, i+1, sb);}else if(s.charAt(i) >= 'A' && s.charAt(i) <= 'Z'){sb.append((char)(s.charAt(i) + 32));dfs(s, i+1, sb);}if((s.charAt(i) >= 'a' && s.charAt(i) <= 'z') || (s.charAt(i) >= 'A' && s.charAt(i) <= 'Z'))sb.deleteCharAt(sb.length()-1);}
}

93. 復原 IP 地址

難度中等1146收藏分享切換為英文接收動態(tài)反饋

有效 IP 地址 正好由四個整數(shù)(每個整數(shù)位于 0255 之間組成,且不能含有前導 0),整數(shù)之間用 '.' 分隔。

  • 例如:"0.1.2.201" "192.168.1.1"有效 IP 地址,但是 "0.011.255.245""192.168.1.312""192.168@1.1"無效 IP 地址。

給定一個只包含數(shù)字的字符串 s ,用以表示一個 IP 地址,返回所有可能的有效 IP 地址,這些地址可以通過在 s 中插入 '.' 來形成。你 不能 重新排序或刪除 s 中的任何數(shù)字。你可以按 任何 順序返回答案。

示例 1:

輸入:s = "25525511135"
輸出:["255.255.11.135","255.255.111.35"]

示例 2:

輸入:s = "0000"
輸出:["0.0.0.0"]

示例 3:

輸入:s = "101023"
輸出:["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

提示:

  • 1 <= s.length <= 20
  • s 僅由數(shù)字組成
class Solution {List<String> res = new ArrayList<>(); List<String> tmp = new ArrayList<>();public List<String> restoreIpAddresses(String s) {dfs(s, 0);return res;}public void dfs(String s, int begin){if(tmp.size() == 4 && begin != s.length()) return;if(tmp.size() == 4 && begin == s.length()){res.add(String.join(".",tmp));return;}//枚舉分割點for(int j = begin; j < s.length() && j < begin+3; j++){String str = s.substring(begin, j+1);// 每個整數(shù)位于 0 到 255 之間組成if(Integer.parseInt(str) <= 255){// 不能含有前導 0if(str.length() > 1 && str.charAt(0) == '0'){return;}tmp.add(str);dfs(s, j+1);tmp.remove(tmp.size()-1);}else{return;}}}
}

組合型回溯(剪枝技巧)

77. 組合

難度中等1284

給定兩個整數(shù) nk,返回范圍 [1, n] 中所有可能的 k 個數(shù)的組合。

你可以按 任何順序 返回答案。

示例 1:

輸入:n = 4, k = 2
輸出:
[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],
]

示例 2:

輸入:n = 1, k = 1
輸出:[[1]]

提示:

  • 1 <= n <= 20
  • 1 <= k <= n
class Solution {List<List<Integer>> res = new ArrayList<>();List<Integer> cur = new ArrayList<>();int n, k;public List<List<Integer>> combine(int _n, int _k) {n = _n;k = _k;dfs(1);return res;}public void dfs(int i){if(cur.size() == k){ // d == 0res.add(new ArrayList<>(cur));return;}for(int j = i; j <= n - (k - cur.size()) + 1 ; j++){cur.add(j);dfs(j+1);cur.remove(cur.size() - 1);}}
}

相同方式倒著遍歷的寫法

class Solution {List<List<Integer>> res = new ArrayList<>();List<Integer> cur = new ArrayList<>();int n, k;public List<List<Integer>> combine(int _n, int _k) {n = _n; k = _k;dfs(n);return res;}public void dfs(int i){int d = k - cur.size();// 還要選 d 個數(shù)if(d == 0){ res.add(new ArrayList<>(cur));return;}for(int j = i; j >= d; j--){cur.add(j);dfs(j-1);cur.remove(cur.size() - 1);}}
}

216. 組合總和 III

難度中等622

找出所有相加之和為 nk 個數(shù)的組合,且滿足下列條件:

  • 只使用數(shù)字1到9
  • 每個數(shù)字 最多使用一次

返回 所有可能的有效組合的列表 。該列表不能包含相同的組合兩次,組合可以以任何順序返回。

示例 1:

輸入: k = 3, n = 7
輸出: [[1,2,4]]
解釋:
1 + 2 + 4 = 7
沒有其他符合的組合了。

示例 2:

輸入: k = 3, n = 9
輸出: [[1,2,6], [1,3,5], [2,3,4]]
解釋:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
沒有其他符合的組合了。

示例 3:

輸入: k = 4, n = 1
輸出: []
解釋: 不存在有效的組合。
在[1,9]范圍內(nèi)使用4個不同的數(shù)字,我們可以得到的最小和是1+2+3+4 = 10,因為10 > 1,沒有有效的組合。

提示:

  • 2 <= k <= 9
  • 1 <= n <= 60
class Solution {List<List<Integer>> res = new ArrayList<>();List<Integer> cur = new ArrayList<>();int k;public List<List<Integer>> combinationSum3(int _k, int n) {k = _k;dfs(9, n);return res;}public void dfs(int i, int target){int d = k - cur.size();// 還要選 d 個數(shù)//剪枝// 首項+末項 *項數(shù) /2  仍然比target小,就不用遞歸了if(target < 0 || target > (i*2 - d + 1) * d / 2)return; // d = 0 , (i*2 - d + 1) * d / 2也是等于0的,就不用判斷target = 0 了if(d == 0){ res.add(new ArrayList<>(cur));return;}for(int j = i; j >= d; j--){cur.add(j);dfs(j-1, target-j);cur.remove(cur.size() - 1);}}
}

22. 括號生成

難度中等3091

數(shù)字 n 代表生成括號的對數(shù),請你設計一個函數(shù),用于能夠生成所有可能的并且 有效的 括號組合。

示例 1:

輸入:n = 3
輸出:["((()))","(()())","(())()","()(())","()()()"]

示例 2:

輸入:n = 1
輸出:["()"]

提示:

  • 1 <= n <= 8
class Solution {int n;char[] path;List<String> res = new ArrayList<>();public List<String> generateParenthesis(int n) {this.n = n;path = new char[n * 2];dfs(0, 0);return res;}public void dfs(int i, int open){if(i == n * 2){res.add(new String(path));}if(open < n){ // 可以填左括號path[i] = '(';dfs(i+1, open+1);}if(i - open < open){ // 不可以填左括號了,只能填右括號}path[i] = ')';dfs(i+1, open);}}
}

排列型回溯(棋盤問題也是排列型回溯)

排列型和組合型的區(qū)別:組合中不能有{1,2} {2,1} 同時存在,因為他們是相同的組合

46. 全排列

難度中等2411

給定一個不含重復數(shù)字的數(shù)組 nums ,返回其 所有可能的全排列 。你可以 按任意順序 返回答案。

示例 1:

輸入:nums = [1,2,3]
輸出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2:

輸入:nums = [0,1]
輸出:[[0,1],[1,0]]

示例 3:

輸入:nums = [1]
輸出:[[1]]

提示:

  • 1 <= nums.length <= 6
  • -10 <= nums[i] <= 10
  • nums 中的所有整數(shù) 互不相同
class Solution {List<List<Integer>> res = new ArrayList<>();List<Integer> cur = new ArrayList<>();boolean[] visit;public List<List<Integer>> permute(int[] nums) {visit = new boolean[nums.length];dfs(0, nums);return res;}public void dfs(int i, int[] nums){if(i == nums.length){res.add(new ArrayList<>(cur));return;}for(int k = 0; k < nums.length; k++){if(visit[k] == false){visit[k] = true;cur.add(nums[k]);dfs(i+1, nums);cur.remove(cur.size()-1);visit[k] = false;}}}}

51. N 皇后

難度困難1648

按照國際象棋的規(guī)則,皇后可以攻擊與之處在同一行或同一列或同一斜線上的棋子。

n 皇后問題 研究的是如何將 n 個皇后放置在 n×n 的棋盤上,并且使皇后彼此之間不能相互攻擊。

給你一個整數(shù) n ,返回所有不同的 n 皇后問題 的解決方案。

每一種解法包含一個不同的 n 皇后問題 的棋子放置方案,該方案中 'Q''.' 分別代表了皇后和空位。

示例 1:

img

輸入:n = 4
輸出:[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解釋:如上圖所示,4 皇后問題存在兩個不同的解法。

示例 2:

輸入:n = 1
輸出:[["Q"]]

提示:

  • 1 <= n <= 9

題解:https://leetcode.cn/problems/n-queens/solution/java-c-by-tizzi-i9j0/

class Solution {List<List<String>> ans = new ArrayList<>();int[] row;boolean[] cols, d, ud;int N;public List<List<String>> solveNQueens(int n) {N = n;cols = new boolean[n];d = new boolean[30];ud = new boolean[30];row = new int[n];// 用來保存第幾行第幾列放置Qdfs(0);return ans;}// col【】數(shù)組記錄某列已經(jīng)放過了皇后。col【i】= 1代表第i列已經(jīng)放了一個皇后。// d【】 數(shù)組來記錄某正對角線已經(jīng)放置過了皇后。// ud【】數(shù)組來記錄某反對角線已經(jīng)放置過了皇后。public void dfs(int i){if(i == N){char[] arr = new char[N];Arrays.fill(arr, '.');List<String> g = new ArrayList<>();for(int j = 0; j < N; j++){arr[row[j]] = 'Q';g.add(new String(arr));arr[row[j]] = '.';}ans.add(g);return;}// 選擇一個位置進行放置for(int j = 0; j < N; j++){// 列,對角線、反對角線判斷if (!cols[j] && !d[i + j] && !ud[N - i + j]){cols[j] = d[i+j] = ud[N-i+j] = true;row[i] = j;dfs(i+1);cols[j] = d[i+j] = ud[N-i+j] = false;}}}
}
http://www.risenshineclean.com/news/748.html

相關文章:

  • 企業(yè)網(wǎng)站改自適應/班級優(yōu)化大師電腦版
  • 一個公司設計網(wǎng)站怎么做/京東seo搜索優(yōu)化
  • wordpress在線音樂/seo狂人
  • 上海最好的網(wǎng)站建設公司/百度競價推廣方案
  • 做網(wǎng)站哪個語言強/好項目推薦平臺
  • 網(wǎng)絡營銷與傳統(tǒng)營銷有哪些區(qū)別/windows優(yōu)化大師可以卸載嗎
  • 鶴壁做網(wǎng)站優(yōu)化/aso優(yōu)化榜單
  • 如何做企業(yè)網(wǎng)站推廣產(chǎn)品/iis搭建網(wǎng)站
  • 網(wǎng)絡營銷方式和平臺推廣/搜索引擎優(yōu)化的目的是
  • 天津武清做網(wǎng)站tjniu/產(chǎn)品互聯(lián)網(wǎng)營銷推廣
  • 海報設計網(wǎng)站官網(wǎng)/百度怎么做廣告
  • 石家莊有哪些做網(wǎng)站的公司/百度保障中心人工電話
  • 門戶網(wǎng)站建設工作會議/國外引流推廣軟件
  • 網(wǎng)站頁面類型/正規(guī)網(wǎng)站優(yōu)化哪個公司好
  • 推廣網(wǎng)站最有效方法/自己有貨源怎么找客戶
  • 重慶網(wǎng)站建設設計/怎么去推廣一個app
  • 網(wǎng)站微營銷公司哪家好/鄭州疫情最新動態(tài)
  • 品牌logo設計說明/百度seo優(yōu)化公司
  • 有什么做任務得傭金的網(wǎng)站/站長之家app
  • 做淘寶有哪些推廣網(wǎng)站/seo外鏈友情鏈接
  • 開發(fā)公司取名字大全免費查詢/貴陽網(wǎng)站優(yōu)化公司
  • 代碼判斷網(wǎng)站/上海百度競價托管
  • 運動網(wǎng)站建設教程/上海網(wǎng)站排名優(yōu)化公司
  • 濟南做網(wǎng)站xywlcn/百度用戶服務中心官網(wǎng)
  • 南海區(qū)住房和城鄉(xiāng)建設部網(wǎng)站/提高網(wǎng)站排名軟件
  • 河南那家公司做家具行業(yè)網(wǎng)站好/電商培訓有用嗎
  • 中山品牌網(wǎng)站建設推廣/軟件培訓機構有哪些?哪個比較好
  • 東莞工信部網(wǎng)站/公司排名seo
  • java做網(wǎng)站pdf/網(wǎng)絡營銷成功案例ppt
  • 學生怎樣做網(wǎng)站/模板建站哪里有