Leecode 93. 復原IP地址

題目描述

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

例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 無效 IP 地址。
給定一個只包含數字的字符串 s ，用以表示一個 IP 地址，返回所有可能的有效 IP 地址，這些地址可以通過在 s 中插入 '.' 來形成。你 不能 重新排序或刪除 s 中的任何數字。你可以按 任何 順序返回答案。

• 示例 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"]

回溯法，解題思路與代碼

感覺這道題對我來說確實有不小難度，思考了并嘗試了很久都沒有什么思路，最后是看完了卡哥的講解才想出來該怎么做的。首先是需要明確本題目標，要在給定的字符串中插入字符'.'，同時還需要將所有滿足條件的字符串都記錄在一個vector中輸出。那么首先是對于字符串中插入與刪除字符的操作：

• str.insert(str.begin() + pos, 'char')，在字符串中插入字符使用insert()函數
• str.erase(pos , length)，在字符串中刪除指定長度字符，使用erase()函數

隨后進一步討論回溯的思路：

• 由于本題要求給定合法IP的條件比較繁雜，所以一個自然的想法是使用一個返回布爾類型的函數來判斷當前字符串是否合法。而此時又需要明確該函數的輸入，如果考慮輸入的是整個字符串，那么可能會遇到當前字符串前一半加了'.'，而后一半沒加'.'的情況，也不能說每次只在已經將三個'.'都插入之后我們再去判斷當前字符串是否合法，否則會導致消耗很多時間在構建不合法的IP字符串的過程中。為此我們需要一個能夠實時判斷當前分割字符串并插入一個'.'的操作是否合法的函數，從而能夠在一旦發現本次分割不合法后迅速剪枝。那么我們理想的情況是輸入字符串的一個區間，即本次分割后所產生的長度不大于3的數字字符是否小于255且不能以0開頭。這里輸入的參數采用：(const string& s, int left, int right)的方式，表示本次判斷字符串s中的左閉右閉區間[left, right]是否合法。
• 在能夠判斷本次分割是否合法之后，就可以按照回溯的框架來寫代碼了：
  • 如果當前已經分割完成（已經插入過3個點，故需要一個變量pointNum來記錄已經插入過幾個點），并且最后一次分割合法，那么將整個字符串存入結果中
  • （如果還未分割完成）則在for循環中用i遍歷分割長度，此時需要一個變量start來記錄開始分割的位置
    • 在循環中每一次判斷不合法則直接返回，如果合法則繼續插入、遞歸、回溯

那么根據上面的思路不難寫出下面代碼：

class Solution {
public:
    vector<string> result;

    void backTracking(string& s, int start, int pointNum){
        if(pointNum == 3 && isValid(s, start, s.size()-1)){
            result.push_back(s);
            return;
        }

        for(int j = start; j < s.size(); j++){
            if(j - start > 2) break; // 剪枝，如果長度大于3，則直接跳出循環
            if(!isValid(s, start, j)) return;
            s.insert(s.begin()+j +1, '.'); // 插入一個.
            backTracking(s, j+2, pointNum+1); // 遞歸
            s.erase(j+1, 1); // 回溯，刪掉插入的.
        }
    }

    bool isValid(const string& s, int left, int right){
        if(left > right) return false; // 輸入的left要小于等于right
        if(right - left > 2) return false; // 檢查長度不能超過3
        if(s[left] == '0' && right != left) return false; // 檢查不能有前導0
        if(right - left == 2){ // 檢查數值要小于等于255
            if(s[left] > '2') return false;
            if(s[left] == '2' && s[left+1] > '5') return false;
            if(s[left] == '2' && s[left+1] == '5' && s[left+2] > '5') return false;
        } 
        return true; 
    }

    vector<string> restoreIpAddresses(string s) {
        backTracking(s, 0 , 0);
        return result;
    }
};

Leecode 78. 子集

題目描述

給你一個整數數組 nums ，數組中的元素 互不相同 。返回該數組所有可能的子集（冪集）。

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

• 示例 1：

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

• 示例 2：

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

迭代法求解

雖然這部分學習的都是回溯，但是本題我最先想出來的解法卻是使用迭代法來求解。

思考如何構造一個集合中的子集且不重復，首先一開始有一個初始的空集，存放到一個用于存放子集的結果族中（族，表示是由集合組成的集合），隨后開始逐個選取集合中的元素（記作元素i）。每次取到的元素i都是當前結果族中所有集合中都沒有的全新元素，那么此時如果要考慮包含這個新的元素的子集，就將目前結果族中的所有集合都復制一份的同時往里面添加當前這個新元素，再把復制得到的這些集合全部存入子集族中。只需要使用同樣的方法，遍歷完集合中的所有元素，我們就完成了不重復地構造子集。

具體可以寫出代碼如下所示：

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> curVec;
        result.push_back(curVec); // 存入空集
        for(int i = 0; i < nums.size(); i++){ // 對于nums中的每一個新的、還沒考慮過包含這個元素的子集的元素
            int size = result.size(); // 記錄目前已有的子集的個數
            for(int j = 0; j < size; j++){ // 在目前已經存放的所有子集中都加上這個元素再進行一次存放
                vector<int> newVec = result[j]; // 遍歷已有的所有子集，都復制一份
                newVec.push_back(nums[i]); // 將復制的子集中新增一個元素
                result.push_back(newVec); // 將得到的新數組存入結果當中
            }
        }
        return result;
    }
};

注意到上面算法中，每一次都將原本的子集族中的元素復制一份并全部添加新元素，就相當于乘以一次2，最終對于\(X\)個元素的集合，就會有\(2^X\)個子集。而這也與數學集合論中冪集的個數相同。

回溯法

本題的回溯法也非常簡單，和之前幾道組合的題目非常類似，區別在于本題的子集是需要取到樹中的每一個節點，而組合是只取樹的葉節點。既然是要取到所有節點，那么只需將原本組合中存放節點時的條件判斷去掉即可。故我們可以得到如下代碼：

class Solution {
public:
    vector<vector<int>> result;
    vector<int> curVec;

    void backTracking(vector<int>&nums, int start){
        result.push_back(curVec); // 每一個節點都進行存放，不需要條件判斷
        for(int i = start; i < nums.size(); i++){
            curVec.push_back(nums[i]); // 將當前節點的數存入自己
            backTracking(nums, i+1); // 遞歸
            curVec.pop_back(); // 回溯
        }
    }

    vector<vector<int>> subsets(vector<int>& nums) {
        backTracking(nums, 0);
        return result;
    }
};

Leecode 90. 子集 II

題目描述

給你一個整數數組 nums ，其中可能包含重復元素，請你返回該數組所有可能的 子集（冪集）。

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

• 示例 1：

輸入：nums = [1,2,2]
輸出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

• 示例 2：

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

使用集合set容器進行回溯

本題與上題的不同在于一開始給定的集合中有重復元素，意味著子集中也可以出現重復元素。但是最終存放到vector<vector>中的子集卻不能重復。為此可以考慮先使用一個sec<vector> 來存放所有子集，再將其轉換為vector，其余操作均和上一題一致。那么本題可以寫作：

class Solution {
public:
    set<vector<int>> result;
    vector<int> curVec;

    void backTracking(vector<int>& nums, int start){
        result.insert(curVec);
        for(int i = start; i < nums.size(); i++){
            curVec.push_back(nums[i]);
            backTracking(nums, i+1);
            curVec.pop_back();
        }
    }

    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        backTracking(nums, 0);
        vector<vector<int>> re(result.begin(), result.end());
        return re;
    }
};

這樣的做法和上一題完全一致。只是先用set后再將其轉換為vector，從而進行去重。接下來再嘗試使用start相關的判斷來去重。

使用start判斷去重

本題要去重的是值相等時不同組合的情況。即例如下面輸入測試案例：

輸入：[1, 2, 2];
如果不進行去重判斷，則會依次存入：[] -> [1] -> [1, 2] -> [1, 2, 2] -> [1, 2] -> ...注意此時就存入了兩個[1,2]。

上面例子中出現了兩個的[1,2]，其中第一個[1,2]中的2來自于原始集合中的第一個2，第二個[1,2]中的2來自于原始集合中的第二個2。為了避免這樣的重復結果存入，可以在for循環中加入下面判斷進行去重：

            if(i != start && nums[i] == nums[i-1] ) continue; // 當有重復元素出現時，只有當其為第一次出現時才進行保留，否則直接跳過

上面注意到上面判斷中，在判斷是否重復之前加了一條i != start的判斷，原因是為了保證該元素第一次出現時的子集結果能夠存入。對應上面列舉出的例子，也就是為了確保[1,2,2]子集能夠被存入，而不是看到重復元素就直接跳過。

在將上面if判斷語句加入for循環后，可以得到代碼如下：

class Solution {
public:
    vector<vector<int>> result;
    vector<int> curVec;

    void backTracking(vector<int>& nums, int start){
        result.push_back(curVec);
        for(int i = start; i < nums.size(); i++){
            if(i != start && nums[i] == nums[i-1] ) continue;
            curVec.push_back(nums[i]);
            backTracking(nums, i+1);
            curVec.pop_back();
        }
    }

    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        backTracking(nums, 0);
        return result;
    }
};

這樣使用上面代碼即可完成去重操作。

今日總結

這第二十四天的打卡實際上晚了兩天，原本該在4.18完成的但是拖到了4.20。最近馬上有兩門考試，所以可能Leecode打卡會不太及時，但是也會盡量檢查全部跟上刷完的，

當前力扣已刷88題，再接再勵！