Skip to content

Commit 68c86a6

Browse files
melody-limelody-li
authored
Merge pull request algorithm004-01#389 from laxlyt/master
246-Week 02
2 parents 241ca43 + 2d7a059 commit 68c86a6

17 files changed

+745
-1
lines changed

‎Week 02/id_246/LeetCode_105_246.py‎

Lines changed: 58 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,58 @@
1+
'''
2+
construct binary tree from preorder and inorder traversal_105
3+
4+
根据一棵树的前序遍历与中序遍历构造二叉树。
5+
6+
注意:
7+
你可以假设树中没有重复的元素。
8+
9+
例如，给出
10+
11+
前序遍历 preorder = [3,9,20,15,7]
12+
中序遍历 inorder = [9,3,15,20,7]
13+
返回如下的二叉树：
14+
15+
3
16+
/ \
17+
9 20
18+
/ \
19+
15 7
20+
'''
21+
22+
23+
#递归
24+
class TreeNode(object):
25+
def __init__(self, x):
26+
self.val = x
27+
self.left = None
28+
self.right = None
29+
30+
def buildTree_1(preorder, inorder):
31+
def helper(in_left = 0, in_right = len(inorder)):
32+
nonlocal pre_idx
33+
if in_left == in_right:
34+
return None
35+
# pick up pre_idx element as a root
36+
root_val = preorder[pre_idx]
37+
root = TreeNode(root_val)
38+
# root splits inorder list
39+
# into left and right subtrees
40+
index = idx_map[root_val]
41+
pre_idx += 1
42+
root.left = helper(in_left, index)
43+
root.right = helper(index+1, in_right)
44+
return root
45+
46+
pre_idx = 0
47+
idx_map = {val:idx for idx, val in enumerate(inorder)}
48+
return helper()
49+
50+
51+
#
52+
def buildTree_2(preorder, inorder):
53+
if inorder:
54+
ind = inorder.index(preorder.pop(0))
55+
root = TreeNode(inorder[ind])
56+
root.left = buildTree_2(preorder, inorder[0:ind])
57+
root.right = buildTree_2(preorder, inorder[ind+1:])
58+
return root

‎Week 02/id_246/LeetCode_144_246.py‎

Lines changed: 76 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,76 @@
1+
'''
2+
binary tree preorder traversal_144
3+
4+
给定一个二叉树，返回它的 前序 遍历。 中左右
5+
6+
 示例:
7+
8+
输入: [1,null,2,3]
9+
1
10+
\
11+
2
12+
/
13+
3
14+
15+
输出: [1,2,3]
16+
'''
17+
18+
from collections import deque
19+
20+
class TreeNode:
21+
def __init__(self,x):
22+
self.val = x
23+
self.left = None
24+
self.right = None
25+
26+
27+
class Tree(object):
28+
def __init__(self):
29+
self.root = None
30+
31+
def construct_tree(self,values=None):
32+
if not values:
33+
return None
34+
self.root = TreeNode(values[0])
35+
queue = deque([self.root])
36+
leng = len(values)
37+
nums = 1
38+
while nums < leng:
39+
node = queue.popleft()
40+
if node:
41+
node.left =TreeNode(values[nums]) if values[nums] else None
42+
queue.append(node.left)
43+
if nums + 1 < leng:
44+
node.right = TreeNode(values[nums+1]) if values[nums+1] else None
45+
queue.append(node.right)
46+
nums += 1
47+
nums += 1
48+
49+
#递归
50+
def preorderTraversal_1(self):
51+
res = []
52+
def traversal(head):
53+
if not head:
54+
return
55+
res.append(head.val)
56+
traversal(head.left)
57+
traversal(head.right)
58+
59+
traversal(self.root)
60+
return res
61+
62+
#迭代
63+
def preorderTraversal_2(self):
64+
if self.root is None:
65+
return []
66+
stack, output = [self.root, ], []
67+
68+
while stack:
69+
self.root = stack.pop()
70+
if self.root is not None:
71+
output.append(self.root.val)
72+
if self.root.right is not None:
73+
stack.append(self.root.right)
74+
if self.root.left is not None:
75+
stack.append(self.root.left)
76+
return output

‎Week 02/id_246/LeetCode_169_246.py‎

Lines changed: 52 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,52 @@
1+
'''
2+
majority element_169
3+
4+
给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
5+
6+
你可以假设数组是非空的，并且给定的数组总是存在众数。
7+
8+
示例 1:
9+
10+
输入: [3,2,3]
11+
输出: 3
12+
示例 2:
13+
14+
输入: [2,2,1,1,1,2,2]
15+
输出: 2
16+
'''
17+
18+
# 暴力
19+
def majorityElement_1(nums):
20+
majority_count = len(nums)//2
21+
for num in nums:
22+
count = sum(1 for elem in nums if elem == num)
23+
if count > majority_count:
24+
return num
25+
26+
27+
# hash
28+
import collections
29+
def majorityElement_2(nums):
30+
counts = collections.Counter(nums)
31+
return max(counts.keys(), key = counts.get)
32+
33+
34+
# 分治
35+
def majorityElement_3(nums, lo=0, hi=None):
36+
def majority_element_rec(lo, hi):
37+
if lo == hi:
38+
return nums[lo]
39+
40+
mid = (hi-lo)//2 + lo
41+
left = majority_element_rec(lo, mid)
42+
right = majority_element_rec(mid+1, hi)
43+
44+
if left == right:
45+
return left
46+
47+
left_count = sum(1 for i in range(lo, hi+1) if nums[i] == left)
48+
right_count = sum(1 for i in range(lo, hi+1) if nums[i] == right)
49+
50+
return left if left_count > right_count else right
51+
52+
return majority_element_rec(0, len(nums)-1)

‎Week 02/id_246/LeetCode_17_246.py‎

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
'''
2+
letter combinations of a-phone number_17
3+
4+
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
5+
6+
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
7+
8+
输入："23"
9+
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
10+
'''
11+
12+
13+
#回溯
14+
def letterCombinations(digits):
15+
phone = {'2': ['a', 'b', 'c'],
16+
'3': ['d', 'e', 'f'],
17+
'4': ['g', 'h', 'i'],
18+
'5': ['j', 'k', 'l'],
19+
'6': ['m', 'n', 'o'],
20+
'7': ['p', 'q', 'r', 's'],
21+
'8': ['t', 'u', 'v'],
22+
'9': ['w', 'x', 'y', 'z']}
23+
24+
def backtrack(combination, next_digits):
25+
if len(next_digits) == 0:
26+
output.append(combination)
27+
else:
28+
for letter in phone[next_digits[0]]:
29+
backtrack(combination+letter, next_digits[1:])
30+
31+
output = []
32+
if digits:
33+
backtrack("", digits)
34+
return output

‎Week 02/id_246/LeetCode_1_246.py‎

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
'''
2+
two sum_1
3+
4+
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
5+
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
6+
7+
示例:
8+
给定 nums = [2, 7, 11, 15], target = 9
9+
10+
因为 nums[0] + nums[1] = 2 + 7 = 9
11+
所以返回 [0, 1]
12+
'''
13+
14+
#hash
15+
def twoSum(nums, target):
16+
wanted_nums = {}
17+
for i in range(len(nums)):
18+
if nums[i] in wanted_nums:
19+
return [wanted_nums[nums[i]], i]
20+
else:
21+
wanted_nums[target - nums[i]] = i

‎Week 02/id_246/LeetCode_236_246.py‎

Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
'''
2+
lowest common ancestor of a binary tree_236
3+
4+
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
5+
6+
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
7+
8+
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
9+
输出: 3
10+
'''
11+
12+
# 递归
13+
class Solution:
14+
def __init__(self):
15+
self.ans = None
16+
17+
def lowestCommonAncestor_1(root, p, q):
18+
self.ans = None
19+
def recurse_tree(current_node):
20+
if not current_node:
21+
return False
22+
left = recurse_tree(current_node.left)
23+
right = recurse_tree(current_node.right)
24+
mid = current_node == p or current_node == q
25+
if mid + left + right >= 2:
26+
self.ans = current_node
27+
return mid or left or right
28+
recurse_tree(root)
29+
return self.ans
30+
31+
32+
# 父指针迭代
33+
def lowestCommonAncestor_2(root, p, q):
34+
stack = [root]
35+
parent = {root: None}
36+
while p not in parent or q not in parent:
37+
node = stack.pop()
38+
if node.left:
39+
parent[node.left] = node
40+
stack.append(node.left)
41+
if node.right:
42+
parent[node.right] = node
43+
stack.append(node.right)
44+
ancestors = set()
45+
while p:
46+
ancestors.add(p)
47+
p = parent[p]
48+
while q not in ancestors:
49+
q = parent[q]
50+
return q

‎Week 02/id_246/LeetCode_242_246.py‎

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
'''
2+
vaild anagram_242
3+
4+
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
5+
6+
示例 1:
7+
8+
输入: s = "anagram", t = "nagaram"
9+
输出: true
10+
示例 2:
11+
12+
输入: s = "rat", t = "car"
13+
输出: false
14+
说明:
15+
你可以假设字符串只包含小写字母。
16+
17+
进阶:
18+
如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？
19+
'''
20+
21+
#内置
22+
import collections
23+
24+
def isAnagram_1(s, t):
25+
return collections.Counter(s) == collections.Counter(t)
26+
27+
28+
#hash
29+
def isAnagram_2(s, t):
30+
dic = {}
31+
for i in s:
32+
if i not in dic:
33+
dic[i] = 1
34+
else:
35+
dic[i] += 1
36+
37+
for j in t:
38+
if j not in dic:
39+
return False
40+
else:
41+
dic[j] -= 1
42+
43+
for val in dic.values():
44+
if val != 0:
45+
return False
46+
return True

‎Week 02/id_246/LeetCode_429_246.py‎

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
'''
2+
n-ary tree level-order traversal_429
3+
4+
给定一个 N 叉树，返回其节点值的层序遍历。 (即从左到右，逐层遍历)。
5+
'''
6+
7+
def levelOrder(root):
8+
if root is None: return []
9+
10+
queue, output = [root,], []
11+
while queue:
12+
child = []
13+
node = []
14+
for item in queue:
15+
child.append(item.val)
16+
if item.children: node += item.children
17+
output.append(child)
18+
queue = node
19+
return output

0 commit comments

Comments
 (0)