三級位址選擇器引出的遞歸回溯方法
- 題目介紹
-
- 題解
- 回溯模闆
- 拓展(leetcode17、22、46、77、79、78)
題目介紹
已知資料格式,實作一個函數 fn ,給一個 id 找對外連結條中其對應的所有的父級 name
示例1: 傳入 id ddrr2, 傳回 廣東省深圳市福田區A街道
示例2: 傳入 id sdsd, 傳回 廣東省深圳市
const cityData = [{
id: 'axzx',
name: '廣東省',
children: [
{
id: 'sdsd',
name: '深圳市',
children: [
{
id: '45dss',
name: '南山區'
},
{
id: 'sdsd11',
name: '福田區',
children: [{
id: 'ddrr2',
name: 'A街道'
}]
}
]
},
{
id: '2323d',
name: '東莞市',
children: [
{
id: 'xxs2',
name: 'A區'
},
{
id: 'kklio2',
name: 'B區',
}
]
}
]
}];
題解
這是三級位址select元件最常用的算法,可以将數組結構看成一棵樹,然後用遞歸+回溯的方法做,首先可以思考遞歸出口以及每一層遞歸的函數傳參,這道題目遞歸出口有兩種情況:第一種找到了對應的id,第二種情況已經周遊到目前最後一層還沒找到。(第一種情況需要結束整個函數并return出結果,第二種情況需要結束目前遞歸并回到上一層狀态)
function search(id,data){
// 1.遞歸函數
function recurse(currentData){
// 2. 遞歸出口
if(currentData?.id===id) return;
if(!currentData?.children) return;
for(const v of currentData){
recurse(v?.children);
}
}
for(const v of data){
recurse(v);
}
}
根據題意還需要一個res數組在每次遞歸時将目前周遊對象的name push進去,并且兩種遞歸出口後續操作完全不同,是以在代碼中新增一個res并且修改遞歸出口函數。
function search(id,data){
let res = [];
// 1.遞歸函數
function recurse(currentData){
// 2. 遞歸出口
if(currentData?.id===id) return true;
if(!currentData.children) return false;
for(const v of currentData.children){
res.push(v.name);
const flag = recurse(v);
if(flag){
return true;
}
// 回溯
res.pop();
}
}
for(const v of data){
res.push(v.name);
const flag = recurse(v);
if(flag){
console.log(res);
return res.join('');
}
// 回溯
res.pop();
}
}
回溯模闆
上述題目中當目前節點無子節點退出目前遞歸後需要執行回溯算法,回溯算法可以套用下面架構
function main(){
function curse(){
/*遞歸出口*/
for(){
/**狀态壓入*/
curse();
/**回溯,狀态推出 */
}
}
curse();
}
拓展(leetcode17、22、46、77、79、78)
leetcode17 連結: 電話号碼的字母組合
leetcode22 連結: 括号生成
leetcode46 連結: 全排列
leetcode77 連結: 組合
leetcode78 連結: 子集
leetcode79 連結: 單詞搜尋
類似題目都可以去根據上述思路來做,先遞歸到最後一層節點,如果滿足題意,那麼直接return,如果不滿足,回溯到上一節點壓入另外的狀态繼續遞歸,直到滿足題目要求為止。注意遞歸中每一層的需要周遊哪些資料,比如電話号碼字母組合中的需要周遊目前數字的所有字母。
var letterCombinations = function(digits) {
let matrix = ['','','abc','def','ghi','jkl','mno','pqrs','tuv','wxyz'];
function curse(i){
/**出口 */
for(const v of matrix[digits[i]]){
/**狀态壓入 */
curse(i+1);
/**狀态pop*/
}
}
curse(0)
};