leetcode-148-152

leetcode148题152题:

leetcode148题(排序链表):

O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序。

示例:

输入:4->2->1->3 输出:1->2->3->4

输入:-1->5->3->4->0 输出:-1->0->3->4->5

解答:

当题目输入的 head == Null 时,直接返回Null。

通过递归实现链表归并排序,有以下两个环节:

  1. 分割 cut 环节:
  • 找到当前链表中点,并从中点将链表断开(以便在下次递归 cut 时,链表片段拥有正确边界);
  • 我们使用 fast,slow 快慢双指针法,奇数个节点找到中点,偶数个节点找到中心左边的节点。
  • 找到中点 slow 后,执行 slow.next = Null 将链表切断。
  • 递归分割时,输入当前链表左端点 head 和中心节点 slow 的下一个节点 mid(因为链表是从 slow 切断的)。
  • cut 递归终止条件: 当head.next == None时,说明只有一个节点了,直接返回此节点。
  1. 合并 merge 环节:
  • 将两个排序链表合并,转化为一个排序链表。
  • 双指针法合并,建立辅助ListNode res(h) 作为头部。
  • 设置两指针 left, right 分别指向两链表头部,比较两指针处节点值大小,由小到大加入合并链表头部,指针交替前进,直至添加完两个链表。
  • 返回辅助ListNode h 作为头部的下个节点 h.next。
  • 时间复杂度 O(l + r),l, r 分别代表两个链表长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
var sortList = function(head) {//首先进行分割,递归分割为两个链表,然后进行合并排序
if(head==null||head.next==null){
return head;
}
var slow = head;
var fast = head.next;
while(fast!=null&&fast.next!=null){
slow = slow.next;
fast = fast.next.next;
}
var mid = slow.next;
slow.next = null;
//以上将链表分割为两个链表
var left = sortList(head);//得到左边链表的排序结果
var right = sortList(mid);//得到右边链表的排序结果
//对两个已经有序的链表进行排序
var res = new ListNode(null);
var h = res;
while(left!=null&&right!=null){
if(left.val<right.val){
res.next = left;
left = left.next;
}else{
res.next = right;
right = right.next;
}
res = res.next;
}
if(left==null){
res.next = right;
}else{
res.next = left;
}
return h.next;
};

leetcode152题(乘积最大子序列):

给定一个整数数组 nums ,找出一个序列中乘积最大的连续子序列(该序列至少包含一个数)。

示例:

输入:[2,3,-2,4] 输出:6

解释:子数组[2,3]有最大乘积6.

输入:[-2,0,-1] 输出:0

解释:结果不能为2,因为[-2,-1]不是子数组.

解答(动态规划):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
我们先定义一个数组 dpMax,用 dpMax[i] 表示以第 i 个元素的结尾的子数组,乘积最大的值,也就是这个数组必须包含第 i 个元素。那么 dpMax[i] 的话有以下几种取值:

1. 当 nums[i] >= 0 并且dpMax[i-1] > 0,dpMax[i] = dpMax[i-1] * nums[i]
2. 当 nums[i] >= 0 并且dpMax[i-1] < 0,此时如果和前边的数累乘的话,会变成负数,所以dpMax[i] = nums[i]

当 nums[i] < 0,此时如果前边累乘结果是一个很大的负数,和当前负数累乘的话就会变成一个更大的数。所以我们还需要一个数组 dpMin 来记录以第 i 个元素的结尾的子数组,乘积最小的值。
3. 当dpMin[i-1] < 0,dpMax[i] = dpMin[i-1] * nums[i]
4. 当dpMin[i-1] >= 0,dpMax[i] = nums[i]

当然,上边引入了 dpMin 数组,怎么求 dpMin 其实和上边求 dpMax 的过程其实是一样的。

按上边的分析,我们就需要加很多的 if else来判断不同的情况,这里可以用个技巧。
我们注意到上边dpMax[i] 的取值无非就是三种,dpMax[i-1] * nums[i]、dpMin[i-1] * nums[i] 以及 nums[i]。
所以我们更新的时候,无需去区分当前是哪种情况,只需要从三个取值中选一个最大的即可。
dpMax[i] = max(dpMax[i-1] * nums[i], dpMin[i-1] * nums[i], nums[i]);

求 dpMin[i] 同理。
dpMin[i] = min(dpMax[i-1] * nums[i], dpMin[i-1] * nums[i], nums[i]);

更新过程中,我们可以用一个变量 max 去保存当前得到的最大值。
1
2
3
4
5
6
7
8
9
10
11
12
var maxProduct = function(nums) {
var dpMax = nums[0];
var dpMin = nums[0];
var max = nums[0];
for(var i=1;i<nums.length;i++){
var preMax = dpMax;
dpMax = Math.max(dpMax*nums[i],nums[i],dpMin*nums[i]);
dpMin = Math.min(preMax*nums[i],nums[i],dpMin*nums[i]);
max = Math.max(max,dpMax);
}
return max;
};

艾丽·范宁

分享到