数据结构习题
学习目标
习题一
题干：
给两个字符串s和t，判断t是否为s的重新排列后组成的单词
s = “anagram”，t = “nagaram”，return true
s = “rat”，t = “car”， return false
解法：
- 对两个字符串进行排序，如果排序后的结果一样，则返回true。
1
2
3
4
5
6
7
8
9
10
|
# leetcode submit region begin(Prohibit modification and deletion)
class Solution(object):
def isAnagram(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""
return sorted(list(s)) == sorted(list(t))
# leetcode submit region end(Prohibit modification and deletion)
|
一行解决，但时间复杂度很高为O(nlogn)。
- 使用字典，计数字符key出现的个数value，如果两个字典相等则返回true。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class Solution(object):
def isAnagram(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""
dict1 = {}
dict2 = {}
for ch in s:
dict1[ch] = dict1.get(ch,0) +1 # 在就返回其数量value，不在就+1
for ch in t:
dict2[ch] = dict2.get(ch,0) +1
return dict1 == dict2
|
时间复杂度为O(n)。
习题二
题干
给定一个m*n的二维列表，查找一个数是否存在，列表有以下特性。
每一行的列表从左到右已经排序好，
每一行的第一个数比上一行最后一个数要大。
解法
- 直接遍历查找，线性查找。
1
2
3
4
5
6
7
8
9
10
11
|
class Solution(object):
def findNumberIn2DArray(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
for line in matrix:
if target in line:
return True
return False
|
时间复杂度为O($n*m$)。比较慢
- 使用二分查找的方式去查找。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
h = len(matrix)
if h == 0:
return False
w = len(matrix[0])
if w == 0:
return False
left = 0
right = w * h - 1
# mid = (left+right) // 2
# 取数组第一个下标的方法是整除列 第二个方法是用高取模
while left <= right: # 候选区有值
mid = (left + right) // 2
i = mid // w # 整除宽可以得到第一个下标
j = mid % w # 取模获得第二个下标
if matrix[i][j] == target: # mid值查找成功
return True
elif matrix[i][j] > target: # 待查找的值在mid左侧
right = mid - 1 # 放弃右选区
else:
left = mid + 1 # 放弃左选区
else:
return False
|
习题三
题干
给定一个列表和一个整数，设计算法找到两个数的下标，使得两个数之和为给定的整数，保证肯定只有一个结果
如：列表[1,2,5,4]与目标数3，1+2=3，返回下标为（0，1）
解法
- 使用暴力解决，两个数遍历查找。
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
n = len(nums)
for i in range(n):
for j in range(i,n):
if i!=j and nums[i] + nums[j] == target:
return sorted([i,j])
|
改进一下，用二分查找来找另一个数：