Skip to content

Commit 3fe32a6

Browse files
hebe3456hebe3456
committed
week3 homework
1 parent e97dba6 commit 3fe32a6

10 files changed

Lines changed: 455 additions & 1 deletion

‎Week03/169.多数元素.py‎

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
# 多数元素#
2+
# @lc app=leetcode.cn id=169 lang=python3
3+
#
4+
# [169] 多数元素
5+
#
6+
7+
# 已经不是暴力了：遍历生成字典，value > n/2
8+
# time: O(N)
9+
# space: O(N)
10+
# 80ms, 13.27%
11+
12+
# 优化：sort升序排列，中间元素就是
13+
# time: O(NlogN) !!!
14+
# space: 自带排序算法，用O(logN)的栈空间，自己写堆排序，用O(1) !!!
15+
# 52ms, beats 68.69%
16+
17+
#
18+
19+
# @lc code=start
20+
class Solution:
21+
def majorityElement1(self, nums):
22+
# 52ms, beats 68.69%
23+
# both are ok
24+
return sorted(nums)[len(nums)//2] # sorted
25+
# nums.sort()
26+
# return nums[len(nums)//2] # even odd same
27+
28+
29+
def majorityElement(self, nums):
30+
# 80ms, 13.27%
31+
num_dict = {}
32+
for num in nums:
33+
num_dict[num] = num_dict.get(num, 0) + 1
34+
for key, value in num_dict.items(): # items()
35+
if value > len(nums)/2: # error: nums not num_dict
36+
return key
37+
38+
39+
s = Solution()
40+
for i in [[1], [3,2,3], [2,2,1,1,1,2,2], [8,8,7,7,7]]:
41+
print(s.majorityElement(i))
42+
43+
# @lc code=end
44+

‎Week03/17.电话号码的字母组合.java‎

Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
/*
2+
* @lc app=leetcode.cn id=17 lang=java
3+
*
4+
* [17] 电话号码的字母组合
5+
*/
6+
7+
// @lc code=start
8+
class Solution {
9+
public List<String> letterCombinations(String digits) {
10+
if (digits == null || digits.length() == 0) {
11+
return new ArrayList();
12+
}
13+
Map<Character, String> map = new HashMap<Character, String>();
14+
map.put('2', "abc");
15+
map.put('3', "def");
16+
map.put('4', "ghi");
17+
map.put('5', "jkl");
18+
map.put('6', "mno");
19+
map.put('7', "pqrs");
20+
map.put('8', "tuv");
21+
map.put('9', "wxyz");
22+
List<String> res = new LinkedList<String>();
23+
search("", digits, 0, res, map);
24+
return res;
25+
}
26+
27+
private void search(String s,
28+
String digits,
29+
int i,
30+
List<String> res,
31+
Map<Character, String> map) {
32+
// terminator
33+
if (i == digits.length()) {
34+
res.add(s);
35+
return;
36+
}
37+
38+
// process
39+
String letters = map.get(digits.charAt(i));
40+
for (int j = 0; j < letters.length(); j++) {
41+
// drill down
42+
search(s + letters.charAt(j), digits, i+1, res, map);
43+
}
44+
45+
// reverse
46+
}
47+
}
48+
// @lc code=end
49+

‎Week03/17.电话号码的字母组合.py‎

Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
#
2+
# @lc app=leetcode.cn id=17 lang=python3
3+
#
4+
# [17] 电话号码的字母组合
5+
#
6+
7+
# @lc code=start
8+
class Solution:
9+
def letterCombinations1(self, digits: str) -> List[str]:
10+
# time: 32ms, beats 94.95%
11+
# define a dict
12+
num_letter_dict = {'2': 'abc', '3': 'def',
13+
'4': 'ghi', '5': 'jkl',
14+
'6': 'mno', '7': 'pqrs',
15+
'8': 'tuv', '9': 'wxyz' }
16+
if len(digits) == 0:
17+
return []
18+
if len(digits) == 1:
19+
return list(num_letter_dict[digits[0]])
20+
# similar to "ziji": previous + the last one
21+
prev = self.letterCombinations(digits[:-1])
22+
additional = num_letter_dict[digits[-1]]
23+
return [s + c for s in prev for c in additional]
24+
25+
26+
def letterCombinations(self, digits: str) -> List[str]:
27+
# backtracking
28+
# 52ms, beats 12.36%
29+
if not digits:
30+
return []
31+
num_letter_dict = {'2': 'abc', '3': 'def',
32+
'4': 'ghi', '5': 'jkl',
33+
'6': 'mno', '7': 'pqrs',
34+
'8': 'tuv', '9': 'wxyz' }
35+
res = []
36+
self.helper(digits, num_letter_dict, 0, "", res)
37+
return res
38+
39+
def helper(self, digits, num_letter_dict, idx, path, res):
40+
if len(path) == len(digits):
41+
res.append(path)
42+
return
43+
44+
for i in range(idx, len(digits)):
45+
for j in num_letter_dict[digits[i]]:
46+
self.helper(digits, num_letter_dict, i + 1, path + j, res)
47+
48+
49+
# @lc code=end
50+

‎Week03/46.全排列.java‎

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
/*
2+
* @lc app=leetcode.cn id=46 lang=java
3+
*
4+
* [46] 全排列
5+
*/
6+
7+
// @lc code=start
8+
class Solution {
9+
public List<List<Integer>> permute(int[] nums) {
10+
// time: 2ms beats 81.74%
11+
List<List<Integer>> res = new ArrayList<List<Integer>>();
12+
if (nums.length == 0 ) return res;
13+
List<Integer> list0 = new ArrayList<Integer>();
14+
list0.add(nums[0]);
15+
res.add(list0);
16+
17+
for (int i = 1; i < nums.length; ++i) {
18+
List<List<Integer>> new_res = new ArrayList<List<Integer>>();
19+
for (int j = 0; j <= i; ++j) {
20+
for (List<Integer> list : res) {
21+
List<Integer> new_list = new ArrayList<Integer>(list);
22+
new_list.add(j, nums[i]);
23+
new_res.add(new_list);
24+
}
25+
}
26+
res = new_res;
27+
}
28+
return res;
29+
}
30+
}
31+
// @lc code=end
32+

‎Week03/46.全排列.py‎

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
#
2+
# @lc app=leetcode.cn id=46 lang=python3
3+
#
4+
# [46] 全排列
5+
#
6+
7+
# @lc code=start
8+
class Solution:
9+
def permute(self, nums: List[int]) -> List[List[int]]:
10+
# time: 36ms, beats 94.71%
11+
res = [[]]
12+
for num in nums:
13+
tmp_res = []
14+
for sub_set in res:
15+
for i in range(len(sub_set)+1):
16+
tmp_res.append(sub_set[:i] + [num] + sub_set[i:]) # insert [num] append!
17+
res = tmp_res
18+
# 想用列表生成式，没成功。。。
19+
return res
20+
# @lc code=end
21+

‎Week03/47.全排列-ii.py‎

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
#
2+
# @lc app=leetcode.cn id=47 lang=python3
3+
#
4+
# [47] 全排列 II
5+
#
6+
7+
# @lc code=start
8+
class Solution:
9+
def permuteUnique(self, nums):
10+
# time：44ms beats 93.58%
11+
res = [[]]
12+
for num in nums:
13+
tmp_res = []
14+
for sub_set in res:
15+
for i in range(len(sub_set)+1):
16+
tmp_res.append(sub_set[:i] + [num] + sub_set[i:])
17+
# handle duplication！
18+
if i < len(sub_set) and sub_set[i] == num: break
19+
res = tmp_res
20+
return res
21+
22+
s = Solution()
23+
print(s.permuteUnique([1,2,1]))
24+
# @lc code=end
25+

‎Week03/50.pow-x-n.java‎

Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
/*
2+
* @lc app=leetcode.cn id=50 lang=java
3+
*
4+
* [50] Pow(x, n)
5+
*/
6+
7+
// @lc code=start
8+
class Solution {
9+
public double myPow(double x, int n) {
10+
// 取绝对值 1ms, 94.4%
11+
long m = n > 0 ? n : -(long)n;
12+
double res = 1.0;
13+
while (m != 0) {
14+
if ((m & 1) == 1) {
15+
res *= x;
16+
}
17+
x *= x;
18+
m >>= 1;
19+
}
20+
return n >= 0 ? res : 1 / res;
21+
}
22+
23+
public double myPow1(double x, int n) {
24+
if (n < 0) {
25+
x = 1 / x;
26+
// n = -(long)n;
27+
// error: incompatible types: possible lossy conversion from long to int
28+
// long n = -(long)n;
29+
// error: variable n is already defined in method myPow(double,int)
30+
long m = -(long)n;
31+
// n < 0 是赋值给 m， 大于0 时也需要赋值，因此不行。。。
32+
}
33+
return 1;
34+
}
35+
36+
37+
public double myPow2(double x, int n) {
38+
/* This is a simple solution based on divide and conquer */
39+
double tmp = x;
40+
if (n==0) return 1;
41+
tmp = myPow(x, n/2);
42+
if (n % 2 == 0) {
43+
return tmp * tmp;
44+
} else {
45+
if (n > 0) {
46+
return x * tmp * tmp;
47+
} else {
48+
return (tmp * tmp) / x;
49+
}
50+
}
51+
}
52+
}
53+
// @lc code=end
54+

‎Week03/50.pow-x-n.py‎

Lines changed: 100 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,100 @@
1+
#
2+
# @lc app=leetcode.cn id=50 lang=python3
3+
#
4+
# [50] Pow(x, n)
5+
#
6+
7+
8+
"""
9+
1 暴力
10+
result = 1
11+
for i in range(n):
12+
result *= x
13+
注意：考虑n为负的情况
14+
time：O(N)
15+
16+
2 分治
17+
template:
18+
1 terminator
19+
2 process(split your big problem)
20+
3 drill down (subproblem), merge(subresult)
21+
4 reverse states
22+
23+
x^n --> 2^10：2^5乘以自己 --> (2^2) 乘以自己 [奇偶数问题]
24+
pow(x, n):
25+
subproblem: subresult = pow(x, n/2)
26+
27+
merge:
28+
if n % 2 == 1{
29+
// 偶数 odd
30+
result = subresult * subresult * x;
31+
} else {
32+
// 奇数 even
33+
result = subresult * subresult;
34+
}
35+
36+
不论我们返回时候如何，我们执行第一步，先设立Base Case:
37+
if b == 0: return 1
38+
39+
完了以后，我们要对大问题进行拆分，也就是不断的对b的值折半
40+
41+
拆分：
42+
half = self.myPow(a, b // 2)
43+
44+
当拆分到了最小的问题，满足base case b == 0 的时候，我们则进行返回，返回时候有三种可能
45+
46+
Function的三种可能性：
47+
当b为偶数的时候，比如 2 ^ 100，拆分的时候就变成 (2 ^ 50) * (2 ^ 50)
48+
当b为基数的时候，比如 2 ^ 25，拆分的时候就变成 (2 ^12) * (2 ^ 12) * 2
49+
当b为负数的时候，返回 1.0 / self.myPow(a, -b)
50+
51+
时间复杂度 = 一叉树里面每层的时间复杂度 * 层数 = 1 * log(b) = log(b)
52+
空间复杂度 = O(h) 也就是一叉树的层数 = log(b)
53+
https://leetcode.com/problems/powx-n/discuss/182026/Python-or-Recursion-tm
54+
"""
55+
56+
# @lc code=start
57+
class Solution:
58+
def myPow(self, x: float, n: int) -> float:
59+
# time: 32ms, beats 97.1%
60+
# 二进制，分治，比用绝对值快，最优！！！
61+
if n < 0: # error: n not x
62+
x = 1 / x
63+
n = -n
64+
res = 1
65+
while n:
66+
if n & 1: # &和 偶数 & 1 = 0; 奇数 & 1 = 1;
67+
res *= x
68+
x *= x
69+
n >>= 1
70+
# n = n>>1; 就是n变成 n向右移一位的那个数
71+
# >>是移位运算符，比如 3>>1 就是将3的二进制向右移移位：
72+
# 11（3的二进制）向右移移位变成 1，低位自动消失。
73+
return res
74+
75+
def myPow1(self, x: float, n: int) -> float:
76+
# 44ms, beats 50.26%
77+
# 二进制，分治
78+
m = abs(n)
79+
res = 1.0
80+
while m:
81+
if m & 1:
82+
res *= x
83+
x *= x
84+
m >>= 1
85+
return res if n >= 0 else 1 / res
86+
87+
def myPow2(self, x: float, n: int) -> float:
88+
# 40ms, beats 74.38%
89+
# 回归
90+
if not n:
91+
return 1
92+
if n < 0:
93+
return 1 / self.myPow(x, -n) # -n
94+
if n % 2:
95+
return x * self.myPow(x, n-1)
96+
return self.myPow(x*x, n/2)
97+
98+
99+
# @lc code=end
100+

0 commit comments

Comments
 (0)