142 环型链表
思路：剑指offer
关键点在于如何找出环的入口：先统计环的长度，然后两个指针从头出发，其中一个先出发环的长度，然后才一起前进，相遇之时就是环的入口。(因为它们本身的距离就相差环的长度)
没看题解 评论区代码 直接写了 或许自己的代码不优雅
后续有时间再说吧
public class Solution {
public ListNode detectCycle(ListNode head) {
if(head==null || head.next==null) return null;
ListNode fast=head.next,slow=head;
while(fast.next!=null&&fast.next.next!=null){
//一定要记得&& 不然 fast=fast.next.next;后可能变null 然后条件这里报空指针错误
if(fast==slow) break;
fast=fast.next.next;
slow=slow.next;
}
if(fast.next==null||fast.next.next==null) return null;//说明无环
//此时fast slow相遇了
//计算环中的节点数
int cnt=1;
fast=fast.next;
while(fast!=slow){
cnt++;
fast=fast.next;
}
ListNode n1=head,n2=head;
for(int i=0;i<cnt;i++){
n1=n1.next;
}
while(n1!=n2){
n1=n1.next;
n2=n2.next;
}
return n1;
}
}
152 乘积最大子数组
思路1:暴力穷举
思路2:dp
此题容易让人联想到之前的“最大子序和”
如果我们用 _max(i) 来表示以第 i 个元素结尾的乘积最大子数组的乘积，a 表示输入参数 nums，那么根据「53. 最大子序和」的经验，我们很容易推导出这样的状态转移方程：
它表示以第 i 个元素结尾的乘积最大子数组的乘积可以考虑 a_i 加入前面的 f_ max(i−1) 对应的一段，或者单独成为一段，这里两种情况下取最大值。求出所有的f_max(i) 之后选取最大的一个作为答案。
也就是说这样子简单的转移是不够完善的！
也就是说很小的负数乘积(最小值)可能遇到负数就翻盘成最大值。
(关键点：要注意的是“乘法”下由于两个负数的乘积也依然可能得到一个很大的正数，所以必须同时计算“最小子数组和”
那时候想到了，却没有想到把它保存下来，加入状态转移)
class Solution {
public int maxProduct(int[] nums) {
int maxF = nums[0], minF = nums[0], ans = nums[0];
int length = nums.length;
for (int i = 1; i < length; ++i) {
int mx = maxF, mn = minF;
maxF = Math.max(mx * nums[i], Math.max(nums[i], mn * nums[i]));
minF = Math.min(mn * nums[i], Math.min(nums[i], mx * nums[i]));
ans = Math.max(maxF, ans);
}
return ans;
}
}
自己的：
class Solution {
public int maxProduct(int[] nums) {
if(nums.length==1) return nums[0];
int pre_max=nums[0],pre_min=nums[0];
int cur_max,cur_min;
//int max=Integer.MIN_VALUE;//注意如何选取极值
//选取极值是错误的！有可能第一个是最大的！!
int max=nums[0];//！！！！
for(int i=1;i<nums.length;i++){
cur_max=Math.max(nums[i],Math.max(pre_max*nums[i],pre_min*nums[i]));
cur_min=Math.min(nums[i],Math.min(pre_max*nums[i],pre_min*nums[i]));
pre_min=cur_min;
pre_max=cur_max;
if(max<cur_max) max=cur_max;
}
return max;
}
}
复杂度分析
记 nums 元素个数为 n。
时间复杂度：程序一次循环遍历了 nums，故渐进时间复杂度为O(n)。
空间复杂度：优化后只使用常数个临时变量作为辅助空间，与 n 无关，故渐进空间复杂度为 O(1)。
https://leetcode-cn.com/problems/maximum-product-subarray/solution/duo-chong-si-lu-qiu-jie-by-powcai-3/
https://leetcode-cn.com/problems/maximum-product-subarray/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by--36/
