ACM决赛新颖试题及配套答案

ACM决赛新颖试题及配套答案考试时间：______分钟总分：______分姓名：______一、给定一个包含n个整数的数组，数组中的整数范围为1到n，且数组中恰好有一个整数重复了两次，其余整数均只出现一次。请设计一个算法，在O(n)时间复杂度和O(1)空间复杂度下，找出这个重复的整数。要求描述算法的核心思想，并分析其时间复杂度和空间复杂度。二、在一个由mxn个格子组成的二维网格中，每个格子可能包含一个障碍物。机器人从左上角的格子(0,0)出发，目标是到达右下角的格子(m-1,n-1)。机器人每次只能向下或向右移动一个格子，且不能移动到包含障碍物的格子。请设计一个算法，计算机器人从起点到达终点的不同路径数量。要求描述算法的核心思想，并分析其时间复杂度。三、给定一个由小写字母组成的字符串s，以及一个整数k。请设计一个算法，找到s中最长的子串，该子串中的所有字母在s中出现的次数都不超过k。要求描述算法的核心思想，并分析其时间复杂度。四、在一个无向图中，每个节点都有一个权重值。请设计一个算法，找到图中的一条简单路径，使得路径上所有节点的权重值之和最大。要求描述算法的核心思想，并分析其时间复杂度。五、给定一个由0和1组成的二维矩阵，矩阵中1的个数远远多于0。请设计一个算法，找到矩阵中最大的矩形，该矩形由所有1组成。要求描述算法的核心思想，并分析其时间复杂度。六、有一个长度为n的排列p，即p包含了1到n的所有整数，且p中的每个整数只出现一次。现在对p进行若干次“翻转”操作，每次翻转操作可以选择排列p中任意一个连续的子数组，并将该子数组中的元素顺序反转。请设计一个算法，判断是否可以通过若干次翻转操作，将排列p变成升序排列（即p[i]=i+1）。要求描述算法的核心思想，并分析其时间复杂度。试卷答案一、核心思想：利用数组本身的性质，将数字i放置到索引为i-1的位置。遍历数组，检查当前位置的数字是否与索引相同，若不同，则继续检查该数字应该放置的位置，直到找到重复的数字或确定不存在重复数字。时间复杂度：O(n)空间复杂度：O(1)解析：初始化slow=0,fast=0.slow=nums[slow],fast=nums[nums[fast]],fast=nums[nums[nums[fast]]],...当slow==fast时，进入循环，slow=nums[slow],fast=nums[fast],直到slow==fast再次相遇。此时，slow=entry。令slow=0,thenslow=nums[slow],fast=nums[fast],untilslow==fast.此时，slow==fast==entry，即为重复元素。二、核心思想：使用动态规划。定义dp[i][j]表示从(0,0)到(i,j)的路径数量。状态转移方程为dp[i][j]=dp[i-1][j]+dp[i][j-1]，其中dp[0][j]=1,dp[i][0]=1。最终结果为dp[m-1][n-1]。时间复杂度：O(m*n)空间复杂度：O(m*n)解析：dp[i][j]表示到达(i,j)的路径数。到达(i,j)的路径，要么从(i-1,j)向下走，要么从(i,j-1)向右走。所以dp[i][j]=dp[i-1][j]+dp[i][j-1]。边界条件：dp[0][j]=1(第一行只能向右走)，dp[i][0]=1(第一列只能向下走)。计算dp矩阵，最终dp[m-1][n-1]即为答案。三、核心思想：使用滑动窗口。维护一个窗口[left,right]，其中窗口内所有字母在s中出现的次数都不超过k。通过调整left和right的位置，找到满足条件的最长子串。时间复杂度：O(n)空间复杂度：O(1)解析：使用哈希表记录窗口内各字母的出现次数count[c]。初始化left=0,max_len=0。遍历字符串s，i从0到n-1。count[s[i]]++。如果count[s[i]]>k，则移动left，直到count[s[i]]<=k。max_len=max(max_len,i-left+1)。最终max_len即为答案。四、核心思想：使用深度优先搜索(DFS)或动态规划。DFS方法中，遍历每个节点，递归计算以该节点为终点的最大权重路径和。动态规划方法中，可以构建一个二叉树（例如使用并查集或LCA算法），然后计算每个节点的最大权重路径和。时间复杂度：DFS为O(N^2)（最坏情况），动态规划为O(NlogN)（使用LCA）空间复杂度：O(N)解析(DFS示例):对于每个节点u，计算以u为终点的最大权重路径和max_path[u]。max_path[u]=weight[u]+max(max_path[child[v]]foralledges(u,v))。遍历所有节点，计算max(max_path[u])即为答案。五、核心思想：将矩阵转化为柱状图，每个元素的高度为该列中连续1的个数。然后利用“LargestRectangleinHistogram”的解法，计算每个柱状图的最大矩形面积，最后找出所有矩形面积中的最大值。时间复杂度：O(m*n)空间复杂度：O(n)解析：height[j]=numberofconsecutive1'sincolumnjuptorowi.Foreachrowifrom0tom-1,updateheight[j]andcalculatethelargestrectangleareainthehistogramformedbyheight[0..n-1]usingastack.Area=height[j]*width,wherewidthisthenumberofconsecutivecolumnswithheight>=height[j].Keeptrackofthemaximumareafound.六、核心思想：利用排列的性质。如果排列p可以通过若干次翻转操作变成升序排列，那么p必须包含不多于1个“上升”的拐点（即存在i，使得p[1..i]是升序，p[i+1..n]是降序，或反之）。如果拐点数量超过1，则无法通过翻转操作将其变为升序排列。时间复杂度：O(n)空间复杂度：O(1)解析：遍历排列p，记录拐点的数量。拐点定义：p[i]<p[i+1]且p[i+1]<p[i+2]（上升拐点），或p[i]>p[i+1]且p[i+1]>p[i+2]（下降拐点）。初始cou