142 環(huán)型鏈表
思路：劍指offer
關(guān)鍵點在于如何找出環(huán)的入口：先統(tǒng)計環(huán)的長度，然后兩個指針從頭出發(fā)，其中一個先出發(fā)環(huán)的長度，然后才一起前進，相遇之時就是環(huán)的入口。(因為它們本身的距離就相差環(huán)的長度)
沒看題解 評論區(qū)代碼 直接寫了 或許自己的代碼不優(yōu)雅
后續(xù)有時間再說吧
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;//說明無環(huán)
//此時fast slow相遇了
//計算環(huán)中的節(jié)點數(shù)
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 乘積最大子數(shù)組
思路1:暴力窮舉
思路2:dp
此題容易讓人聯(lián)想到之前的“最大子序和”
如果我們用 _max(i) 來表示以第 i 個元素結(jié)尾的乘積最大子數(shù)組的乘積，a 表示輸入?yún)?shù) nums，那么根據(jù)「53. 最大子序和」的經(jīng)驗，我們很容易推導(dǎo)出這樣的狀態(tài)轉(zhuǎn)移方程：
它表示以第 i 個元素結(jié)尾的乘積最大子數(shù)組的乘積可以考慮 a_i 加入前面的 f_ max(i?1) 對應(yīng)的一段，或者單獨成為一段，這里兩種情況下取最大值。求出所有的f_max(i) 之后選取最大的一個作為答案。
也就是說這樣子簡單的轉(zhuǎn)移是不夠完善的！
也就是說很小的負數(shù)乘積(最小值)可能遇到負數(shù)就翻盤成最大值。
(關(guān)鍵點：要注意的是“乘法”下由于兩個負數(shù)的乘積也依然可能得到一個很大的正數(shù)，所以必須同時計算“最小子數(shù)組和”
那時候想到了，卻沒有想到把它保存下來，加入狀態(tài)轉(zhuǎn)移)
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;
}
}
復(fù)雜度分析
記 nums 元素個數(shù)為 n。
時間復(fù)雜度：程序一次循環(huán)遍歷了 nums，故漸進時間復(fù)雜度為O(n)。
空間復(fù)雜度：優(yōu)化后只使用常數(shù)個臨時變量作為輔助空間，與 n 無關(guān)，故漸進空間復(fù)雜度為 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/
