Leetcode题解（4）- Easy
# 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
上面的写法中，从上而下判断是否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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
解释下上面代码中对 left and right的判断，如果左右都有孩子，则选左右孩子中深度min；如果只有一侧有孩子，那么应当按有孩子这一侧的深度来算，所以取max。
例如
3
/
9
/
15
2
3
4
5
这种情况，深度为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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 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)
2
3
4
5
6
7
8
9
10
11
12
13
14
# 118- 杨辉三角
# 问题
给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。
在杨辉三角中，每个数是它左上方和右上方的数的和。例如，
# 代码
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 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
2
3
4
5
6
7
8
# 121- 买卖股票的最佳时机
# 问题
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票。
示例 1:
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
2
3
4
示例 2:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
2
3
# 思路
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
2
3
4
5
6
7
8
9
10
# 122- 买卖股票的最佳时机2
# 问题
修改规则，可以多次买入、卖出，求最大利润；但限制必须先卖出再买入，不可以在持有的情况下再继续买入。
输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
2
3
4
# 思路
思路就是遇到今天低明天高的情况就完成一次买入卖出，贪心。思路很简单，想清楚道理就行了。
如下图，如果AB两段做了两次买入卖出，赚到的肯定比C段多。
即使像下面连续涨的情况，赚到的也跟长期持有直至最高点时赚到的一样多，所以可以使用贪心的简单方法。
# 代码
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
2
3
4
5
6
7
# 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
2
3
4
5
6
7
8
9
10
11
12
# 136- 只出现一次的数字
# 问题
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
# 思路
二进制异或 xor，出现两次的数字，每个数字和自身xor后结果为0，一堆0和那个只出现了一次的数字xor后，结果就是那个只出现一次的数字了。
更多可见 数组中只出现一次的数字 (opens new window)
# 代码
class Solution:
def singleNumber(self, nums: List[int]) -> int:
ret = 0
for num in nums:
ret = ret ^ num
return ret
2
3
4
5
6
# 141- 环形链表
# 问题
给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
# 思路
快慢两个指针，相遇说明有环。 请参见剑指Offer 链表中环的入口结点 (opens new window)
# 代码
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
2
3
4
5
6
7
8
9
10
11
12
13
14
# 155- 最小栈
# 问题
实现一个栈，除了具有栈的基本功能外，还支持 min 函数，随时返回当前栈中的最小值。
# 思路
入栈时不仅把元素入栈，还把当时栈中的最小值也入栈。 详见 包含min函数的栈 (opens new window)
# 代码
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()
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
# 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
2
3
4
5
6
7
8
9
10
11
12
13
短短几行代码，处理了有长有短、相交不交，各种情况！！
主要就是先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 []
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 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])
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 169- 数组中的众数
# 问题
给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
# 思路
多种解题思路，可参考剑指offer 数组中出现次数超过一半的数字 (opens new window).
# 代码
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# 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
2
3
4
5
6
7
8
9
10
11
# 172- 阶乘后的零
# 问题
给定一个整数 n，返回 n! 结果末尾连续的零的数量。
示例 1: 输入: 3 输出: 0 解释: 3! = 6, 尾数中没有零。
示例 2: 输入: 5 输出: 1 解释: 5! = 120, 尾数中有 1 个连续的零.
# 思路
首先题目的意思是末尾有几个连续的0，比如6! = 1 x 2 x 3 x 4 x 5 x 6，其中只有2x5末尾才有0，所以就可以只看阶乘中会有几个 2x5。比如10！ = 2 x 4 x 5 x 6 x 8 x 10，其中 4能拆成2x2 ，10能拆成2x5 ，所以10！ = 【2x（2x2）x5x（2x3）x（2x2x2）x（2x5）。一个2和一个5配对 就产生一个0 所以10！末尾2个0。
转头一想 2肯定比5多 所以只数5的个数就行了，有几个，末尾就有几个0. 假若N=31， 31的阶乘里，包含5的数为为[5, 2x5, 3x5, 4x5, 25, 6x5] ，其中 25还能拆为 5^2. 所以 里面的5的个数为 int(31/(5^1)) + int(31/(5^2))
所以 只要先找个一个 5^x < n 的x的最大数 然后按上面循环加起来
# 代码
class Solution:
def trailingZeroes(self, n: int) -> int:
cnt = 0
while n >= 1:
n //= 5
cnt += n
return cnt
2
3
4
5
6
7