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

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

  • 93. 复原 IP 地址
    • 题目
    • 解法
  • 78. 子集
    • 题目
    • 解法
  • 90. 子集 II
    • 题目
    • 解法
  • 感悟

93. 复原 IP 地址

题目

在这里插入图片描述

解法

  1. 暴力破解,自己初始想法加上看完题解中思想的修补
class Solution {
private:
    vector<string> result;
    string path;
    int num = 0;
    void backtracking(string s, int startIdx) {
        if(startIdx >= s.size() && num == 4) { //终止条件
            result.push_back(path);
            return ;
        }
        if (num > 4) return; // 终止条件
        for (int i = startIdx; i < s.size(); i++) {
            string str = s.substr(startIdx, i - startIdx + 1);
            if (isTrue(str)) {
                if(!path.empty()) path += '.';
                path += str;  
                num += 1;
            } else {
                continue ;
            }
            backtracking(s, i+1);
            int fenge = 0; // 为了刚才移动进来的str
            for(int j = path.size(); j >= 0; j--) {
                if(path[j] == '.') {
                    fenge = j;
                    break;
                }
            }
            if(fenge > 0) {
                path = path.substr(0, fenge); // 回溯
            }else {
                path.clear();
            }  
            num -= 1;
        }
        return ;
    }
    bool isTrue(string str) {
        if (stod(str) < 0 || stod(str) >255) return false;
        
        if(str[0] == '0' && str.size() > 1) return false;
      
        return true;
    }

public:
    
    vector<string> restoreIpAddresses(string s) {
        result.clear();
        path.clear();
        backtracking(s, 0);
        return result;
    }
};

2.使用指针,空间利用率提高,删除很多没必要的循环,时间利用率提高

class Solution {
private:
    vector<string> result;
    // 在合适的位置插入点号就ok
    void backtracking(string& s, int startIdx, int pointNum) {
        // 终止条件
        if (pointNum == 3) {
            if(isValid(s, startIdx, s.size()-1)){
                result.push_back(s);
            }
            return;
        }
        // 单层逻辑
        for (int i = startIdx ; i < s.size() ; i++) {
            if(isValid(s, startIdx, i)){ // 判断 [startIdx, i ]是否符合要求
                s.insert(s.begin() + i + 1, '.');
                pointNum++;
                backtracking(s, i + 2, pointNum );
                pointNum--;
                s.erase(s.begin() + i + 1);// 删除点号
            }else break; // 数字多了,之后肯定就不符合
            
        }
        return ;

    }
    bool isValid(string s, int start, int end){
        if(start > end) return false; // 没有数值

        if(s[start] == '0' && start != end) return false; // 前导有0
        int num = 0;
        for(int i = start; i <= end; i++) {
            if(s[i] > '9' || s[i] < '0') return false; // 出现非数字元素
            num = num*10 + s[i] - '0';
            if(num > 255) return false; // 超过最大数值
        }
        return true;
    }
        

public:
    
    vector<string> restoreIpAddresses(string s) {
        result.clear();
        if (s.size() < 4 || s.size() > 12) return result;
        backtracking(s, 0, 0);
        return result;
    }
};

78. 子集

题目

在这里插入图片描述

解法

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int> nums, int startIdx) {
        result.push_back(path); // 是取所有节点,之前是取叶子节点
        if(startIdx >= nums.size()){ // 
            return;
        }
        for (int i = startIdx; i < nums.size(); i++) {
            path.push_back(nums[i]);
            backtracking(nums, i + 1);
            path.pop_back();
        }
        return ;
    }

public:
    vector<vector<int>> subsets(vector<int>& nums) {
        result.clear();
        path.clear();
        backtracking(nums,0);
        return result;
    }
};

90. 子集 II

题目

在这里插入图片描述

解法

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int> nums, int startIdx, vector<bool> used) {
        result.push_back(path); // 是取所有节点,之前是取叶子节点
        if(startIdx >= nums.size()){ // 
            return;
        }
        for (int i = startIdx; i < nums.size(); i++) {
            if(i > 0 && nums[i] == nums[i-1] && used[i-1] == false) continue;
            path.push_back(nums[i]);
            used[i] = true;
            backtracking(nums, i + 1, used);
            used[i] =false;
            path.pop_back();
        }
        return ;
    }
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        result.clear();
        path.clear();
        vector<bool> used(nums.size(), false);
        sort(nums.begin(), nums.end());
        backtracking(nums,0,used);
        return result;
    }
};

感悟

大道至简,代码写的越繁杂,说明对问题理解和把握越不够透彻。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/469887.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Swift中 any some的作用

前言 在学习Swift ui看到一个函数返回了some view。view我可以理解那some是什么&#xff1f; //ContentView.swift struct ContentView_Previews: PreviewProvider{static var previews: some View{ContentView()} }如果你仔细看一些官方文档甚至还有any关键字&#xff0c;也…

容器数据卷

目录 一、容器数据卷概念 二、使用数据卷 2.1直接使用命令来挂载 三、实战测试 四、具名挂载和匿名挂载 4.1匿名挂载举例&#xff1a; 4.2具名挂载举例&#xff1a; 五、数据卷容器 一、容器数据卷概念 数据&#xff1f;如果数据都在容器中&#xff0c;那么容器删除&am…

使用Anthenticator验证github

下载 各应用商城都有。 准备扫描 启动应用&#xff0c;点击加号&#xff0c;选择其他账户&#xff0c;进入扫描状态。 打开github的二维码 https://github.com/settings/security 下滚&#xff1a; 如图 扫描&#xff0c;添加&#xff0c;完成

SSH服务

目录 一. 熟悉SSH服务 1.1 何为SSH协议 1.2 SSH服务优点 1.3 常见的SSH协议 1.4 SSH服务的功能 1.5 为何使用SSH服务 1.6 SSH服务的工作原理 1.6.1 公钥传输原理 1.6.2 ssh加密通讯原理 1.7 SSH服务的最佳应用场景 1.8 SSH服务远程登录的方式 1.8.1 方法一&#…

逻辑数据平台的 NoETL 之道(内含QA)

作者简介&#xff1a; 余俊&#xff0c;Aloudata 合伙人 & 技术副总裁。拥有 18 年互联网技术和大数据平台相关架构经验。作为主架构师及核心研发主导并完成了 Alibaba B2B 首个海量分布式 KV 存储系统&#xff0c;作为网站架构师负责 Aliexpress 全球买全球卖交易系统的第…

基于Springboot的船运物流管理系统(有报告)。Javaee项目,springboot项目。

演示视频&#xff1a; 基于Springboot的船运物流管理系统&#xff08;有报告&#xff09;。Javaee项目&#xff0c;springboot项目。 项目介绍&#xff1a; 采用M&#xff08;model&#xff09;V&#xff08;view&#xff09;C&#xff08;controller&#xff09;三层体系结构…

springboot企业级抽奖项目-整体展示

项目地址 GitHub - kiorr/lottery: 企业红包雨项目 star截图q&#xff1a;3353441618可以领取资料 原型效果 前台 后台 业务分析 项目介绍 项目概述 京东的红包雨大家可能都参与过&#xff0c;在某段时间内随机发放不同的红包 本项目为一个通用的红包雨模式抽奖系统&…

全国人口密度分布数据

数据福利是专门为关注小编博客及公众号的朋友定制的&#xff0c;未关注用户不享受免费共享服务&#xff0c;已经被列入黑名单的用户和单位不享受免费共享服务。参与本号发起的数据众筹&#xff0c;向本号捐赠过硬盘以及多次转发、评论的朋友优先享有免费共享服务。 对人口数量、…

ARM开发板实现24位BMP图片缩放

ARM开发板实现24位BMP图片缩放 一、linux平台bmp图片缩放 最近想在ARM开发板实现BMP图片的缩放&#xff0c;查看了一些资料&#xff0c;大家部分理论知识可参考&#xff1a; akynazh博主 &#xff0c;这位博主程序以window平台为主进行显示&#xff0c;发现在linux平台下编译…

后端系统开发之——接口参数校验

今天难得双更&#xff0c;大家点个关注捧个场 原文地址&#xff1a;后端系统开发之——接口参数校验 - Pleasure的博客 下面是正文内容&#xff1a; 前言 在上一篇文章中提到了接口的开发&#xff0c;虽然是完成了&#xff0c;但还是缺少一些细节——传入参数的校验。 即用户…

51、CR-GCN:EEG通道拓扑结构+脑功能连接捕获EEG通道关系,用于情感识别[我处理的是原始EEG数据哦]

文章&#xff1a; CR-GCN: Channel-Relationships-Based Graph Convolutional Network for EEG Emotion Recognition 单位&#xff1a; 上海大学计算机学院、上海工业计算机、喀什大学计算机学院。提出CR-GCN&#xff0c;使用GCN的邻接矩阵提取情感数据中的特征用于分类。 2…

分布式搜索引擎elasticsearch专栏三

1.数据聚合 聚合&#xff08;aggregations&#xff09;可以让我们极其方便的实现对数据的统计、分析、运算。例如&#xff1a; 什么品牌的手机最受欢迎&#xff1f; 这些手机的平均价格、最高价格、最低价格&#xff1f; 这些手机每月的销售情况如何&#xff1f; 实现这些…

【双指针】算法例题

目录 二、双指针 25. 验证回文数 ① 26. 判断子序列 ① 27. 两数之和II - 输入有序数组 ② 28. 盛最多水的容器 ② 29. 三数之和 ② 二、双指针 25. 验证回文数 ① 如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后&#xff0c;短语正着读和反着读都一…

面试六分钟,难题显真章

职场&#xff0c;这个充满机遇与挑战的舞台&#xff0c;总会在不经意间上演着意想不到的转折。我从一家小公司转投到另一家&#xff0c;原本期待着新的工作环境和更多的发展机会&#xff0c;然而现实却给了我一个不小的打击。 新公司的加班文化&#xff0c;如同一个巨大的漩涡…

服务器端(Debian 12)配置jupyter与R 语言的融合

融合前&#xff1a; 服务器端Debian 12,域名&#xff1a;www.leyuxy.online 1.安装r-base #apt install r-base 2.进入R并安装IRkernel #R >install.packages(“IRkernel”) 3.通过jupyter notebook的Terminal执行&#xff1a; R >IRkernel::installspec() 报错 解决办…

leetcode 303

leetcode 303 题目 例子 思路 使用数组存储[0, i] 的vals 值之和&#xff0c; sum[i] 表示 第0个元素到第(i-1)个元素之和。 代码 class NumArray {vector<int> sum; public:NumArray(vector<int>& nums) {int n nums.size();sum.resize(n1);for(int i0; …

springboot项目讲解

技术栈 vue(前端) springboot(后端主框架) mybatis&#xff08;ORM&#xff0c;用于后端和数据库的映射&#xff0c;即java对象转换成表&#xff09; mysql (关系型数据库) 顶层结构 .idea&#xff1a; idea缓存文件(不需要管) src&#xff1a;代码核心文件夹 —main&#xf…

进程间通信 之 共享内存

目录 什么是共享内存&#xff1f; 共享内存的系统调用接口 共享内存 进程间通信的本质及前提&#xff1a;让不同的进程看到同一份资源&#xff01; 共享内存区是最快的IPC形式。一旦这样的内存映射到共享它的进程的地址空间&#xff0c;这些进程间数据传递不再涉及到内核&a…

知识学习app

管理端&#xff1a; &#xff08;1&#xff09;登录 &#xff08;2&#xff09;首页数据报表&#xff1a;1.数据概括2.一周数据走势 &#xff08;3&#xff09;内容管理&#xff1a; 1.分类管理&#xff1a;新增&#xff0c;修改&#xff0c;删除&#xff0c;排序 2.八股文&…

基础监控理论

文章目录 监控流程架构体系监控分类 监控发展和技术企业中监控发展阶段通用技术和工具 监控流程架构体系 监控流程架构体系是确保信息系统健康、稳定运行的重要组成部分&#xff0c;它包括监控系统的设计、搭建、数据分析、数据采集、稳定性测试、自动化集成、部署上线以及图形…