Skip to content

Commit 04c5b40

Browse files
hebe3456hebe3456
committed
week2 homework
1 parent 2ab66b9 commit 04c5b40

18 files changed

Lines changed: 562 additions & 0 deletions

‎Week02/1.两数之和.py‎

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
#
2+
# @lc app=leetcode.cn id=1 lang=python3
3+
#
4+
# [1] 两数之和
5+
#
6+
7+
# @lc code=start
8+
class Solution:
9+
def twoSum(self, nums: List[int], target: int) -> List[int]:
10+
"""
11+
1 暴力，两轮遍历，和 = target，则返回，注意：index不一样
12+
O(N*2) O(1) 没用额外数组等
13+
2 用字典，一轮遍历，生成字典；第二轮遍历，如果 target - num 在 num前面的值列表中
14+
O(N) O(N)
15+
3 用字典，一轮遍历，如果 target - num 在 字典中！！！不要用列表，慢，就返回，否则就加到字典当中
16+
O(N) O(N)
17+
436ms if ano_num in nums[:idx]:
18+
68ms if ano_num in num_idx_dict: 这个还是快非常多的！！！
19+
字典：用字典存储，一一对应查找最快，用空间换时间~
20+
"""
21+
22+
if len(nums) < 2: return False # 别忘了！
23+
num_idx_dict = {}
24+
25+
for idx, num in enumerate(nums):
26+
# 表示另一个数字another_num
27+
ano_num = target - num # 错误：如果放在语句里，记得加括号！
28+
# 如果another_num num在字典中，就是所求结果，返回索引
29+
if ano_num in num_idx_dict: # ！！！
30+
return [num_idx_dict[ano_num], idx]
31+
# 否则就加到字典中
32+
num_idx_dict[num] = idx # num 不是ano_num
33+
34+
35+
# @lc code=end
36+
37+
38+
# s = Solution()
39+
# print(s.twoSum([2,7,11,15], 9))

‎Week02/125.验证回文串.java‎

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
/*
2+
* @lc app=leetcode.cn id=125 lang=java
3+
*
4+
* [125] 验证回文串
5+
*/
6+
7+
// @lc code=start
8+
class Solution {
9+
public boolean isPalindrome(String s) {
10+
if (s.length() <= 1) {
11+
return true;
12+
}
13+
14+
int l = 0, r = s.length() - 1;
15+
char cL, cR;
16+
while (l <= r) {
17+
cL = s.charAt(l);
18+
cR = s.charAt(r);
19+
if (!Character.isLetterOrDigit(cL)) {
20+
l++;
21+
} else if (!Character.isLetterOrDigit(cR)) {
22+
r--;
23+
} else {
24+
if (Character.toLowerCase(cL) != Character.toLowerCase(cR)) {
25+
return false;
26+
}
27+
l++;
28+
r--;
29+
}
30+
}
31+
return true;
32+
}
33+
}
34+
// @lc code=end
35+

‎Week02/125.验证回文串.py‎

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
#
2+
# @lc app=leetcode.cn id=125 lang=python3
3+
#
4+
# [125] 验证回文串
5+
#
6+
# 基础：首先生成新字符串（去掉字母数字以外字符） + 切片：[] == [::-1] 或者 reversed()函数
7+
# 优化：首先生成新字符串（去掉字母数字以外字符） + 双指针法
8+
# 时间复杂度：O(|s|)，其中 |s|是字符串 s 的长度。
9+
# 空间复杂度：O(|s|)。将所有字母和数字字符存放在另一个字符串中，在最坏情况下，新的字符串 与原字符串 s完全相同
10+
11+
# 优化：双指针法直接遍历原字符串
12+
# 时间复杂度：O(|s|)，其中 |s|是字符串 s 的长度。
13+
# 空间复杂度：O(1)
14+
15+
# @lc code=start
16+
class Solution1:
17+
def isPalindrome(self, s: str) -> bool:
18+
# 双指针法 60ms
19+
if len(s) <= 1:
20+
return True
21+
l, r = 0, len(s)-1
22+
while l < r:
23+
# 如果不是字母和数字，就移动指针
24+
while l < r and not s[l].isalnum():
25+
l += 1
26+
while l < r and not s[r].isalnum():
27+
r -= 1
28+
# 如果不等，返回False；相等，移动指针
29+
if s[l].lower() != s[r].lower():
30+
return False
31+
l += 1
32+
r -= 1
33+
return True
34+
35+
36+
class Solution:
37+
def isPalindrome(self, s: str) -> bool:
38+
import re
39+
s = s.lower()
40+
s = re.sub(r'\W+','',s)
41+
# s = re.sub('[^a-z0-9]+','',s)
42+
return s == s[::-1]
43+
44+
# @lc code=end
45+

‎Week02/14.最长公共前缀.py‎

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
#
2+
# @lc app=leetcode.cn id=14 lang=python3
3+
#
4+
# [14] 最长公共前缀
5+
#
6+
7+
# @lc code=start
8+
class Solution:
9+
def longestCommonPrefix(self, strs):
10+
# 1 暴力：两个for循环，外循环遍历单词，内循环遍历单词的字母索引，如果同一索引字母均相同，则加到结果中；不相同，终止跳出循环
11+
# time: (N*2) space: O(N) 结果数组
12+
# 2 按照长度排序，再循环查找
13+
# 3 直接按长度取最短的字符串即可， 循环用enumerate()
14+
# time: (N*2) space: O(1)
15+
if not strs: return ""
16+
shortest_str = min(strs, key=len)
17+
for idx, letter in enumerate(shortest_str):
18+
for word in strs: # 没排序所以要遍历所有单词！
19+
if letter != word[idx]:
20+
return shortest_str[:idx]
21+
return shortest_str
22+
23+
24+
# 按照长度排序，再循环：
25+
class Solution2:
26+
def longestCommonPrefix(self, strs):
27+
# 44ms
28+
if not strs: return ""
29+
strs.sort(key = len)
30+
for idx in range(len(strs[0])):
31+
for word in strs[1:]:
32+
if strs[0][idx] != word[idx]:
33+
# if idx == 0: a[:0] = ""!
34+
# return ""
35+
return word[:idx]
36+
return strs[0] # 缩进层级！
37+
38+
39+
s = Solution()
40+
print(s.longestCommonPrefix(["flower","flow","flight"]))
41+
42+
# @lc code=end
43+

‎Week02/141.环形链表.py‎

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
#
2+
# @lc app=leetcode.cn id=141 lang=python3
3+
#
4+
# [141] 环形链表
5+
#
6+
7+
# @lc code=start
8+
# Definition for singly-linked list.
9+
# class ListNode:
10+
# def __init__(self, x):
11+
# self.val = x
12+
# self.next = None
13+
14+
class Solution:
15+
def hasCycle(self, head: ListNode) -> bool:
16+
17+
# @lc code=end
18+

‎Week02/144.二叉树的前序遍历.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=144 lang=python3
3+
#
4+
# [144] 二叉树的前序遍历
5+
#
6+
7+
# @lc code=start
8+
# Definition for a binary tree node.
9+
# class TreeNode:
10+
# def __init__(self, x):
11+
# self.val = x
12+
# self.left = None
13+
# self.right = None
14+
15+
16+
class Solution:
17+
def preorderTraversal(self, root: TreeNode) -> List[int]:
18+
# recursively
19+
# 40ms
20+
ans = []
21+
self.dfs(root, ans)
22+
return ans
23+
24+
def dfs(self, root, ans):
25+
if root:
26+
ans.append(root.val)
27+
self.dfs(root.left, ans)
28+
self.dfs(root.right, ans)
29+
30+
31+
class Solution2:
32+
def preorderTraversal(self, root: TreeNode) -> List[int]:
33+
# 36ms
34+
# iteratively
35+
if not root: return [] # []
36+
ans = []
37+
stack = [root]
38+
while stack:
39+
node = stack.pop()
40+
if node:
41+
ans.append(node.val)
42+
if node.right:
43+
stack.append(node.right) # 后进先出
44+
if node.left:
45+
stack.append(node.left)
46+
return ans
47+
48+
49+
# @lc code=end
50+

‎Week02/153.寻找旋转排序数组中的最小值.py‎

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=153 lang=python3
3+
#
4+
# [153] 寻找旋转排序数组中的最小值
5+
#
6+
7+
# 暴力，遍历整个数组，找到最小元素
8+
# time: O(N) N 给定数组长度
9+
10+
# 优化：改进二分搜索：找到中间点，根据条件决定是取左半还是右半
11+
# 二分搜索应用前提：升序
12+
# 升序且无重复值，旋转一次，
13+
# 找规律：
14+
# 算法：
15+
# 如果尾元素 > 头元素，未旋转
16+
# 如果尾元素 < 头元素，旋转，尾元素后一个元素是头元素(可能中间不连接？)，此时中间有个变化点，需要找到
17+
# 找到中间元素 mid，
18+
# 如果 mid > 0元素，变化点在mid右边
19+
# 如果 mid < 0元素，变化点在mid左边
20+
# 找到变化点停止搜索，判断满足如下条件即可：（和左右两边值比较，返回小的!）
21+
# 如果 nums[mid] > nums[mid + 1], mid+1 是最小值
22+
# 如果 nums[mid - 1] > nums[mid], mid 是最小值
23+
# 40ms
24+
# time: O(logN)
25+
# space: O(1)
26+
27+
# @lc code=start
28+
class Solution:
29+
def findMin(self, nums: List[int]) -> int:
30+
# 特例处理
31+
if len(nums) == 1:
32+
return nums[0]
33+
l, r = 0, len(nums) - 1
34+
if nums[r] > nums[l]: return nums[0]
35+
while l < r:
36+
# mid = l + (r - l)//2 # 二者没太大区别，
37+
mid = (l + r)//2
38+
if nums[mid] > nums[mid + 1]: # mid + 1
39+
return nums[mid + 1] # 返回小的
40+
if nums[mid - 1] > nums[mid]:
41+
return nums[mid]
42+
if nums[mid] > nums[0]:
43+
l = mid + 1
44+
else:
45+
r = mid - 1
46+
47+
48+
# @lc code=end
49+

‎Week02/242.有效的字母异位词.py‎

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
#
2+
# @lc app=leetcode.cn id=242 lang=python3
3+
#
4+
# [242] 有效的字母异位词
5+
#
6+
7+
# @lc code=start
8+
class Solution:
9+
def isAnagram(self, s: str, t: str) -> bool:
10+
# 审题：大小写问题
11+
# 含有的字母个数相同
12+
# 两个字典，用字典统计字母出现的次数，两个字典相等
13+
# O(N)
14+
# 一个字典，一个+， 一个 -， 最后次数均为0
15+
# O(N)
16+
17+
# 两个字典
18+
s_dict = {}
19+
t_dict = {}
20+
for i in s:
21+
if i in s_dict:
22+
s_dict[i] += 1
23+
else:
24+
s_dict[i] = 1
25+
for j in t:
26+
if j in t_dict:
27+
t_dict[j] += 1
28+
else:
29+
t_dict[j] = 1
30+
return s_dict == t_dict
31+
32+
# @lc code=end
33+

‎Week02/264.丑数-ii.py‎

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
#
2+
# @lc app=leetcode.cn id=264 lang=python3
3+
#
4+
# [264] 丑数 II
5+
#
6+
7+
# @lc code=start
8+
class Solution:
9+
def nthUglyNumber(self, n: int) -> int:
10+
# @lc code=end
11+

‎Week02/344.反转字符串.java‎

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
/*
2+
* @lc app=leetcode.cn id=344 lang=java
3+
*
4+
* [344] 反转字符串
5+
*/
6+
7+
8+
9+
// @lc code=start
10+
class Solution {
11+
public void reverseString(char[] s) {
12+
// 思路：收尾交换，双指针 1ms, 99.9%
13+
int l = 0, r = s.length - 1;
14+
while (l < r) { // < 即可，<=多交换了一次中间字符（自己跟自己交换）
15+
char tmp = s[l];
16+
s[l++] = s[r];
17+
s[r--] = tmp;
18+
}
19+
}
20+
}
21+
22+
23+
24+
25+
26+
// @lc code=end
27+

0 commit comments

Comments
 (0)