1.回溯問題簡介

回溯問題,就是決策樹的遍歷程序,回溯問題需要有下面幾個問題考慮

• 路徑:已經做出的選擇,即從根節點到當前節點的路徑

• 選擇串列:當前情況下還可以做哪些選擇,即繼續往下遍歷節點,可以走哪些路

• 結束條件:到達決策樹的葉子節點,或者不滿足條件停止

2.回溯問題框架

明白回溯問題的幾個問題后,我們來看,回溯的基本框架

List<String> result = new ArrayList<String>();
public void backtrack(已經選擇的路徑,可以做選擇的串列) {
  if (滿足結束條件)
    result.add(已經選擇的路徑);
    return;
    
   for 選擇 in 可以做選擇的串列 {
     選擇串列.remove(選擇);
     已經選擇的路徑.add(選擇);
     backtrack(已經選擇路徑,可以做選擇的路徑);
     
     //撤銷
     已經選擇的路徑.remove(選擇);
     可以做選擇的串列.add(選擇);
   }
} 

3.案例

光學不練假把式,在看到思路前,先自己寫一遍實作,再看有沒有可以優化的地方.

3.1 字串全排列

給定一個 沒有重復 數字的序列，回傳其所有可能的全排列，來源:https://leetcode-cn.com/problems/permutations/

示例:

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

class Solution {

    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        int[] visited = new int[nums.length];
        backtrack(res, nums, new ArrayList<Integer>(), visited);
        return res;

    }

    private void backtrack(List<List<Integer>> res, int[] nums, ArrayList<Integer> tmp, int[] visited) {
        if (tmp.size() == nums.length) {
            res.add(new ArrayList<>(tmp));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (visited[i] == 1) continue;
            visited[i] = 1;
            tmp.add(nums[i]);
            backtrack(res, nums, tmp, visited);
            visited[i] = 0;
            tmp.remove(tmp.size() - 1);
        }
    }
}

注: 其中res是全域回傳,tmp是當前路徑上的節點,visited 和 nums 來標識當前還有哪些節點可以訪問

3.2 合法ip地址

給定一個只包含數字的字串，復原它并回傳所有可能的 IP 地址格式，來源:https://leetcode-cn.com/problems/restore-ip-addresses/

有效的 IP 地址 正好由四個整數（每個整數位于 0 到 255 之間組成，且不能含有前導 0），整數之間用 '.' 分隔，

例如："0.1.2.201" 和 "192.168.1.1" 是 有效的 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "[email protected]" 是 無效的 IP 地址，

示例 1：

輸入：s = "25525511135"
輸出：["255.255.11.135","255.255.111.35"]
示例 2：

輸入：s = "0000"
輸出：["0.0.0.0"]
示例 3：

輸入：s = "1111"
輸出：["1.1.1.1"]
示例 4：

輸入：s = "010010"
輸出：["0.10.0.10","0.100.1.0"]
示例 5：

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

解決代碼

class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList();
        List<String> temp = new ArrayList();
        helper(res,temp,s);
        return res;
    }

    void helper(List<String> res,List<String> temp,String next) {
        if(temp.size() > 4) {
            return;
        }
        if(temp.size() == 4 && next.length() == 0) {
            String ip = temp.get(0) + "." + temp.get(1) + "." + temp.get(2) + "." + temp.get(3);
            res.add(ip);
            return;
        }
        for(int i = 0; i < next.length(); i++) {
            String s = next.substring(0,i+1);
            if(s.length() > 1 && s.charAt(0) == '0') {
                continue;
            } 
            if(s.length() > 3) {
                continue;
            }
            if(s.length() == 3 && "255".compareTo(s) < 0) {
                continue;
            }
            temp.add(s);
            helper(res,temp,next.substring(i+1));
            temp.remove(temp.size() - 1);
        }
    }
}

注: 整體框架還是采用上面的結構,不過在判斷當前節點是否應該加入temp時候,要做一點稍微復雜的判斷
吳邪，小三爺，混跡于后臺，大資料，人工智能領域的小菜鳥，
更多請關注

標籤：其他

上一篇：大資料開發-Spark-一文理解常見RDD

下一篇：linux操作基礎二三事（一）