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)
# 反射并添加高位的1
for 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=1
if (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]
提示：
- 链表中节点数目为
n1 <= n <= 500-500 <= Node.val <= 5001 <= 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 head
dummy = ListNode(0, head)
prev = dummy
# Step 1: 定位到 left 的前一个节点
for _ in range(left - 1):
prev = prev.next
# Step 2: 开始反转
reverse = None
current = prev.next
for _ in range(right - left + 1):
next_temp = current.next
current.next = reverse
reverse = current
current = next_temp
# Step 3: 重连链表
prev.next.next = current
prev.next = reverse
return dummy.nextJava
/**
* 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 <= 20s仅由数字组成
解题思路
生成所有可能的有效 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))
return
if len(parts) == 4 or start == len(s):
return
# 尝试每一部分的长度：1, 2, 或 3
for 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;
}
}
