组队学习第9期-数据结构与算法学习笔记

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
1赞