160. 相交鏈表
我的思路
先到空的node轉(zhuǎn)向另一個鏈表重新開始。
然后根據(jù)誰是空的走到另一邊也走到空為止蓝厌，此時兩個節(jié)點在同一起跑線
再相遇就是相交點或者大家都為空了
題解思路
我在判斷誰先走到nullptr上寫了大量代碼處理.其實大家都是各自走自己的一遍,對方的一遍到達(dá)空
while (nodeA != nodeB) {
if (nodeA != nullptr) {
nodeA = nodeA -> next;
}
else {
nodeA = headB;
}
if (nodeB != nullptr) {
nodeB = nodeB -> next;
}
else {
nodeB = headA;
}
}
某一刻為空時我們就走上了對方走過的路.
"錯的人遲早會走散,而對的人終會相逢"
這TM就是代碼的浪漫嗎
155. 最小棧
我原來的思路是用隊列或者哈希表什么的來模擬一個棧扮碧。結(jié)果告訴我搞一個同一數(shù)據(jù)結(jié)構(gòu)的輔助棧就可以了...
題解思路
使用輔助棧存放最小元素
1.如果不小于最小元素,assistantstack就push. st.top <= ast.top
注意:等于的時候ast也push
2.pop:不大于就pop. ast.top <= st.top
152. 乘積最大子數(shù)組
題解思路
當(dāng)前乘積max有三個可能瑟俭，一個是dpmax[i - 1] * nums[i] nums[i] dpmin[i - 1] * nums[i]
for (int i = 1; i < len; ++i) {
int premax = maxnum, premin = minnum;
maxnum = max(nums[i], max(premax * nums[i], premin * nums[i]));
minnum = min(nums[i], min(premin * nums[i], premax * nums[i]));
ans = max(ans, maxnum);
}
需要注意的地方：還需要比較nums[i]是為了消除0的影響[2,3,0,4,4,4]幫助災(zāi)后重建.否則0后大家都是0了
148. 排序鏈表
題解思路
分為兩個方法
1.將當(dāng)前鏈表拆成長度相似的兩個继蜡，分別排序
2.合并有序鏈表
146. LRU 緩存機制
題解思路
查找和獲得使用哈希表就能實現(xiàn)O(1)的復(fù)雜度赚楚，但是不能實現(xiàn)長時間未使用的在最后菱蔬，鏈表能夠處理的了這個問題圆兵，但是單向無法記錄最后的指針，所以使用雙向鏈表
