1，数组
1.1，实现一个动态扩容的数组
1.2，实现一个大小固定的有序数组，支持动态增删改操作
class Array():
def __init__(self):
'''数组类初始化方法.'''
self.__data = [] # 数据存储List
def find(self, index):
'''数组的查找方法.
参数：
index:将要查找的数据的下标
返回：
如果查找成功，则返回找到的数据
如果查找失败，则返回False
'''
if index > len(self.__data) or index < 0:
return False
else:
return self.__data[index]
def delete(self, index):
'''数组的删除方法.
参数：
index:将要删除的数据的下标
返回：
如果删除成功，则返回True
如果删除失败，则返回False
'''
if index > len(self.__data) or index < 0:
return False
else:
self.__data.pop(index)
return True
def insert(self, index, value):
'''数组插入数据操作.
参数：
index:将要插入的下标
value：将要插入的数据
返回：
如果插入成功，则返回True
如果插入失败，则返回False
'''
if index > len(self.__data) or index < 0:
return False
else:
self.__data.insert(index, value)
return True
def insertToTail(self, value):
'''直接在数组尾部插入数据.
参数：
value:将要插入的数据
'''
self.__data.append(value)
def printAll(self):
'''打印当前数组所有数据'''
print(self.__data)
1.3，实现两个有序数组合并为一个有序数组
def merge(nums1, m, nums2, n):
while m>0 and n>0:
if nums1[m-1]>nums2[n-1]:
#若nums1中最后一个元素大于nums2[]中最后一个元素
nums1[m+n-1]=nums1[m-1]#则扩展后的列表最后一个元素是俩元素中最大的
m-=1
#nums1中元素-1
else:
nums1[m+n-1]=nums2[n-1]
n-=1
if n>0:
#若nums1完了，nums2还没完
nums1[:n]=nums2[:n]
#把剩下nums2加在最开始
if name=='main':
nums1 = [0]#0的位置用来方nums2
m = 0
nums2 = [2, 5, 6]
n = 3
merge(nums1,m,nums2,n)
print(nums1)
2，哈希表
2.1LeetCode 两数之和（1）
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
numlist ={}
for index,num in enumerate(nums):
another_num = target - num
if another_num in numlist:
return [numlist[another_num],index]
numlist[num] = index
return None
2.2 LeetCode Happy Number（202）
def isHappy(self, n: int) -> bool:
hash_dict = dict()
while n != 1:
hash_dict[n] = n
m = 0
while n != 0:
m = m + (n%10)**2
n = n//10
n = m
# n = self.square(n)
# 或者新建一个函数处理平方求和问题
if n in hash_dict.keys():
# 利用哈希表，如果出现在哈希表中表示开始循环，不可能是开心数
return False
return True
3字符串
3.1 实现一个字符串，只包含a~z这26个英文字母的Trie树
class TrieNode:
def __init__(self, data: str):
self._data = data
self._children = [None] * 26
self._is_ending_char = False
class Trie:
def __init__(self):
self._root = TrieNode("/")
def insert(self, text: str) -> None:
node = self._root
for index, char in map(lambda x: (ord(x) - ord("a"), x), text):
if not node._children[index]:
node._children[index] = TrieNode(char)
node = node._children[index]
node._is_ending_char = True
def find(self, pattern: str) -> bool:
node = self._root
for index in map(lambda x: ord(x) - ord("a"), pattern):
if not node._children[index]: return False
node = node._children[index]
return node._is_ending_char
if __name__ == "__main__":
strs = ["saw", "hi", "her", "hello", "so", "volley"]
trie = Trie()
for s in strs:
trie.insert(s)
for s in strs:
print(trie.find(s))
print(trie.find("swift"))
3.2实现朴素的字符串匹配算法
def bf(main, pattern):
"""
字符串匹配，bf暴搜
:param main: 主串
:param pattern: 模式串
:return:
"""
n = len(main)
m = len(pattern)
if n <= m:
return 0
if pattern == main:
return main
else:
return -1
for i in range(n-m+1):
for j in range(m):
if main[i+j] == pattern[j]:
if j == m-1:
return i
else:
continue
else:
break
return -1
