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

Leetcode: 0081-0090题速览

article 2024/10/4 15:04:33

Leetcode: 0081-0090题速览

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

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

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

目录

  • Leetcode: 0081-0090题速览
    • [81. 搜索旋转排序数组 II](https://leetcode.cn/problems/search-in-rotated-sorted-array-ii)
      • 题目描述
      • 解法
        • 方法一：二分查找
          • Python3
          • Java
          • C++
    • [82. 删除排序链表中的重复元素 II](https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii)
      • 题目描述
      • 解法
        • 方法一：一次遍历
          • Python3
          • Java
          • C++
    • [83. 删除排序链表中的重复元素](https://leetcode.cn/problems/remove-duplicates-from-sorted-list)
      • 题目描述
      • 解法
        • 方法一：一次遍历
          • Python3
          • Java
          • C++
    • [84. 柱状图中最大的矩形](https://leetcode.cn/problems/largest-rectangle-in-histogram)
      • 题目描述
      • 解法
        • 方法一：单调栈
          • Python3
          • Java
          • C++
    • [85. 最大矩形](https://leetcode.cn/problems/maximal-rectangle)
      • 题目描述
      • 解法
        • 方法一：单调栈
          • Python3
          • Java
          • C++
    • [86. 分隔链表](https://leetcode.cn/problems/partition-list)
      • 题目描述
      • 解法
        • 方法一：模拟
          • Python3
          • Java
          • C++
    • [87. 扰乱字符串](https://leetcode.cn/problems/scramble-string)
      • 题目描述
      • 解法
        • 方法一：记忆化搜索
          • Python3
          • Java
          • C++
    • [88. 合并两个有序数组](https://leetcode.cn/problems/merge-sorted-array)
      • 题目描述
      • 解法
        • 方法一：双指针
          • Python3
          • Java
          • C++
    • [89. 格雷编码](https://leetcode.cn/problems/gray-code)
      • 题目描述
      • 解法
        • 方法一：二进制码转格雷码
          • Python3
          • Java
          • C++
    • [90. 子集 II](https://leetcode.cn/problems/subsets-ii)
      • 题目描述
      • 解法
        • 方法一：排序 + DFS
          • Python3
          • Java
          • C++

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 ，算法停止
  2. 如果字符串的长度 > 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−1​Bn−2​...B2​B1​B0​，其格雷码表示为 G n − 1 G n − 2 . . . G 2 G 1 G 0 G_{n-1}G_{n-2}...G_2G_1G_0 Gn−1​Gn−2​...G2​G1​G0​。最高位保留，所以 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;
    }
};

http://www.kler.cn/news/331862.html

相关文章：

  • 信息学奥赛一本通 1416：【17NOIP普及组】棋盘 | 洛谷 P3956 [NOIP2017 普及组] 棋盘
  • 从认识String类，到走进String类的世界
  • fNIRS光极排布——基于fNIRS Optodes’ Location Decider (fOLD)工具包
  • 用户登录与信息管理：实现小程序登录与用户信息存储
  • 民峰：助力投资者实现财务自由
  • 大语言模型入门（三）——提示词编写注意事项
  • 查缺补漏----I/O中断处理过程
  • 什么是大语言模型的上下文窗口
  • 记一次vue-cli老项目的打包时长优化
  • 操作系统的组成及层次模型
  • C（九）while循环 --- 军训匕首操情景
  • c++ arrayfire库 矩阵分块
  • SUP-NeRF-ECCV2024数据集: 单目3D对象重建的新突破
  • kafka监控平台Kafdrop：使用记录
  • STL之list篇（下）（从底层分析实现list容器，逐步剥开list的外表）
  • Ubuntu环境下字体安装
  • 问：如何判断系统环境是大端/小端存储？
  • 接口隔离原则在前端的应用
  • 大数据处理从零开始————8.基于Java构建WordCount项目
  • 升级 OpenSSL 的详细步骤（解决 SSH 漏洞的前提）