- 博客(107)
- 收藏
- 关注
RSS订阅原创 coursera 之 machine learning 编程作业
作业地址：https://github.com/Zkwei/machine-learning-exercises
2018-11-23 20:02:14
1020
原创 PAT (Advanced) 1104. Sum of Number Segments (20)
原题：1104 Sum of Number Segments (20)解题思路：找出每个数的出现次数与其位置的关系即可代码如下：#include<cstdio>const int maxn = 100000 + 5;double num[maxn];int main(){ int n; while(scanf("%d", &n) == 1) { for(int...
2018-05-19 14:01:24
256
原创 PAT (Advanced) 1103. Integer Factorization (30)
原题：1103. Integer Factorization (30)解题思路：dfs从大数往小数暴力递归即可。代码如下：#include<cstdio>#include<algorithm>#include<vector>using namespace std;int n, k, p, maxSum;vector<int> ans, t...
2018-05-19 13:47:31
227
原创 PAT (Advanced) 1102. Invert a Binary Tree (25)
原题：1102. Invert a Binary Tree (25)解题思路；输入是把左右子树全换一遍，再按正常层序和中序遍历输出即可。代码如下：#include<cstdio>#include<cstring>#include<algorithm>#include<queue>using namespace std;const int m...
2018-04-28 14:52:44
150
原创 PAT (Advanced) 1101. Quick Sort (25)
原题：1101. Quick Sort (25)解题思路：主要要求哪些数已经在对应的排好序的位置上了，主要特征是左边都比它小，右边都比它大。那只要用数组保存每个数左边的最大值，右边的最小值即可，每次判断可以直接读取不需要再判断左右的情况。代码如下：#include<cstdio>#include<algorithm>#include<vector>usin...
2018-04-28 14:23:42
158
原创 PAT (Advanced) 1100. Mars Numbers (20)
原题：1100. Mars Numbers (20)解题思路；按题意模拟即可。代码如下：#include<cstdio>#include<iostream>#include<algorithm>#include<string>#include<sstream>using namespace std;string ge[13]...
2018-04-27 15:00:11
150
原创 PAT (Advanced) 1099. Build A Binary Search Tree (30)
原题：1099. Build A Binary Search Tree (30)解题思路：数量不大，可以用数组解决。题目中给出的0-N-1为一个先序遍历，BST的中序遍历实际上是数据从小到大的，所以先用中序遍历构造好BST，然后用层序遍历输出结果即可。代码如下：#include<cstdio>#include<algorithm>#include<queue>...
2018-04-27 14:26:21
118
原创 PAT (Advanced) 1098. Insertion or Heap Sort (25)
原题：1098. Insertion or Heap Sort (25)解题思路：写好模拟一次堆排序或插入排序的函数即可，提高效率，判断是否为插入排序即可。注：插入排序最后输出的排序序列必须与输入给的中间结果不同。代码如下：#include<cstdio>#include<algorithm>#include<cstring>using namespace...
2018-04-27 14:00:06
100
原创 PAT (Advanced) 1097. Deduplication on a Linked List (25)
原题：1097. Deduplication on a Linked List (25)解题思路：按题意模拟静态链表操作即可。代码如下：#include<cstdio>#include<algorithm>#include<cstring>using namespace std;const int maxn = 100000 + 5;const int...
2018-04-23 13:48:34
116
原创 PAT (Advanced) 1096. Consecutive Factors (20)
原题：1096. Consecutive Factors (20)解题思路：最暴力的方法是一个一个去除，不过实际上只要算前开方个数即可。被中间一个溢出卡了最后一个样例，最后把i*i转成long long才得以解决。代码如下：#include<cstdio>#include<algorithm>using namespace std;int main(){ ...
2018-04-22 14:35:18
133
原创 PAT (Advanced) 1095. Cars on Campus (30)
原题：1095. Cars on Campus (30)解题思路：两轮排序。第一轮筛选出有效的停车记录，然后统计每辆车的时间。第二轮按记录的时间排序，可以按时间计算当前的车辆数。把时间转换成秒，会方便很多。代码如下：#include<cstdio>#include<algorithm>#include<cstring>#include<string&...
2018-04-22 11:15:32
147
原创 PAT (Advanced) 1094. The Largest Generation (25)
1094. The Largest Generation (25)解题思路：利用bfs保存每层宽度，最后求最大宽度即可。代码如下：#include<cstdio>#include<algorithm>#include<vector>#include<queue>using namespace std;const int maxn = 105...
2018-04-19 21:45:21
149
原创 PAT (Advanced) 1093. Count PAT's (25)
原题：1093. Count PAT's (25)解题思路：总共只有三个字母，np记录目前为止P的数量，tmp记录目前为止所有PA的数量，每次遇到T在答案里加上tmp即可。代码如下：#include<cstdio>#include<iostream>#include<algorithm>#include<string>using namesp...
2018-04-19 21:15:46
92
原创 PAT (Advanced) 1092. To Buy or Not to Buy (20)
原题：1092. To Buy or Not to Buy (20)解题思路：建一个记录所要的所有字符出现次数的向量，再与给出的字符串进行比对即可。代码如下：#include<iostream>#include<cstdio>#include<algorithm>#include<string>using namespace std;con...
2018-04-17 12:32:35
154
原创 PAT (Advanced) 1091. Acute Stroke (30)
原题：1091. Acute Stroke (30)解题思路：按题意进行bfs即可（dfs会爆栈），求出值为1的联通分量，数量大于等于阈值的加入最终答案。代码如下：#include<cstdio>#include<algorithm>#include<cstring>#include<queue>using namespace std;co...
2018-04-15 01:05:42
147
原创 PAT (Advanced) 1090. Highest Price in Supply Chain (25)
原题：1090. Highest Price in Supply Chain (25)解题思路：建立供应树，用bfs求解即可。代码如下：#include<cstdio>#include<algorithm>#include<vector>#include<queue>using namespace std;const int maxn = ...
2018-04-13 11:29:41
139
原创 PAT (Advanced) 1089. Insert or Merge (25)
原题：1089. Insert or Merge (25)解题思路：主要是模拟归并和插入排序的过程，数据量较小，就把归并和插入的过程直接用sort实现了。注：可以先判断是不是插入排序，如果不是，肯定是归并排序。另外，最初的序列不参与比较。代码如下：#include<cstdio>#include<algorithm>#include<cstring>usi...
2018-04-13 11:09:55
141
原创 PAT (Advanced) 1088. Rational Arithmetic (20)
原题：1088. Rational Arithmetic (20)解题思路：按题意计算即可。用公约数一直化成最简，注意数的输出格式，用long long 防溢出。代码如下：#include<cstdio>#include<algorithm>#include<cstring>using namespace std;long long gcd(long ...
2018-04-12 16:33:04
131
原创 PAT (Advanced) 1087. All Roads Lead to Rome (30)
原题：1087. All Roads Lead to Rome (30)解题思路：用最短路径算法求出所有最短路径，再用dfs方法探索每条路径，选出符合条件的路径即可。代码如下：#include<cstdio>#include<algorithm>#include<vector>#include<string>#include<map&g...
2018-04-12 15:45:22
219
原创 PAT (Advanced) 1086. Tree Traversals Again (25)
原题：1086. Tree Traversals Again (25)解题思路：实际上入栈顺序就是前序遍历，出栈顺序就是中序遍历，那么有了两个遍历就可以直接构造一个二叉树，后续遍历也就可以直接得到。代码如下：#include<cstdio>#include<algorithm>#include<cstring>#include<stack>u...
2018-04-07 23:17:07
165
原创 PAT (Advanced) 1085. Perfect Sequence (25)
原题：1085. Perfect Sequence (25)解题思路：双指针。将数据从小到大排序后，满足条件时不断将右指针右移，不满足时左指针右移，每次都保存最大个数即可。代码如下:#include<cstdio>#include<algorithm>using namespace std;typedef long long ll;const int maxn = ...
2018-04-06 23:38:06
148
原创 PAT (Advanced) 1084. Broken Keyboard (20)
原题：1084. Broken Keyboard (20)解题思路：哈希记录实际句子，与原句子比较，找出缺少的字符并大写。代码如下：#include<iostream>#include<algorithm>#include<string>#include<cstring>using namespace std;int h[256];ch...
2018-04-06 22:47:54
95
原创 PAT (Advanced) 1083. List Grades (25)
原题：1083. List Grades (25)解题思路：排序。按顺序输出即可。不过不知道N的范围，猜了一个代码如下：#include<cstdio>#include<algorithm>#include<cstring>using namespace std;const int maxn = 10000;struct Record{ c...
2018-04-06 22:27:20
98
原创 PAT (Advanced) 1082. Read Number in Chinese (25)
原题：1082. Read Number in Chinese (25)解题思路：主要理清楚规律，每位应该输出什么数字，模拟一遍就好了。代码如下：#include<cstdio>#include<algorithm>#include<cstring>using namespace std;char tab1[11][10] = {"ling", "yi...
2018-04-03 23:10:59
79
原创 PAT (Advanced) 1081. Rational Sum (20)
原题：1081. Rational Sum (20)解题思路：用long long 去模拟分数加法即可，注意最后一个样例和为0代码如下：#include<cstdio>#include<algorithm>#include<cstring>using namespace std;long long gcd(long long a, long long ...
2018-04-03 22:25:21
109
原创 PAT (Advanced) 1080. Graduate Admission (30)
原题：1080. Graduate Admission (30)解题思路：关键在于理解题意：1.按总分排序，总分一样按GE排序，GE也一样，则序号一样2.按照志愿从高到低，直到最后3.每个志愿只要目标院校没满员，或者当前学生名次和该校最后录取的学生名次一样，就录取4.注意最后输出按照id从小到大代码如下：#include<cstdio>#include<algorithm>...
2018-04-01 23:20:38
101
原创 PAT (Advanced) 1079. Total Sales of Supply Chain (25)
原题：1079. Total Sales of Supply Chain (25)解题思路：bfs把每层的价格算出来，遇到叶节点就加入总和即可。代码如下：#include<cstdio>#include<algorithm>#include<cstring>#include<vector>#include<queue>using...
2018-04-01 21:02:21
119
原创 PAT (Advanced) 1078. Hashing (25)
原题：1078. Hashing (25)解题思路：按题意模拟，注意平方探测只有正向。代码如下：#include<cstdio>#include<algorithm>#include<cstring>using namespace std;const int maxn = 10000 + 8;int mp[maxn];int num[maxn];i...
2018-03-29 21:25:58
99
原创 PAT (Advanced) 1077. Kuchiguse (20)
1077. Kuchiguse (20)解题思路：暴力就行，从末尾开始比较。代码如下：#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int maxn = 100 + 5;const int maxl = 300 + 5;char str[ma...
2018-03-29 20:27:43
103
原创 PAT (Advanced) 1076. Forwards on Weibo (30)
原题：1076. Forwards on Weibo (30)解题思路：实际上就是bfs对应的层数并求出点的数量，注意在输入数据时有向边应由被关注者指向关注者，方便处理。在结点内维护一个level表示层数，在bfs就能判断当前的层了。代码如下：#include<cstdio>#include<algorithm>#include<vector>#inclu...
2018-03-28 15:44:42
109
原创 PAT (Advanced) 1075. PAT Judge (25)
原题：1075. PAT Judge (25)解题思路：主要理解题意即可，设置-2为未提交过，-1为编译未通过，最后按题目要求排序输出。代码如下：#include<cstdio>#include<algorithm>#include<cstring>using namespace std;const int maxn = 10000 + 5;str...
2018-03-28 15:10:09
87
原创 PAT (Advanced) 1074. Reversing Linked List (25)
原题：1074. Reversing Linked List (25)解题思路：构造双链表。主要在原链表中加入一个pre表示前一个节点，反转只要将next与pre互换即可，当然首尾需要特殊处理。代码如下：#include<cstdio>#include<algorithm>using namespace std;const int maxn = 100000;str...
2018-03-26 23:44:58
189
原创 PAT (Advanced) 1073. Scientific Notation (20)
原题：1073. Scientific Notation (20)解题思路：实际上就是模拟题，考虑好所有情况（需要不需要添0），以及去掉+号即可。我用的是stl库的函数对字符串进行处理。代码如下：#include<iostream>#include<algorithm>#include<string>using namespace std;int tr...
2018-03-24 01:04:13
168
原创 2018清华计算机考研总结
算是度过了艰辛的二战，好在结果不错，已被网络研究院拟录取，应该算是通过复试了。三跨清华计算机，一战的时候不知深浅，通过初试，但没想到机考难度这么高，第一天考完心态崩溃，面试，卒。于是乎选择二战，依旧通过初试，也练了机试，面试也没崩，不过也不知道什么情况，依旧被刷，好在有云龙胸（代号）的支持，迅速调整心态，并在狗头（代号）的帮助下备战网研院，最终成功通过复试。————————————————————...
2018-03-24 00:06:41
45824
19
原创 PAT (Advanced) 1072. Gas Station (30)
原题：1072. Gas Station (30)解题思路：用dijkstra算法计算出每个加油站到村庄的最短距离即可。对于加油站的优先级：1）保证距离最大的村庄在服务范围内2）在1）下，保证距离最小的村庄离加油站最远3）在2）下，保证平均距离最小4）在3）下，保证id最小代码如下：#include<cstdio>#include<algorithm>#include&...
2018-03-10 16:09:26
128
原创 PAT (Advanced) 1071. Speech Patterns (25)
原题：1071. Speech Patterns (25)解题思路：为了方便用string流，拿map做了低效的hash，时间还可以承受。第一步把字符串里的无关字符全部去掉，把大写换成小写，后再统计单词个数即可。map是自动排序的，所以第一个解就是答案。代码如下：#include<cstdio>#include<iostream>#include<string&g...
2018-03-09 17:37:27
149
原创 PAT (Advanced) 1070. Mooncake (25)
原题：1070. Mooncake (25)解题思路：贪心。每次挑单价最高的即可。注意质量用double保存，不然第三个样例过不去。代码如下：#include<cstdio>#include<algorithm>using namespace std;const int maxn = 1000 + 5;struct MC{ double price; ...
2018-03-09 17:17:55
141
原创 PAT (Advanced) 1069. The Black Hole of Numbers (20)
原题：1069. The Black Hole of Numbers (20)解题思路：按题意做即可。代码如下：#include<cstdio>#include<algorithm>#include<string>using namespace std;int main(){ char s[10]; while(scanf("%s"...
2018-03-09 16:53:02
110
原创 PAT (Advanced) 1068. Find More Coins (30)
原题：1068. Find More Coins (30)解题思路：一开始想用搜索+回溯来做，但发现最后一个样例过不去，也想不出该怎么剪枝，就考虑其他方法了。仔细分析一下就是一个01背包问题，只不过物品质量和价值比为1:1，求解就简单了。如果最后结果dp[n][m]不等于价值量，也就是无解了。第二个问题是求最小解，一开始我是从小到大放，但是无法求出最小解，就试着从大到小放硬币，发现可以完成任务。代...
2018-03-09 15:27:11
147
3
原创 PAT (Advanced) 1067. Sort with Swap(0,*) (25)
原题：1067. Sort with Swap(0,*) (25)解题思路：每次把0所在位置上数找到是使用次数最少的。然后按题目意思去模拟就好，不过会出现还未排序完0就在位置0上的情况，所以要加一个计数器来计算剩下的不在位置上的数，当0回到0位置时，如果未排好，就找一个不在位置上的数与0交换（不要总是从头找，会超时，设置一个每次都更新的标记，每次都从标记往后找），再继续排序即可。代码如下：#inc...
2018-03-07 18:58:59
145
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人