题目101 对称二叉树
解法一：递归比对
- 结束条件：1.两个节点有空——都空T 否则F；2.两个节点数值不同——F
- 递归部分：两个节点数值相同——递归往两侧递归
但是没有看到特别的其他解法
#Definition for a binary tree node:
#class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
def isSymmetric(root):
if root==None:
return True
def is_mirror(left, right):
if (left == None) or (right == None):
return (left == None) and (right == None)
elif left.val !=right.val:
return False
else:
return (is_mirror(left.right, right.left) and is_mirror(left.left, right.right))
return is_mirror(root.left, root.right)
题目104 二叉树的最大深度
解答一：经典递归解答：
- 结束条件：==None
同样没有看到特别的其他解法
def maxDepth(root):
if root==None:
return 0
else:
depth1 = maxDepth(root.left)+1
depth2 = maxDepth(root.right)+1
if depth1>depth2:
return depth1
else:
return depth2
题目121 买卖股票的最佳时机
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
注意：你不能在买入股票前卖出股票。
-
输入: [7,1,5,3,6,4]
-
输出: 5
-
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。 -
输入: [7,6,4,3,1]
-
输出: 0
-
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
解答一，遍历
def maxprofit(prices):
maxprofit = 0
minprice = float('inf') # 无穷大
for price in prices:
minprice = min(minprice, price)
maxprofit = max(price-minprice, maxprofit)
return maxprofit
maxprofit([7,1,5,3,6,4])
maxprofit([7,6,4,3,1])
0
题目136 只出现一次的数字
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
输入: [4,1,2,1,2]
输出: 4
解法一，字典
随便写了一个
def singleNumber(numlist):
d = dict()
for i in numlist:
if i in d:
d[i] += 1
else:
d[i] = 1
for j in d.keys():
if d[j] == 1:
break
return j
singleNumber([4,1,2,1,2])
4
解法二：引入“异或”的概念
- 两个数字异或的结果a^b——将 a 和 b 的二进制每一位进行运算
- 任何数和本身异或: 0
- 任何数和 0 异或: 本身
时间击败94% 内存击败67%！
def singleNumber(numlist):
single = 0
for i in numlist:
single ^= i
return single
singleNumber([4,1,2,1,2])
4
题目141 环形链表
给定一个链表，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
解法一，遍历+字典
第一反应，遍历过的node +1；第二次next经过有就return True
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
def hasCycle(head):
d = dict()
node = head
while node:
if node in d:
return True
else:
d[node] = None
node = node.next
return False
解法二，快慢指针
快慢指针（龟兔赛跑，空间复杂度O(1)）
**要点：**枚举时添加一个慢一拍的指针（指针对应的是节点），如果有环最终两个指针会相遇
def hasCycle(head):
rabbit = head
turtle = head
tmp = False
while rabbit:
if tmp: # 乌龟走一步停一步
turtle = turtle.next
tmp = False
else:
tmp = True
rabbit = rabbit.next
if rabbit==turtle:
return True
return False
题目155 最小栈
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
- push(x) —— 将元素 x 推入栈中。
- pop() —— 删除栈顶的元素。
- top() —— 获取栈顶元素。
- getMin() —— 检索栈中的最小元素。
解法——辅助栈
关键点删除栈顶时候最小元素会变动，因此不能只保留最小值，要保留前i个中最小值序列（辅助栈），这样删除时把最小序列的栈顶也pop就可以了。
class MinStack:
def __init__(self):
self.stack = []
self.min_s = [math.inf]
def push(self, x):
self.stack.append(x)
self.min_s.append(min(x, self.min_s[-1]))
def pop(self):
self.stack.pop()
self.min_s.pop()
def top(self):
return self.stack[-1]
def getMin(self):
return self.min_s[-1]
题目169 多数元素
给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
解法一：字典
class Solution:
def majorityElement(self, nums: List[int]) -> int:
d = dict()
for i in nums:
if i in d:
d[i] += 1
else:
d[i] = 1
for j in d.keys():
if d[j]>len(nums)/2:
return j
break
解法二：多数投票法
候选人(cand_num)初始化为nums[0]，票数count初始化为1。
当遇到与cand_num相同的数，则票数count = count + 1，否则票数count = count - 1。
当票数count为0时，更换候选人，并将票数count重置为1。
遍历完数组后，cand_num即为最终答案。
def majorityElement(nums):
major = 0
count = 0
for n in nums:
if count == 0:
count = 1
major = n
elif n == major:
count += 1
else:
count -= 1
return major
majorityElement([2,2,1,1,1,2,2,3,2])
2