Peterliang

题解

PAT挑战日记(15) 《算法竞赛进阶指南》系列题解(4) 心路历程(1) 未归档(5) 模板(2)

/ 注册

全部文章 / 题解（共145篇）

NC28 题解 | #最小覆盖子串#

题意分析给出两个字符串S和T，需要我们在S字符串里面找到一个最短的字符串，使得这个这个字符串中包含T字符串里面的所有的字符。题目要求使用O(n)的时间复杂度。题目一定保证如果存在这个字符串，那么这个字符串一定是唯一的。思路分析解法一二分查找我们看到求最短的字符串，那么很容易可以想到用...

牛客题霸

2021-08-11

0 2870

NC27 题解 | #集合的所有子集#

题意分析给你一个序列，需要找到这个序列的所有的子序列的集合，要求这些子序列的内部需要按照元素的大小进行升序排列。前置知识什么是子序列？子序列是一个序列里面选择若干个元素，这些元素要保持初始的相对位置，然后组成的一个新的序列就叫做这个初始序列的子序列。思路分析解法一回溯法对于每...

牛客题霸

2021-08-11

0 736

NC26 题解 | #括号生成#

题意分析给你一个数字n，需要找到所有的合法的括号序列，括号的个数为n个。前置知识首先，我们需要知道什么是合法的括号序列？我们知道()这种括号序列是一个合法的序列，)(这种的括号序列不是一个合法的括号序列。那么如果A和B都是合法的括号序列，那么AB也是合法的括号序列，(AB)也是合法的括号...

牛客题霸

2021-08-11

1 719

NC24 题解 | #删除有序链表中重复的元素-II#

题意分析给出一个链表，要求我们返回这个链表中的所有的元素，但是与NC25不同的是，要求这些元素是在初始的链表里面只出现一次的元素，同时这个链表的所有的元素需要保持原来的相对位置关系。这个就不是去重了。思路分析我们思考，如何把出现多次的元素在链表里面去掉呢？方法还是利用哈希进行处理，我们...

牛客题霸

2021-08-10

0 725

NC25 题解 | #划分链表I#

题意分析给出一个链表，要求我们返回这个链表中的所有的元素，要求这些元素只出现一次，同时这个链表的所有的元素需要保持原来的相对位置关系。简单来说就是先去重，然后我们按照原来的位置关系重新构造这个链表返回即可。思路分析我们思考，如果出现相同的数字我们如何去重呢？这里我是利用的map进行处理...

牛客题霸

2021-08-10

0 545

NC42 题解 | #有重复项数字的所有排列#

题意分析首先，题目给出一个大小为n的数组，然后，需要我们求出这个数组的全排列。但是要注意的是这个数组里面可能存在相同的数字。思路分析解法一库函数实现学习过C++的同学应该都直到，C++有一个库函数next_permutation可以用来处理数组的全排列问题，但是这个库函数需要我们先对...

牛客题霸

2021-08-09

0 765

NC41 题解 | #最长无重复子数组#

题意分析给你一个数组，需要找出这个数组里面最长的子序列的长度，要求这个子序列里面的所有的数不重复。前置知识，首先，你需要了解什么是子序列？子序列是一个连续的序列，你可以理解为一个数组去掉前面和后面的一部分元素形成的。然后，你需要了解如何哈希，这里的C++给我们提供了STL，里面的map就是...

牛客题霸

2021-08-09

0 629

NC40 题解 | #两个链表生成相加链表#

题意分析给出两个链表，这两个链表代表两个数字（注意，这个数字可能很大,大数),从表头到表尾表示的是这个链表的高位到低位。需要我们将这两个链表的数字进行相加，然后构造一个新的链表表示出这个和。样例解释请看下面的图思路分析首先，我们可以看到这个题目的本质就是一个大数加法运算，两个链...

牛客题霸

2021-08-04

0 670

NC38 题解 | #螺旋矩阵#

题意分析给出一个n行n列的矩阵，需要我们返回这个矩阵的螺旋序列。也就是从左上角开始顺时针进行遍历，从外面往里面遍历，知道遍历了所有的数字。每个位置的数字只能被遍历一遍。思路分析我们可以观察得到，这个遍历的序列是从外面逐渐往里面进行扩展的。也就是先遍历完最外面的一层，然后遍历倒数第二层...

牛客题霸

2021-08-04

0 560

NC37 题解 | #合并区间#

题意分析给出若干个区间，注意这些区间的左右端点是没有顺序的，我们需要将有交集的区间进行合并，然后按照左端点的大小进行返回。思路分析我们发现这个数组是没有顺序的，为了方便处理，我们可以先对区间进行排序，只需要按照左端点进行排序即可。排好序之后，我们对两个区间进行比较，当出现有重叠的时候就可...

牛客题霸

2021-08-02

0 1936