Leetcode: 0021-0030题速览

本文材料来自于LeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer（第 2 版）》、《程序员面试金典（第 6 版）》题解

遵从开源协议为知识共享 版权归属-相同方式共享 4.0 国际 公共许可证

研一在读备战就业，制此集合便于空闲时间浏览，有任何疑惑问题欢迎讨论，共同进步

21. 合并两个有序链表

题目描述

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = []
输出：[]

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

提示：

• 两个链表的节点数目范围是 [0, 50]
• -100 <= Node.val <= 100
• l1 和 l2 均按 非递减顺序 排列

难度：简单

标签：递归,链表

解法

方法一：递归

我们先判断链表 $l_1$ 和 $l_2$ 是否为空，若其中一个为空，则返回另一个链表。否则，我们比较 $l_1$ 和 $l_2$ 的头节点：

• 若 $l_1$ 的头节点的值小于等于 $l_2$ 的头节点的值，则递归调用函数 $mergeTwoLists(l_1.next,l_2)$，并将 $l_1$ 的头节点与返回的链表头节点相连，返回 $l_1$ 的头节点。
• 否则，递归调用函数 $mergeTwoLists(l_1,l_2.next)$，并将 $l_2$ 的头节点与返回的链表头节点相连，返回 $l_2$ 的头节点。

时间复杂度 $O(m+n)$，空间复杂度 $O(m+n)$。其中 $m$ 和 $n$ 分别为两个链表的长度。

Python3

## Definition for singly-linked list.
## class ListNode:
##     def __init__(self, val=0, next=None):
##         self.val = val
##         self.next = next
class Solution:def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:if list1 is None or list2 is None:return list1 or list2if list1.val <= list2.val:list1.next = self.mergeTwoLists(list1.next, list2)return list1else:list2.next = self.mergeTwoLists(list1, list2.next)return list2

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 mergeTwoLists(ListNode list1, ListNode list2) {if (list1 == null) {return list2;}if (list2 == null) {return list1;}if (list1.val <= list2.val) {list1.next = mergeTwoLists(list1.next, list2);return list1;} else {list2.next = mergeTwoLists(list1, list2.next);return list2;}}
}

C++

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {if (!list1) return list2;if (!list2) return list1;if (list1->val <= list2->val) {list1->next = mergeTwoLists(list1->next, list2);return list1;} else {list2->next = mergeTwoLists(list1, list2->next);return list2;}}
};

---

22. 括号生成

题目描述

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

 

示例 1：

输入：n = 3
输出：[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]

示例 2：

输入：n = 1
输出：[“()”]

 

提示：

• 1 <= n <= 8

难度：中等

标签：字符串,动态规划,回溯

解法

方法一：DFS + 剪枝

题目中 $n$ 的范围为 $[1,8]$，因此我们直接通过“暴力搜索 + 剪枝”的方式通过本题。

我们设计一个函数 $dfs(l,r,t)$，其中 $l$ 和 $r$ 分别表示左括号和右括号的数量，而 $t$ 表示当前的括号序列。那么我们可以得到如下的递归结构：

• 如果 $l>n$ 或者 $r>n$ 或者 $l<r$，那么当前括号组合 $t$ 不合法，直接返回；
• 如果 $l=n$ 且 $r=n$，那么当前括号组合 $t$ 合法，将其加入答案数组 ans 中，直接返回；
• 我们可以选择添加一个左括号，递归执行 dfs(l + 1, r, t + "(")；
• 我们也可以选择添加一个右括号，递归执行 dfs(l, r + 1, t + ")")。

时间复杂度 $O(2^{n\times 2}\times n)$，空间复杂度 $O(n)$。

Python3

class Solution:def generateParenthesis(self, n: int) -> List[str]:def dfs(l, r, t):if l > n or r > n or l < r:returnif l == n and r == n:ans.append(t)returndfs(l + 1, r, t + '(')dfs(l, r + 1, t + ')')ans = []dfs(0, 0, '')return ans

Java

class Solution {private List<String> ans = new ArrayList<>();private int n;public List<String> generateParenthesis(int n) {this.n = n;dfs(0, 0, "");return ans;}private void dfs(int l, int r, String t) {if (l > n || r > n || l < r) {return;}if (l == n && r == n) {ans.add(t);return;}dfs(l + 1, r, t + "(");dfs(l, r + 1, t + ")");}
}

C++

class Solution {
public:vector<string> generateParenthesis(int n) {vector<string> ans;function<void(int, int, string)> dfs = [&](int l, int r, string t) {if (l > n || r > n || l < r) return;if (l == n && r == n) {ans.push_back(t);return;}dfs(l + 1, r, t + "(");dfs(l, r + 1, t + ")");};dfs(0, 0, "");return ans;}
};

---

23. 合并 K 个升序链表

题目描述

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

 

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2：

输入：lists = []
输出：[]

示例 3：

输入：lists = [[]]
输出：[]

 

提示：

• k == lists.length
• 0 <= k <= 10^4
• 0 <= lists[i].length <= 500
• -10^4 <= lists[i][j] <= 10^4
• lists[i] 按 升序 排列
• lists[i].length 的总和不超过 10^4

难度：困难

标签：链表,分治,堆（优先队列）,归并排序

解法

方法一：优先队列（小根堆）

我们可以创建一个小根堆来 $pq$ 维护所有链表的头节点，每次从小根堆中取出值最小的节点，添加到结果链表的末尾，然后将该节点的下一个节点加入堆中，重复上述步骤直到堆为空。

时间复杂度 $O(n\times \log k)$，空间复杂度 $O(k)$。其中 $n$ 是所有链表节点数目的总和，而 $k$ 是题目给定的链表数目。

Python3

## Definition for singly-linked list.
## class ListNode:
##     def __init__(self, val=0, next=None):
##         self.val = val
##         self.next = next
class Solution:def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:setattr(ListNode, "__lt__", lambda a, b: a.val < b.val)pq = [head for head in lists if head]heapify(pq)dummy = cur = ListNode()while pq:node = heappop(pq)if node.next:heappush(pq, node.next)cur.next = nodecur = cur.nextreturn 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 mergeKLists(ListNode[] lists) {PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);for (ListNode head : lists) {if (head != null) {pq.offer(head);}}ListNode dummy = new ListNode();ListNode cur = dummy;while (!pq.isEmpty()) {ListNode node = pq.poll();if (node.next != null) {pq.offer(node.next);}cur.next = node;cur = cur.next;}return dummy.next;}
}

C++

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* mergeKLists(vector<ListNode*>& lists) {auto cmp = [](ListNode* a, ListNode* b) { return a->val > b->val; };priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq;for (auto head : lists) {if (head) {pq.push(head);}}ListNode* dummy = new ListNode();ListNode* cur = dummy;while (!pq.empty()) {ListNode* node = pq.top();pq.pop();if (node->next) {pq.push(node->next);}cur->next = node;cur = cur->next;}return dummy->next;}
};

---

24. 两两交换链表中的节点

题目描述

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

 

示例 1：

输入：head = [1,2,3,4]
输出：[2,1,4,3]

示例 2：

输入：head = []
输出：[]

示例 3：

输入：head = [1]
输出：[1]

 

提示：

• 链表中节点的数目在范围 [0, 100] 内
• 0 <= Node.val <= 100

难度：中等

标签：递归,链表

解法

方法一：递归

我们可以通过递归的方式实现两两交换链表中的节点。

递归的终止条件是链表中没有节点，或者链表中只有一个节点，此时无法进行交换，直接返回该节点。

否则，我们递归交换链表 $head.next.next$，记交换后的头节点为 $t$，然后我们记 $head$ 的下一个节点为 $p$，然后令 $p$ 指向 $head$，而 $head$ 指向 $t$，最后返回 $p$。

时间复杂度 $O(n)$，空间复杂度 $O(n)$，其中 $n$ 是链表的长度。

Python3

## Definition for singly-linked list.
## class ListNode:
##     def __init__(self, val=0, next=None):
##         self.val = val
##         self.next = next
class Solution:def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:if head is None or head.next is None:return headt = self.swapPairs(head.next.next)p = head.nextp.next = headhead.next = treturn p

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 swapPairs(ListNode head) {if (head == null || head.next == null) {return head;}ListNode t = swapPairs(head.next.next);ListNode p = head.next;p.next = head;head.next = t;return p;}
}

C++

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* swapPairs(ListNode* head) {if (!head || !head->next) {return head;}ListNode* t = swapPairs(head->next->next);ListNode* p = head->next;p->next = head;head->next = t;return p;}
};

---

25. K 个一组翻转链表

题目描述

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

 

示例 1：

输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]

示例 2：

输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]

 

提示：

• 链表中的节点数目为 n
• 1 <= k <= n <= 5000
• 0 <= Node.val <= 1000

 

进阶：你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗？

难度：困难

标签：递归,链表

解法

方法一：迭代

时间复杂度为 $O(n)$，空间复杂度为 $O(1)$，其中 $n$ 是链表的长度。

Python3

## Definition for singly-linked list.
## class ListNode:
##     def __init__(self, val=0, next=None):
##         self.val = val
##         self.next = next
class Solution:def reverseKGroup(self, head: ListNode, k: int) -> ListNode:def reverseList(head):pre, p = None, headwhile p:q = p.nextp.next = prepre = pp = qreturn predummy = ListNode(next=head)pre = cur = dummywhile cur.next:for _ in range(k):cur = cur.nextif cur is None:return dummy.nextt = cur.nextcur.next = Nonestart = pre.nextpre.next = reverseList(start)start.next = tpre = startcur = prereturn 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 reverseKGroup(ListNode head, int k) {ListNode dummy = new ListNode(0, head);ListNode pre = dummy, cur = dummy;while (cur.next != null) {for (int i = 0; i < k && cur != null; ++i) {cur = cur.next;}if (cur == null) {return dummy.next;}ListNode t = cur.next;cur.next = null;ListNode start = pre.next;pre.next = reverseList(start);start.next = t;pre = start;cur = pre;}return dummy.next;}private ListNode reverseList(ListNode head) {ListNode pre = null, p = head;while (p != null) {ListNode q = p.next;p.next = pre;pre = p;p = q;}return pre;}
}

---

26. 删除有序数组中的重复项

题目描述

给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：

• 更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
• 返回 k 。

判题标准:

系统会用下面的代码来测试你的题解:

int[] nums = […]; // 输入数组
int[] expectedNums = […]; // 长度正确的期望答案

int k = removeDuplicates(nums); // 调用

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
assert nums[i] == expectedNums[i];
}

如果所有断言都通过，那么您的题解将被 通过。

 

示例 1：

输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

示例 2：

输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

 

提示：

• 1 <= nums.length <= 3 * 104
• -104 <= nums[i] <= 104
• nums 已按 非严格递增 排列

难度：简单

标签：数组,双指针

解法

方法一：一次遍历

我们用一个变量 $k$ 记录当前已经处理好的数组的长度，初始时 $k=0$，表示空数组。

然后我们从左到右遍历数组，对于遍历到的每个元素 $x$，如果 $k=0$ 或者 $x\ne nums[k-1]$，我们就将 $x$ 放到 $nums[k]$ 的位置，然后 $k$ 自增 $1$。否则，$x$ 与 $nums[k-1]$ 相同，我们直接跳过这个元素。继续遍历，直到遍历完整个数组。

这样，当遍历结束时，$nums$ 中前 $k$ 个元素就是我们要求的答案，且 $k$ 就是答案的长度。

时间复杂度 $O(n)$，空间复杂度 $O(1)$。其中 $n$ 为数组的长度。

补充：

原问题要求最多相同的数字最多出现 $1$ 次，我们可以扩展至相同的数字最多保留 $k$ 个。

• 由于相同的数字最多保留 $k$ 个，那么原数组的前 $k$ 个元素我们可以直接保留；
• 对于后面的数字，能够保留的前提是：当前数字 $x$ 与前面已保留的数字的倒数第 $k$ 个元素比较，不同则保留，相同则跳过。

相似题目：

• 80. 删除有序数组中的重复项 II

Python3

class Solution:def removeDuplicates(self, nums: List[int]) -> int:k = 0for x in nums:if k == 0 or x != nums[k - 1]:nums[k] = xk += 1return k

Java

class Solution {public int removeDuplicates(int[] nums) {int k = 0;for (int x : nums) {if (k == 0 || x != nums[k - 1]) {nums[k++] = x;}}return k;}
}

C++

class Solution {
public:int removeDuplicates(vector<int>& nums) {int k = 0;for (int x : nums) {if (k == 0 || x != nums[k - 1]) {nums[k++] = x;}}return k;}
};

---

27. 移除元素

题目描述

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

• 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
• 返回 k。

用户评测：

评测机将使用以下代码测试您的解决方案：

int[] nums = […]; // 输入数组
int val = …; // 要移除的值
int[] expectedNums = […]; // 长度正确的预期答案。
// 它以不等于 val 的值排序。

int k = removeElement(nums, val); // 调用你的实现

assert k == expectedNums.length;
sort(nums, 0, k); // 排序 nums 的前 k 个元素
for (int i = 0; i < actualLength; i++) {
assert nums[i] == expectedNums[i];
}

如果所有的断言都通过，你的解决方案将会 通过。

 

示例 1：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2,,]
解释：你的函数函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

示例 2：

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3,,,_]
解释：你的函数应该返回 k = 5，并且 nums 中的前五个元素为 0,0,1,3,4。
注意这五个元素可以任意顺序返回。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

 

提示：

• 0 <= nums.length <= 100
• 0 <= nums[i] <= 50
• 0 <= val <= 100

难度：简单

标签：数组,双指针

解法

方法一：一次遍历

我们用变量 $k$ 记录当前不等于 $val$ 的元素个数。

遍历数组 $nums$，如果当前元素 $x$ 不等于 $val$，则将 $x$ 赋值给 $nums[k]$，并将 $k$ 自增 $1$。

最后返回 $k$ 即可。

时间复杂度 $O(n)$，空间复杂度 $O(1)$。其中 $n$ 为数组 $nums$ 的长度。

Python3

class Solution:def removeElement(self, nums: List[int], val: int) -> int:k = 0for x in nums:if x != val:nums[k] = xk += 1return k

Java

class Solution {public int removeElement(int[] nums, int val) {int k = 0;for (int x : nums) {if (x != val) {nums[k++] = x;}}return k;}
}

C++

class Solution {
public:int removeElement(vector<int>& nums, int val) {int k = 0;for (int x : nums) {if (x != val) {nums[k++] = x;}}return k;}
};

---

28. 找出字符串中第一个匹配项的下标

题目描述

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回  -1 。

 

示例 1：

输入：haystack = “sadbutsad”, needle = “sad”
输出：0
解释：“sad” 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。

示例 2：

输入：haystack = “leetcode”, needle = “leeto”
输出：-1
解释：“leeto” 没有在 “leetcode” 中出现，所以返回 -1 。

 

提示：

• 1 <= haystack.length, needle.length <= 104
• haystack 和 needle 仅由小写英文字符组成

难度：简单

标签：双指针,字符串,字符串匹配

解法

方法一：遍历

以字符串 haystack 的每一个字符为起点与字符串 needle 进行比较，若发现能够匹配的索引，直接返回即可。

假设字符串 haystack 长度为 $n$，字符串 needle 长度为 $m$，则时间复杂度为 $O((n-m)\times m)$，空间复杂度 $O(1)$。

Python3

class Solution:def strStr(self, haystack: str, needle: str) -> int:n, m = len(haystack), len(needle)for i in range(n - m + 1):if haystack[i : i + m] == needle:return ireturn -1

Java

class Solution {public int strStr(String haystack, String needle) {if ("".equals(needle)) {return 0;}int len1 = haystack.length();int len2 = needle.length();int p = 0;int q = 0;while (p < len1) {if (haystack.charAt(p) == needle.charAt(q)) {if (len2 == 1) {return p;}++p;++q;} else {p -= q - 1;q = 0;}if (q == len2) {return p - q;}}return -1;}
}

C++

class Solution {
private:vector<int> Next(string str) {vector<int> n(str.length());n[0] = -1;int i = 0, pre = -1;int len = str.length();while (i < len) {while (pre >= 0 && str[i] != str[pre])pre = n[pre];++i, ++pre;if (i >= len)break;if (str[i] == str[pre])n[i] = n[pre];elsen[i] = pre;}return n;}public:int strStr(string haystack, string needle) {if (0 == needle.length())return 0;vector<int> n(Next(needle));int len = haystack.length() - needle.length() + 1;for (int i = 0; i < len; ++i) {int j = 0, k = i;while (j < needle.length() && k < haystack.length()) {if (haystack[k] != needle[j]) {if (n[j] >= 0) {j = n[j];continue;} elsebreak;}++k, ++j;}if (j >= needle.length())return k - j;}return -1;}
};

---

29. 两数相除

题目描述

给你两个整数，被除数 dividend 和除数 divisor。将两数相除，要求 不使用 乘法、除法和取余运算。

整数除法应该向零截断，也就是截去（truncate）其小数部分。例如，8.345 将被截断为 8 ，-2.7335 将被截断至 -2 。

返回被除数 dividend 除以除数 divisor 得到的 商 。

注意：假设我们的环境只能存储 32 位 有符号整数，其数值范围是 [−231,  231 − 1] 。本题中，如果商 严格大于 231 − 1 ，则返回 231 − 1 ；如果商 严格小于 -231 ，则返回 -231 。

 

示例 1:

输入: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = 3.33333… ，向零截断后得到 3 。

示例 2:

输入: dividend = 7, divisor = -3
输出: -2
解释: 7/-3 = -2.33333… ，向零截断后得到 -2 。

 

提示：

• -231 <= dividend, divisor <= 231 - 1
• divisor != 0

难度：中等

标签：位运算,数学

解法

方法一：模拟 + 快速幂

除法本质上就是减法，题目要求我们计算出两个数相除之后的取整结果，其实就是计算被除数是多少个除数加上一个小于除数的数构成的。但是一次循环只能做一次减法，效率太低会导致超时，可借助快速幂的思想进行优化。

需要注意的是，由于题目明确要求最大只能使用 32 位有符号整数，所以需要将除数和被除数同时转换为负数进行计算。因为转换正数可能会导致溢出，如当被除数为 INT32_MIN 时，转换为正数时会大于 INT32_MAX。

假设被除数为 $a$，除数为 $b$，则时间复杂度为 $O(\log a\times \log b)$，空间复杂度 $O(1)$。

Python3

class Solution:def divide(self, a: int, b: int) -> int:if b == 1:return aif a == -(2**31) and b == -1:return 2**31 - 1sign = (a > 0 and b > 0) or (a < 0 and b < 0)a = -a if a > 0 else ab = -b if b > 0 else bans = 0while a <= b:x = bcnt = 1while x >= (-(2**30)) and a <= (x << 1):x <<= 1cnt <<= 1a -= xans += cntreturn ans if sign else -ans

Java

class Solution {public int divide(int a, int b) {if (b == 1) {return a;}if (a == Integer.MIN_VALUE && b == -1) {return Integer.MAX_VALUE;}boolean sign = (a > 0 && b > 0) || (a < 0 && b < 0);a = a > 0 ? -a : a;b = b > 0 ? -b : b;int ans = 0;while (a <= b) {int x = b;int cnt = 1;while (x >= (Integer.MIN_VALUE >> 1) && a <= (x << 1)) {x <<= 1;cnt <<= 1;}ans += cnt;a -= x;}return sign ? ans : -ans;}
}

C++

class Solution {
public:int divide(int a, int b) {if (b == 1) {return a;}if (a == INT_MIN && b == -1) {return INT_MAX;}bool sign = (a > 0 && b > 0) || (a < 0 && b < 0);a = a > 0 ? -a : a;b = b > 0 ? -b : b;int ans = 0;while (a <= b) {int x = b;int cnt = 1;while (x >= (INT_MIN >> 1) && a <= (x << 1)) {x <<= 1;cnt <<= 1;}ans += cnt;a -= x;}return sign ? ans : -ans;}
};

---

30. 串联所有单词的子串

题目描述

给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。

 s 中的 串联子串 是指一个包含  words 中所有字符串以任意顺序排列连接起来的子串。

• 例如，如果 words = ["ab","cd","ef"]， 那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"， 和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。

返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。

 

示例 1：

输入：s = “barfoothefoobarman”, words = [“foo”,“bar”]
输出：[0,9]
解释：因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。
子串 “barfoo” 开始位置是 0。它是 words 中以 [“bar”,“foo”] 顺序排列的连接。
子串 “foobar” 开始位置是 9。它是 words 中以 [“foo”,“bar”] 顺序排列的连接。
输出顺序无关紧要。返回 [9,0] 也是可以的。

示例 2：

输入：s = “wordgoodgoodgoodbestword”, words = [“word”,“good”,“best”,“word”]
输出：[]
解释：因为 words.length == 4 并且 words[i].length == 4，所以串联子串的长度必须为 16。
s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。
所以我们返回一个空数组。

示例 3：

输入：s = “barfoofoobarthefoobarman”, words = [“bar”,“foo”,“the”]
输出：[6,9,12]
解释：因为 words.length == 3 并且 words[i].length == 3，所以串联子串的长度必须为 9。
子串 “foobarthe” 开始位置是 6。它是 words 中以 [“foo”,“bar”,“the”] 顺序排列的连接。
子串 “barthefoo” 开始位置是 9。它是 words 中以 [“bar”,“the”,“foo”] 顺序排列的连接。
子串 “thefoobar” 开始位置是 12。它是 words 中以 [“the”,“foo”,“bar”] 顺序排列的连接。

 

提示：

• 1 <= s.length <= 104
• 1 <= words.length <= 5000
• 1 <= words[i].length <= 30
• words[i] 和 s 由小写英文字母组成

难度：困难

标签：哈希表,字符串,滑动窗口

解法

方法一：哈希表 + 滑动窗口

我们用哈希表 $cnt$ 统计 $words$ 中每个单词出现的次数，用哈希表 $cnt1$ 统计当前滑动窗口中每个单词出现的次数。我们记字符串 $s$ 的长度为 $m$，字符串数组 $words$ 中单词的数量为 $n$，每个单词的长度为 $k$。

我们可以枚举滑动窗口的起点 $i$，其中 $0<i<k$。对于每个起点，我们维护一个滑动窗口，左边界为 $l$，右边界为 $r$，滑动窗口中的单词个数为 $t$，另外用一个哈希表 $cnt1$ 统计滑动窗口中每个单词出现的次数。

每一次，我们提取字符串 $s[r:r+k]$，如果 $s[r:r+k]$ 不在哈希表 $cnt$ 中，说明当前滑动窗口中的单词不合法，我们将左边界 $l$ 更新为 $r$，同时将哈希表 $cnt1$ 清空，单词个数 $t$ 重置为 0。如果 $s[r:r+k]$ 在哈希表 $cnt$ 中，说明当前滑动窗口中的单词合法，我们将单词个数 $t$ 加 1，将哈希表 $cnt1$ 中 $s[r:r+k]$ 的次数加 1。如果 $cnt1[s[r:r+k]]$ 大于 $cnt[s[r:r+k]]$，说明当前滑动窗口中 $s[r:r+k]$ 出现的次数过多，我们需要将左边界 $l$ 右移，直到 $cnt1[s[r:r+k]]=cnt[s[r:r+k]]$。如果 $t=n$，说明当前滑动窗口中的单词正好合法，我们将左边界 $l$ 加入答案数组。

时间复杂度 $O(m\times k)$，空间复杂度 $O(n\times k)$。其中 $m$ 和 $n$ 分别是字符串 $s$ 和字符串数组 $words$ 的长度，而 $k$ 是字符串数组 $words$ 中单词的长度。

Python3

class Solution:def findSubstring(self, s: str, words: List[str]) -> List[int]:cnt = Counter(words)m, n = len(s), len(words)k = len(words[0])ans = []for i in range(k):cnt1 = Counter()l = r = it = 0while r + k <= m:w = s[r : r + k]r += kif w not in cnt:l = rcnt1.clear()t = 0continuecnt1[w] += 1t += 1while cnt1[w] > cnt[w]:remove = s[l : l + k]l += kcnt1[remove] -= 1t -= 1if t == n:ans.append(l)return ans

Java

class Solution {public List<Integer> findSubstring(String s, String[] words) {Map<String, Integer> cnt = new HashMap<>();for (String w : words) {cnt.merge(w, 1, Integer::sum);}int m = s.length(), n = words.length;int k = words[0].length();List<Integer> ans = new ArrayList<>();for (int i = 0; i < k; ++i) {Map<String, Integer> cnt1 = new HashMap<>();int l = i, r = i;int t = 0;while (r + k <= m) {String w = s.substring(r, r + k);r += k;if (!cnt.containsKey(w)) {cnt1.clear();l = r;t = 0;continue;}cnt1.merge(w, 1, Integer::sum);++t;while (cnt1.get(w) > cnt.get(w)) {String remove = s.substring(l, l + k);l += k;cnt1.merge(remove, -1, Integer::sum);--t;}if (t == n) {ans.add(l);}}}return ans;}
}

C++

class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {