Day24- 回溯算法part04

2024-01-09 13:38:06

一、复原IP地址

题目一:93. 复原IP地址

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?中的任何数字。你可以按?任何?顺序返回答案。

  • 使用回溯法来生成所有可能的 IP 地址。
  • 每个 IP 地址包含四段,每段的数字范围是 0 到 255。
  • 检查每段数字是否合法(不包含前导零,除非该段为 0)。
  • restoreIpAddresses 函数初始化结果集合,并开始回溯。
  • backtrack 函数进行回溯,递归地构建 IP 地址的每一段。
  • 检查每个段的合法性:不以零开头(除非是 0)并且小于等于 255。
  • 当有 4 个合法段且遍历完整个字符串时,将其添加到结果集。
/*
 * @lc app=leetcode.cn id=93 lang=cpp
 *
 * [93] 复原 IP 地址
 */

// @lc code=start
class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> result;
        vector<string> ipAddress;
        backtrack(s, 0, ipAddress, result);
        return result;
    }

private:
    void backtrack(const string& s, int start, vector<string>& ipAddress, vector<string>& result) {
        if (ipAddress.size() == 4) {
            if (start == s.size()) {
                result.push_back(ipAddress[0] + "." + ipAddress[1] + "." + ipAddress[2] + "." + ipAddress[3]);
            }
            return;
        }

        for (int len = 1; len <= 3 && start + len <= s.size(); ++len) {
            string segment = s.substr(start, len);
            if ((segment.size() > 1 && segment[0] == '0') || stoi(segment) > 255) continue;
            ipAddress.push_back(segment);
            backtrack(s, start + len, ipAddress, result);
            ipAddress.pop_back();
        }
    }
};
// @lc code=end

二、子集

题目一:78. 子集

78. 子集

给你一个整数数组?nums?,数组中的元素?互不相同?。返回该数组所有可能的子集(幂集)。

解集?不能?包含重复的子集。你可以按?任意顺序?返回解集。

  • subsets 函数初始化结果列表,并开始回溯过程。
  • backtrack 函数执行回溯。它以递归的方式添加或不添加当前元素,从而构建所有可能的子集。
  • 在每次递归调用中,当前构建的子集被添加到结果列表中。
  • 对于 nums 中的每个元素,选择将其包含在当前子集中或不包含。
  • 当所有元素都被考虑过后,回溯过程结束,得到了所有可能的子集。
/*
 * @lc app=leetcode.cn id=78 lang=cpp
 *
 * [78] 子集
 */

// @lc code=start
class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> current;
        backtrack(nums, 0, current, result);
        return result;
    }

private:
    void backtrack(const vector<int>& nums, int start, vector<int>& current, vector<vector<int>>& result) {
        result.push_back(current);
        for (int i = start; i < nums.size(); ++i) {
            current.push_back(nums[i]);
            backtrack(nums, i + 1, current, result);
            current.pop_back();
        }
    }
};
// @lc code=end

题目二:90. 子集II?

90. 子集 II

给你一个整数数组?nums?,其中可能包含重复元素,请你返回该数组所有可能的子集(幂集)。

解集?不能?包含重复的子集。返回的解集中,子集可以按?任意顺序?排列。

  • subsetsWithDup 函数首先对输入数组进行排序。
  • 使用 backtrack 函数进行回溯,它以递归的方式构建子集。
  • 在每次递归调用中,添加当前构建的子集到结果列表中。
  • 重要的一步是检查并跳过重复元素,这样确保不会生成重复的子集。
  • 对于 nums 中的每个元素,决定是否将其包含在当前子集中。
/*
 * @lc app=leetcode.cn id=90 lang=cpp
 *
 * [90] 子集 II
 */

// @lc code=start
class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end()); 
        vector<vector<int>> result;
        vector<int> current;
        backtrack(nums, 0, current, result);
        return result;
    }

private:
    void backtrack(const vector<int>& nums, int start, vector<int>& current, vector<vector<int>>& result) {
        result.push_back(current);
        for (int i = start; i < nums.size(); ++i) {
            if (i > start && nums[i] == nums[i - 1]) {
                continue;
            }
            current.push_back(nums[i]);
            backtrack(nums, i + 1, current, result);
            current.pop_back();
        }
    }
};
// @lc code=end

文章来源:https://blog.csdn.net/m0_66690787/article/details/135477154
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。