TOP 100 51 - 56

160. 相交链表

我的思路

先到空的node转向另一个链表重新开始。
然后根据谁是空的走到另一边也走到空为止，此时两个节点在同一起跑线
再相遇就是相交点或者大家都为空了

题解思路

我在判断谁先走到nullptr上写了大量代码处理.其实大家都是各自走自己的一遍,对方的一遍到达空

while (nodeA != nodeB) {
    if (nodeA != nullptr) {
        nodeA = nodeA -> next;
    }
    else {
        nodeA = headB;
    }

    if (nodeB != nullptr) {
        nodeB = nodeB -> next;
    }
    else {
        nodeB = headA;
    }
}

某一刻为空时我们就走上了对方走过的路.
"错的人迟早会走散,而对的人终会相逢"

这TM就是代码的浪漫吗

155. 最小栈

我原来的思路是用队列或者哈希表什么的来模拟一个栈。结果告诉我搞一个同一数据结构的辅助栈就可以了...

题解思路

使用辅助栈存放最小元素
1.如果不小于最小元素,assistantstack就push. st.top <= ast.top
注意:等于的时候ast也push
2.pop:不大于就pop. ast.top <= st.top

152. 乘积最大子数组

题解思路

当前乘积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]帮助灾后重建.否则0后大家都是0了

148. 排序链表

题解思路

分为两个方法
1.将当前链表拆成长度相似的两个，分别排序
2.合并有序链表

146. LRU 缓存机制

题解思路

查找和获得使用哈希表就能实现O(1)的复杂度，但是不能实现长时间未使用的在最后，链表能够处理的了这个问题，但是单向无法记录最后的指针，所以使用双向链表