分类 DS-Algo 下的文章

xiin 1周前 DS-Algo

数据结构：出栈顺序可能的数目——卡特兰数

编号为 1、2、3、4、5 的 5 辆列车顺序开进栈式结构的站台，请问开出车站的顺序有多少种可能？A.1B.15C.42D.120要解决 “5 辆列车按固定顺序进栈，出栈顺序有多少种可能” 的问题，核心是理解栈的 “先进后出（LIFO）” 特性，并匹配对应的数学模型 ——卡特兰数（Catalan Number），以下是详细推导与分析：

51 0 0

数据结构作业&实验：银行排队问题系列问题题解

xiin 1周前 DS-Algo

数据结构作业&实验：银行排队问题系列问题题解

7-1 银行排队问题之单队列多窗口服务假设银行有K个窗口提供服务，窗口前设一条黄线，所有顾客按到达时间在黄线后排成一条长龙。当有窗口空闲时，下一位顾客即去该窗口处理事务。当有多个窗口可选择时，假设顾客总是选择编号最小的窗口。本题要求输出前来等待服务的N位顾客的平均等待时间、最长等待时间、最后完成时间，并且统计每个窗口服务了多少名顾客。输入格式:输入第1行给出正整数N（≤1000），为顾客总人数；随后N行，每行给出一位顾客的到达时间T和事务处理时间P，并且假设输入数据已经按到达时间先后排好了顺序；最后一行给出正整数K（≤10），为开设的营业窗口数。这里假设每位顾客事务被处理的最长时间为60...

33 0 0

C++

KMP 算法笔记

xiin 2周前 DS-Algo

KMP 算法笔记

next 数组定义（核心思想）对于一个模式串 pattern：next[i] 表示：pattern[0..i-1]（长度为 i 的前缀）中，最长的“相等的真前缀与真后缀”的长度。模式串pattern = "ababaca"1-base：i（从1开始）子串 pattern[0..i-1]最长相等前后缀长度next[i]1a无002ab无003abaa114ababab225ababaaba336ababac无007ababacaa11所以：next = [ 0, 0, 1, 2, 3, 0, 1]0-base：模式串 pattern[0..i]（长度为 i+1 的...

51 0 0

C++

LeetCode 42. 接雨水 [Hot 100] —— DP/双指针

xiin 3周前 DS-Algo

LeetCode 42. 接雨水 [Hot 100] —— DP/双指针

42. 接雨水已解答算术评级: 6给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。示例 1：输入：height = [0,1,0,2,1,0,1,3,2,1,2,1] 输出：6 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。示例 2：输入：height = [4,2,0,3,2,5] 输出：9第一种解法：动态规划（双数组法）核心思路：分别计算每个位置左侧的最大高度（left 数组）和右侧的最大高度（right 数组）对于每个位置，能接的雨...

79 0 0

Java

数据结构作业题：列车调度 —— 最长递增子序列

xiin 3周前 DS-Algo

数据结构作业题：列车调度 —— 最长递增子序列

列车调度火车站的列车调度铁轨的结构如下图所示。两端分别是一条入口（Entrance）轨道和一条出口（Exit）轨道，它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入，最后从出口离开。在图中有9趟列车，在入口处按照{8，4，2，5，3，9，1，6，7}的顺序排队等待进入。如果要求它们必须按序号递减的顺序从出口离开，则至少需要多少条平行铁轨用于调度？输入格式：输入第一行给出一个整数N (2 ≤ N ≤105)，下一行给出从1到N的整数序号的一个重排列。数字间以空格分隔。输出格式：在一行中输出可以将输入的列车按序号递减的顺序调离所需要的最少的铁轨条数。输入样例：9 8 4 2 ...

66 0 0

C++

分类：DS-Algo

数据结构：出栈顺序可能的数目——卡特兰数

数据结构作业&实验：银行排队问题系列问题题解

KMP 算法笔记

LeetCode 42. 接雨水 [Hot 100] —— DP/双指针

数据结构作业题：列车调度 —— 最长递增子序列

最近评论

博客文章RSS订阅

博客评论RSS订阅

登录

分类：DS-Algo

数据结构：出栈顺序可能的数目——卡特兰数

数据结构作业&实验：银行排队问题系列问题题解

KMP 算法笔记

LeetCode 42. 接雨水 [Hot 100] —— DP/双指针

数据结构作业题：列车调度 —— 最长递增子序列

最近评论

博客文章RSS订阅

博客评论RSS订阅