中间经历了一段时间的思想斗争，发现自己还是想换个环境的，毕竟在这边已经显然拿不到年终奖了，晋升也没什么希望，所以还是应该尽快换到一个新的环境，所以从这周开始继续面试吧。今天看了几道LeetCode题目。简单记录一下思路。
- 53# 最大子序和
解题思路是两个变量tmp和max，tmp记录到当前位置之前的所有数字的和，当tmp小于0时，tmp赋值为当前数字，如果不小于0，继续加和。如果tmp大于max时，把tmp赋值给max。 - 70# 爬楼梯
解题思路是，当前的爬楼梯n需要的步数只有两种来源，一个是从n-1位置走一步到n，一种是从n-2位置走两步到n，所以s[n] = s[n-1] + s[n-2]。这个式子正好是满足斐波那契数列的。 - 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)
- 104# 二叉树的最大深度
解题思路就是递归求左子树的最大深度和右子树的最大深度，如果root为None，返回0，最后返回max(left, right) + 1，就是所求的结果。 - 121# 买卖股票的最佳时机
解题思路就是需要两个变量，一个min记录到目前为止出现的最小值，用max_profit记录利润的最大值，如果出现比min小的值更新min，如果出现比max_profit大的利润，更新max_profit。 - 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
- 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中的元素数量始终是一一对应的。 - 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
- 169# 求众数
这个题目很简单，但是一开始也没想到这个思路，排序后，位置在中间的就是众数了。因为出现次数要是整个长度的一半以上，所以排序后必然会是这样。 - 198# 打家劫舍
这个题目也是动态规划的题目，因为从某个点来看，它的来源只有两个，一个是偷了n-1家，就不能偷n了，一个是没有偷n-1, 那就是n-2偷完又偷了n，所以迭代公式为：memo[n] = max(memo[n-1], memo[n-2]+memo[n])。初始化的时候memo初始化为第一个元素即可。 - 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就是反转后的链表了。
网友评论