Peterliang

分类

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

/ 注册

全部文章（共38篇）

NC39 题解 | #N皇后问题#

题意分析经典模板题，n皇后问题。给你一张nxn的棋盘。需要往这个棋盘里面放一些棋子。然后需要保证这n个棋子之间不同同行同列和同正反斜线。也就是下图中在同一条线上面的不能同时放置棋子。思路分析好了，我们现在知道题目意思了，我们可以来说说怎么解这题。首先，我们需要知道如何判断两个位...

牛客题霸

2021-08-13

0 725

NC35 题解 | #最小编辑代价#

题目大意给你两个字符串，需要你通过执行三种操作，将一个字符串修改为另一个字符串。但是你执行这三种操作都是有代价的。三种操作分别对应三种代价。你需要使用最少的代价将这个字符串修改为另一个字符串。思路分析首先，这个题目是比较难的，我来大致介绍一下我的思路和想法。对于这个问题，最开始我想的是利...

牛客题霸

2021-08-13

0 1058

NC36 题解 | #在两个长度相等的排序数组中找到上中位数#

题意分析给你两个数组。数组都是按照从小到达进行排序的两个数组的大小相等需要我们求出两个数组的上中位数上中位数：假设递增序列长度为n，若n为奇数，则上中位数为第n/2+1个数；否则为第n/2个数同时时间复杂度为O(logn)，空间复杂度为O(1) 思路分析其实稍微了解过排序...

牛客题霸

2021-08-12

0 985

NC30 题解 | #数组中未出现的最小正整数#

题意分析首先，这个题目的题目描述有点问题。而且测试数据估计比较水。希望可以加强一下。其实，我们来说一下这个题目的大意。就是给你一个数组，需要你快速找出这个数组里面没有出现过的最小的正整数。怎么快速呢？就是要做到O(n),然后呢？就是，空间复杂度要控制在O(1). 思路分析解法一哈希这...

牛客题霸

2021-08-12

0 822

NC29 题解 | #二维数组中的查找#

题意分析给你一个二维数组，这个二维数组从左到右是递增的，从上到下也是递增的。要我们判断某一个整数是否在这个数组里面。思路分析解法一暴力解法二维数组，判断是否存在某一个数字，似乎很好理解。最直接的方法就是直接暴力循环所有的位置，直接判断是否存在，这样的话最好的时间复杂度为O(1),最坏...

牛客题霸

2021-08-11

0 572

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

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

牛客题霸

2021-08-11

0 2866

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 724

NC25 题解 | #划分链表I#

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

牛客题霸

2021-08-10

0 545