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

本文主要是介绍代码随想录算法训练营第二十八天| LeetCode93.复原IP地址 、LeetCode78.子集、LeetCode90.子集II,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

LeetCode 93. Restore IP Addresses

LeetCode 93. 视频讲解:回溯算法如何分割字符串并判断是合法IP?| LeetCode:93.复原IP地址_哔哩哔哩_bilibili

这里返回的数字类型是List<String> 类型,那么可以直接操作String s,可以通过字符串拼接等来生成最终符合IP Addresses 的字符串。这与上一个题目获取回文字符串的思路相似,同样是获得分割后的字符,使用startIndex 来作为分割线。

String.substring 函数的start 和end 是左闭右开的,那么就会有s.substring(0, i + 1) 来获取前i 个字符组成的字符串。在递归的时候,用i + 2,因为包含了新加入的'.' ,递归后使用回溯,用字符串拼接的方法移除掉加入的'.' 。判断是否加入的字符串,需要判断余下的字符串是否符合标准,不是直接添加。

在判断isValid 函数中,通过num = num * 10 + (s.charAt(i) - '0'); 将字符转换成其相应的数字值(s.charAt(i) - '0'),然后加到num上。这里num乘以10的目的是将之前已经构造的数字左移一位,即从个位变十位,十位变百位等,然后添加新的数字到个位。

回溯方法代码:

class Solution {List<String> result = new ArrayList<>();public List<String> restoreIpAddresses(String s) {int pointNum = 0;backtracking(s, 0, pointNum);return result;}public void backtracking (String s, int startIndex, int pointNum) {if (pointNum == 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);pointNum += 1;backtracking(s, i + 2 , pointNum);pointNum -= 1;s = s.substring(0, i + 1) + s.substring(i + 2);}else {break;}}}public boolean isValid(String s, int startIndex, int endIndex) {if (startIndex > endIndex) {return false;}if (s.charAt(startIndex) == '0' && startIndex != endIndex) {return false;}int num = 0;for (int i = startIndex; i <= endIndex; i++) {if (s.charAt(i) > '9' || s.charAt(i) < '0') { // the current character is not a number.return false;}num = num * 10 + (s.charAt(i) - '0');if (num > 255) {return false;}}return true;}
}

LeetCode 78. Subsets

LeetCode 78. 视频讲解:回溯算法解决子集问题,树上节点都是目标集和! | LeetCode:78.子集_哔哩哔哩_bilibili

题目比较简单,考虑组成不同的子集,以及组合不考虑顺序即可。

代码:

class Solution {List<List<Integer>> result = new ArrayList<>();List<Integer> path = new ArrayList<>();public List<List<Integer>> subsets(int[] nums) {backtracking(nums, 0);return result;}public void backtracking(int[] nums, int startIndex) {if (startIndex > nums.length) {return;}result.add(new ArrayList<>(path));for (int i = startIndex; i < nums.length; i++) {path.add(nums[i]);backtracking(nums, i + 1);path.remove(path.size() - 1);}}
}

LeetCode 90. Subsets II

LeetCode 90. 视频讲解:回溯算法解决子集问题,如何去重?| LeetCode:90.子集II_哔哩哔哩_bilibili

与上一个题目的区别是,这个题目需要考虑去重的问题。题目比较简单,与之前的去重问题考虑一致,用一个used 数组来标记。

代码:

class Solution {List<List<Integer>> result = new ArrayList<>();List<Integer> path = new ArrayList<>();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;}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]) {continue;}path.add(nums[i]);used[i] = true;backtracking(nums, i + 1, used);path.remove(path.size() - 1);used[i] = false;}}
}

这篇关于代码随想录算法训练营第二十八天| LeetCode93.复原IP地址 、LeetCode78.子集、LeetCode90.子集II的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/990231

相关文章

Go语言开发实现查询IP信息的MCP服务器

《Go语言开发实现查询IP信息的MCP服务器》随着MCP的快速普及和广泛应用,MCP服务器也层出不穷,本文将详细介绍如何在Go语言中使用go-mcp库来开发一个查询IP信息的MCP... 目录前言mcp-ip-geo 服务器目录结构说明查询 IP 信息功能实现工具实现工具管理查询单个 IP 信息工具的实现服

利用Python调试串口的示例代码

《利用Python调试串口的示例代码》在嵌入式开发、物联网设备调试过程中,串口通信是最基础的调试手段本文将带你用Python+ttkbootstrap打造一款高颜值、多功能的串口调试助手,需要的可以了... 目录概述:为什么需要专业的串口调试工具项目架构设计1.1 技术栈选型1.2 关键类说明1.3 线程模

Python Transformers库(NLP处理库)案例代码讲解

《PythonTransformers库(NLP处理库)案例代码讲解》本文介绍transformers库的全面讲解,包含基础知识、高级用法、案例代码及学习路径,内容经过组织,适合不同阶段的学习者,对... 目录一、基础知识1. Transformers 库简介2. 安装与环境配置3. 快速上手示例二、核心模

Java的栈与队列实现代码解析

《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念(Stack)栈的实现代码队列(Queue)模拟实现队列(双链表实现)循环队列(循环数组

使用Java将DOCX文档解析为Markdown文档的代码实现

《使用Java将DOCX文档解析为Markdown文档的代码实现》在现代文档处理中,Markdown(MD)因其简洁的语法和良好的可读性,逐渐成为开发者、技术写作者和内容创作者的首选格式,然而,许多文... 目录引言1. 工具和库介绍2. 安装依赖库3. 使用Apache POI解析DOCX文档4. 将解析

C++使用printf语句实现进制转换的示例代码

《C++使用printf语句实现进制转换的示例代码》在C语言中,printf函数可以直接实现部分进制转换功能,通过格式说明符(formatspecifier)快速输出不同进制的数值,下面给大家分享C+... 目录一、printf 原生支持的进制转换1. 十进制、八进制、十六进制转换2. 显示进制前缀3. 指

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

Python中使用正则表达式精准匹配IP地址的案例

《Python中使用正则表达式精准匹配IP地址的案例》Python的正则表达式(re模块)是完成这个任务的利器,但你知道怎么写才能准确匹配各种合法的IP地址吗,今天我们就来详细探讨这个问题,感兴趣的朋... 目录为什么需要IP正则表达式?IP地址的基本结构基础正则表达式写法精确匹配0-255的数字验证IP地

使用Python实现全能手机虚拟键盘的示例代码

《使用Python实现全能手机虚拟键盘的示例代码》在数字化办公时代,你是否遇到过这样的场景:会议室投影电脑突然键盘失灵、躺在沙发上想远程控制书房电脑、或者需要给长辈远程协助操作?今天我要分享的Pyth... 目录一、项目概述:不止于键盘的远程控制方案1.1 创新价值1.2 技术栈全景二、需求实现步骤一、需求

Java中Date、LocalDate、LocalDateTime、LocalTime、时间戳之间的相互转换代码

《Java中Date、LocalDate、LocalDateTime、LocalTime、时间戳之间的相互转换代码》:本文主要介绍Java中日期时间转换的多种方法,包括将Date转换为LocalD... 目录一、Date转LocalDateTime二、Date转LocalDate三、LocalDateTim