Task01：数组（1天）
理论部分
- 理解数组的存储与分类。
- 实现动态数组，该数组能够根据需要修改数组的长度。
1. 利用动态数组解决数据存放问题
编写一段代码，要求输入一个整数N，用动态数组A来存放2~N之间所有5或7的倍数，输出该数组。
def dynamiclist(N):
if N < 2:
return []
return filter(lambda x:x % 5 == 0 or x % 7 == 0, range(2,N+1))
nums = dynamiclist(100)
for i in nums:
print(i, end = ',')
5,7,10,14,15,20,21,25,28,30,35,40,42,45,49,50,55,56,60,63,65,70,75,77,80,84,85,90,91,95,98,100,
2. 托普利茨矩阵问题
如果一个矩阵的每一方向由左上到右下的对角线上具有相同元素，那么这个矩阵是托普利茨矩阵。
给定一个M x N的矩阵，当且仅当它是托普利茨矩阵时返回True。
输入:
matrix = [
[1,2,3,4],
[5,1,2,3],
[9,5,1,2]
]
输出: True
解释:
在上述矩阵中, 其对角线为:
"[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]"。
各条对角线上的所有元素均相同, 因此答案是`True`。
说明:
- matrix 是一个包含整数的二维数组。
- matrix 的行数和列数均在 [1, 20]范围内。
- matrix[i][j] 包含的整数在 [0, 99]范围内。
进阶:
- 如果矩阵存储在磁盘上，并且磁盘内存是有限的，因此一次最多只能将一行矩阵加载到内存中，该怎么办？
- 如果矩阵太大以至于只能一次将部分行加载到内存中，该怎么办？
def toeplitz_mat(matrix):
if not matrix or not matrix[0]:
return False
for i in range(1, len(matrix)):
for j in range(1, len(matrix[0])):
if matrix[i][j] != matrix[i - 1][j - 1]:
return False
return True
matrix = [[1,2,3,4],
[5,1,2,3],
[9,5,1,2]]
toeplitz_mat(matrix)
True
matrix = [[1,2],
[2,2]]
toeplitz_mat(matrix)
False
3.三数之和
给定一个包含 n 个整数的数组nums，判断nums中是否存在三个元素a，b，c，使得a + b + c = 0？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
def threesum(nums, target = 0):
if len(nums) < 3:
return []
nums.sort()
res = []
for i in range(len(nums) - 2):
if nums[i] > target:
return res
if i > 0 and nums[i] == nums[i - 1]:
continue
l, r = i + 1, len(nums) - 1
while l < r:
sum_ = nums[i] + nums[l] + nums[r]
if sum_ < target:
l += 1
elif sum_ > target:
r -= 1
else:
res.append([nums[i], nums[l], nums[r]])
while l < r and nums[l] == nums[l+1]:
l += 1
while l < r and nums[r] == nums[r-1]:
r -= 1
l += 1
r -= 1
return res
nums = [-1, 0, 1, 2, -1, -4]
print(threesum(nums))
[[-1, -1, 2], [-1, 0, 1]]
Task02：顺序表和链表
理论部分
- 理解线性表的定义与操作。
- 实现顺序表。
- 实现单链表、循环链表、双向链表。
1.合并两个有序链表
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
# 链表定义
class ListNode:
def __init__(self, val, nextnode = None):
self.val = val
self.next = nextnode
# 生成链表
def generate(nums):
head = cur = ListNode(-1)
for i in nums:
cur.next = cur = ListNode(i)
return head.next
# 递归
def mergelist(head_1, head_2):
if not head_1:
return head_2
elif not head_2:
return head_1
elif head_1.val < head_2.val:
head_1.next = mergelist(head_1.next, head_2)
return head_1
else:
head_2.next = mergelist(head_1, head_2.next)
return head_2
nums1, nums2 = [1,2,4], [1,3,4]
nums1, nums2 = generate(nums1), generate(nums2)
head = mergelist(nums1, nums2)
while head:
print(head.val, end = '->' if head.next else '')
head = head.next
1->1->2->3->4->4
# 哑结点
def mergelist_1(head_1, head_2):
head = cur = ListNode(-1)
while head_1 and head_2:
if head_1.val < head_2.val:
cur.next, head_1 = head_1, head_1.next
else:
cur.next, head_2 = head_2, head_2.next
cur = cur.next
cur.next = head_1 if head_1 else head_2
return head.next
nums1, nums2 = [1,2,4], [1,3,4]
nums1, nums2 = generate(nums1), generate(nums2)
head = mergelist_1(nums1, nums2)
while head:
print(head.val, end = '->' if head.next else '')
head = head.next
1->1->2->3->4->4
2. 删除链表的倒数第N个节点
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：给定的 n 保证是有效的。
进阶：你能尝试使用一趟扫描实现吗？
# 2次扫描
def deletenode(head, n):
cur, ans = head, 0
while cur:
ans += 1
cur = cur.next
dummy = cur = ListNode(-1, head)
for i in range(ans - n):
cur = cur.next
cur.next = cur.next.next
return dummy.next
nums = generate(range(1, 6))
head = deletenode(nums, 1)
while head:
print(head.val, end = '->' if head.next else '')
head = head.next
1->2->3->4
# 1次扫描 空间换时间
def deletenode_1(head, n):
hash_map = {}
cur = dummy = ListNode(-1, head)
ans = 0
while cur:
ans += 1
hash_map[ans] = cur
cur = cur.next
# 被删除的节点索引
index = ans - n
hash_map[index].next = hash_map[index].next.next
return dummy.next
nums = generate(range(1,6))
head = deletenode_1(nums, 3)
while head:
print(head.val, end = '->' if head.next else '')
head = head.next
1->2->4->5
# 栈实现
def deletenode_2(head, n):
dummy = cur = ListNode(-1, head)
stack = []
while cur:
stack.append(cur)
cur = cur.next
for i in range(n):
stack.pop()
prev = stack[-1]
prev.next = prev.next.next
return dummy.next
nums = generate(range(1,6))
head = deletenode_2(nums, 2)
while head:
print(head.val, end = '->' if head.next else '')
head = head.next
1->2->3->5
3. 旋转链表
给定一个链表，旋转链表，将链表每个节点向右移动k个位置，其中k是非负数。
示例 1:
输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL
示例2：
输入: 0->1->2->NULL, k = 4
输出: 2->0->1->NULL
解释:
向右旋转 1 步: 2->0->1->NULL
向右旋转 2 步: 1->2->0->NULL
向右旋转 3 步: 0->1->2->NULL
向右旋转 4 步: 2->0->1->NULL
# 首先建立循环链表
def rotate(head, k):
cur, n = head, 1
while cur.next:
cur = cur.next
n += 1
cur.next = head
new_tail = head
for i in range(n - k%n - 1):
new_tail = new_tail.next
new_head = new_tail.next
new_tail.next = None
return new_head
nums, k = generate(range(1,6)), 2
head = rotate(nums, k)
while head:
print(head.val, end = '->' if head.next else '')
head = head.next
4->5->1->2->3
Task03：栈与递归
理论部分
- 用数组实现一个顺序栈。
- 用链表实现一个链栈。
- 理解递归的原理。
1. 根据要求完成车辆重排的程序代码
假设一列货运列车共有n节车厢，每节车厢将停放在不同的车站。假定n个车站的编号分别为1至n，货运列车按照第n站至第1站的次序经过这些车站。车厢的编号与它们的目的地相同。为了便于从列车上卸掉相应的车厢，必须重新排列车厢，使各车厢从前至后按编号1至n的次序排列。当所有的车厢都按照这种次序排列时，在每个车站只需卸掉最后一节车厢即可。
我们在一个转轨站里完成车厢的重排工作，在转轨站中有一个入轨、一个出轨和k个缓冲铁轨（位于入轨和出轨之间）。图（a）给出一个转轨站，其中有k个（k=3）缓冲铁轨H1，H2 和H3。开始时，n节车厢的货车从入轨处进入转轨站，转轨结束时各车厢从右到左按照编号1至n的次序离开转轨站（通过出轨处）。在图（a）中，n=9，车厢从后至前的初始次序为5，8，1，7，4，2，9，6，3。图（b）给出了按所要求的次序重新排列后的结果。
- 第一步：若需出轨的编号恰是入轨编号，则直接出轨。
- 第二步：若需出轨的编号恰是缓冲轨的最小编号，则直接出轨。
- 第三步：将入轨编号放入缓冲轨。（规则：放到满足小于缓冲轨栈顶元素编号且栈顶元素最小的上面。）
class Solution:
def __init__(self):
self.nowOut = 1 # 下一次要输出的车厢号
self.minH = float('inf') # 缓冲铁轨中编号最小的车厢
self.minS = -1 # minH号车厢对应的缓冲铁轨
def RailRoad(self, p, k):
"""
车厢重排算法
p:入轨序列
k:缓冲轨条数
return: 重排是否成功
"""
self.h = [[] for i in range(k)] # 缓冲铁轨
for i in range(len(p)):
if p[i] == self.nowOut:
print("直接出轨 ==> {0}从入轨到出轨。".format(p[i]))
self.nowOut += 1
# 从缓冲铁轨中输出
while self.minH == self.nowOut:
self.Output() # 出轨
self.nowOut += 1
else:
# 将p[i]送入某个缓冲铁轨
if not self.Input(p[i]):
return False
return True
def Output(self):
"""
从缓冲轨移除车厢出轨
minH: 缓冲铁轨中编号最小的车厢
minS: minH号车厢对应的缓冲铁轨
h: 缓冲轨道的集合
"""
self.h[self.minS].pop()
print("缓冲出轨 ==> {0}从缓冲轨{1}到出轨。".format(self.minH, self.minS))
# 通过检查所有的栈顶，搜索新的minH和minS
minH = float('inf')
minS = -1
for i in range(len(self.h)):
if self.h[i] and self.h[i][-1] < minH:
minH = self.h[i][-1]
minS = i
self.minH = minH
self.minS = minS
def Input(self, c):
"""
在一个缓冲铁轨中放入车厢c
c: 放入车厢编号
minH: 栈顶编号的最小值
minS: 栈顶编号最小值所在堆栈的编号
h: 缓冲轨道的集合
return: 如果没有可用的缓冲铁轨，则返回False，否则返回True
"""
bestTrack = -1 # 目前最优的铁轨
bestTop = float('inf') # 最优铁轨上的头辆车厢
for i in range(len(self.h)):
if self.h[i]:
x = self.h[i][-1]
if c < x and x < bestTop:
bestTop = x
bestTrack = i
else:
if bestTrack == -1:
bestTrack = i
break
if bestTrack == -1:
return False
self.h[bestTrack].append(c);
print("入轨缓冲 ==> {0}从入轨到缓冲轨{1}。".format(c, bestTrack))
if c < self.minH:
self.minH = c
self.minS = bestTrack
return True
if __name__ == "__main__":
p = [3, 6, 9, 2, 4, 7, 1, 8, 5]
k = 3
result = Solution().RailRoad(p, k)
while not result:
k_ = int(input("需要更多的缓冲轨道,请输入需要添加的数量:"))
k += k_
result = Solution().RailRoad(p, k)
入轨缓冲 ==> 3从入轨到缓冲轨0。
入轨缓冲 ==> 6从入轨到缓冲轨1。
入轨缓冲 ==> 9从入轨到缓冲轨2。
入轨缓冲 ==> 2从入轨到缓冲轨0。
入轨缓冲 ==> 4从入轨到缓冲轨1。
入轨缓冲 ==> 7从入轨到缓冲轨2。
直接出轨 ==> 1从入轨到出轨。
缓冲出轨 ==> 2从缓冲轨0到出轨。
缓冲出轨 ==> 3从缓冲轨0到出轨。
缓冲出轨 ==> 4从缓冲轨1到出轨。
入轨缓冲 ==> 8从入轨到缓冲轨0。
直接出轨 ==> 5从入轨到出轨。
缓冲出轨 ==> 6从缓冲轨1到出轨。
缓冲出轨 ==> 7从缓冲轨2到出轨。
缓冲出轨 ==> 8从缓冲轨0到出轨。
缓冲出轨 ==> 9从缓冲轨2到出轨。
Task04：队列
理论部分
- 用数组实现一个顺序队列。
- 用数组实现一个循环队列。
- 用链表实现一个链式队列。
1. 模拟银行服务完成程序代码。
目前，在以银行营业大厅为代表的窗口行业中大量使用排队（叫号）系统，该系统完全模拟了人群排队全过程，通过取票进队、排队等待、叫号服务等功能，代替了人们站队的辛苦。
排队叫号软件的具体操作流程为：
- 顾客取服务序号
当顾客抵达服务大厅时，前往放置在入口处旁的取号机，并按一下其上的相应服务按钮，取号机会自动打印出一张服务单。单上显示服务号及该服务号前面正在等待服务的人数。
- 服务员工呼叫顾客
服务员工只需按一下其柜台上呼叫器的相应按钮，则顾客的服务号就会按顺序的显示在显示屏上，并发出“叮咚”和相关语音信息，提示顾客前往该窗口办事。当一位顾客办事完毕后，柜台服务员工只需按呼叫器相应键，即可自动呼叫下一位顾客。
编写程序模拟上面的工作过程，主要要求如下：
- 程序运行后，当看到“请点击触摸屏获取号码：”的提示时，只要按回车键，即可显示“您的号码是：XXX，您前面有YYY位”的提示，其中XXX是所获得的服务号码，YYY是在XXX之前来到的正在等待服务的人数。
- 用多线程技术模拟服务窗口（可模拟多个），具有服务员呼叫顾客的行为，假设每个顾客服务的时间是10000ms，时间到后，显示“请XXX号到ZZZ号窗口！”的提示。其中ZZZ是即将为客户服务的窗口号。
import queue
import threading
import time
exitFlag = 0
class BankServe(threading.Thread):
def __init__(self, threadID, name, q):
threading.Thread.__init__(self)
self.threadID = threadID
self.name = name
self.q = q
def run(self):
print ("开启服务：" + self.name + '\n')
process_data(self.name, self.q)
print ("退出服务：" + self.name + '\n')
def process_data(threadName, q):
while not exitFlag:
queueLock.acquire()
if not workQueue.empty():
data = q.get()
queueLock.release()
print('请{}号到{}号窗口!\n'.format(data, threadName))
else:
queueLock.release()
time.sleep(1)
serve_num = 3
custom_num = 5
queueLock = threading.Lock()
workQueue = queue.Queue(100)
threads = []
threadID = 1
# 创建新线程
for i in range(serve_num):
thread = BankServe(threadID, 'S' + str(i+1).rjust(2, '0'), workQueue)
thread.start()
threads.append(thread)
threadID += 1
# 填充队列
queueLock.acquire()
for i in range(custom_num):
print('Y' + str(i+1).rjust(4, '0'))
workQueue.put('Y' + str(i+1).rjust(4, '0'))
queueLock.release()
# 等待队列清空
while not workQueue.empty():
pass
# 通知线程是时候退出
exitFlag = 1
# 等待所有线程完成
for t in threads:
t.join()
print ("退出服务")
开启服务：S01
开启服务：S02
开启服务：S03
Y0001
Y0002
Y0003
Y0004
Y0005
请Y0001号到S03号窗口!
请Y0002号到S02号窗口!
请Y0003号到S01号窗口!
请Y0004号到S03号窗口!
请Y0005号到S02号窗口!
退出服务：S01
退出服务：S03
退出服务：S02
退出服务
Task05：字符串
理论部分
用数组实现一个顺序的串结构。
为该串结构提供丰富的操作，比如插入子串、在指定位置移除给定长度的子串、在指定位置取子串、连接串、串匹配等。
练习部分
1.无重复字符的最长子串
给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。
示例1
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例2
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例3
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
def lengthoflongestsubstring(s):
if not s:return 0
lookup = set()
maxlen = curlen = left = 0
for i in range(len(s)):
curlen += 1
while s[i] in lookup:
lookup.remove(s[left])
left += 1
curlen -= 1
maxlen = max(maxlen, curlen)
lookup.add(s[i])
return maxlen
for s in ['abcabcbb','bbbbb','pwwkew']:
print(s, lengthoflongestsubstring(s))
abcabcbb 3
bbbbb 1
pwwkew 3
from itertools import permutations
s = "barfoothefoobarman"
words = ["foo","bar"]
res = []
for i in map(lambda x:''.join(x), set(permutations(words, len(words)))):
index = s.find(i)
if index != -1:
res.append(index)
res
[0, 9]
from collections import defaultdict
def balancedString(s):
n = len(s)
if n <=0 or n%4 != 0:
return 0
m = n // 4
dic = defaultdict(int)
for c in s:
dic[c] += 1
if dic['Q']==m and dic['W']==m and dic['E']==m and dic['R']==m: #已经平衡了
return 0
min_window_len = n #窗口内为多了的 窗口外为ok的 没超阈值的
L = 0 #L R 均为实指
for R in range(n):
dic[s[R]] -= 1
while L <= R and dic['Q']<=m and dic['W']<=m and dic['E']<=m and dic['R']<=m:
min_window_len = min(min_window_len, R - L + 1)
dic[s[L]] += 1
L += 1
return min_window_len
for s in ['QWER','QQWE','QQQW','QQQQ']:
print(s, balancedString(s))
QWER 0
QQWE 1
QQQW 2
QQQQ 3