当前位置：首页 > news >正文

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

news 来源：原创 2024/5/20 11:17:23

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 位的格雷码。这种方法称为反射法，其步骤如下：

开始于基础情况：当 n = 1 时，格雷码序列是 [0, 1]。
递归生成 n-1 位的格雷码序列：对于 n > 1，首先生成 n-1 位的格雷码序列。
复制并反射：将 n-1 位的格雷码序列复制一份，并反转这个副本，以保持相邻数字只有一位二进制差异。
添加高位 1：在反转的副本序列的每个数字前添加一个高位的 1，而在原始序列的每个数字前添加一个高位的 0（实际上不需要操作，因为默认高位就是0）。
合并序列：最后将这两个序列合并，得到 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 的节点，可以通过一次遍历来实现。这个过程大致可以分为以下几个步骤：

定位到 left：首先，遍历链表直到到达位置 left。我们需要记录这个位置的前一个节点，因为反转之后，left 节点将会连接到 left 前一个节点上。
反转 left 到 right：从 left 开始，遍历到 right，并在遍历过程中逐个反转节点的指向。我们需要记录 left 节点，因为反转后，它将指向 right 节点之后的节点。
重连链表：最后，将链表的未反转部分与反转后的部分正确连接起来。

完整代码

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 地址的每一部分，并在每一步中确保该部分是有效的。具体步骤如下：

定义回溯函数：定义一个回溯函数，该函数接收当前构造的 IP 地址部分、剩余的字符串和已经确定的段数作为参数。
结束条件：当已经确定了 4 段 IP 地址并且消耗完了输入字符串时，将当前构建的 IP 地址添加到结果集中。
递归和回溯：从输入字符串中选择 1 到 3 个字符作为当前段的候选，如果选择的字符串是有效的 IP 段（0-255，且无前导 0，除非是单独的 0），则递归地继续选择下一段。
有效性检查：检查当前选择的字符串是否形成一个有效的 IP 地址段。
剪枝：在某些情况下提前终止搜索，例如，如果剩余的字符串太长或太短，无法形成有效的剩余段。

完整代码

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;}
}