当前位置: 首页 > article >正文

算法打卡 Day29(回溯算法)-复原 IP 地址 + 子集 + 子集 Ⅱ

文章目录

  • Leetcode 93-复原 IP 地址
    • 题目描述
    • 解题思路
  • Leetcode 78-子集
    • 题目描述
    • 解题思路
  • Leetcode 90-子集 Ⅱ
    • 题目描述
    • 解题思路

Leetcode 93-复原 IP 地址

题目描述

https://leetcode.cn/problems/restore-ip-addresses/description/

在这里插入图片描述

解题思路

这是一道切割问题,可以参考分割回文串的思路

采用 isValid 函数判断当前切割得到的子串是否有效

class Solution {
public:
    vector<string> res;
    bool isValid(string s, int start, int end){
        if(start > end) return false;
        if (s[start] == '0' && end - start > 0) return false;
        if (end - start + 1 > 3) return false; // 添加长度检查
        string sub = s.substr(start, end-start+1);
        int num = stoi(sub);
        if (num > 255) return false;
        return true;
    }
    void backTracking(string s, int startIndex, int dotNum){
        if(dotNum == 3){
            if (isValid(s, startIndex,s.size()-1)){
                res.push_back(s);
            }
            return;
        }
        for (int i = startIndex; i< startIndex+3 && i <s.size();i++){
            if (isValid(s, startIndex,i)){
                s.insert(s.begin()+i+1,'.');
                dotNum += 1;
                backTracking(s, i + 2, dotNum);
                dotNum -= 1;
                s.erase(s.begin()+i+1);
            }
        }
    }
    vector<string> restoreIpAddresses(string s) {
        backTracking(s,0,0);
        return res;
    }
};

Leetcode 78-子集

题目描述

https://leetcode.cn/problems/subsets/description/

在这里插入图片描述

解题思路

在子集问题中需要在每一层递归中进行结果的收集

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

Leetcode 90-子集 Ⅱ

题目描述

https://leetcode.cn/problems/subsets-ii/description/

在这里插入图片描述

解题思路

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

http://www.kler.cn/a/290942.html

相关文章:

  • curl也支持断点续传
  • OpenHarmony-6.IPC/RPC组件
  • 拆解一个微型气泵了解工作原理
  • 冯诺依曼架构与哈佛架构的对比与应用
  • 中国量子计算机领域的发展现状与展望
  • 计算机毕业设计原创定制(免费送源码):NodeJS+MVVM+MySQL 樱花在线视频网站
  • Gin框架中的全局中间件与中间件传值
  • IDEA 安装lombok插件不兼容的问题及解决方法
  • 【弱监督时间动作定位】Probabilistic Vision-Language Representation for WSTAL 论文阅读
  • Linux shell调试:高效定位错误提高脚本可靠性
  • 修改SpringBoot启动图标banner
  • 使用AI写WebSocket知识是一种怎么样的体验?
  • 17. 如何决定使用ArrayList或LinkedList?在什么情况下选择其中之一?
  • 【Linux】进程周边:进程概念
  • RabbitMQ 入门:基本概念、特性及简单示例
  • 职场关系课:辞退下属的行动指南
  • 智能医学(二)——MDPI特刊推荐
  • HarmonyOS开发实战( Beta5.0)自定义组件冻结功能规范
  • flowable 国产数据库并发性能优化
  • Linux 学习之路 - 信号的保存
  • BUUCTF Crypto wp--RSA1
  • 记一种常用的实时数据同步方案:Canal+Kafka+Flume
  • Nacos Config的配置中心
  • react文件详情
  • 去中心化身份(DID)与你:SOEX安全的交易未来
  • three.js 图片加载器