开篇记录面试第56天

中间经历了一段时间的思想斗争，发现自己还是想换个环境的，毕竟在这边已经显然拿不到年终奖了，晋升也没什么希望，所以还是应该尽快换到一个新的环境，所以从这周开始继续面试吧。今天看了几道LeetCode题目。简单记录一下思路。

1. 53# 最大子序和
   解题思路是两个变量tmp和max，tmp记录到当前位置之前的所有数字的和，当tmp小于0时，tmp赋值为当前数字，如果不小于0，继续加和。如果tmp大于max时，把tmp赋值给max。
2. 70# 爬楼梯
   解题思路是，当前的爬楼梯n需要的步数只有两种来源，一个是从n-1位置走一步到n，一种是从n-2位置走两步到n，所以s[n] = s[n-1] + s[n-2]。这个式子正好是满足斐波那契数列的。
3. 101# 对称二叉树
   解题思路，大的方向是判断递归判断左子树和右子树是否对称，这里判断对称需要另外一个函数来完成。在这个函数里，传入两个参数就是要比较的两个子树的两个父结点，如果他们的值相等，那递归调用issymmetric，判断左子树的右孩子和右子树的左孩子是否对称，以及右子树的左孩子和左子树的右孩子是否对称。如果值不相等，则直接返回False。贴一下代码：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        def issymmetric(ltree, rtree):
            if ltree == None:
                return rtree == None
            if rtree == None:
                return ltree == None
            # 如果左右孩子的值相同，那就比较左孩子的左孩子和右孩子的右孩子是否对称
            #以及右孩子的左孩子和左孩子的右孩子是否对称
            if ltree.val == rtree.val:
                return issymmetric(ltree.left,rtree.right) and issymmetric(rtree.left, ltree.right)
            if ltree.val != rtree.val:
                return False
        
        
        
        if root == None:
            return True
        return issymmetric(root.left, root.right)

4. 104# 二叉树的最大深度
   解题思路就是递归求左子树的最大深度和右子树的最大深度，如果root为None，返回0，最后返回max(left, right) + 1，就是所求的结果。
5. 121# 买卖股票的最佳时机
   解题思路就是需要两个变量，一个min记录到目前为止出现的最小值，用max_profit记录利润的最大值，如果出现比min小的值更新min，如果出现比max_profit大的利润，更新max_profit。
6. 141# 环形链表
   这里有一个重要的思路就是如果要实现O(1)的空间复杂度，往往需要借助两个指针，由于这里不能从后往前遍历，所以就让一个指针移动一步，一个指针移动两步，如果两个指针相遇了就是有环。另一个要注意的问题就是循环的结束条件，是快指针为空，或者它的next为空。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def hasCycle(self, head):
        """
        一个快指针，一个慢指针，快指针一次走两步
        慢指针一次走一步，
        如果快指针和慢指针遇到了，
        就说明有环了
        :type head: ListNode
        :rtype: bool
        """
        former = head
        after = head
        while(after and after.next):
            former = former.next
            after = after.next.next
            if former == after:
                return True
        return False

7. 155# 最小栈
   这个题目中栈的实现使用list，append操作就可以实现push函数，del就可以pop，要实现最小栈的功能，就需要另外一个记录A栈最小值的B栈。每当A插入一个元素，就需要跟B的top进行比较，因为B始终存的是A的最小值，所以如果这个值比B的top小，那就是新的最小值，把它压入B，否则，把B的top压入B。同时在popA中的元素时，也要同时把B中的top元素pop出去，因为A和B中的元素数量始终是一一对应的。
8. 160# 相交链表
   这个题目的解法是两个指针从两个链表的头部开始遍历，如果到尾部了，就把尾指针指向另一个链表的头指针。这个地方如果有交点肯定很好理解了，但是如果没有交点的话会不会无限循环下去呢？如果有知道答案的小伙伴可以在下面留言哈。非常感谢！

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        p, q = headA, headB
        while p != q:
            p = headB if p is None else p.next
            q = headA if q is None else q.next
        return p

9. 169# 求众数
   这个题目很简单，但是一开始也没想到这个思路，排序后，位置在中间的就是众数了。因为出现次数要是整个长度的一半以上，所以排序后必然会是这样。
10. 198# 打家劫舍
    这个题目也是动态规划的题目，因为从某个点来看，它的来源只有两个，一个是偷了n-1家，就不能偷n了，一个是没有偷n-1, 那就是n-2偷完又偷了n，所以迭代公式为：memo[n] = max(memo[n-1], memo[n-2]+memo[n])。初始化的时候memo初始化为第一个元素即可。
11. 206# 反转链表
    这个题目关键的点就是能画图画清楚，指针是如何指的。这里面涉及三个指针，cur代表当前节点，pre代表上一个节点，nxt代表下一个节点。在最开始我们要让cur=head，pre=None，nxt=cur.next，进入循环以后，cur.next = pre,pre=cur,cur=nxt,nxt=nxt.next,最后到末尾的时候，pre已经指在最后一个值上了，这时候需要来一个head指针，所以令cur.next =pre,head=pre,返回head就是反转后的链表了。