大内高手

题解

前端(1)

/ 注册

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

最短路径 - Travel Plan

这是一道最短路径的变形问题，其中不仅要计算最短的路径，还要在最短路径的基础上计算最小花费，而且要记录所经过的“城市”。总体上来说这是一道“简单”的30分题目。一些关键代码我给出了注释。注意输出路径的时候，要逆序输出（我用了stack，也可以不用）。 // runtime: 4ms // space:...

CPP PAT 最短路径

2020-05-03

0 815

二叉树构建与遍历 - Tree Traversals

我采用经典思路：构建二叉树、然后再进行层序遍历。思路很简单，构建过程也是很基础。柳神的思路很特殊，值得对照思考。链接在此 // runtime: 4ms // space: 384K // https://pintia.cn/problem-sets/994805342720868352/probl...

CPP PAT 二叉树

2020-05-01

0 814

贪心 - Shortest Distance

本以为这是一道水题，但谁知水题也有“坑”啊！先说一下情况，这个最终版本的答案是OK的，这是我第三遍做出来的。第一个答案是暴力加和，比如求2-5，那我就从2-5加起来，然后用sum减去此和，然后取两者的较小值。但是后面一看N最大是，而M最大是，所以最多可能产生次操作，肯定超时。第二个答...

CPP PAT 最短路径贪心

2020-04-09

0 646

PAT1013 - Battle Over Cities

这是一道并查集问题，需要注意的是，并不是所有的点都进行并查集操作，而是除了“某点”之外其余各点均进行合并，然后输出合并后集合的个数-1 // runtime: 4ms // space: 512K // https://pintia.cn/problem-sets/99480534272086835...

CPP PAT 并查集

2020-04-05

0 728

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 1154

PAT1004 - Counting Leaves

此题考查树的层序遍历，需要记住的是层数n // runtime: 3ms // https://pintia.cn/problem-sets/994805342720868352/problems/994805521431773184 #include <iostream> #inclu...

树的遍历 CPP PAT

2020-04-02

0 599