Leetcode: 0081-0090题速览
Leetcode: 0081-0090题速览
研一在读备战就业,制此集合便于空闲时间浏览,有任何疑惑问题欢迎讨论,共同进步
目录
- Leetcode: 0081-0090题速览
- [81. 搜索旋转排序数组 II](https://leetcode.cn/problems/search-in-rotated-sorted-array-ii)
- [82. 删除排序链表中的重复元素 II](https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii)
- [83. 删除排序链表中的重复元素](https://leetcode.cn/problems/remove-duplicates-from-sorted-list)
- [84. 柱状图中最大的矩形](https://leetcode.cn/problems/largest-rectangle-in-histogram)
- [85. 最大矩形](https://leetcode.cn/problems/maximal-rectangle)
- [86. 分隔链表](https://leetcode.cn/problems/partition-list)
- [87. 扰乱字符串](https://leetcode.cn/problems/scramble-string)
- [88. 合并两个有序数组](https://leetcode.cn/problems/merge-sorted-array)
- [89. 格雷编码](https://leetcode.cn/problems/gray-code)
- [90. 子集 II](https://leetcode.cn/problems/subsets-ii)
81. 搜索旋转排序数组 II
题目描述
已知存在一个按非降序排列的整数数组 nums
,数组中的值不必互不相同。
在传递给函数之前,nums
在预先未知的某个下标 k
(0 <= k < nums.length
)上进行了 旋转 ,使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]
(下标 从 0 开始 计数)。例如, [0,1,2,4,4,4,5,6,6,7]
在下标 5
处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4]
。
给你 旋转后 的数组 nums
和一个整数 target
,请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums
中存在这个目标值 target
,则返回 true
,否则返回 false
。
你必须尽可能减少整个操作步骤。
示例 1:
输入:nums = [2,5,6,0,0,1,2]
, target = 0
输出:true
示例 2:
输入:nums = [2,5,6,0,0,1,2]
, target = 3
输出:false
提示:
1 <= nums.length <= 5000
-104 <= nums[i] <= 104
- 题目数据保证
nums
在预先未知的某个下标上进行了旋转 -104 <= target <= 104
进阶:
- 此题与 搜索旋转排序数组 相似,但本题中的
nums
可能包含 重复 元素。这会影响到程序的时间复杂度吗?会有怎样的影响,为什么?
难度:中等
标签:数组,二分查找
解法
方法一:二分查找
我们定义二分查找的左边界 l = 0 l=0 l=0,右边界 r = n − 1 r=n-1 r=n−1,其中 n n n 为数组的长度。
每次在二分查找的过程中,我们会得到当前的中点 m i d = ( l + r ) / 2 mid=(l+r)/2 mid=(l+r)/2。
- 如果 n u m s [ m i d ] > n u m s [ r ] nums[mid] \gt nums[r] nums[mid]>nums[r],说明 [ l , m i d ] [l,mid] [l,mid] 是有序的,此时如果 n u m s [ l ] ≤ t a r g e t ≤ n u m s [ m i d ] nums[l] \le target \le nums[mid] nums[l]≤target≤nums[mid],说明 t a r g e t target target 位于 [ l , m i d ] [l,mid] [l,mid],否则 t a r g e t target target 位于 [ m i d + 1 , r ] [mid+1,r] [mid+1,r]。
- 如果 n u m s [ m i d ] < n u m s [ r ] nums[mid] \lt nums[r] nums[mid]<nums[r],说明 [ m i d + 1 , r ] [mid+1,r] [mid+1,r] 是有序的,此时如果 n u m s [ m i d ] < t a r g e t ≤ n u m s [ r ] nums[mid] \lt target \le nums[r] nums[mid]<target≤nums[r],说明 t a r g e t target target 位于 [ m i d + 1 , r ] [mid+1,r] [mid+1,r],否则 t a r g e t target target 位于 [ l , m i d ] [l,mid] [l,mid]。
- 如果 n u m s [ m i d ] = n u m s [ r ] nums[mid] = nums[r] nums[mid]=nums[r],说明元素 n u m s [ m i d ] nums[mid] nums[mid] 和 n u m s [ r ] nums[r] nums[r] 相等,此时无法判断 t a r g e t target target 位于哪个区间,我们只能将 r r r 减少 1 1 1。
二分查找结束后,如果 n u m s [ l ] = t a r g e t nums[l] = target nums[l]=target,则说明数组中存在目标值 t a r g e t target target,否则说明不存在。
时间复杂度近似 O ( log n ) O(\log n) O(logn),空间复杂度 O ( 1 ) O(1) O(1)。其中 n n n 为数组的长度。
Python3
class Solution:
def search(self, nums: List[int], target: int) -> bool:
n = len(nums)
l, r = 0, n - 1
while l < r:
mid = (l + r) >> 1
if nums[mid] > nums[r]:
if nums[l] <= target <= nums[mid]:
r = mid
else:
l = mid + 1
elif nums[mid] < nums[r]:
if nums[mid] < target <= nums[r]:
l = mid + 1
else:
r = mid
else:
r -= 1
return nums[l] == target
Java
class Solution {
public boolean search(int[] nums, int target) {
int l = 0, r = nums.length - 1;
while (l < r) {
int mid = (l + r) >> 1;
if (nums[mid] > nums[r]) {
if (nums[l] <= target && target <= nums[mid]) {
r = mid;
} else {
l = mid + 1;
}
} else if (nums[mid] < nums[r]) {
if (nums[mid] < target && target <= nums[r]) {
l = mid + 1;
} else {
r = mid;
}
} else {
--r;
}
}
return nums[l] == target;
}
}
C++
class Solution {
public:
bool search(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while (l < r) {
int mid = (l + r) >> 1;
if (nums[mid] > nums[r]) {
if (nums[l] <= target && target <= nums[mid]) {
r = mid;
} else {
l = mid + 1;
}
} else if (nums[mid] < nums[r]) {
if (nums[mid] < target && target <= nums[r]) {
l = mid + 1;
} else {
r = mid;
}
} else {
--r;
}
}
return nums[l] == target;
}
};
82. 删除排序链表中的重复元素 II
题目描述
给定一个已排序的链表的头 head
, 删除原始链表中所有重复数字的节点,只留下不同的数字 。返回 已排序的链表 。
示例 1:
输入:head = [1,2,3,3,4,4,5]
输出:[1,2,5]
示例 2:
输入:head = [1,1,1,2,3]
输出:[2,3]
提示:
- 链表中节点数目在范围
[0, 300]
内 -100 <= Node.val <= 100
- 题目数据保证链表已经按升序 排列
难度:中等
标签:链表,双指针
解法
方法一:一次遍历
我们先创建一个虚拟头节点 d u m m y dummy dummy,令 d u m m y . n e x t = h e a d dummy.next = head dummy.next=head,然后创建指针 p r e pre pre 指向 d u m m y dummy dummy,指针 c u r cur cur 指向 h e a d head head,开始遍历链表。
当 c u r cur cur 指向的节点值与 c u r . n e x t cur.next cur.next 指向的节点值相同时,我们就让 c u r cur cur 不断向后移动,直到 c u r cur cur 指向的节点值与 c u r . n e x t cur.next cur.next 指向的节点值不相同时,停止移动。此时,我们判断 p r e . n e x t pre.next pre.next 是否等于 c u r cur cur,如果相等,说明 p r e pre pre 与 c u r cur cur 之间没有重复节点,我们就让 p r e pre pre 移动到 c u r cur cur 的位置;否则,说明 p r e pre pre 与 c u r cur cur 之间有重复节点,我们就让 p r e . n e x t pre.next pre.next 指向 c u r . n e x t cur.next cur.next。然后让 c u r cur cur 继续向后移动。继续上述操作,直到 c u r cur cur 为空,遍历结束。
最后,返回 d u m m y . n e x t dummy.next dummy.next 即可。
时间复杂度 O ( n ) O(n) O(n),其中 n n n 为链表的长度。空间复杂度 O ( 1 ) O(1) O(1)。
Python3
## Definition for singly-linked list.
## class ListNode:
## def __init__(self, val=0, next=None):
## self.val = val
## self.next = next
class Solution:
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
dummy = pre = ListNode(next=head)
cur = head
while cur:
while cur.next and cur.next.val == cur.val:
cur = cur.next
if pre.next == cur:
pre = cur
else:
pre.next = cur.next
cur = cur.next
return 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 deleteDuplicates(ListNode head) {
ListNode dummy = new ListNode(0, head);
ListNode pre = dummy;
ListNode cur = head;
while (cur != null) {
while (cur.next != null && cur.next.val == cur.val) {
cur = cur.next;
}
if (pre.next == cur) {
pre = cur;
} else {
pre.next = cur.next;
}
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* deleteDuplicates(ListNode* head) {
ListNode* dummy = new ListNode(0, head);
ListNode* pre = dummy;
ListNode* cur = head;
while (cur) {
while (cur->next && cur->next->val == cur->val) {
cur = cur->next;
}
if (pre->next == cur) {
pre = cur;
} else {
pre->next = cur->next;
}
cur = cur->next;
}
return dummy->next;
}
};
83. 删除排序链表中的重复元素
题目描述
给定一个已排序的链表的头 head
, 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。
示例 1:
输入:head = [1,1,2]
输出:[1,2]
示例 2:
输入:head = [1,1,2,3,3]
输出:[1,2,3]
提示:
- 链表中节点数目在范围
[0, 300]
内 -100 <= Node.val <= 100
- 题目数据保证链表已经按升序 排列
难度:简单
标签:链表
解法
方法一:一次遍历
我们用一个指针 c u r cur cur 来遍历链表。如果当前 c u r cur cur 与 c u r . n e x t cur.next cur.next 对应的元素相同,我们就将 c u r cur cur 的 n e x t next next 指针指向 c u r cur cur 的下下个节点。否则,说明链表中 c u r cur cur 对应的元素是不重复的,因此可以将 c u r cur cur 指针移动到下一个节点。
遍历结束后,返回链表的头节点即可。
时间复杂度 O ( n ) O(n) O(n),其中 n n n 是链表的长度。空间复杂度 O ( 1 ) O(1) O(1)。
Python3
## Definition for singly-linked list.
## class ListNode:
## def __init__(self, val=0, next=None):
## self.val = val
## self.next = next
class Solution:
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
cur = head
while cur and cur.next:
if cur.val == cur.next.val:
cur.next = cur.next.next
else:
cur = cur.next
return head
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 deleteDuplicates(ListNode head) {
ListNode cur = head;
while (cur != null && cur.next != null) {
if (cur.val == cur.next.val) {
cur.next = cur.next.next;
} else {
cur = cur.next;
}
}
return head;
}
}
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* deleteDuplicates(ListNode* head) {
ListNode* cur = head;
while (cur != nullptr && cur->next != nullptr) {
if (cur->val == cur->next->val) {
cur->next = cur->next->next;
} else {
cur = cur->next;
}
}
return head;
}
};
84. 柱状图中最大的矩形
题目描述
给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。
求在该柱状图中,能够勾勒出来的矩形的最大面积。
示例 1:
输入:heights = [2,1,5,6,2,3]
输出:10
解释:最大的矩形为图中红色区域,面积为 10
示例 2:
输入: heights = [2,4]
输出: 4
提示:
1 <= heights.length <=105
0 <= heights[i] <= 104
难度:困难
标签:栈,数组,单调栈
解法
方法一:单调栈
我们可以枚举每根柱子的高度 h h h 作为矩形的高度,利用单调栈,向左右两边找第一个高度小于 h h h 的下标 l e f t i left_i lefti, r i g h t i right_i righti。那么此时矩形面积为 h × ( r i g h t i − l e f t i − 1 ) h \times (right_i-left_i-1) h×(righti−lefti−1),求最大值即可。
时间复杂度 O ( n ) O(n) O(n),空间复杂度 O ( n ) O(n) O(n)。其中 n n n 表示 h e i g h t s heights heights 的长度。
单调栈常见模型:找出每个数左/右边离它最近的且比它大/小的数。模板:
stk = []
for i in range(n):
while stk and check(stk[-1], i):
stk.pop()
stk.append(i)
Python3
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
n = len(heights)
stk = []
left = [-1] * n
right = [n] * n
for i, h in enumerate(heights):
while stk and heights[stk[-1]] >= h:
right[stk[-1]] = i
stk.pop()
if stk:
left[i] = stk[-1]
stk.append(i)
return max(h * (right[i] - left[i] - 1) for i, h in enumerate(heights))
Java
class Solution {
public int largestRectangleArea(int[] heights) {
int res = 0, n = heights.length;
Deque<Integer> stk = new ArrayDeque<>();
int[] left = new int[n];
int[] right = new int[n];
Arrays.fill(right, n);
for (int i = 0; i < n; ++i) {
while (!stk.isEmpty() && heights[stk.peek()] >= heights[i]) {
right[stk.pop()] = i;
}
left[i] = stk.isEmpty() ? -1 : stk.peek();
stk.push(i);
}
for (int i = 0; i < n; ++i) {
res = Math.max(res, heights[i] * (right[i] - left[i] - 1));
}
return res;
}
}
C++
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int res = 0, n = heights.size();
stack<int> stk;
vector<int> left(n, -1);
vector<int> right(n, n);
for (int i = 0; i < n; ++i) {
while (!stk.empty() && heights[stk.top()] >= heights[i]) {
right[stk.top()] = i;
stk.pop();
}
if (!stk.empty()) left[i] = stk.top();
stk.push(i);
}
for (int i = 0; i < n; ++i)
res = max(res, heights[i] * (right[i] - left[i] - 1));
return res;
}
};
85. 最大矩形
题目描述
给定一个仅包含 0
和 1
、大小为 rows x cols
的二维二进制矩阵,找出只包含 1
的最大矩形,并返回其面积。
示例 1:
输入:matrix = [[“1”,“0”,“1”,“0”,“0”],[“1”,“0”,“1”,“1”,“1”],[“1”,“1”,“1”,“1”,“1”],[“1”,“0”,“0”,“1”,“0”]]
输出:6
解释:最大矩形如上图所示。
示例 2:
输入:matrix = [[“0”]]
输出:0
示例 3:
输入:matrix = [[“1”]]
输出:1
提示:
rows == matrix.length
cols == matrix[0].length
1 <= row, cols <= 200
matrix[i][j]
为'0'
或'1'
难度:困难
标签:栈,数组,动态规划,矩阵,单调栈
解法
方法一:单调栈
我们把每一行视为柱状图的底部,对每一行求柱状图的最大面积即可。
时间复杂度 O ( m × n ) O(m \times n) O(m×n),其中 m m m 表示 m a t r i x matrix matrix 的行数, n n n 表示 m a t r i x matrix matrix 的列数。
Python3
class Solution:
def maximalRectangle(self, matrix: List[List[str]]) -> int:
heights = [0] * len(matrix[0])
ans = 0
for row in matrix:
for j, v in enumerate(row):
if v == "1":
heights[j] += 1
else:
heights[j] = 0
ans = max(ans, self.largestRectangleArea(heights))
return ans
def largestRectangleArea(self, heights: List[int]) -> int:
n = len(heights)
stk = []
left = [-1] * n
right = [n] * n
for i, h in enumerate(heights):
while stk and heights[stk[-1]] >= h:
stk.pop()
if stk:
left[i] = stk[-1]
stk.append(i)
stk = []
for i in range(n - 1, -1, -1):
h = heights[i]
while stk and heights[stk[-1]] >= h:
stk.pop()
if stk:
right[i] = stk[-1]
stk.append(i)
return max(h * (right[i] - left[i] - 1) for i, h in enumerate(heights))
Java
class Solution {
public int maximalRectangle(char[][] matrix) {
int n = matrix[0].length;
int[] heights = new int[n];
int ans = 0;
for (var row : matrix) {
for (int j = 0; j < n; ++j) {
if (row[j] == '1') {
heights[j] += 1;
} else {
heights[j] = 0;
}
}
ans = Math.max(ans, largestRectangleArea(heights));
}
return ans;
}
private int largestRectangleArea(int[] heights) {
int res = 0, n = heights.length;
Deque<Integer> stk = new ArrayDeque<>();
int[] left = new int[n];
int[] right = new int[n];
Arrays.fill(right, n);
for (int i = 0; i < n; ++i) {
while (!stk.isEmpty() && heights[stk.peek()] >= heights[i]) {
right[stk.pop()] = i;
}
left[i] = stk.isEmpty() ? -1 : stk.peek();
stk.push(i);
}
for (int i = 0; i < n; ++i) {
res = Math.max(res, heights[i] * (right[i] - left[i] - 1));
}
return res;
}
}
C++
class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
int n = matrix[0].size();
vector<int> heights(n);
int ans = 0;
for (auto& row : matrix) {
for (int j = 0; j < n; ++j) {
if (row[j] == '1')
++heights[j];
else
heights[j] = 0;
}
ans = max(ans, largestRectangleArea(heights));
}
return ans;
}
int largestRectangleArea(vector<int>& heights) {
int res = 0, n = heights.size();
stack<int> stk;
vector<int> left(n, -1);
vector<int> right(n, n);
for (int i = 0; i < n; ++i) {
while (!stk.empty() && heights[stk.top()] >= heights[i]) {
right[stk.top()] = i;
stk.pop();
}
if (!stk.empty()) left[i] = stk.top();
stk.push(i);
}
for (int i = 0; i < n; ++i)
res = max(res, heights[i] * (right[i] - left[i] - 1));
return res;
}
};
86. 分隔链表
题目描述
给你一个链表的头节点 head
和一个特定值 x
,请你对链表进行分隔,使得所有 小于 x
的节点都出现在 大于或等于 x
的节点之前。
你应当 保留 两个分区中每个节点的初始相对位置。
示例 1:
输入:head = [1,4,3,2,5,2], x = 3
输出:[1,2,2,4,3,5]
示例 2:
输入:head = [2,1], x = 2
输出:[1,2]
提示:
- 链表中节点的数目在范围
[0, 200]
内 -100 <= Node.val <= 100
-200 <= x <= 200
难度:中等
标签:链表,双指针
解法
方法一:模拟
我们创建两个链表,一个存放小于 x x x 的节点,另一个存放大于等于 x x x 的节点,之后进行拼接即可。
时间复杂度 $O(n),其中 n n n 是原链表的长度。空间复杂度 O ( 1 ) O(1) O(1)。
Python3
## Definition for singly-linked list.
## class ListNode:
## def __init__(self, val=0, next=None):
## self.val = val
## self.next = next
class Solution:
def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
d1, d2 = ListNode(), ListNode()
t1, t2 = d1, d2
while head:
if head.val < x:
t1.next = head
t1 = t1.next
else:
t2.next = head
t2 = t2.next
head = head.next
t1.next = d2.next
t2.next = None
return d1.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 partition(ListNode head, int x) {
ListNode d1 = new ListNode();
ListNode d2 = new ListNode();
ListNode t1 = d1, t2 = d2;
while (head != null) {
if (head.val < x) {
t1.next = head;
t1 = t1.next;
} else {
t2.next = head;
t2 = t2.next;
}
head = head.next;
}
t1.next = d2.next;
t2.next = null;
return d1.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* partition(ListNode* head, int x) {
ListNode* d1 = new ListNode();
ListNode* d2 = new ListNode();
ListNode* t1 = d1;
ListNode* t2 = d2;
while (head) {
if (head->val < x) {
t1->next = head;
t1 = t1->next;
} else {
t2->next = head;
t2 = t2->next;
}
head = head->next;
}
t1->next = d2->next;
t2->next = nullptr;
return d1->next;
}
};
87. 扰乱字符串
题目描述
使用下面描述的算法可以扰乱字符串 s
得到字符串 t
:
- 如果字符串的长度为 1 ,算法停止
- 如果字符串的长度 > 1 ,执行下述步骤:
- 在一个随机下标处将字符串分割成两个非空的子字符串。即,如果已知字符串
s
,则可以将其分成两个子字符串x
和y
,且满足s = x + y
。 - 随机 决定是要「交换两个子字符串」还是要「保持这两个子字符串的顺序不变」。即,在执行这一步骤之后,
s
可能是s = x + y
或者s = y + x
。 - 在
x
和y
这两个子字符串上继续从步骤 1 开始递归执行此算法。
- 在一个随机下标处将字符串分割成两个非空的子字符串。即,如果已知字符串
给你两个 长度相等 的字符串 s1
和 s2
,判断 s2
是否是 s1
的扰乱字符串。如果是,返回 true
;否则,返回 false
。
示例 1:
输入:s1 = “great”, s2 = “rgeat”
输出:true
解释:s1 上可能发生的一种情形是:
“great” --> “gr/eat” // 在一个随机下标处分割得到两个子字符串
“gr/eat” --> “gr/eat” // 随机决定:「保持这两个子字符串的顺序不变」
“gr/eat” --> “g/r / e/at” // 在子字符串上递归执行此算法。两个子字符串分别在随机下标处进行一轮分割
“g/r / e/at” --> “r/g / e/at” // 随机决定:第一组「交换两个子字符串」,第二组「保持这两个子字符串的顺序不变」
“r/g / e/at” --> “r/g / e/ a/t” // 继续递归执行此算法,将 “at” 分割得到 “a/t”
“r/g / e/ a/t” --> “r/g / e/ a/t” // 随机决定:「保持这两个子字符串的顺序不变」
算法终止,结果字符串和 s2 相同,都是 “rgeat”
这是一种能够扰乱 s1 得到 s2 的情形,可以认为 s2 是 s1 的扰乱字符串,返回 true
示例 2:
输入:s1 = “abcde”, s2 = “caebd”
输出:false
示例 3:
输入:s1 = “a”, s2 = “a”
输出:true
提示:
s1.length == s2.length
1 <= s1.length <= 30
s1
和s2
由小写英文字母组成
难度:困难
标签:字符串,动态规划
解法
方法一:记忆化搜索
我们设计一个函数
d
f
s
(
i
,
j
,
k
)
dfs(i, j, k)
dfs(i,j,k),表示字符串
s
1
s_1
s1 从
i
i
i 开始长度为
k
k
k 的子串是否能变换为字符串
s
2
s_2
s2 从
j
j
j 开始长度为
k
k
k 的子串。如果能变换,返回 true
,否则返回 false
。那么答案就是
d
f
s
(
0
,
0
,
n
)
dfs(0, 0, n)
dfs(0,0,n),其中
n
n
n 是字符串的长度。
函数 d f s ( i , j , k ) dfs(i, j, k) dfs(i,j,k) 的计算方式如下:
- 如果
k
=
1
k=1
k=1,那么只需要判断
s
1
[
i
]
s_1[i]
s1[i] 和
s
2
[
j
]
s_2[j]
s2[j] 是否相等,如果相等返回
true
,否则返回false
; - 如果
k
>
1
k \gt 1
k>1,我们枚举分割部分的长度
h
h
h,那么有两种情况:如果不交换分割的两个子字符串,那么就是
d
f
s
(
i
,
j
,
h
)
∧
d
f
s
(
i
+
h
,
j
+
h
,
k
−
h
)
dfs(i, j, h) \land dfs(i+h, j+h, k-h)
dfs(i,j,h)∧dfs(i+h,j+h,k−h);如果交换了分割的两个子字符串,那么就是
d
f
s
(
i
,
j
+
k
−
h
,
h
)
∧
d
f
s
(
i
+
h
,
j
,
k
−
h
)
dfs(i, j+k-h, h) \land dfs(i+h, j, k-h)
dfs(i,j+k−h,h)∧dfs(i+h,j,k−h)。如果两种情况中有一种情况成立,那么就说明
d
f
s
(
i
,
j
,
k
)
dfs(i, j, k)
dfs(i,j,k) 成立,返回
true
,否则返回false
。
最后,我们返回 d f s ( 0 , 0 , n ) dfs(0, 0, n) dfs(0,0,n)。
为了避免重复计算,我们可以使用记忆化搜索的方式。
时间复杂度 O ( n 4 ) O(n^4) O(n4),空间复杂度 O ( n 3 ) O(n^3) O(n3)。其中 n n n 是字符串的长度。
Python3
class Solution:
def isScramble(self, s1: str, s2: str) -> bool:
@cache
def dfs(i: int, j: int, k: int) -> bool:
if k == 1:
return s1[i] == s2[j]
for h in range(1, k):
if dfs(i, j, h) and dfs(i + h, j + h, k - h):
return True
if dfs(i + h, j, k - h) and dfs(i, j + k - h, h):
return True
return False
return dfs(0, 0, len(s1))
Java
class Solution {
private Boolean[][][] f;
private String s1;
private String s2;
public boolean isScramble(String s1, String s2) {
int n = s1.length();
this.s1 = s1;
this.s2 = s2;
f = new Boolean[n][n][n + 1];
return dfs(0, 0, n);
}
private boolean dfs(int i, int j, int k) {
if (f[i][j][k] != null) {
return f[i][j][k];
}
if (k == 1) {
return s1.charAt(i) == s2.charAt(j);
}
for (int h = 1; h < k; ++h) {
if (dfs(i, j, h) && dfs(i + h, j + h, k - h)) {
return f[i][j][k] = true;
}
if (dfs(i + h, j, k - h) && dfs(i, j + k - h, h)) {
return f[i][j][k] = true;
}
}
return f[i][j][k] = false;
}
}
C++
class Solution {
public:
bool isScramble(string s1, string s2) {
int n = s1.size();
int f[n][n][n + 1];
memset(f, -1, sizeof(f));
function<bool(int, int, int)> dfs = [&](int i, int j, int k) -> int {
if (f[i][j][k] != -1) {
return f[i][j][k] == 1;
}
if (k == 1) {
return s1[i] == s2[j];
}
for (int h = 1; h < k; ++h) {
if (dfs(i, j, h) && dfs(i + h, j + h, k - h)) {
return f[i][j][k] = true;
}
if (dfs(i + h, j, k - h) && dfs(i, j + k - h, h)) {
return f[i][j][k] = true;
}
}
return f[i][j][k] = false;
};
return dfs(0, 0, n);
}
};
88. 合并两个有序数组
题目描述
给你两个按 非递减顺序 排列的整数数组 nums1
和 nums2
,另有两个整数 m
和 n
,分别表示 nums1
和 nums2
中的元素数目。
请你 合并 nums2
到 nums1
中,使合并后的数组同样按 非递减顺序 排列。
注意:最终,合并后数组不应由函数返回,而是存储在数组 nums1
中。为了应对这种情况,nums1
的初始长度为 m + n
,其中前 m
个元素表示应合并的元素,后 n
个元素为 0
,应忽略。nums2
的长度为 n
。
示例 1:
输入:nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出:[1,2,2,3,5,6]
解释:需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ,其中斜体加粗标注的为 nums1 中的元素。
示例 2:
输入:nums1 = [1], m = 1, nums2 = [], n = 0
输出:[1]
解释:需要合并 [1] 和 [] 。
合并结果是 [1] 。
示例 3:
输入:nums1 = [0], m = 0, nums2 = [1], n = 1
输出:[1]
解释:需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意,因为 m = 0 ,所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。
提示:
nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-109 <= nums1[i], nums2[j] <= 109
进阶:你可以设计实现一个时间复杂度为 O(m + n)
的算法解决此问题吗?
难度:简单
标签:数组,双指针,排序
解法
方法一:双指针
我们注意到数组的有序性,可以使用双指针的方法,从后向前遍历两个数组,每次取两个数组中较大的一个放进合并后的数组的最后面。
具体地,我们用两个指针 i i i 和 j j j 分别指向两个数组的末尾,用一个指针 k k k 指向合并后的数组的末尾。每次比较两个数组的末尾元素,将较大的元素放在合并后的数组的末尾,然后将指针向前移动一位,重复这个过程,直到两个数组的指针都指向了数组的开头。
时间复杂度 O ( m + n ) O(m + n) O(m+n),其中 m m m 和 n n n 分别是两个数组的长度。空间复杂度 O ( 1 ) O(1) O(1)。
Python3
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
k = m + n - 1
i, j = m - 1, n - 1
while j >= 0:
if i >= 0 and nums1[i] > nums2[j]:
nums1[k] = nums1[i]
i -= 1
else:
nums1[k] = nums2[j]
j -= 1
k -= 1
Java
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
for (int i = m - 1, j = n - 1, k = m + n - 1; j >= 0; --k) {
nums1[k] = i >= 0 && nums1[i] > nums2[j] ? nums1[i--] : nums2[j--];
}
}
}
C++
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
for (int i = m - 1, j = n - 1, k = m + n - 1; ~j; --k) {
nums1[k] = i >= 0 && nums1[i] > nums2[j] ? nums1[i--] : nums2[j--];
}
}
};
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]
提示:
1 <= n <= 16
难度:中等
标签:位运算,数学,回溯
解法
方法一:二进制码转格雷码
格雷码是我们在工程中常会遇到的一种编码方式,它的基本的特点就是任意两个相邻的代码只有一位二进制数不同。
二进制码转换成二进制格雷码,其法则是保留二进制码的最高位作为格雷码的最高位,而次高位格雷码为二进制码的高位与次高位相异或,而格雷码其余各位与次高位的求法相类似。
假设某个二进制数表示为 B n − 1 B n − 2 . . . B 2 B 1 B 0 B_{n-1}B_{n-2}...B_2B_1B_0 Bn−1Bn−2...B2B1B0,其格雷码表示为 G n − 1 G n − 2 . . . G 2 G 1 G 0 G_{n-1}G_{n-2}...G_2G_1G_0 Gn−1Gn−2...G2G1G0。最高位保留,所以 G n − 1 = B n − 1 G_{n-1} = B_{n-1} Gn−1=Bn−1;而其它各位 G i = B i + 1 ⊕ B i G_i = B_{i+1} \oplus B_{i} Gi=Bi+1⊕Bi,其中 i = 0 , 1 , 2.. , n − 2 i=0,1,2..,n-2 i=0,1,2..,n−2。
因此,对于一个整数 x x x,我们可以用函数 g r a y ( x ) gray(x) gray(x) 得到其格雷码:
int gray(x) {
return x ^ (x >> 1);
}
我们直接将 [ 0 , . . 2 n − 1 ] [0,..2^n - 1] [0,..2n−1] 这些整数映射成对应的格雷码,即可得到答案数组。
时间复杂度 O ( 2 n ) O(2^n) O(2n),其中 n n n 为题目给定的整数。忽略答案的空间消耗,空间复杂度 O ( 1 ) O(1) O(1)。
Python3
class Solution:
def grayCode(self, n: int) -> List[int]:
return [i ^ (i >> 1) for i in range(1 << n)]
Java
class Solution {
public List<Integer> grayCode(int n) {
List<Integer> ans = new ArrayList<>();
for (int i = 0; i < 1 << n; ++i) {
ans.add(i ^ (i >> 1));
}
return ans;
}
}
C++
class Solution {
public:
vector<int> grayCode(int n) {
vector<int> ans;
for (int i = 0; i < 1 << n; ++i) {
ans.push_back(i ^ (i >> 1));
}
return ans;
}
};
90. 子集 II
题目描述
给你一个整数数组 nums
,其中可能包含重复元素,请你返回该数组所有可能的 子集(幂集)。
解集 不能 包含重复的子集。返回的解集中,子集可以按 任意顺序 排列。
示例 1:
输入:nums = [1,2,2]
输出:[[],[1],[1,2],[1,2,2],[2],[2,2]]
示例 2:
输入:nums = [0]
输出:[[],[0]]
提示:
1 <= nums.length <= 10
-10 <= nums[i] <= 10
难度:中等
标签:位运算,数组,回溯
解法
方法一:排序 + DFS
我们可以先对数组 n u m s nums nums 进行排序,方便去重。
然后,我们设计一个函数 d f s ( i ) dfs(i) dfs(i),表示当前从第 i i i 个元素开始搜索子集。函数 d f s ( i ) dfs(i) dfs(i) 的执行逻辑如下:
如果 i ≥ n i \geq n i≥n,说明已经搜索完所有元素,将当前子集加入答案数组中,递归结束。
如果 i < n i < n i<n,将第 i i i 个元素加入子集,执行 d f s ( i + 1 ) dfs(i + 1) dfs(i+1),然后将第 i i i 个元素从子集中移除。接下来,我们判断第 i i i 个元素是否和下一个元素相同,如果相同,则循环跳过该元素,直到找到第一个和第 i i i 个元素不同的元素,执行 d f s ( i + 1 ) dfs(i + 1) dfs(i+1)。
最后,我们只需要调用 d f s ( 0 ) dfs(0) dfs(0),返回答案数组即可。
时间复杂度 O ( n × 2 n ) O(n \times 2^n) O(n×2n),空间复杂度 O ( n ) O(n) O(n)。其中 n n n 是数组的长度。
Python3
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
def dfs(i: int):
if i == len(nums):
ans.append(t[:])
return
t.append(nums[i])
dfs(i + 1)
x = t.pop()
while i + 1 < len(nums) and nums[i + 1] == x:
i += 1
dfs(i + 1)
nums.sort()
ans = []
t = []
dfs(0)
return ans
Java
class Solution {
private List<List<Integer>> ans = new ArrayList<>();
private List<Integer> t = new ArrayList<>();
private int[] nums;
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
this.nums = nums;
dfs(0);
return ans;
}
private void dfs(int i) {
if (i >= nums.length) {
ans.add(new ArrayList<>(t));
return;
}
t.add(nums[i]);
dfs(i + 1);
int x = t.remove(t.size() - 1);
while (i + 1 < nums.length && nums[i + 1] == x) {
++i;
}
dfs(i + 1);
}
}
C++
class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> ans;
vector<int> t;
int n = nums.size();
function<void(int)> dfs = [&](int i) {
if (i >= n) {
ans.push_back(t);
return;
}
t.push_back(nums[i]);
dfs(i + 1);
t.pop_back();
while (i + 1 < n && nums[i + 1] == nums[i]) {
++i;
}
dfs(i + 1);
};
dfs(0);
return ans;
}
};
原文地址:https://blog.csdn.net/qq_53481114/article/details/142695088
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!