Leetcode 1. 两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
解题思路：一种是遍历一遍，复杂度O(n2)，也可以使用额外的字典来存储，只需要O(n)的复杂度。
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
dic = {}
for i in range(len(nums)):
another = target - nums[i]
if another in dic.keys():
res = (dic[another], i)
else:
dic[nums[i]] = i
return res
Leetcode 187. 重复的DNA序列
所有 DNA 由一系列缩写为 A，C，G 和 T 的核苷酸组成，例如：“ACGAATTCCG”。在研究 DNA 时，识别 DNA 中的重复序列有时会对研究非常有帮助。编写一个函数来查找 DNA 分子中所有出现超多一次的10个字母长的序列（子串）。
示例:
输入: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
输出: ["AAAAACCCCC", "CCCCCAAAAA"]
解题思路：用字典存储所有长度大于10的序列及其个数，然后输出个数大于2的序列。
class Solution(object):
def findRepeatedDnaSequences(self, s):
"""
:type s: str
:rtype: List[str]
"""
dic = {}
res = []
if len(s) < 10:
return None
for i in range(len(s)-10 + 1):
key = s[i:i+10]
if key not in dic:
dic[key] = 1
else:
dic[key] += 1
for j in dic.keys():
if dic[j] > 1:
res.append(j)
return res
Leetcode 652. 寻找重复结点
给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。两棵树重复是指它们具有相同的结构以及相同的结点值。
解题思路：前序遍历这棵树，然后把所有节点的前序遍历结果存在字典里面，然后看会不会重复。
# 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 dfs(self, root, hashmap, ans):
if root == None:
return '#END#'
my_order = str(root.val) + '\t' + self.dfs(root.left, hashmap, ans) + '\t' + self.dfs(root.right, hashmap, ans)
if hashmap.get(my_order) == 1:
ans.append(root)
hashmap[my_order] = max(1, hashmap.get(my_order, 0) + 1)
return my_order
def findDuplicateSubtrees(self, root):
"""
:type root: TreeNode
:rtype: List[TreeNode]
"""
hashmap = {}
ans = []
self.dfs(root, hashmap, ans)
return ans
Leetcode 560. 和为K的子数组
给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。
示例 1 :输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
说明 :
数组的长度为 [1, 20,000]。
数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。
解题思路：
前缀和
P[i] = A[0] + A[1] + … + A[i-1]
P[j] = A[0] + A[1] + … + A[j-1]
那么P[j] – P[i] = A[i] + A[i+1] + … + A[j-1]。
如果P[j] – P[i] == S的话，那么[i,j]就是符合条件的区间。所以对于每个j，只要计算有多少个i使得P[j] – P[i] == S。
class Solution(object):
def subarraySum(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
hashmap = {0:1}
cur_sum = 0
res = 0
for num in nums:
cur_sum += num
if cur_sum - k in hashmap:
res += hashmap[cur_sum-k]
hashmap[cur_sum] = hashmap[cur_sum] + 1 if cur_sum in hashmap else 1
return res
Leetcode 547. 朋友圈
班上有 N 名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。
给定一个 N * N 的矩阵 M，表示班级中学生之间的朋友关系。如果M[i][j] = 1，表示已知第 i 个和 j 个学生互为朋友关系，否则为不知道。你必须输出所有学生中的已知的朋友圈总数。
示例 1:
输入:
[[1,1,0],
[1,1,0],
[0,0,1]]
输出: 2
说明：已知学生0和学生1互为朋友，他们在一个朋友圈。
第2个学生自己在一个朋友圈。所以返回2。
示例 2:
输入:
[[1,1,0],
[1,1,1],
[0,1,1]]
输出: 1
说明：已知学生0和学生1互为朋友，学生1和学生2互为朋友，所以学生0和学生2也是朋友，所以他们三个在一个朋友圈，返回1。
解题思路：查并集，首先将每个元素初始化与自己的下标相对应，然后根据然后根据合并后下标的个数决定最终划分的集合个数。
class Solution(object):
def find(self, i, f):
if i == f[i]:
return i
else:
return self.find(f[i], f)
def findCircleNum(self, M):
"""
:type M: List[List[int]]
:rtype: int
"""
n = len(M)
f = [i for i in range(n)]
for i in range(n):
for j in range(i+1, n):
if M[i][j] == 1:
dx = self.find(i, f)
dy = self.find(j, f)
if dx != dy:
f[dy] = dx
ans = 0
for i in range(n):
if i == self.find(i, f):
ans += 1
return ans
Leetcode 684. 冗余连接
图片.png
解题思路：跟上一题一样，采用查并集法，每次往树结构里面增加一条边，如果增加的边上面的点以前出现过的话，那么就具有了连通性，从而判断是否为冗余边。
class Solution(object):
def find(self, i, f):
if i == f[i]:
return i
else:
return self.find(f[i], f)
def findRedundantConnection(self, edges):
"""
:type edges: List[List[int]]
:rtype: List[int]
"""
n = len(edges)
f = list(range(n+1))
for e in edges:
p1 = self.find(e[0], f)
p2 = self.find(e[1], f)
if p1 == p2:
return e
f[p2] = p1
Leetcode 692. 前K个高频单词
图片.png
解题思路：这里用到了优先队列。先统计所有词的词频存起来，然后取字典里面的前K个，放进初始的优先队列，然后比较后面的词频与优先队列中最小的词频的大小，如果词频更大，则进入优先队列。最后将优先队列中的词逆序输出。
import queue
class word:
def __init__(self, str, count):
self.str = str
self.count = count
def __gt__(self, other):
if self.count == other.count:
return self.str < other.str
else:
return self.count > other.count
def __lt__(self, other):
if self.count == other.count:
return self.str > other.str
else:
return self.count < other.count
class Solution(object):
def topKFrequent(self, words, k):
hash = {}
for w in words:
if w not in hash.keys():
hash[w] = 1
else:
hash[w] += 1
dict = [word(w, hash[w]) for w in hash.keys()]
que = queue.PriorityQueue()
for i in range(k):
que.put(dict[i])
for i in range(k, len(dict)):
if dict[i] > que.queue[0]:
que.get()
que.put(dict[i])
res = []
while not que.empty():
res.append(que.get().str)
res = res[::-1]
return res
Leetcode 295. 数据流的中位数
中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。
例如，
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构：
void addNum(int num) - 从数据流中添加一个整数到数据结构中。
double findMedian() - 返回目前所有元素的中位数。
class Solution:
def minWindow(self, s: 'str', t: 'str') -> 'str':
from collections import defaultdict
lookup = defaultdict(int)
for c in t:
lookup[c] += 1
start = 0
end = 0
min_len = float("inf")
counter = len(t)
res = ""
while end < len(s):
if lookup[s[end]] > 0:
counter -= 1
lookup[s[end]] -= 1
end += 1
while counter == 0:
if min_len > end - start:
min_len = end - start
res = s[start:end]
if lookup[s[start]] == 0:
counter += 1
lookup[s[start]] += 1
start += 1
return res
