代碼隨想錄算法訓(xùn)練營打卡Day28 | LeetCode93 復(fù)原 IP 地址、LeetCode78 子集、LeetCode90 子集II

摘要

分割問題首先要明確如何對字符串分割赞辩，構(gòu)造樹形結(jié)構(gòu)來分析問題雌芽。
子集問題需要收集樹形結(jié)構(gòu)中的每個節(jié)點，所以要將收集結(jié)果的語句放在遞歸終止條件之前辨嗽。

LeetCode93 復(fù)原 IP 地址

93. 復(fù)原 IP 地址 - 力扣（Leetcode）

這也是一道分割字符串的問題世落，首先要確定分割的規(guī)則，先確定每次分割出的子串應(yīng)該符合的規(guī)則：
- 每次分割出的子串的長度最多為3
- 子串中不能含有前導(dǎo)0
- 子串中不能含有非數(shù)字的字符
- 子串對應(yīng)的整數(shù)數(shù)值在[0, 255]中
用以上的子串規(guī)則作為剪枝條件糟需，不難寫出以下函數(shù)

bool isValid(const string& s) {
    if (s.size() > 3) return false;// 長度最多為3
    if (s[0] == '0' && s.size() > 1) return false;// 不能含有前導(dǎo)0
    int temp = -1;
    try {
        temp = stoi(s);
    }
    catch (invalid_argument) {
        return false;// 不能含有非數(shù)字的字符
    }
    if (temp < 0 || temp > 255) return false;// 子串對應(yīng)的整數(shù)數(shù)值應(yīng)在[0, 255]中
    return true;
}

確定了剪枝函數(shù)屉佳，再套用回溯法的遞歸函數(shù)模板
- 遞歸函數(shù)的終止條件：整個輸入字符串被分割完成且分割出的子串?dāng)?shù)量恰好為4，說明應(yīng)收集答案洲押；分割出的子串?dāng)?shù)量大于4武花，說明分割出的子串不能組合出合法的IP地址，應(yīng)直接返回杈帐。
- 遞歸函數(shù)的參數(shù)列表：輸入的字符串s体箕，結(jié)果集res，當(dāng)前分割出的子串列表cur娘荡，下一次分割的起始位置start干旁，當(dāng)前分割出的子串?dāng)?shù)量part。
- 單層遞歸的邏輯：以start作為當(dāng)前子串的起始位置炮沐，i作為當(dāng)前子串的終止位置争群，左閉右閉區(qū)間，來枚舉在本層可能分割出的子串大年，并通過檢查分割出的子串是否能組成合法IP進行剪枝换薄。

完整的題解代碼如下，采用vector<string>來暫存子串翔试，便于回溯（直接push和pop即可轻要，比字符串操作方便一些，但效率好像不如直接操作字符串）垦缅。注意part初始化為0冲泥，對應(yīng)的是cur中的子串?dāng)?shù)量。

class Solution {
public:
    bool isValid(const string& s) {
        if (s.size() > 3) return false;
        if (s[0] == '0' && s.size() > 1) return false;
        int temp = -1;
        try {
            temp = stoi(s);
        }
        catch (invalid_argument) {
            return false;
        }
        if (temp < 0 || temp > 255) return false;
        return true;
    }
    void backtracking(const string& s, vector<string>& res,
                    vector<string>& cur, int start, int part)
    {
        if (part > 4) return;
        if (start >= s.size()) {
            if (part != 4) return;
            string temp;
            for (auto& iter : cur) {
                temp += iter;
                if (--part) temp += ".";
            }
            res.push_back(temp);
            return;
        }
        for (int i = start; i < s.size(); i++) {
            if (isValid(s.substr(start, i - start + 1))) {
                cur.push_back(s.substr(start, i - start + 1));
                backtracking(s, res, cur, i + 1, part + 1);
                cur.pop_back();
            }
        }
    }
    vector<string> restoreIpAddresses(string s) {
        vector<string> res;
        vector<string> cur;
        backtracking(s, res, cur, 0, 0);// part 初始化為 0
        return res;
    }
};

直接操作字符串的版本，注意part要初始化為1凡恍，直接操作字符串是以插入.的形式來分割的志秃，在未插入.時，將整個串看作一個子串嚼酝，所以part初始化為1浮还。

class Solution {
public:
    bool isValid(const string& s) {
        if (s.size() > 3) return false;
        if (s[0] == '0' && s.size() > 1) return false;
        int temp = -1;
        try {
            temp = stoi(s);
        }
        catch (invalid_argument) {
            return false;
        }
        if (temp < 0 || temp > 255) return false;
        return true;
    }
    void backtracking(string& s, vector<string>& res,
                    int start, int part)
    {
        if (part > 4) return;
        if (part == 4) {
            if (isValid(s.substr(start))) res.push_back(s);// 判斷最后一個子串是否合法
            return;
        }
        for (int i = start; i < s.size(); i++) {
            if (isValid(s.substr(start, i - start + 1))) {
                s.insert(s.begin() + i + 1, '.');
                backtracking(s, res, i + 2, part + 1);
                s.erase(s.begin() + i + 1);
            }
        }
    }
    vector<string> restoreIpAddresses(string s) {
        vector<string> res;
        vector<string> cur;
        backtracking(s, res, 0, 1);// part 初始化為 1
        return res;
    }
};

LeetCode78 子集

78. 子集 - 力扣（Leetcode）

這道題目與之前的區(qū)別就是要收集樹形結(jié)構(gòu)中的每個節(jié)點進入結(jié)果集，所以關(guān)鍵在于收集結(jié)果的語句要放在遞歸終止的語句之前闽巩。
以[1, 2, 3]為例钧舌，其子集的構(gòu)造樹如下圖，回溯法能遍歷到每個節(jié)點涎跨，所以只需要每次遞歸都收集結(jié)果即可洼冻。

完整的題解代碼如下

class Solution {
public:
    void backtracking(vector<int>& nums, vector<vector<int>>& res,
                    vector<int>& cur, int start)
    {
        res.push_back(cur);
        if (start >= nums.size()) return;
        for (int i = start; i < nums.size(); i++) {
            cur.push_back(nums[i]);
            backtracking(nums, res, cur, i + 1);
            cur.pop_back();
        }
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> cur;
        backtracking(nums, res, cur, 0);
        return res;
    }
};

LeetCode90 子集II

90. 子集 II - 力扣（Leetcode）

本題除了要在回溯法的樹形結(jié)構(gòu)中的每個節(jié)點收集結(jié)果外，還要做“樹層去重”六敬。
以[1, 2, 2]為例碘赖，其子集構(gòu)造的樹形結(jié)構(gòu)如下

在這里復(fù)習(xí)“樹枝去重”和“樹層去重”
- 樹枝去重：為了防止使用相同的元素，每次向下搜索時外构，可用元素的起始位置start應(yīng)向右移一位普泡。
- 樹層去重：結(jié)果集中出現(xiàn)重復(fù)組合的原因不是使用了相同的元素，而是在樹的同一層中使用值相同的不同元素审编。觀察子集構(gòu)造的樹形結(jié)構(gòu)撼班，因為樹枝去重，所以有多個值相同的元素出現(xiàn)時垒酬，選取其中第一個元素之后得到的組合就包含了在本層中選取該元素的所有可能砰嘁。例如上面的第二層的第一個1，從第二層的第一個1開始搜索得到的組合勘究，包含了從第二層的第二個1開始搜索得到的所有組合矮湘。所以，只需要保留從第一個1搜索得到的結(jié)果即可完成樹層去重口糕。
- 對原數(shù)組進行排序的意義就在于讓值相同的元素在數(shù)組中連續(xù)分布缅阳，便于去重。

完整的題解代碼如下

class Solution {
public:
    void backtracking(vector<int>& nums, vector<vector<int>>& res,
                    vector<int>& cur, int start)
    {
        res.push_back(cur);
        if (start >= nums.size()) return;
        for (int i = start; i < nums.size(); i++) {
            if (i - start && nums[i - 1] == nums[i]) continue;
            cur.push_back(nums[i]);
            backtracking(nums, res, cur, i + 1);
            cur.pop_back();
        }
    }
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> cur;
        sort(nums.begin(), nums.end());
        backtracking(nums, res, cur, 0);
        return res;
    }
};

代碼隨想錄算法訓(xùn)練營打卡Day28 | LeetCode93 復(fù)原 IP 地址、LeetCode78 子集盏触、LeetCode90 子集II

代碼隨想錄算法訓(xùn)練營打卡Day28 | LeetCode93 復(fù)原 IP 地址渗蟹、LeetCode78 子集、LeetCode90 子集II

摘要

LeetCode93 復(fù)原 IP 地址

LeetCode78 子集

LeetCode90 子集II