110- 平衡二叉树

问题

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

思路

递归。

代码

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

class Solution:
    def isBalanced(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return True
        if abs(self.max_len(root.left) - self.max_len(root.right)) > 1:
            return False
        else:
            return self.isBalanced(root.left) and self.isBalanced(root.right)
    
    def max_len(self, root):
        if not root:
            return 0
        else:
            return max(self.max_len(root.left), self.max_len(root.right)) + 1

上面的写法中，从上而下判断是否balance时要递归，判断到每个节点时计算max_len又要递归，导致递归很多，效率差。

其实只需递归一次。

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

class Solution:
    def isBalanced(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        return self.check(root) != -1
        
    def check(self, root):
        if not root:
            return 0
        l = self.check(root.left)
        r = self.check(root.right)
        
        if l == -1 or r == -1 or (abs(l - r) > 1):
            return -1
        else:
            return max(l, r) + 1
        

111- 二叉树的最小深度

问题

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

思路

递归来做。

代码

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

class Solution:
    def minDepth(self, root: 'TreeNode') -> 'int':
        if not root:
            return 0
        if root.left and root.right:
            return min(self.minDepth(root.left), self.minDepth(root.right)) + 1
        else:
            return max(self.minDepth(root.left), self.minDepth(root.right)) + 1

解释下上面代码中对 left and right的判断，如果左右都有孩子，则选左右孩子中深度min；如果只有一侧有孩子，那么应当按有孩子这一侧的深度来算，所以取max。

例如

          3
       /
      9
    /
   15

这种情况，深度为3，而不是1，因为3和9不是叶子节点。

解答这个题还有更好的思路，可以从上到下层次遍历，遇到叶节点时即返回其深度，不用递归就能实现。

class Solution:
    def minDepth(self, root: 'TreeNode') -> 'int':
        if not root:
            return 0
        n = 1
        q = [root, ]
        while q:
            size = len(q)
            for i in range(size):
                current = q.pop(0)
                if not current.left and not current.right:
                    return n
                if current.left:
                    q.append(current.left)
                if current.right:
                    q.append(current.right)
            n += 1

112- 路径总和

问题

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

代码

递归来做。

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

class Solution:
    def hasPathSum(self, root: TreeNode, sum: int) -> bool:
        if not root:
            return False
        if not root.left and not root.right:
            return sum - root.val == 0
        return self.hasPathSum(root.left, sum - root.val) or self.hasPathSum(root.right, sum - root.val)

118- 杨辉三角

问题

给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。

在杨辉三角中，每个数是它左上方和右上方的数的和。例如，

image

代码

class Solution:
    def generate(self, numRows):
        """
        :type numRows: int
        :rtype: List[List[int]]
        """
        result = []
        for i in range(numRows):
            now = [1] * (i + 1)
            if i >= 2:
                for n in range(1, i):
                    now[n] = pre[n-1]+pre[n]
            result.append(now)
            pre = now
        return result

119- 杨辉三角2

问题

给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。优化你的算法到 O(k) 空间复杂度
示例：
输入: 3（注意，3是0-based下标，实际是第4行了）
输出: [1,3,3,1]

思路

似乎避免不了要从第一层逐层迭代计算，但在迭代时可以只开辟 O(k)的空间，重复利用这块空间。

代码

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        # rowIndex是指下标
        result = [1] * (rowIndex + 1)
        for i in range(rowIndex + 1):
            for j in range(i-1, 0, -1): # 注意 要倒着做，正着会导致新值覆盖掉还要用到的旧值
                result[j] = result[j-1] + result[j]
        return result

121- 买卖股票的最佳时机

问题

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。

注意你不能在买入股票前卖出股票。

示例 1:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

示例 2:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

思路

1）暴力法，比较好想，从前往后逐个与它后面的所有计算一遍，记下最大值就行，n^2的时间复杂度

2）动态规划，从前往后遍历，记下之前的最小值和当前的最大利润，对每个新的点，更新最小值、最大利润即可。

代码

import sys

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        min_price = sys.maxsize
        max_profit = 0
        for i in range(len(prices)):
            max_profit = max(max_profit, prices[i] - min_price)
            min_price = min(min_price, prices[i])
        return max_profit

122- 买卖股票的最佳时机2

问题

修改规则，可以多次买入、卖出，求最大利润；但限制必须先卖出再买入，不可以在持有的情况下再继续买入。

输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

思路

思路就是遇到今天低明天高的情况就完成一次买入卖出，贪心。思路很简单，想清楚道理就行了。

如下图，如果AB两段做了两次买入卖出，赚到的肯定比C段多。

image

即使像下面连续涨的情况，赚到的也跟长期持有直至最高点时赚到的一样多，所以可以使用贪心的简单方法。

image

代码

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit = 0
        for i in range(len(prices) - 1):
            if prices[i] < prices[i+1]:
                profit += prices[i+1] - prices[i]
        return profit

125- 验证回文串

问题

给定字符串判断是否回文。只判断字母（大小写忽略）、数字，其他符号及空格忽略。空串认为是回文。

代码

class Solution:
    def isPalindrome(self, s: str) -> bool:
        if not s:
            return True
        s = ''.join(filter(str.isalnum,s)).lower() # 如何高效滤除其他字符！
        i, j = 0, len(s) - 1
        while i < j:
            if s[i] != s[j]:
                return False
            i += 1
            j -= 1
        return True

136- 只出现一次的数字

问题

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

思路

二进制异或 xor，出现两次的数字，每个数字和自身xor后结果为0，一堆0和那个只出现了一次的数字xor后，结果就是那个只出现一次的数字了。

更多可见 数组中只出现一次的数字

代码

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ret = 0
        for num in nums:
            ret = ret ^ num
        return ret

141- 环形链表

问题

给定一个链表，判断链表中是否有环。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

思路

快慢两个指针，相遇说明有环。
请参见剑指Offer 链表中环的入口结点

代码

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        fast = head
        slow = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                return True
        return False

155- 最小栈

问题

实现一个栈，除了具有栈的基本功能外，还支持 min 函数，随时返回当前栈中的最小值。

思路

入栈时不仅把元素入栈，还把当时栈中的最小值也入栈。
详见 包含min函数的栈

代码

class MinStack(object):

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.data = []

    def push(self, x):
        """
        :type x: int
        :rtype: None
        """
        if not self.data:
            self.data.append((x, x))
        else:
            min_value = min(x, self.data[-1][1])
            self.data.append((x, min_value))
        

    def pop(self):
        """
        :rtype: None
        """
        if self.data:
            return self.data.pop(-1)
        else:
            return None
        

    def top(self):
        """
        :rtype: int
        """
        if self.data:
            return self.data[-1][0]
        else:
            return None
        

    def getMin(self):
        """
        :rtype: int
        """
        if self.data:
            return self.data[-1][1]
        else:
            return None
        


# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

160- 相交链表

问题

编写一个程序，找到两个单链表相交的起始节点。

思路

要考虑的情况比较多：A长B短或者A短B长但最终相交，or 最终不相交。思维不清楚很容易就搞乱了。

代码

赏析一个很巧妙的写法。

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        if not headA or not headB:
            return None
        a, b = headA, headB
        while a != b:
            a = headB if not a else a.next
            b = headA if not b else b.next
        return a

短短几行代码，处理了有长有短、相交不交，各种情况！！

主要就是先ab各自从头走，a如果走到尽头的话，就指向headB，b如果尽头就指向headA，这样的操作目的是抹平了两条链表的长度差，不论a长还是b长，两个指针最终都会走过 len(A) + len(B) 的长度。而且如果有交点的话，由于交点之后的部分是公共的，长度相同，所以第二趟走到交点的时候必定会相交。如果不相交，最终同时到达null，返回值也是null。

妙啊！实在是太妙了！！

167- 两数之和2（有序数组）

问题

给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。

函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。

思路

由于数组已升序了，就比较好操作，两个指针前后向中间寻找。和小于target说明和太小了，应当增大left，大于target说明和太大了，应当减小right。

代码

class Solution(object):
    def twoSum(self, numbers, target):
        """
        :type numbers: List[int]
        :type target: int
        :rtype: List[int]
        """
        if not numbers:
            return []
        l, r = 0, len(numbers) - 1
        while l < r:
            if numbers[l] + numbers[r] == target:
                return [l+1, r+1] # 注意返回值不是下标，而是1-based，所以这里+1
            elif numbers[l] + numbers[r] < target:
                l += 1
            else:
                r -= 1
        return []

168- Excel表列名称

问题

给定一个正整数，返回它在 Excel 表中相对应的列名称。

思路

本质就是一个十进制转26进制，需要多留意一下边界条件。

代码

class Solution(object):
    def convertToTitle(self, n):
        """
        :type n: int
        :rtype: str
        """
        chars = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L',
             'M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z']
        result = []
        while n:
            mod = n % 26
            n //= 26
            if mod == 0:
                mod = 26
                n -= 1
            result.append(chars[mod-1])  # 注意下标
        return ''.join(result[::-1])

169- 数组中的众数

问题

给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

思路

多种解题思路，可参考剑指offer 数组中出现次数超过一半的数字.

代码

class Solution(object):
    def majorityElement(self, numbers):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not numbers:
            return 0
        target = numbers[0]
        count = 1
        for i in range(1, len(numbers)):
            if count == 0:
                target = numbers[i]
                count = 1
            elif target == numbers[i]:
                count += 1
            elif target != numbers[i]:
                count -= 1
        # count==0说明刚好消干净了，没有个数多于一半的，就不用再数了直接返回0
        if count == 0:
            return 0
        count = 0
        for i in range(0, len(numbers)):
            if numbers[i] == target:
                count += 1
        if count > len(numbers)/2:
            return target
        else:
            return 0

171- Excel表列序号

问题

给定一个Excel表格中的列名称，返回其相应的列序号。相当于之前168倒过来做，26进制转10进制。

代码

class Solution(object):
    def titleToNumber(self, s):
        """
        :type s: str
        :rtype: int
        """
        result = 0
        for c in s:
            result *= 26
            result += ord(c) - ord('A') + 1
        return result