Skip to content

Commit 98fd84f

Browse files
GeekUniversityGeekUniversity
authored
Merge pull request #248 from lection/master
003 第四周作业
2 parents 77b1d5a + 7087f0a commit 98fd84f

46 files changed

Lines changed: 2245 additions & 5 deletions

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

‎Week_03/id_3/dfs/LeetCode_127_3_v2.py‎

Lines changed: 3 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -22,9 +22,7 @@ def ladderLength(self, begin, end, word_list) -> int:
2222
begin_queue = [begin]
2323
end_queue = [end]
2424

25-
while True:
26-
if not begin_queue and not end_queue:
27-
return 0
25+
while begin_queue or end_queue:
2826
if count % 2 == 0:
2927
queue = begin_queue
3028
cur_set, target_set = begin_set, end_set
@@ -56,6 +54,6 @@ def ladderLength(self, begin, end, word_list) -> int:
5654

5755

5856
s = Solution()
59-
# print(s.ladderLength("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"]))
60-
# print(s.ladderLength("hit", "cog", ["hot", "dot", "dog", "lot"]))
57+
print(s.ladderLength("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"]))
58+
print(s.ladderLength("hit", "cog", ["hot", "dot", "dog", "lot"]))
6159
print(s.ladderLength("hot", "dog", ["hot", "dog"]))

‎Week_04/id_3/backtracking/LeetCode_46_3_v1.py‎

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
"""
2+
全排列 O(n^n) 似乎没啥悬念
3+
====== 但是我居然没通过
4+
两点问题
5+
1 递归的退出条件不能忘了return
6+
2 set在迭代到时候要小心插入和删除，还是list复制一份更为稳妥
7+
"""
8+
9+
10+
class Solution:
11+
def permute(self, nums):
12+
results = []
13+
if not nums:
14+
return results
15+
self.recursion([], set(nums), results)
16+
return results
17+
18+
def recursion(self, curr, num_set, results):
19+
if len(num_set) == 0:
20+
results.append(curr)
21+
return
22+
23+
for n in list(num_set):
24+
num_set.remove(n)
25+
self.recursion(curr + [n], num_set, results)
26+
num_set.add(n)
27+
28+
29+
s = Solution()
30+
print(s.permute([1, 2, 3]))
31+
print(s.permute([6, 2, -1, 8]))

‎Week_04/id_3/backtracking/LeetCode_51_3.py‎

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
"""
2+
最原始回溯解决n皇后方法
3+
每一行判断是否可行，对角线方向用set可以简易实现
4+
"""
5+
6+
7+
class Solution:
8+
def solveNQueens(self, n):
9+
results = []
10+
if n == 0:
11+
return []
12+
self.recursion(n, [], [0]*n, set(), set(), results)
13+
return results
14+
15+
def recursion(self, n, curr, dis_col, dis_pie, dis_na, results):
16+
row = len(curr) - 1
17+
if n == (row + 1):
18+
results.append(curr)
19+
return
20+
for i in range(n):
21+
if dis_col[i] == 1:
22+
continue
23+
pie = i + row
24+
if pie in dis_pie:
25+
continue
26+
na = i - row
27+
if na in dis_na:
28+
continue
29+
30+
line = ['.'] * n
31+
line[i] = 'Q'
32+
33+
dis_col[i] = 1
34+
dis_pie.add(pie)
35+
dis_na.add(na)
36+
37+
self.recursion(n, curr + [''.join(line)], dis_col, dis_pie, dis_na, results)
38+
39+
dis_col[i] = 0
40+
dis_pie.remove(pie)
41+
dis_na.remove(na)
42+
43+
44+
s = Solution()
45+
print(s.solveNQueens(4))

‎Week_04/id_3/backtracking/LeetCode_77_3_v1.py‎

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
"""
2+
全组合 避免重复元素出现
3+
使用下标过滤掉已经组合过的是一个常用的技巧
4+
"""
5+
6+
7+
class Solution:
8+
def combine(self, n, k):
9+
results = []
10+
if n == 0:
11+
return results
12+
self.recursion([], 1, n+1, k, results)
13+
return results
14+
15+
def recursion(self, curr, index, n, k, results):
16+
if len(curr) == k:
17+
results.append(curr)
18+
return
19+
20+
for i in range(index, n):
21+
self.recursion(curr + [i], i + 1, n, k, results)
22+
23+
24+
s = Solution()
25+
print(s.combine(4, 2))

‎Week_04/id_3/backtracking/LeetCode_784_3_v1.py‎

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
class Solution:
2+
def letterCasePermutation(self, ss):
3+
results = []
4+
if not ss:
5+
return results
6+
self.recursion(ss, 0, [], results)
7+
return results
8+
9+
def recursion(self, ss, i, curr_arr, results):
10+
if i == len(ss):
11+
results.append(''.join(curr_arr))
12+
return
13+
14+
c = ss[i]
15+
self.recursion(ss, i + 1, curr_arr + [c], results)
16+
if c.isupper():
17+
self.recursion(ss, i + 1, curr_arr + [c.lower()], results)
18+
elif c.islower():
19+
self.recursion(ss, i + 1, curr_arr + [c.upper()], results)
20+
21+
22+
s = Solution()
23+
print(s.letterCasePermutation('a1b2'))
24+
print(s.letterCasePermutation('3z4'))
25+
print(s.letterCasePermutation('12345'))

‎Week_04/id_3/backtracking/LeetCode_784_3_v2.py‎

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
"""
2+
尝试非递归解决
3+
"""
4+
5+
6+
class Solution:
7+
def letterCasePermutation(self, ss):
8+
if not ss:
9+
return []
10+
11+
results = ['']
12+
for c in ss:
13+
_results = []
14+
for r in results:
15+
if c.islower() or c.isupper():
16+
_results.append(r + c.upper())
17+
_results.append(r + c.lower())
18+
else:
19+
_results.append(r + c)
20+
21+
results = _results
22+
return results
23+
24+
25+
s = Solution()
26+
print(s.letterCasePermutation('a1b2'))
27+
print(s.letterCasePermutation('3z4'))
28+
print(s.letterCasePermutation('12345'))

‎Week_04/id_3/backtracking/LeetCode_78_3_v1.py‎

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
"""
2+
经典全组合
3+
"""
4+
5+
6+
class Solution:
7+
def subsets(self, nums):
8+
results = []
9+
if not nums:
10+
return results
11+
self.recursion([], nums, results)
12+
return results
13+
14+
def recursion(self, cur, nums, results):
15+
results.append(cur)
16+
if not nums:
17+
return
18+
for i in range(len(nums)):
19+
self.recursion(cur + [nums[i]], nums[i+1:], results)
20+
21+
22+
s = Solution()
23+
print(s.subsets([1, 2, 3]))

‎Week_04/id_3/backtracking/LeetCode_78_3_v2.py‎

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
"""
2+
经典全组合 直接调用库函数 其实为了点进去看看他的实现代码
3+
"""
4+
import itertools
5+
6+
7+
class Solution:
8+
def subsets(self, nums):
9+
results = []
10+
for i in range(len(nums) + 1):
11+
for r in itertools.combinations(nums, i):
12+
results.append(list(r))
13+
return results
14+
15+
16+
s = Solution()
17+
print(s.subsets([1, 2, 3]))

‎Week_04/id_3/backtracking/LeetCode_78_3_v3.py‎

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
"""
2+
经典全组合 非递归
3+
"""
4+
import itertools
5+
6+
7+
class Solution:
8+
def subsets(self, nums):
9+
results = [[]]
10+
for n in nums:
11+
_results = []
12+
for pn in results:
13+
_results.append(pn + [n])
14+
results += _results
15+
return results
16+
17+
18+
s = Solution()
19+
print(s.subsets([1, 2, 3]))

‎Week_04/id_3/division/LeetCode_169_3_v1.py‎

Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,65 @@
1+
"""
2+
既然是分治专题的，那么估计用hash的玩法是没啥意义了
3+
看答案 分治有点儿勉强 算是学习个思路吧
4+
O(nlogn)
5+
6+
似乎分治总会比暴力要好，只要从n^2变成nlogn，如果找不到最优的O(n)，那么先用nlogn也不错。
7+
"""
8+
9+
10+
class Solution:
11+
def majorityElement(self, nums):
12+
if not nums:
13+
return None
14+
# return self._division1(nums)
15+
return self._division2(nums, 0, len(nums) - 1)
16+
17+
def _division1(self, nums):
18+
if len(nums) == 1:
19+
return nums[0]
20+
21+
mid = len(nums) // 2
22+
left = self._division1(nums[:mid])
23+
right = self._division1(nums[mid:])
24+
if left == right:
25+
return left
26+
27+
lc = 0
28+
rc = 0
29+
for n in nums:
30+
if n == left:
31+
lc += 1
32+
continue
33+
if n == right:
34+
rc += 1
35+
continue
36+
return left if lc > rc else right
37+
38+
def _division2(self, nums, low, high):
39+
if low == high:
40+
return nums[low]
41+
42+
mid = low + (high-low)//2
43+
left = self._division2(nums, low, mid)
44+
right = self._division2(nums, mid+1, high)
45+
46+
if left == right:
47+
return left
48+
49+
lc = 0
50+
rc = 0
51+
for i in range(low, high+1):
52+
n = nums[i]
53+
if left == n:
54+
lc += 1
55+
continue
56+
if right == n:
57+
rc += 1
58+
continue
59+
60+
return left if lc > rc else right
61+
62+
63+
s = Solution()
64+
# print(s.majorityElement([2, 2, 1, 1, 1, 2, 2]))
65+
print(s.majorityElement([3, 3, 4]))

0 commit comments

Comments
 (0)