前端程式員學好演算法系列(九)遞歸回溯演算法

来源:https://www.cnblogs.com/kbnet/archive/2020/07/28/13388607.html
-Advertisement-
Play Games

回溯演算法主要應用於樹形問題,我們先從一個簡單的演算法入手 17. 電話號碼的字母組合給定一個僅包含數字 2-9 的字元串,返回所有它能表示的字母組合。 給出數字到字母的映射如下(與電話按鍵相同)。註意 1 不對應任何字母。 示例: 輸入:"23" 輸出:["ad", "ae", "af", "bd", ...


回溯演算法主要應用於樹形問題,我們先從一個簡單的演算法入手

17. 電話號碼的字母組合
給定一個僅包含數字 2-9 的字元串,返回所有它能表示的字母組合。

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

 

示例:

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

解題:

digits是數字字元串
s(digits) 是digits所能代表的字元串
s(digits[0..n-1])
  = letter(digits[0]) +s(digits[1...n-1])
  =letter(digits[0]) + letter(digits[1])  +s(digits[2...n-1])

 

1.我們建立一個map的數據結構,把鍵盤數字代表的字母一一傳入map中; map.get(digits[i])為當前傳入的第i個字元代表的字母集合

2. _generate() 我們傳入兩個變數 i 當前選擇的第幾個字母,str 預設傳入''
3. 當i的值等於digits.length是我們獲得了一個結果push到result中
4.迴圈當前的數字代表的字母 ,一一傳入_generate(i+1,str+tmp[r]);  遍歷其他結果

/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function(digits) {
     if(!digits){
        return [];
    }
    var len = digits.length;
    var map = new Map();
    map.set('1','');
    map.set('2','abc');
    map.set('3','def');
    map.set('4','ghi');
    map.set('5','jkl');
    map.set('6','mno');
    map.set('7','pqrs');
    map.set('8','tuv');
    map.set('9','wxyz');
    var result = [];
    function _generate(i,str){
        
        if(i == len){
            result.push(str);
            return;
        }
        var tmp = map.get(digits[i]);
        for(var r = 0;r<tmp.length;r++){
            _generate(i+1,str+tmp[r]);
        }
    }
    _generate(0,'');
    return result;
};

 

46. 全排列
給定一個 沒有重覆 數字的序列,返回其所有可能的全排列。

示例:

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

 解題:
1.回溯標準解題模板res 存放結果的數組,tmpPath為傳入的數組,當 tmpPath.length == n是我們得到一個滿足條件的解,
2. !tmpPath.includes(nums[i]) 來過濾防止數組tmpPath存在重覆的值
3. tmpPath.push(nums[i]); 數組中加入值後,遞歸完成後,相應的值需要從數組中減去,tmpPath.pop()
4.數組為引用類型,防止取值錯誤我們取 tmpPath.slice()繼續遍歷
5.每次遍歷index+1 進行下次遍歷

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {
    let n = nums.length;
    let res = [];
    let tmpPath = [];
    let backtrack = (index,tmpPath) => {
        if(tmpPath.length == n){
            res.push(tmpPath);
            return;
        }
        for(let i = 0;i < n;i++){
            if(!tmpPath.includes(nums[i])){
                tmpPath.push(nums[i]);
                backtrack(index+1,tmpPath.slice());
                tmpPath.pop();
            }
        }
    }
    backtrack(0,tmpPath);
    return res;
  
}

 

77. 組合
給定兩個整數 n 和 k,返回 1 ... n 中所有可能的 k 個數的組合。

示例:

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

 

1.求解n,k,當前已經找到的組合儲存在res中,需要從start位置處開始搜索

2.could.length == k我們獲得了一個滿足條件的解

3. could.push(i)  could.pop() 每次我們加入的數據在遞歸結果前需要刪除掉
4.每次遞歸迴圈時從i的下一位開始找

/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */
var combine = function(n, k) {
   
    var res = [];
    var could = [];
    if(k==0){
        return [[]]
    }
    function dfs(start,n,res,could){
        if(could.length == k){
            res.push(could.slice(0));
            return;
        }
        for(var i = start ; i<n+1;i++){
            could.push(i);
            dfs(i+1,n,res,could);
            could.pop()
        }
        return res;
    }
    return dfs(1,n,res,could)

};

 


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • DOM:Document/Object/Model DOM是一棵樹,樹上有Node,分為Document(html)、Element(元素)、Text(文本)、Comment(註釋)及其他 DOM最主要的功能是:通過 構造函數 把 節點 變成 對象,通過調用對象的 API 來操作對象 Node的介面 ...
  • 標簽語義化一含義 合適標簽做合適的事情,例如文章段落用p標簽,標題用h1-h6標簽 標簽語義化為瀏覽器和搜索引擎服務 標簽語乂化一為什麼要遵循標簽語義化 利於SE0優化(也就是搜索引擎的抓取,搜索引擎的爬蟲也依賴於標記來確定上下文和各個關鍵字的權重) 在樣式丟失的時候,還是可以比較好的呈現結構 更好 ...
  • 行內元素:a,button.big,em,i,input,mark,span,select,option,strog,b,sup,sub,textarea,u 內聯元素是指本身屬性為display:inline的元素.因為它自身的特點,我們通常使用行內元素來進行文字\小圖標(小結構)的搭建 塊級元素 ...
  • HTML元素指的是從開始標簽( start tag)到結束標簽( end tag)的所有代碼 開始標簽元素內容結束標簽 <p> this is a paragraph </p> <a href="default.htm"> this is a link </a> <br/> 註釋:開始標簽被稱為開放 ...
  • 60個\參考網址https://www.w3school.com.cn/tags/index.asp 標簽描述 <!--...--> 定義註釋。 <!DOCTYPE> 定義文檔類型。 <a> 定義錨。 <abbr> 定義縮寫。 <acronym> 定義只取首字母的縮寫。 <address> 定義文檔 ...
  • HTML:超文本標記語言,是使用標記標簽來描述網頁的一種語言,也是一種規範,一種標準,它通過標記符號來標記要顯示的網頁中的各個部分; css層疊樣式表是一種用來表現HTML(標準通用標記語言的一個應用)或XML(標準通用標記語言的一個子集)等文件樣式的的電腦語言。css不僅可以靜態地修飾網頁,還可 ...
  • HTML基本結構 document是指整個文件,它下麵就是咱們的html 超文本標記語言的結構包括"頭"(head)和主體(body) 其中"頭"部提供關於網頁的信息,"主體"部分提供網頁的具體內容 #HTML基本結構-文檔聲明 為了說明文檔使用的超文本標記原因標準,所有的超文本標記語言文檔應該以“ ...
  • 一夜無眠,學習不是為了別人,自己執行力好差,對自己過高期望,以為任務目標Soeasy,結果徘徊了幾個月,還是在原地踏步,怎麼講了?學習還是要腳踏實地,專註,不要為自己找藉口!畢竟虛長幾歲,曾經的年少輕狂高傲、曲動琴聲美妙一不復返!如今的自己在為曾經的不學習,努力向著生活買單!希望下麵可以越來越好! ...
一周排行
    -Advertisement-
    Play Games
  • 比如要拆分“呵呵呵90909086676喝喝999”,下麵當type=0返回的是中文字元串“呵呵呵,喝喝”,type=1返回的是數字字元串“90909086676,999”, private string GetStrings(string str,int type=0) { IList<strin ...
  • Swagger一個優秀的Api介面文檔生成工具。Swagger可以可以動態生成Api介面文檔,有效的降低前後端人員關於Api介面的溝通成本,促進項目高效開發。 1、使用NuGet安裝最新的包:Swashbuckle.AspNetCore。 2、編輯項目文件(NetCoreTemplate.Web.c ...
  • 2020 年 7 月 30 日, 由.NET基金會和微軟 將舉辦一個線上和為期一天的活動,包括 微軟 .NET 團隊的演講者以及社區的演講者。本次線上大會 專註.NET框架構建微服務,演講者分享構建和部署雲原生應用程式的最佳實踐、模式、提示和技巧。有關更多信息和隨時瞭解情況:https://focu... ...
  • #abp框架Excel導出——基於vue #1.技術棧 ##1.1 前端採用vue,官方提供 UI套件用的是iview ##1.2 後臺是abp——aspnetboilerplate 即abp v1,https://github.com/aspnetboilerplate/aspnetboilerp ...
  • 前言 本文的文字及圖片來源於網路,僅供學習、交流使用,不具有任何商業用途,版權歸原作者所有,如有問題請及時聯繫我們以作處理。 作者:碧茂大數據 PS:如有需要Python學習資料的小伙伴可以加下方的群去找免費管理員領取 input()輸入 Python提供了 input() 內置函數從標準輸入讀入一 ...
  • 從12年到20年,python以肉眼可見的趨勢超過了java,成為了當今It界人人皆知的編程語言。 python為什麼這麼火? 網路編程語言搜索指數 適合初學者 Python具有語法簡單、語句清晰的特點,這就讓初學者在學習階段可以把精力集中在編程對象和思維方法上。 大佬都在用 Google,YouT ...
  • 在社會上存在一種普遍的對培訓機構的學生一種歧視的現象,具體表現在,比如:當你去公司面試的時候,一旦你說了你是培訓機構出來的,那麼基本上你就涼了,那麼你瞞著不說,然後又通過了面試成功入職,但是以後一旦在公司被髮現有培訓經歷,可能會面臨被降薪,甚至被辭退,培訓機構出來的學生,在用人單位眼裡就是能力低下的 ...
  • from typing import List# 這道題看了大佬寫的代碼,經過自己的理解寫出來了。# 從最外圍的四周找有沒有為O的,如果有的話就進入深搜函數,然後深搜遍歷# 判斷上下左右的位置是否為Oclass Solution: def solve(self, board: List[List[s ...
  • import requests; import re; import os; # 1.請求網頁 header = { "user-agent":'Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_5) AppleWebKit/537.36 (KHTML, li ...
  • import requests; import re; import os; import parsel; 1.請求網頁 header = { "user-agent":'Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_5) AppleWebKit/537. ...