代码随想录算法训练营第28天 | 93.复原IP地址, 78.子集, 90.子集II

今天题目都是自己A出来的, 不错.

93.复原IP地址

代码随想录链接

题目

LeetCode-93.复原IP地址

给定一个只包含数字的字符串, 求这个字符串所能分割成的所有合法的IPv4地址.

自己的想法

回溯法, 一个IPv4地址由四个位置组成, for循环横向扩展当前位置的长度, 长度至多为3, 如果当前位置的的字符串合法. 则推入当前的结果当中, 并纵向递归进行后续位置的分割.

结束条件是当前IP的记录满足四个位置, 且已经访问了字符串的所有字符.

题解

class Solution {
private:
    vector<string> result;          // 所有可能的结果
    vector<int> path;               // 当前的IP划分
    int pathLen = 0;                // 已经划分掉的字符数
    bool isValid(const string &s, int start, int end) {
        string str = s.substr(start, end - start + 1);
        if (str[0] == '0' && str.size() > 1) return false;  // 如果开头是0且不止一个字符, 也是不行的
        int num = stoi(str);                                // 懒狗选择使用stoi来转int
        if (num < 256 && num >= 0) return true;             // 大于等于0, 小于256符合条件
        return false;
    }
    
    void backtracing(const string &s, int position, int startIndex) {
        if (path.size() == 4 && pathLen == s.size()) {      // 划分出了4块且所有字符都包含在内时, 才算满足条件
            string addr = "";
            for (int seg : path) addr += to_string(seg) + ".";  // 拼接IPv4地址
            addr.pop_back();                                    // 去掉最后一个'.'
            result.push_back(addr);
            return;
        }

        for (int i = startIndex; i < startIndex + 3 && position < 4 && i < s.size(); i++) { // 横向扩展当前位置的长度
            if (isValid(s, startIndex, i)) { // 如果当前位置的取值合法, 再进行纵向递归
                path.push_back(stoi(s.substr(startIndex, i - startIndex + 1))); // 人生苦短, 我选STL
                pathLen += i - startIndex + 1;  // 统计当前划分的字符数
                backtracing(s, position + 1, i + 1);    // 递归
                path.pop_back();    // 回溯
                pathLen -= i - startIndex + 1;
            }
        }
    }
public:
    vector<string> restoreIpAddresses(string s) {
        backtracing(s, 0, 0);
        return result;
    }
};

78.子集

代码随想录链接

题目

LeetCode-78.子集

给定一个没有重复元素的数组, 返回这个数组的所有子集.

自己的想法

就回溯法, 但记录结果的时机和结束递归的条件需要注意一下.

题解

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracing(vector<int> &nums, int startIndex) {
        result.push_back(path);                     // 不管有什么, 都记录下来
        if (startIndex >= nums.size()) {            // 到头了, 就结束递归
            return;
        }

        for (int i = startIndex; i < nums.size(); i++) {    // for循环横向决定当前位置包含哪个元素
            path.push_back(nums[i]);
            backtracing(nums, i + 1);                       // 子集不能重复使用当前位置的元素, 传入startIndex需要是 i + 1
            path.pop_back();
        }
    }
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        backtracing(nums, 0);
        return result;
    }
};

90.子集II

代码随想录链接

题目

LeetCode-90.子集II

给定一个整数数组, 其中可能包含重复元素, 返回所有可能的子集. 子集中不能重复.

自己的想法

在有重复元素的前提下避免重复子集, 这是与LeetCode-40.组合总和II中一样的要求.

同样地, 我们也可以再次使用那道题避免重复的方法来解决这道题.

题解

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracing(vector<int> &nums, int startIndex, vector<bool> &used) {
        result.push_back(path);         // 不管有什么都记录下来
        if (startIndex >= nums.size()) return;

        for (int i = startIndex; i < nums.size(); i++) {
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue; // 如果和左侧数一样, 且左侧没有被使用, 就跳过自身来避免重复
            path.push_back(nums[i]);
            used[i] = true;         // 标记当前数据已经在当前子集里了
            backtracing(nums, i + 1, used);
            path.pop_back();        // 回溯
            used[i] = false;
        }
    }
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<bool> used(nums.size(), false);
        sort(nums.begin(), nums.end());
        backtracing(nums, 0, used);
        return result;
    }
};