Peterliang

题解

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

/ 注册

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

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

题意分析给我们一个二维数组，这个二维数组从上到下，从左到右都是递增的，需要我们判断这个二维数组中是否存在一个给定的数字。如果存在，那么直接返回true，否则返回false 思路分析思路一暴力法我们可以对这个二维数组直接进行遍历，然后我们逐个进行判断是否存在，如果存在直接返回true，最...

牛客题霸

2021-07-18

4 1152

NC6 题解 | #二叉树的最大路径和#

题意分析这个题目我们需要计算出一棵二叉树上面的所有的路径当中，找出路径的和最大的那个值。这个题目的难点就是中途可能会存在权值为负数的情况，还有权值为0的情况不好处理。这个题目还是有点意思的，我们可以用一个类似与树形DP的方法进行求解。前缀知识，树形DP，树形DP就是我们假设我们知道了一棵二...

牛客题霸

2021-07-18

4 1596

NC8 题解 | #二叉树根节点到叶子节点和为指定值的路径#

题目意思这个题目的意思和JZ24的题目几乎一模一样，就是对于从根节点到叶子节点的所组成的路径中。选择路径中的所有的权值之和等于给定的某一个数的路径。并且将他们返回。前置知识。这个题目我用的分别是DFS和BFS进行处理的。其中DFS用了一个回溯的方法进行处理。回溯法是一个DFS的技巧，就是当我...

牛客题霸

2021-07-18

0 714

NC7 题解 | #买卖股票的最好时机#

题意分析这个题目就是给我们一个数组，数组中的每个数字代表第i天某支股票的价格，我们需要选择一天买入，选择一天卖出。最后使我们的收益最大化。题目难度：简单思路分析解法一暴力枚举这个思路就是对于每一天的股票的价格，我们假设这天我们卖出这个股票，那么我们可以枚举这天之前的股票价格作为买入...

牛客题霸

2021-07-16

27 2823

NC5 题解 | #二叉树根节点到叶子节点的所有路径和#

题意分析这个题目就是要我们找出从根结点到叶子结点的所有的数字，然后我们需要将这些数字拼接成一个数，将所有的数相加起来就是我们的答案了。前置知识，DFS。对于DFS我们可以想象成一棵树，我们需要不断递归到树的最下面的叶子节点。思路分析思路一 DFS 我们对整棵二叉树进行递归操作，同时...

牛客题霸

2021-07-16

0 875

NC4 题解 | #判断链表中是否有环#

题意分析这个题目是NC3的弱化版，这个题目不需要我们求出环的入口结点，只需要我们判断是否存在环就可以。思路分析所以我们可以按照NC3那题的思路来写。思路一哈希处理我们首先将所有的结点存入一个哈希表里面，然后我们需要遍历整个链表，如果存在相同的节点说明存在环，返回true即可。 ...

牛客题霸

2021-07-16

3 1708

NC3 题解 | #链表中环的入口结点#

题意分析这个题目给我们一个经过特殊处理的链表，这个链表分为两段，每一段包含一个链表的非环的部分和成环的部分。大多数人可能一开始看样例的时候会感觉不是很理解。其实你就只要知道它给你一个链表，这个链表中如果成环的话就说明这个链表里面存在相同的结点。也就是转化为问你给出一个链表，需要你判断这个链表里面...

牛客题霸

2021-07-15

1 855

NC2 题解 | #重排链表#

题意分析给出一个链表，需要我们对这个链表进行重新排列，交错取出原来的链表最前面没有被取过的和最后面没有被取过的结点，新的链表就是按照这个取出的顺序重新拼接而成的一个链表。样例解释思路分析题目的意思是给我们一个链表的头结点，需要我们不能改变结点内部的值，只能改变结点的next指针。这样...

牛客题霸题解

2021-07-15

2 1056

NC1 题解 | #大数加法#

题意分析这个题目让我们求出两个很大很大的数的和。思路分析思路一用Python 我们知道，目前对于大多数高级语言，都存在着对高精度的处理。所以我们直接使用Python就行了。代码如下** 需要遍历字符串a和b的每个字符，时间复杂度为O(lena+lenb) 需要存储a和b字符串，空...

题解刷题牛客题霸

2021-07-15

34 6444

JZ67 题解 | #剪绳子#

题意分析题目的意思是给出一个数字，让我们将这个数字进行分解，然后找到分解后所有的数的乘积最大的情况。样例分析，我们可以将8分解为2x3x3，得到的结果就是18,这个可以自己暴力枚举一下所有的情况进行验证。思路分析这个题目，我主要用的是三种方法进行解答解法一暴力枚举我们可以发现...

题解刷题

2021-07-14

3 947