大内高手
大内高手
全部文章
题解
前端(1)
归档
标签
去牛客网
登录
/
注册
大内高手
There is challenge, there is chance.
全部文章
/ 题解
(共9篇)
最短路径 - Travel Plan
这是一道最短路径的变形问题,其中不仅要计算最短的路径,还要在最短路径的基础上计算最小花费,而且要记录所经过的“城市”。总体上来说这是一道“简单”的30分题目。一些关键代码我给出了注释。注意输出路径的时候,要逆序输出(我用了stack,也可以不用)。 // runtime: 4ms // space:...
CPP
PAT
最短路径
2020-05-03
0
835
二叉树构建与遍历 - Tree Traversals
我采用经典思路:构建二叉树、然后再进行层序遍历。思路很简单,构建过程也是很基础。柳神的思路很特殊,值得对照思考。链接在此 // runtime: 4ms // space: 384K // https://pintia.cn/problem-sets/994805342720868352/probl...
CPP
PAT
二叉树
2020-05-01
0
823
贪心 - Shortest Distance
本以为这是一道水题,但谁知水题也有“坑”啊! 先说一下情况,这个最终版本的答案是OK的,这是我第三遍做出来的。 第一个答案是暴力加和,比如求2-5,那我就从2-5加起来,然后用sum减去此和,然后取两者的较小值。但是后面一看N最大是 ,而M最大是 ,所以最多可能产生 次操作,肯定超时。 第二个答...
CPP
PAT
最短路径
贪心
2020-04-09
0
648
PAT1013 - Battle Over Cities
这是一道并查集问题,需要注意的是,并不是所有的点都进行并查集操作,而是除了“某点”之外其余各点均进行合并,然后输出合并后集合的个数-1 // runtime: 4ms // space: 512K // https://pintia.cn/problem-sets/99480534272086835...
CPP
PAT
并查集
2020-04-05
0
733
PAT1033 - To Fill or Not to Fill
此题考察的是贪心算法。 解题思路: 在起点加油,加多少不确定。记录当前油价,从下一站开始查找,满足条件 下一站的dis <= (当前dis + 加满油最多的距离),如果遇到此站的油价小于当前油价,则从上一站加油只需要加到能够跑到此站为止即可,若满足条件的站点的油价都大于上一次当前站的油价,那么...
CPP
PAT
贪心
2020-04-05
0
1173
PAT1010 - Radix
这题看起来不难,实际上并不是一道简单的进制转换问题,有几点需要注意。 没有给最大的radix,第一次提交我最大radix设置到了100,只有第7个测试点错误,其余全部正确,于是我把radix设置到了10000,还是只有第七个测试点错误,设置到了1000000,这时有测试点TLE了。。。 根据1可知...
CPP
PAT
2020-04-04
0
755
PAT1012 - The Best Rank
此题虽说不是什么高级算法题目,但是很多细节方面很到位。 本题“坑位”: 总分是四舍五入,而不是向下取整 exist数组里保存的应该是四次单科排序过后的index+1,这里+1是为了规避0,因为全局int数组默认初始化为0 sort四科需要四个compare函数,但是cmp很巧妙的只写一个函数就OK...
CPP
PAT
2020-04-04
0
656
PAT1007 - Maximum Subsequence Sum
这是一道求最大连续子序列和的问题(DP问题)。除了求最大连续子序列的和之外,还需要输出最大连续子序列的起点和终点的值。 // runtime: 8ms // space: 424K // https://pintia.cn/problem-sets/994805342720868352/proble...
CPP
DP
PAT
2020-04-03
0
1157
PAT1004 - Counting Leaves
此题考查树的层序遍历,需要记住的是层数n // runtime: 3ms // https://pintia.cn/problem-sets/994805342720868352/problems/994805521431773184 #include <iostream> #inclu...
树的遍历
CPP
PAT
2020-04-02
0
589