152. 乘积最大子数组
给你一个整数数组
nums，请你找出数组中乘积最大的非空连续子数组
（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。测试用例的答案是一个 32-位 整数。
示例 1:
输入: nums = [2,3,-2,4] 输出:6解释: 子数组 [2,3] 有最大乘积 6。示例 2:
输入: nums = [-2,0,-1] 输出: 0 解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
解题思路
可以使用动态规划的方法。对于数组中的每一个元素，我们需要考虑到达该元素位置时的最大乘积和最小乘积（负数乘以负数可能得到最大乘积）。这样，我们可以维护两个动态数组：maxDP 和 minDP，其中 maxDP[i] 表示以 nums[i] 结尾的子数组的最大乘积，minDP[i] 表示以 nums[i] 结尾的子数组的最小乘积。
对于每一个元素 nums[i]，我们需要考虑以下三种情况来决定 maxDP[i] 和 minDP[i] 的值：
- 只取当前元素 nums[i]。
- 当前元素 nums[i] 乘以前一个元素的最大乘积 maxDP[i-1]。
- 当前元素 nums[i] 乘以前一个元素的最小乘积 minDP[i-1]（当当前元素为负数时可能得到最大乘积）。
因此，状态转移方程为：
- maxDP[i] = max(nums[i], nums[i] * maxDP[i-1], nums[i] * minDP[i-1])
- minDP[i] = min(nums[i], nums[i] * maxDP[i-1], nums[i] * minDP[i-1])
最终答案为 maxDP 数组中的最大值。
完整代码
Python
class Solution:
def maxProduct(self, nums: List[int]) -> int:
if not nums:
return 0
# 初始化 maxDP 和 minDP 为 nums，因为最小的子数组就是数组本身
maxDP = nums[:]
minDP = nums[:]
for i in range(1, len(nums)):
maxDP[i] = max(nums[i], nums[i] * maxDP[i-1], nums[i] * minDP[i-1])
minDP[i] = min(nums[i], nums[i] * maxDP[i-1], nums[i] * minDP[i-1])
# 最大乘积为 maxDP 中的最大值
return max(maxDP)Java
public class Solution {
public int maxProduct(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int[] maxDP = new int[nums.length];
int[] minDP = new int[nums.length];
maxDP[0] = minDP[0] = nums[0];
int result = nums[0];
for (int i = 1; i < nums.length; i++) {
maxDP[i] = Math.max(nums[i], Math.max(nums[i] * maxDP[i - 1], nums[i] * minDP[i - 1]));
minDP[i] = Math.min(nums[i], Math.min(nums[i] * maxDP[i - 1], nums[i] * minDP[i - 1]));
result = Math.max(result, maxDP[i]);
}
return result;
}
}153. 寻找旋转排序数组中的最小值
已知一个长度为
n的数组，预先按照升序排列，经由1到n次 旋转 后，得到输入数组。例如，原数组nums = [0,1,2,4,5,6,7]在变化后可能得到：
- 若旋转
4次，则可以得到[4,5,6,7,0,1,2]- 若旋转
7次，则可以得到[0,1,2,4,5,6,7]注意，数组
[a[0], a[1], a[2], ..., a[n-1]]旋转一次 的结果为数组[a[n-1], a[0], a[1], a[2], ..., a[n-2]]。给你一个元素值 互不相同 的数组
nums，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。你必须设计一个时间复杂度为
O(log n)的算法解决此问题。
示例 1：
输入：nums = [3,4,5,1,2] 输出：1 解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。示例 2：
输入：nums = [4,5,6,7,0,1,2] 输出：0 解释：原数组为 [0,1,2,4,5,6,7] ，旋转 3 次得到输入数组。示例 3：
输入：nums = [11,13,15,17] 输出：11 解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。
解题思路
我们可以使用二分查找算法。由于数组原本是升序的，并且进行了旋转，因此我们可以观察到至少有一半的数组仍然是有序的。我们可以利用这个特点来进行二分查找，从而在 O(log n) 的时间复杂度内找到数组中的最小元素。
具体算法如下：
- 初始化左指针
left为 0，右指针right为nums.length - 1。 - 当
left < right时，进行二分查找：- 找到中间位置
mid= (left+right) / 2。 - 如果
nums[mid] > nums[right]，说明最小值在mid的右边，将left设置为mid + 1。 - 否则，最小值在
mid或其左边，将right设置为mid。
- 找到中间位置
- 当二分查找结束时，
left和right将指向数组中最小元素的位置，返回nums[left]即可。
完整代码
Python
class Solution:
def findMin(self, nums: List[int]) -> int:
left, right = 0, len(nums) - 1
while left < right:
mid = (left + right) // 2
if nums[mid] > nums[right]:
left = mid + 1
else:
right = mid
return nums[left]Java
public class Solution {
public int findMin(int[] nums) {
int left = 0, right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[right]) {
left = mid + 1;
} else {
right = mid;
}
}
return nums[left];
}
}160. 相交链表
给你两个单链表的头节点
headA和headB，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回null。图示两个链表在节点
c1开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
自定义评测：
评测系统 的输入如下（你设计的程序 不适用 此输入）：
intersectVal- 相交的起始节点的值。如果不存在相交节点，这一值为0listA- 第一个链表listB- 第二个链表skipA- 在listA中（从头节点开始）跳到交叉节点的节点数skipB- 在listB中（从头节点开始）跳到交叉节点的节点数评测系统将根据这些输入创建链式数据结构，并将两个头节点
headA和headB传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。
示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3 输出：Intersected at '8' 解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。 从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。 在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。 — 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。
示例 2：
输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1 输出：Intersected at '2' 解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。 从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。 在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。示例 3：
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2 输出：null 解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。 由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。 这两个链表不相交，因此返回 null 。
解题思路
要找到两个单链表相交的起始节点，我们可以使用双指针法。这个方法的核心思想是让两个指针分别遍历两个链表，当一个指针到达链表末尾时，将其重定向到另一个链表的头部继续遍历。如果两个链表相交，那么这两个指针最终会在相交节点相遇；如果不相交，那么这两个指针会同时到达各自链表的末尾（即都为 null），此时也能得到结果。
- 初始化两个指针
pA和pB，分别指向两个链表的头节点headA和headB。 - 同时遍历两个链表，每次各自前进一步。
- 当
pA到达链表末尾时，将pA重定向到headB；同理，当pB到达链表末尾时，将pB重定向到headA。 - 如果两个链表相交，
pA和pB最终会在相交节点相遇；如果不相交，pA和pB会同时为null，此时退出循环。
完整代码
Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
pA, pB = headA, headB
while pA != pB:
pA = pA.next if pA else headB
pB = pB.next if pB else headA
return pA
Java
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode pA = headA, pB = headB;
while (pA != pB) {
pA = (pA != null) ? pA.next : headB;
pB = (pB != null) ? pB.next : headA;
}
return pA;
}
}
