[代码随想录Day24打卡] 93.复原IP地址 78.子集 90.子集II

93.复原IP地址

一个合法的IP地址是什么样的：
有3个’.'分割得到4个数，每个数第一个数不能是0，不能含有非法字符，不能大于255。
在这里插入图片描述
这个是否属于合法IP相当于一个分割问题，把一串字符串分割成4部分，分别判断每个部分是否合法，如果全部合法就保存结果，否则就return;
回溯三部曲：

  1. 确定参数和返回值：参数要处理的字符串s,startIndex来防止我们重复分割和pointNum存储当前加的’.‘的个数。我们把path（存储当前的字符串）和result(存储加了’.'符合合法IP条件的字符串的结果列表）定义为了全局变量所以不需要返回值。
  2. 递归终止条件：if(pointNum==3)说明我们已经加了三个’.'，然后直接判断最后一个数字是否合法，如果合法就保存结果，如果不合法就return。
  3. 单层递归逻辑：我们就是把整体字符串分段，分别判断每一段分割结果是否合法，如果合法就往字符串中加’.'，并且递归调用backtracking进行下一次分割如果不合法就直接return不操作。
    当前分割的结果：startIndex指明当前循环中开始位置在这个循环过程中是不变的，i不断地向右循环，[startIndex, i]就是当前处理的字符串（就是IP地址中的一段，那段数字，我们只需要判断这段数字是否合法就可以）。
    分割标志：startIndex就是相当于分割标志，指明了前一次分割的位置。
    下面是C++、JAVA、Python的代码。
class Solution {
private:
    vector<string> result;
    bool isValid(const string& s, int start, int end){
        if(start>end){
            return false;
        }
        if(s[start]=='0' && start != end){//0开头的数字不合法
            return false;
        }
        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){
                //数字大于255不合法
                return false;
            }
        }
        return true;
    }
    void backtracking(string& s, int startIndex, int pointSum){
        if(pointSum == 3){
            //对最后一段的合法性进行判断
            if(isValid(s, startIndex, s.size()-1)){//
                result.push_back(s);
            }
            return;
        }//递归终止条件
        for(int i = startIndex; i < s.size(); i++){//单层递归
            if(isValid(s, startIndex, i)){
                s.insert(s.begin()+i+1, '.');
                pointSum += 1;
                backtracking(s, i+2, pointSum);
                s.erase(s.begin()+i+1);
                pointSum-=1;
            }
        }
    }
public:
    vector<string> restoreIpAddresses(string s) {
        if (s.size() < 4 || s.size() > 12) return result;
        backtracking(s, 0, 0);
        return result;
    }
};

class Solution {
    List<String> result = new ArrayList<>();//建立一个列表存储最终结果
    public List<String> restoreIpAddresses(String s) {
        backtracking(s, 0, 0);
        return result;
    }
    private void backtracking(String s, int startIndex, int pointNum){
        if(pointNum == 3){
            //如果逗号数量为3停止向下递归
            if(isValid(s, startIndex, s.length()-1)){
                result.add(s);
            }
            return;
        }
        for(int i = startIndex; i < s.length(); i++){//单层递归逻辑
            if(isValid(s, startIndex, i)){
                //如果合法
                s = s.substring(0, i+1) + "." + s.substring(i + 1);//在str的后面插入"."
                pointNum++;
                backtracking(s, i+2, pointNum);//
                pointNum--;//回溯
                s = s.substring(0, i+1) + s.substring(i+2);//回溯删掉逗点，substring一个参数是从beginIndex开始到末尾，有两个参数从 beginIndex 开始到 endIndex 结束前（不包括 endIndex）提取子字符串
            }else{
                break;
            }
        }
    }
    //判断字符串s在左闭右闭区间[start, end]所组成的数字是否合法
    private Boolean isValid(String s, int start, int end){
        if(start > end){
            return false;
        }//start和end本身就不合法
        if(s.charAt(start) == '0' && start != end){
            //0开头的数字不合法
            return false;
        }
        int num = 0;//这个是存储从字符串变成数字的数字
        for(int i = start; i <= end; i++){
            //判断每个字符的合法性
            if(s.charAt(i) > '9' || s.charAt(i)<'0'){
                return false;
            }
            num = num*10 + (s.charAt(i)-'0');//这个就是计算当前的数字
            if(num > 255){
                //如果大于255了不合法
                return false;
            }
        }
        return true;
    }
}

class Solution(object):
    def __init__(self):
        self.result = []
    def restoreIpAddresses(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        if(len(s)<4 or len(s)>12):
            return self.result
        self.backtracking(s, 0, 0)
        return self.result
    def backtracking(self, s, startIndex, pointNum):
        #递归终止条件
        if(pointNum == 3):
            if(self.isValid(s, startIndex, len(s)-1)):
                self.result.append(s)#如果合法就存入
        for i in range(startIndex, len(s)):
            if(self.isValid(s, startIndex, i)):
                s = s[:i+1]+'.'+s[i+1:]
                pointNum+=1#往字符串中加入一个点
                self.backtracking(s, i+2, pointNum)
                s = s[:i+1] + s[i+2:]
                pointNum -= 1#回溯
    def isValid(self, s, start, end):#判断所给字符的合法性，左闭右闭区间
        #首先判断传入的参数是否合法
        if(start > end):
            return False
        #判断是否开头有0
        if s[start] == '0' and start!=end:
            return False
        num = 0#这个是存储当前这个子串对应的数值的
        for i in range(start, end+1):
            if s[i]>'9' or s[i]<'0':
                return False #判断每个字符是否合法
            num = num*10 + int(s[i])
            if(num > 255):
                return False#超出255非法
        return True

参考文章

  1. https://programmercarl.com/0093.%E5%A4%8D%E5%8E%9FIP%E5%9C%B0%E5%9D%80.html

78.子集

在这里插入图片描述遍历这个树的时候，把所有节点都记录下来，就是要求的子集集合。
注意：这个题目时每个节点的结果都要保存，不是只保存叶子节点。其他的和组合差不多。
回溯三部曲：
1. 确定参数和返回值：参数就是数组nums和startIndex指示之前使用了那些元素，防止重复取数。我们把path金额result定义为全局变量，所以不需要返回值。
2. 遍历终止条件：startIndex>= nums.size() return;就是如果startIndex超出了数组的范围就停止递归。
单层递归的逻辑：i从startIndex到nums.size()遍历，每次遍历都把nums[i]当前元素加入到path当前结果中，然后backtracking()继续下层递归，然后path.pop_back()回溯。

class Solution {
private:
    vector<int> path;
    vector<vector<int>> result;
    void backtracking(vector<int>& nums, int startIndex){
        result.push_back(path);
        if(startIndex>= nums.size()) return;//递归终止条件
        for(int i = startIndex; 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) {
        backtracking(nums, 0);
        return result;
    }
};

class Solution {
    List<Integer> path = new LinkedList<>();
    List<List<Integer>> result = new ArrayList<>();
    public void backtracking(int[] nums, int startIndex){
        result.add(new ArrayList<>(path));
        if(startIndex>=nums.length){
            return;//递归终止条件
        }
        for(int i=startIndex; i < nums.length; i++){
            path.add(nums[i]);
            backtracking(nums, i+1);
            path.removeLast();
        }

    }
    public List<List<Integer>> subsets(int[] nums) {
        backtracking(nums, 0);
        return result;
    }
}

class Solution(object):
    def __init__(self):
        self.result = []
        self.path = []
    def backtracking(self, nums, startIndex):
        self.result.append(list(self.path))#别忘了这个加list为了就是不指向同一个地址
        if(startIndex>=len(nums)):
            return
        for i in range(startIndex, len(nums)):
            self.path.append(nums[i])#存入元素
            self.backtracking(nums, i+1)
            self.path.pop()
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        self.backtracking(nums, 0)
        return self.result

参考文章

  1. https://programmercarl.com/0078.%E5%AD%90%E9%9B%86.html

90.子集II

在这里插入图片描述
这个就是子集和组合Ⅱ的应用。
秒了。
注意：

  1. 对于有重复元素的题目，要去重，先排序。
  2. 设置used数组来判断时树枝还是树层。每个语言怎么定义要清楚。
  3. 保存结果的时候要根据每个语言，JAVA和Python都是需要处理一下path再加入到result中，不然result中的元素都指向同一个位置，最后结果都[]
  4. 去重的两行代码要记住。

回溯三部曲：

  1. 确定参数和返回值：参数时数组nums和startIndex，返回值为None。
  2. 递归终止条件：看startIndex是否越界，如果越界就直接返回。没有也可以，因为后面for循环也会因为startIndex越界不运行直接return。
  3. 单层递归逻辑：加入去重的两行代码if(i>0 && nums[i]==nums[i-1] && used[i-1]==0)continue;（直接跳过，到不是重复的数，不是break，break会漏掉重复数字之后的所有的数字）然后把当前数字放到path中，更新used使当前索引的位置used[i]=true，然后backtracking()递归处理下一个数，path.pop(),used[i]=false回溯一下。
class Solution {
private:
    vector<int> path;
    vector<vector<int>> result;
    void backtracking(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>startIndex && nums[i]==nums[i-1] && used[i-1]==0){
                continue;//跳过重复元素
            }
            path.push_back(nums[i]);
            used[i] = true;
            backtracking(nums, i+1, used);
            used[i] = false;
            path.pop_back();
        }
    }
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<bool> used(nums.size(), false);
        sort(nums.begin(), nums.end());
        backtracking(nums, 0, used);
        return result;
    }
};

class Solution {
    List<Integer> path = new LinkedList<>();
    List<List<Integer>> result = new ArrayList<>();
    public void backtracking(int[] nums, int startIndex, boolean[] used){
        result.add(new ArrayList<>(path));
        //想想递归终止条件
        if(startIndex>=nums.length) return;
        for(int i = startIndex; i< nums.length; i++){
            if(i>0 && nums[i] == nums[i-1] && used[i-1] == false){
                continue;
            }
            path.add(nums[i]);
            used[i] = true;
            backtracking(nums, i+1, used);
            used[i] = false;
            path.removeLast();
        }
    }
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        boolean[] used = new boolean[nums.length];
        Arrays.fill(used, false);
        Arrays.sort(nums);
        backtracking(nums, 0, used);
        return result;
    }
}

class Solution(object):
    def __init__(self):
        self.result = []
        self.path = []
    def backtracking(self, nums, startIndex, used):
        self.result.append(list(self.path))
        if(startIndex>=len(nums)):#递归终止条件也可以不写
            return
        for i in range(startIndex, len(nums)):
            if(i>startIndex and nums[i] == nums[i-1] and not used[i-1]):
                continue#去重
            self.path.append(nums[i])
            used[i] = True
            self.backtracking(nums, i+1, used)
            used[i] = False
            self.path.pop()
    def subsetsWithDup(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums.sort()#别忘了排序
        used = [False]*len(nums)
        self.backtracking(nums, 0, used)
        return self.result

参考文章

  1. https://programmercarl.com/0090.%E5%AD%90%E9%9B%86II.html

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

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

相关文章

v-for产生 You may have an infinite update loop in a component render function

v-for产生 You may have an infinite update loop in a component render function

参考文章&#xff1a; 报错解析 [Vue warn]: You may have an infinite update loop in a component render function. 另外一个解决方法 例如: MyList 是一个数组&#xff0c;我希望将排序后的结果返回进行for循环&#xff0c;因此设计了一个myMethon函数 <div v-for"…
阅读更多...
中国前首富胡志标亮相创客匠人盛会，点燃创始人 IP 新思维火花

中国前首富胡志标亮相创客匠人盛会，点燃创始人 IP 新思维火花

创客匠人正式官宣&#xff01;原爱多VCD创始人、中国前首富胡志标受邀出席创客匠人5000人“全球创始人IP领袖高峰论坛”&#xff0c;将与我们携手共赴这场商业巅峰盛宴。 由创客匠人打造的“全球创始人IP领袖高峰论坛”将在2024年12月26日-28日在厦门市国际博览会议中心如期举…
阅读更多...
qsort函数详解+代码展示

qsort函数详解+代码展示

文章目录 概要系列文章目录前言(1) 定义(2) 使用&#xff08;举例子 上代码&#xff09;1、定义数组&#xff1a;2、定义比较函数&#xff1a;3、调用 qsort&#xff1a;4、输出结果&#xff1a; (3) 注意事项 小结 概要 本篇博客将详细地介绍qsort排序函数&#xff0c;&#x…
阅读更多...
CSS之3D转换

CSS之3D转换

三维坐标系 三维坐标系其实就是指立体空间&#xff0c;立体空间是由3个轴共同组成的。 x轴:水平向右注意:x右边是正值&#xff0c;左边是负值 y轴:垂直向下注意:y下面是正值&#xff0c;上面是负值 z轴:垂直屏幕注意:往外面是正值&#xff0c;往里面是负值 3D移动 translat…
阅读更多...
2024年nvm保姆级安装教程

2024年nvm保姆级安装教程

需求&#xff1a;当前我的nodejs的版本是6.14.10&#xff0c;想切换为更高的版本。故使用nvm工具来实现不同node版本之间的切换 目录 一、删除node二、nvm安装三、配置nvm镜像四、安装所需要的nodejs版本nvm常用命令 一、删除node 第一步&#xff1a;首先在控制面板删除node.j…
阅读更多...
Python编程语言中的优雅艺术：数值分隔符的巧妙运用

Python编程语言中的优雅艺术：数值分隔符的巧妙运用

在Python编程的世界里&#xff0c;有许多精巧的设计让代码更优雅、更易读。今天要分享的是一个看似简单却能大幅提升代码可读性的特性 —— 数值分隔符。这个特性从Python 3.6版本开始引入&#xff0c;它用一种极其优雅的方式解决了大数值表示的难题。 数值分隔符的本质与应用…
阅读更多...
JS-06-事件监听

JS-06-事件监听

事件监听 当鼠标进行操作的时候能够对网页页面进行操作。 事件绑定 常见事件 onload: 当某个页面或者元素加载完成之后执行指定的代码块 onclick:鼠标单机的时候就执行指定的代码块 onblur\onfocus:鼠标点击的时候光标在的地方就是获得焦点否则失去焦点 onkeydown:绑定键盘…
阅读更多...
Adaboost集成学习 | Python实现基于NuSVR-Adaboost多输入单输出回归预测

Adaboost集成学习 | Python实现基于NuSVR-Adaboost多输入单输出回归预测

目录 效果一览基本介绍程序设计参考资料效果一览 基本介绍 基于NuSVR-Adaboost多输入单输出回归预测python代码 NuSVR是一种支持向量回归（SVR）算法的变体，用于解决回归问题。SVR是一种监督学习方法，它用于预测连续目标变量，而不是分类标签。NuSVR在SVR的基础上引入了一个…
阅读更多...
数据结构C语言描述5(图文结合)--队列，数组、链式、优先队列的实现

数据结构C语言描述5(图文结合)--队列，数组、链式、优先队列的实现

前言 这个专栏将会用纯C实现常用的数据结构和简单的算法&#xff1b;有C基础即可跟着学习&#xff0c;代码均可运行&#xff1b;准备考研的也可跟着写&#xff0c;个人感觉&#xff0c;如果时间充裕&#xff0c;手写一遍比看书、刷题管用很多&#xff0c;这也是本人采用纯C语言…
阅读更多...
ADS9-V2EBZ 评估板

ADS9-V2EBZ 评估板

ADS9-V2EBZ 评估板 概览 优势和特点 Xilinx Kintex Ultrascale XCKU15P-2FFVE1517E FPGA。 1 个 FMC 连接器。 20 个 28 Gbps 收发器&#xff0c;由一 (1) 个 FMC 连接器提供支持 HMC DRAM 简单 USB 3.0 端口接口。 随附两张微型 SD 卡&#xff0c;“TRX”用于 ADRV9026 评估…
阅读更多...
深入探讨 Redis 持久化机制：原理、配置与优化策略

深入探讨 Redis 持久化机制：原理、配置与优化策略

文章目录 一、引言二、Redis持久化概述三、RDB&#xff08;Redis DataBase&#xff09;持久化1、RDB概念与工作原理2、RDB的配置选项3、RDB优化配置项4、RDB的优势与劣势 三、AOF&#xff08;Append-Only File&#xff09;持久化1、AOF概念与工作原理2、AOF的三种写回策略3、Re…
阅读更多...
【回文数组——另类递推】

【回文数组——另类递推】

题目 代码 #include <bits/stdc.h> using namespace std; using ll long long; const int N 1e510; int a[N], b[N]; int main() {int n;cin >> n;for(int i 1; i < n; i)cin >> a[i];for(int i 1; i < n / 2; i)b[i] a[i] - a[n1-i];ll ans 0;…
阅读更多...
scala统计词频

scala统计词频

package test23import java.io.PrintWriter import scala.io.Source object test {def main(args: Array[String]): Unit {//从文件1.txt中&#xff0c;读取内容val content Source.fromFile("1.txt").mkStringprintln(content)//把字符串中的每个单词&#xff0c;…
阅读更多...
数据结构——排序算法第二幕（交换排序：冒泡排序、快速排序（三种版本） 归并排序：归并排序（分治））超详细！！！！

数据结构——排序算法第二幕（交换排序：冒泡排序、快速排序（三种版本） 归并排序：归并排序（分治））超详细！！！！

文章目录 前言一、交换排序1.1 冒泡排序1.2 快速排序1.2.1 hoare版本 快排1.2.2 挖坑法 快排1.2.3 lomuto前后指针 快排 二、归并排序总结 前言 继上篇学习了排序的前面两个部分:直接插入排序和选择排序 今天我们来学习排序中常用的交换排序以及非常稳定的归并排序 快排可是有多…
阅读更多...
Android基本概念及控件

Android基本概念及控件

Android是Google公司基于Linux平台开发的主要应用于智能手机及平板电脑的操作系统。 ART模式与Dalvik模式最大的不同在于:在启用ART模式后&#xff0c;系统在安装应用程序的时候会进行一次预编译&#xff0c;并先将代码转换为机器语言存储在本地,这样在运行程序时就不会每次都…
阅读更多...
【JavaEE初阶 — 网络编程】Socket 套接字 ＆ UDP数据报套接字编程

【JavaEE初阶 — 网络编程】Socket 套接字 ＆ UDP数据报套接字编程

1. Socket套接字 1.1 概念 Socket 套接字&#xff0c;是由系统提供用于网络通信的技术&#xff0c;是基于TCP / IP协议的网络通信的基本操作单元。基于 Socket 套接字的网络程序开发就是网络编程。 1.2 分类 Socket套接字主要针对传输层协议划分为如下三类&#x…
阅读更多...
Leecode刷题C语言之交替组②

Leecode刷题C语言之交替组②

执行结果:通过 执行用时和内存消耗如下&#xff1a; 代码如下&#xff1a; int numberOfAlternatingGroups(int* colors, int colorsSize, int k) {int res 0, cnt 1;for (int i -k 2; i < colorsSize; i) {if (colors[(i colorsSize) % colorsSize] ! colors[(i - …
阅读更多...
科技惊艳：RFID技术引领被装物联网信息化革新

科技惊艳：RFID技术引领被装物联网信息化革新

被装物联网信息化监控系统是一项错综复杂却成效斐然的解决方案&#xff0c;它巧妙地将物联网技术的先进性与装设备资源管理的实际需求相融合&#xff0c;实现了对被装设备资源的即时追踪、智能化调控以及资源的最优化配置。以下是对被装物联网的深度剖析与高端解读&#xff1a;…
阅读更多...
360推出全新的生成式 AI 搜索产品：纳米搜索，要重塑搜索产品

360推出全新的生成式 AI 搜索产品：纳米搜索，要重塑搜索产品

【大力财经】直击互联网最前线&#xff1a;360 集团在 2024 年 11 月 27 日开发布会&#xff0c;重磅推出了一款全新的生成式 AI 搜索产品——纳米搜索&#xff0c;并且已经上架到苹果 App Store 以及应用宝等安卓应用商店&#xff0c;直接与百度、阿里夸克、秘塔 AI、Perplexi…
阅读更多...
Android Deep Links 深度链接解析

Android Deep Links 深度链接解析

在实现 Android 应用链接之前&#xff0c;请务必了解您可以在 Android 应用中创建的不同类型的链接&#xff1a;深层链接、网页链接和 Android 应用链接。 Android Deep Links 深度链接解析 一、什么是Deep Links&#xff1f;二、Deep Links的优势三、Deep Links的实现方式1. …
阅读更多...
最新文章

Copyright @ 2022~2023