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