开篇记录面试第57天

真的没想到这次找工作会经历这么长的时间，不过感觉最近公司的活动频繁一些了，开始有比较多的公司在接触了，所以现在要打起精神来了，一举拿下满意的offer。

Leetcode题目分析

1. 226# 翻转二叉树
   这个题目的思路是用递归，左子树等于右子树的翻转，右子树等于左子树的翻转，要注意的就是递归之前要先记录子树变量，不能直接用root.left这种直接进行递归，看代码：

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

class Solution(object):
    def invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        if root is None:
            return None
        left = root.left
        right = root.right
        root.left = self.invertTree(right)
        root.right = self.invertTree(left)
        return root

2. 234# 回文链表
   因为题目要求用O(n)时间复杂度O(1)空间复杂度，所以还是要依赖两个指针，具体的做法是需要一快一慢两个指针，快指针到末尾的时候，将慢指针后面的链表进行逆序，这时候就需要另外一个指针，p，p从链表头部和慢指针同时移动，如果p和慢指针指向的元素都相同，就是回文链表，如果有不一样的值，就不是了。
   代码如下：

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

class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if head is None or head.next is None:
            return True
        if head.next.next is None:
            return head.val == head.next.val
        slow = fast = p = head
        while fast.next and fast.next.next:
            fast = fast.next.next
            slow = slow.next
        def reverselinklist(head):
            if head is None:
                return None
            cur = head
            pre = None
            nxt = cur.next
            while nxt:
                cur.next = pre
                pre = cur
                cur = nxt
                nxt = nxt.next
            cur.next = pre
            head = cur
            return head
        q = reverselinklist(slow.next)
        while q.next:
            if p.val != q.val:
                return False
            p = p.next
            q = q.next
        return p.val == q.val

3. 283# 移动0
   这道题的思路有一个比较巧妙的解，就是用一个变量j记录前面遍历到的非0位置，从头开始遍历数组，如果数不为0，则把当前数与j位置的数交换，同时j向后移动一位，如果数为0，j不动，所以j指向的是遍历到目前位置，最后一个非0数字的位置。
   代码：

class Solution(object):
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        j = 0
        for i in range(len(nums)):
            nums[i], nums[j] = nums[j], nums[i]
            j += 1
        return nums

4. 437# 路径总和三
   这个题目的关键是dfs（深度优先搜索），首先是要对每一个节点都遍历到，这个通过一个search函数实现，其次要通过dfs计算每个节点的路径值。直接上代码吧。

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

class Solution(object):
    def pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: int
        """
        self.result = 0
        self.search(root, sum)
        return self.result
    
    def search(self, root, sum):
        if root is None:
            return
        self.dfs(root, 0, sum)
        self.search(root.left, sum)
        self.search(root.right, sum)
        
    def dfs(self, root, sum1, sum):
        if root is None:
            return
        sum1 += root.val
        if sum1 == sum:
            self.result += 1
        self.dfs(root.left, sum1, sum)
        self.dfs(root.right, sum1, sum)