力扣热门算法题 89. 格雷编码,92. 反转链表 II,93. 复原 IP 地址

2024-03-26 07:44

本文主要是介绍力扣热门算法题 89. 格雷编码,92. 反转链表 II,93. 复原 IP 地址,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

89. 格雷编码,92. 反转链表 II,93. 复原 IP 地址,每题做详细思路梳理,配套Python&Java双语代码, 2024.03.24 可通过leetcode所有测试用例。

目录

89. 格雷编码

解题思路

完整代码

Python

Java

92. 反转链表 II

解题思路

完整代码

Python

Java

93. 复原 IP 地址

解题思路

完整代码

Python

Java


89. 格雷编码

n 位格雷码序列 是一个由 2n 个整数组成的序列,其中:

  • 每个整数都在范围 [0, 2n - 1] 内(含 0 和 2n - 1
  • 第一个整数是 0
  • 一个整数在序列中出现 不超过一次
  • 每对 相邻 整数的二进制表示 恰好一位不同 ,且
  • 第一个 和 最后一个 整数的二进制表示 恰好一位不同

给你一个整数 n ,返回任一有效的 n 位格雷码序列 。

示例 1:

输入:n = 2
输出:[0,1,3,2]
解释:
[0,1,3,2] 的二进制表示是 [00,01,11,10] 。
- 00 和 01 有一位不同
- 01 和 11 有一位不同
- 11 和 10 有一位不同
- 10 和 00 有一位不同
[0,2,3,1] 也是一个有效的格雷码序列,其二进制表示是 [00,10,11,01] 。
- 00 和 10 有一位不同
- 10 和 11 有一位不同
- 11 和 01 有一位不同
- 01 和 00 有一位不同

示例 2:

输入:n = 1
输出:[0,1]

解题思路

要生成一个 n 位的格雷码序列,我们可以使用递归的方法。格雷码有一个很有趣的性质,即可以通过 n-1 位的格雷码来生成 n 位的格雷码。这种方法称为反射法,其步骤如下:

  1. 开始于基础情况:当 n = 1 时,格雷码序列是 [0, 1]。
  2. 递归生成 n-1 位的格雷码序列:对于 n > 1,首先生成 n-1 位的格雷码序列。
  3. 复制并反射:将 n-1 位的格雷码序列复制一份,并反转这个副本,以保持相邻数字只有一位二进制差异。
  4. 添加高位 1:在反转的副本序列的每个数字前添加一个高位的 1,而在原始序列的每个数字前添加一个高位的 0(实际上不需要操作,因为默认高位就是0)。
  5. 合并序列:最后将这两个序列合并,得到 n 位的格雷码序列。

完整代码

Python
class Solution:def grayCode(self, n: int) -> List[int]:if n == 0:return [0]# 递归生成 n-1 位的格雷码prev_gray = self.grayCode(n - 1)result = []# 将前一序列的值添加进结果,前面加0(实际不操作,因为默认就是0)result.extend(prev_gray)# 反射并添加高位的1for code in reversed(prev_gray):result.append(code | 1 << (n - 1))return result
Java
class Solution {public List<Integer> grayCode(int n) {List<Integer> result = new ArrayList<>();// 基础情况:n=1if (n == 0) {result.add(0);return result;}// 递归生成 n-1 位的格雷码List<Integer> prevGray = grayCode(n - 1);// 添加低位的格雷码result.addAll(prevGray);// 添加高位的 1 并反射int addNumber = 1 << (n - 1);for (int i = prevGray.size() - 1; i >= 0; i--) {result.add(prevGray.get(i) + addNumber);}return result;}}

92. 反转链表 II

​给你单链表的头指针 head 和两个整数 left 和 right ,其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点,返回 反转后的链表 。

示例 1:

输入:head = [1,2,3,4,5], left = 2, right = 4
输出:[1,4,3,2,5]

示例 2:

输入:head = [5], left = 1, right = 1
输出:[5]

提示:

  • 链表中节点数目为 n
  • 1 <= n <= 500
  • -500 <= Node.val <= 500
  • 1 <= left <= right <= n

进阶: 你可以使用一趟扫描完成反转吗?

解题思路

要在链表中反转从位置 left 到位置 right 的节点,可以通过一次遍历来实现。这个过程大致可以分为以下几个步骤:

  1. 定位到 left:首先,遍历链表直到到达位置 left。我们需要记录这个位置的前一个节点,因为反转之后,left 节点将会连接到 left 前一个节点上。

  2. 反转 left 到 right:从 left 开始,遍历到 right,并在遍历过程中逐个反转节点的指向。我们需要记录 left 节点,因为反转后,它将指向 right 节点之后的节点。

  3. 重连链表:最后,将链表的未反转部分与反转后的部分正确连接起来。

完整代码

Python
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:if not head or left == right:return headdummy = ListNode(0, head)prev = dummy# Step 1: 定位到 left 的前一个节点for _ in range(left - 1):prev = prev.next# Step 2: 开始反转reverse = Nonecurrent = prev.nextfor _ in range(right - left + 1):next_temp = current.nextcurrent.next = reversereverse = currentcurrent = next_temp# Step 3: 重连链表prev.next.next = currentprev.next = reversereturn dummy.next
Java
/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode reverseBetween(ListNode head, int left, int right) {if (head == null || left == right) {return head;}ListNode dummy = new ListNode(0);dummy.next = head;ListNode prev = dummy;// Step 1: 定位到 left 的前一个节点for (int i = 0; i < left - 1; i++) {prev = prev.next;}// Step 2: 开始反转ListNode start = prev.next;ListNode then = start.next;for (int i = 0; i < right - left; i++) {start.next = then.next;then.next = prev.next;prev.next = then;then = start.next;}// Step 3: 链表已经在反转过程中正确连接,不需要额外操作return dummy.next;}
}

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

示例 1:

输入:s = "25525511135"
输出:["255.255.11.135","255.255.111.35"]

示例 2:

输入:s = "0000"
输出:["0.0.0.0"]

示例 3:

输入:s = "101023"
输出:["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

提示:

  • 1 <= s.length <= 20
  • s 仅由数字组成

解题思路

生成所有可能的有效 IP 地址,可以通过回溯算法来解决。这个问题的关键在于逐步构建 IP 地址的每一部分,并在每一步中确保该部分是有效的。具体步骤如下:

  1. 定义回溯函数:定义一个回溯函数,该函数接收当前构造的 IP 地址部分、剩余的字符串和已经确定的段数作为参数。

  2. 结束条件:当已经确定了 4 段 IP 地址并且消耗完了输入字符串时,将当前构建的 IP 地址添加到结果集中。

  3. 递归和回溯:从输入字符串中选择 1 到 3 个字符作为当前段的候选,如果选择的字符串是有效的 IP 段(0-255,且无前导 0,除非是单独的 0),则递归地继续选择下一段。

  4. 有效性检查:检查当前选择的字符串是否形成一个有效的 IP 地址段。

  5. 剪枝:在某些情况下提前终止搜索,例如,如果剩余的字符串太长或太短,无法形成有效的剩余段。

完整代码

Python
class Solution:def restoreIpAddresses(self, s: str) -> List[str]:def isValid(segment):# 检查 IP 段的有效性return len(segment) == 1 or (segment[0] != '0' and int(segment) <= 255)def backtrack(start=0, parts=[]):# 如果找到了 4 部分,并且用完了所有字符if len(parts) == 4 and start == len(s):result.append('.'.join(parts))returnif len(parts) == 4 or start == len(s):return# 尝试每一部分的长度:1, 2, 或 3for end in range(start + 1, min(start + 4, len(s) + 1)):segment = s[start:end]if isValid(segment):backtrack(end, parts + [segment])result = []backtrack()return result
Java
public class Solution {public List<String> restoreIpAddresses(String s) {List<String> result = new ArrayList<>();void backtrack(int start, List<String> parts) {if (parts.size() == 4 && start == s.length()) {result.add(String.join(".", parts));return;}if (parts.size() == 4 || start == s.length()) return;for (int end = start + 1; end <= Math.min(start + 3, s.length()); end++) {String segment = s.substring(start, end);if ((segment.length() == 1 || (segment.length() > 1 && segment.charAt(0) != '0')) && Integer.parseInt(segment) <= 255) {parts.add(segment);backtrack(end, new ArrayList<>(parts));parts.remove(parts.size() - 1);}}}backtrack(0, new ArrayList<>());return result;}
}

这篇关于力扣热门算法题 89. 格雷编码,92. 反转链表 II,93. 复原 IP 地址的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

Linux系统中配置静态IP地址的详细步骤

《Linux系统中配置静态IP地址的详细步骤》本文详细介绍了在Linux系统中配置静态IP地址的五个步骤,包括打开终端、编辑网络配置文件、配置IP地址、保存并重启网络服务,这对于系统管理员和新手都极具... 目录步骤一:打开终端步骤二:编辑网络配置文件步骤三:配置静态IP地址步骤四:保存并关闭文件步骤五:重

Linux配置IP地址的三种实现方式

《Linux配置IP地址的三种实现方式》:本文主要介绍Linux配置IP地址的三种实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录环境RedHat9第一种安装 直接配置网卡文件第二种方式 nmcli(Networkmanager command-line

VSCode中C/C++编码乱码问题的两种解决方法

《VSCode中C/C++编码乱码问题的两种解决方法》在中国地区,Windows系统中的cmd和PowerShell默认编码是GBK,但VSCode默认使用UTF-8编码,这种编码不一致会导致在VSC... 目录问题方法一:通过 Code Runner 插件调整编码配置步骤方法二:在 PowerShell

Java反转字符串的五种方法总结

《Java反转字符串的五种方法总结》:本文主要介绍五种在Java中反转字符串的方法,包括使用StringBuilder的reverse()方法、字符数组、自定义StringBuilder方法、直接... 目录前言方法一:使用StringBuilder的reverse()方法方法二:使用字符数组方法三:使用自

Linux虚拟机不显示IP地址的解决方法(亲测有效)

《Linux虚拟机不显示IP地址的解决方法(亲测有效)》本文主要介绍了通过VMware新装的Linux系统没有IP地址的解决方法,主要步骤包括:关闭虚拟机、打开VM虚拟网络编辑器、还原VMnet8或修... 目录前言步骤0.问题情况1.关闭虚拟机2.China编程打开VM虚拟网络编辑器3.1 方法一:点击还原VM

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

Python如何实现读取csv文件时忽略文件的编码格式

《Python如何实现读取csv文件时忽略文件的编码格式》我们再日常读取csv文件的时候经常会发现csv文件的格式有多种,所以这篇文章为大家介绍了Python如何实现读取csv文件时忽略文件的编码格式... 目录1、背景介绍2、库的安装3、核心代码4、完整代码1、背景介绍我们再日常读取csv文件的时候经常

Springboot控制反转与Bean对象的方法

《Springboot控制反转与Bean对象的方法》文章介绍了SpringBoot中的控制反转(IoC)概念,描述了IoC容器如何管理Bean的生命周期和依赖关系,它详细讲解了Bean的注册过程,包括... 目录1 控制反转1.1 什么是控制反转1.2 SpringBoot中的控制反转2 Ioc容器对Bea