- 博客(153)
- 资源 (4)
- 收藏
- 关注
RSS订阅原创 [code] PTA 胡凡算法笔记 DAY055
文章目录题目 A1047 Student List for Course小结题目 A1047 Student List for Course题意输入学生人数和课程数。输入学生名字，选择课程数和各选择课程编号。输出每门课程选课的学生数。课程编号从小到大输出，学生名字按字母序输出。思路根据需要输出的内容很明显可以看出这里映射课程号是key，学生姓名是value。而且因为同一个学生会...
2020-01-11 18:26:40
322
原创 [code] PTA 胡凡算法笔记 DAY054
文章目录题目 A1039 Course List for Student小结题目 A1039 Course List for Student题意输入学生人数和课程数。之后输入课程编号及选课人数及所有学生姓名。最后输入所有学生姓名进行查询选课情况。输出格式为：学生姓名 课程数 各课程编号（递增顺序输出）思路开始很暴力直接用的map做映射，结果最后有一个case爆了。看解析之后采用...
2020-01-10 21:16:03
278
原创 [code] PTA 胡凡算法笔记 DAY053
文章目录题目 A1024 Palindromic Number小结题目 A1024 Palindromic Number题意输入数N和最大操作次数K，按如下规则进行操作：n += reverse(n)，当n为回文数字或者操作次数到达K后，输出最后的数和操作次数。思路因为数据范围超过了long long的范围所以需要设置大整数结构，然后就是大整数的加法操作和判断回文的操作，数字反...
2020-01-09 21:38:49
307
原创 [code] PTA 胡凡算法笔记 DAY052
文章目录题目 A1023 Have Fun with Numbers小结题目 A1023 Have Fun with Numbers题意输入一个数，判断两倍后的数字是否含有和原来数相同的数字及个数。输出Yes or No及两倍后的结果。思路构建大整数结构体字符串输入，转换为大整数类型*2函数实现，这里我主要通过首数字>=5时会lenth + 1判断是否两个数所...
2020-01-08 20:48:22
159
原创 [code] PTA 胡凡算法笔记 DAY051
文章目录题目B1017 A除以B小结题目B1017 A除以B题意输入被除数（最长1000位）与除数（1位），输出商和余数。思路基本就是按照我们手算的流程进行的，落一位小了再落一位这样。不过这里因为我开始设置余数是0，然后首位不会商0，所以后续多处理了几步，一个是在处理过程中如果出现商0的情况需要单独处理，再就是结果商就是0的情况，需要单独处理。另外一种方法就是，不够就商0，之...
2020-01-07 20:05:38
186
原创 [code] PTA 胡凡算法笔记 DAY050
文章目录题目 A1059 Prime Factors小结题目 A1059 Prime Factors题意输入n，输出其所有素因子，通过n= p1 ^ k1 * p2 ^ k2 * ....形式。其中pn为质因子，kn为该质因子出现次数，只有kn>1时才输出。思路核心点：构造素数表减轻时间复杂度；边计算边输出无需存储结果。需要考虑一下异常，n = 1的情况以及当质因子大于我...
2020-01-06 20:31:51
120
原创 [code] PTA 胡凡算法笔记 DAY049
文章目录题目 A1096 Consecutive Factors小结题目 A1096 Consecutive Factors题意输入数字N，求一段连续的整数序列，其乘积为N的因子。求最长的连续序列，输出长度及序列。如果存在多个序列长度相同的情况，输出最小的序列。思路首先需要确定思路，是采用构造连续整数乘积判断是否能被n整除的方式。然后确定范围，最大为sqrt(n)。然后再就是存...
2020-01-02 22:50:26
146
原创 [code] PTA 胡凡算法笔记 DAY048
文章目录题目 A1078 Hashing小结题目 A1078 Hashing题意输入hashtable的大小msize和数字序列的大小n，采用hash(key) = key % msize的hash策略和二次正向探测策略解决碰撞问题。将msize改为>=msize的最小素数，输出数字序列中每个数字在hashtable中的下标，从0开始，如果无法存储输出-。思路首先遍历求&...
2019-12-28 23:33:19
169
原创 [code] PTA 胡凡算法笔记 DAY047
文章目录题目 A1015 Reversible Primes小结题目 A1015 Reversible Primes题意输入数字N,D，如果数字N是素数并且按进制D反转后的数字也是素数，则输出Yes，否则输出No。当输入N为负数时，停止操作。思路首先肯定是要写一个判断是否为素数的函数，然后就是将数字按给定的进制进行反转然后求出其在10进制下的和。在进行进制转换时，很自然的求出来...
2019-12-27 22:55:05
166
原创 [code] PTA 胡凡算法笔记 DAY046
文章目录题目 B1013 数素数小结题目 B1013 数素数题意输入m,n，输出第m个素数到第 n个素数之间所有的素数(包含两端)。思路为了不要每次输出的时候去判断要输出哪个数，先利用初始化函数，初始化好第m到第n个素数的值，然后写好判断素数的函数和控制输出格式即可。Code in C++#include <cstdio>#include <cm...
2019-12-25 20:10:00
121
原创 [code] PTA 胡凡算法笔记 DAY045
文章目录题目 B1007 素数对猜想小结题目 B1007 素数对猜想题意给出一个数字n，在不超过这个范围内数相邻两个素数之间间隔为2的个数并输出。思路主要就是写一下判断素数的函数，然后在遍历范围的时候为了保证尽量少的判断是否为素数，使判断数为奇数（偶数除2外一定不是素数），然后遍历数数即可。Code in C++#include <cstdio>#in...
2019-12-24 20:51:26
164
原创 [code] PTA 胡凡算法笔记 DAY044
文章目录题目 A1088 Rational Arithmetic小结题目 A1088 Rational Arithmetic题意输入两个分数，输出进行加减乘除的结果，需要输出最简的方式（带分数或整数或真分数）。除法分母为0时，输出Inf。思路数据用结构体的方式存储，主要是对数据的化简和输出真分数函数的书写。然后这里还需要注意一下除法分母为0时需要单独处理。然后设计四则运算函数的...
2019-12-23 22:21:28
117
原创 [code] PTA 胡凡算法笔记 DAY043
文章目录题目 A1081 Rational Sum小结题目 A1081 Rational Sum题意输入n个分数，计算它们的和，输出化简后的形式，即带分数或整数或真分数。思路数据的存储方式采用结构体，每次输入的时候就将两个分数进行暴力加和之后化简。化简需要用到求最大公约数，并且需要将分母上的负数移到分子上。然后在最后输出的时候需要注意格式（是否会输出多余的空格）。注意：以下示...
2019-12-19 22:56:35
135
原创 [code] PTA 胡凡算法笔记 DAY042
文章目录题目 B1008 数组元素循环右移问题小结题目 B1008 数组元素循环右移问题题意输入n个数即需要循环右移的次数m，采用最少的移动次数，输出最后移动后的结果。思路因为循环右移后只要移动一位（排除不需要移动的情况外）所有数都不在自己原来的位置上了，所以最少的次数至少是移动n次。这里采用的方式就是从需要开始移动的位置开始，把数放在临时变量中，不断用移动后的数字填充。有可能...
2019-12-18 23:26:17
130
原创 [code] PTA 胡凡算法笔记 DAY041
文章目录题目 A1049 Counting Ones小结题目 A1049 Counting Ones题意给出一个数n，计算1~n过程中所有数字包含1的总个数。思路这一题暴力会超时，所以需要想想数学规律。最好想到的一个思路就是根据数字的位数去分，因为位数每增加一位不但包含低一位的所有情况还会有个倍数的情况。所以就可以扫描n的每一位来进行分类，主要分类就是当前位为==0, ==1,...
2019-12-17 20:52:25
192
原创 [code] PTA 胡凡算法笔记 DAY040
文章目录题目 A1008 Elevator小结题目 A1008 Elevator题意输入电梯需要达到的层数序列，电梯上行需要6s，下行4s，每层需要停5s，计算总共需要花费的时长并输出。思路这一题没有要求计算最小的时长，所以就是按照输入的序列根据上行还是下行处理就好，需要注意的是达到楼层之后都需要停5s即可。Code in C++#include <cstdi...
2019-12-16 23:34:09
160
原创 [code] PTA 胡凡算法笔记 DAY039
文章目录题目 B1049 数列的片段和小结题目 B1049 数列的片段和题意输入数字序列，求出可以截出的所有片段的数字和。思路主要就是找出每个数字出现的次数规律即可，这里第i个数字出现的次数为i*(n+1-i)。通过举例子的方式去分析其中的规律（像解数学题一样）。Code in C++#include <cstdio>const int MAXN =...
2019-12-15 19:48:49
119
原创 [code] PTA 胡凡算法笔记 DAY038
文章目录题目 B1019 数字黑洞小结题目 B1019 数字黑洞题意输入一个4位整数，不断执行以下规则直到为0或者为数字黑洞6174为止。对于整数n，先将n中各数字非递增排序后得到减数，然后递增排序得到被减数，两者相减。输出执行过程。思路很明显涉及到数字的排序，所以需要将整数进行拆分为整型数组，所以主要完成整型到数组的转换，以及数组到整型的转换即可。注意：当输入为6174...
2019-12-14 22:25:10
151
原创 [code] PTA 胡凡算法笔记 DAY037
文章目录题意 B1003 我要通过！小结题意 B1003 我要通过！题意看输入字符串是否满足如下规则，满足则输出YES，不满足输出NO。只包含P,A,T形如xPATx，其中x表示0个或多个A如果aPbTc满足，则aPbATca满足，其中a, b, c表示0个或多个A思路根据规则分析，输入的字符串只能包含P,A,T并且P和T只能包含一个。然后根据规则2 + 规则3可以演...
2019-12-14 00:37:42
178
原创 [code] PTA胡凡算法笔记 DAY036
文章目录题目 A1101 Quick Sort小结题目 A1101 Quick Sort题意输入序列，找到满足pivot性质的数（左边的数都小于它，右边的数都大于它），输出其个数及按从小到大顺序输出具体的数字。思路暴力会超时，所以我们需要从O(n^2)的时间复杂度往下降。根据给出的性质我们可以发现，在遍历的时候如果我们知道在这个点左边的最大值和右边的最大值就可以判断是否为piv...
2019-12-12 20:00:40
109
原创 [code] PTA 胡凡算法笔记 DAY035
文章目录题目 A1093 Count PAT's小结题目 A1093 Count PAT’s题意输入字符串，输出其中可以按顺序组成多少个PAT，最后输出模1000000007之后的结果。思路这题很明显暴力n接近10^5会超时。然后根据题目有几个特点，一个是PAT字母的顺序性，再就是字母可重复数，所以映射的方式也不可取。这里很明显因为顺序性就需要有定位的点，这里可以采取定位A的位...
2019-12-11 22:23:21
81
原创 [code] PTA 胡凡算法笔记 DAY034
文章目录题意 A1029 Median小结题意 A1029 Median题意输入两个序列，输出两个序列合并之后的中位数（偶数取前面）。思路这题其实和链表合并的思路很像，这里我是将输入的数据先进行排序，然后分别用i,j标识扫描到的位置，中位数的位置我是采用从1开始的所以是四舍五入的方式，然后循环，因为要考虑有一方过长的情况，所以循环完之后还需要处理。小结处有更简洁的实现方式。注...
2019-12-10 20:31:12
95
原创 [code] PTA 胡凡算法笔记 DAY033
文章目录题目 A1089小结题目 A1089题意输入一个序列和经过操作之后的一个序列，判断操作是插入排序还是归并排序，然后输出接下来再一次操作后的序列。思路核心就是需要写出插入排序和归并排序的模拟code，插入排序的一个特点就是排过序的部分是有序的，然后操作是拿出一个数之后找到它要在已排过序部分插入的位置，因为是数组需要挪动而且是递增排序所以直接从后向前扫描，在扫描过程可以挪动...
2019-12-09 22:11:06
86
原创 [code] PTA 胡凡算法笔记 DAY032
文章目录题目 A1048 Find Coins小结题目 A1048 Find Coins题意输入n个数字和一个数字m，给出v1+v2=m,v1<=v2，输出最小的v1和其对应的v2或者输出No Solution。思路很明显要使用二分搜索需要将序列进行排序，然后因为v1<=v2所以循环限制条件里面应该有<=m/2，并且不会再搜自己，所以开始的序号为i+1，因为输...
2019-12-08 20:08:15
102
原创 [code] PTA胡凡算法笔记 DAY 031
文章目录题目 A1044 Shopping in Mars小结题目 A1044 Shopping in Mars题意输出序列和最接近M的所有序列区间，区间从1开始。思路求序列和的方法一般都采用前缀和的方式去解决。这里前缀和的数组sum单调递增，抽象为二分查找其实就是要找sum[i-1] + m的下标，找不到的时候需要返回大于该值的第一个。所以二分查找right更新方式为 rig...
2019-12-05 22:46:08
112
原创 [code] PTA 胡凡算法笔记 DAY030
文章目录题目 A1085 Perfect Sequence题目 A1010 Radix小结题目 A1085 Perfect Sequence题意从输入的n个数中选出一个序列，使得其中max <= min * p并且序列长度最长。思路这里可以自己证明一下，先排完序之后顺序选择的策略是正确的。所以这里我们先排序，然后进行循环在i+1~n-1进行二分查找<= number...
2019-12-05 00:15:26
119
原创 [code] PTA 胡凡算法笔记 DAY029
文章目录题目A1038 Recover the Smallest Number小结题目A1038 Recover the Smallest Number题意根据输入的n个数字片段，组合成一个最小的数。思路这里一开始简单的想法是按字符串从小到大排序就好了，但是根据示例中321在32前面来看不是这样的。策略应该是s1 + s2 < s2 + s1则s1排在前面，可自行证明。然...
2019-12-03 20:48:57
85
原创 [code] PTA 胡凡算法笔记 DAY028
文章目录题目A1037 Magic Coupon题目A1067 Sort with Swap(0, i)小结题目A1037 Magic Coupon题意根据输入的奖券和产品情况，计算出能获取到的最大收益。每个只能选一次。当乘积是负数的时候需要倒贴钱。思路这里贪心思路很直观，将数字排序之后，正数部分从大的数开始相乘，乘到有一方或者都不为正数为止。对于负数部分就是从小开始乘，乘到不...
2019-12-02 21:44:15
134
原创 [code] PTA 胡凡算法笔记 DAY027
文章目录题目 A1033 To Fill or Not to Fill小结题目 A1033 To Fill or Not to Fill题意输入汽车油箱容量，需要行驶的距离，单位油量行驶的距离以及加油站个数n。然后随后输出n个加油站的信息，油价及据起点的距离。输出若能达到目的地的最小开销，若不能达到，输出最大行驶距离。思路这题其实贪心的目标就是，花最少的钱。所以每次加油的时候应...
2019-12-01 20:50:45
110
原创 [code] PTA 胡凡算法笔记 DAY026
文章目录题目 A1048 Find Coins题目 B1023 组个最小数题目 B1020 月饼小结题目 A1048 Find Coins题意给出需要的钱数和拥有的n个硬币，然后给出是否可以由两枚硬币支付。可以输出两枚硬币的面额，不能输出No Solution。思路用hashtable记录对应硬币面额的数量，这里数组大小需要设置为1000+，因为面额最大为500Code ...
2019-11-30 23:22:22
211
原创 [code] PTA 胡凡算法笔记 DAY025
文章目录题目 B1047 编程团体赛题目 A1041 Be Unique题目 A1050 String Subtraction题目 B1005 继续(3n+1)猜想小结题目 B1047 编程团体赛题意计算每个队伍的总分数，并输出得分最高的队伍编号及其分数。思路队伍编号连续大小固定，直接建立数组以下标与之对应，并且在输入的过程中就可以用一个变量去指示最大值得下标。（这里可以巧妙利...
2019-11-29 20:43:49
147
原创 [code] PTA 胡凡算法笔记 DAY024
文章目录题目 B1038 统计同成绩学生题目 B1039 到底买不买题目 B1042 统计字符题目 B1043 输出PATest小结题目 B1038 统计同成绩学生题意输入n个学生成绩，然后输入k个成绩进行查询，输出该成绩对应的学生人数。思路因为成绩是百分制整数，所以采用大小为101的数组下标与分数对应。输入时记录个数，查询时直接根据下标查询即可。Code in C++...
2019-11-28 21:36:20
126
原创 [code] PTA 胡凡算法笔记 DAY023
文章目录题目 A1084题目 B1033 旧键盘打字小结题目 A1084题意根据输入的两个字符串判断输出坏掉的键，不用重复输出，字母用大写输出。思路用原始串扫描输出串，不相同的字符即为坏掉的键，输出时需判断之前是否已记录过，这里我采取map的方法做映射。注意：可能扫描完了输出串，原始串后部分还未判断。Code in C++#include <cctype&g...
2019-11-27 22:32:56
117
原创 [code] PTA 胡凡算法笔记 DAY022
文章目录题目 A1095 Cars on Campus小结题目 A1095 Cars on Campus题意去除无效记录，然后根据查询时间点给出停车场停车数量及今天一天停车时间最长的车的编号及时长。思路主要需要实现几个功能：过滤无效信息，判断时间区间，获取每个车的停车时间然后取最大值。① 过滤无效信息。先将记录以id和时间排序，这样相同车牌号的记录会按时间顺序排在一起。就可以...
2019-11-26 20:58:08
116
原创 [code] PTA 胡凡算法笔记 DAY021
文章目录题目 A1083 List Grades题目 A1080 Graduate Admission小结题目 A1083 List Grades题意按成绩排序，然后按排序顺序输出在成绩范围内[grade1, grade2]的学生信息。不存在的输出NONE。思路这题和福布斯那题很像，主要就是写个cmp排序函数，然后识别成绩范围输出。这里需要注意的就是没有的情况，需要输出NONE...
2019-11-25 20:44:19
120
原创 [code] PTA胡凡算法笔记 DAY020
文章目录题目A1028 List Sorting题目A1055 The World's Richest题目A1075 PAT Judge小结题目A1028 List Sorting题意按输入C的数值决定排序方式，排序后输出。C = 1 按ID升序C = 2 按name从小到大，相同按ID升序。C = 3 按grade从小到大，相同按ID升序思路利用结构体存储数据，然后实现...
2019-11-24 22:35:59
126
原创 [code] PTA 胡凡算法笔记 DAY019
文章目录题目A1025 PAT Ranking小结题目A1025 PAT Ranking题意分别输入N个考室的各考生成绩，按总排名输出，排名相同按编号从小到大输出。输出信息为：registration_number final_rank location_number local_rank思路首先数据需要保存，所以按数据范围申请数组，然后根据输出格式可以确定结构体中的属性是哪些...
2019-11-23 21:45:01
132
原创 [code] PTA 胡凡算法笔记 DAY018
文章目录题目 A1016 Phone Bills小结题目 A1016 Phone Bills题意给出一天24小时每个小时的分钟计费，然后给出用户及其通话记录，判断其中有效的记录，计算产生费用，最终采用名字升序的顺序给出用户的月账单。思路主要要实现三个模块：① 将按题意记录排序（name, day, hour, minute递增）② 获取其中的有效记录（采用needPrint...
2019-11-22 22:53:04
114
原创 [code] PTA 胡凡算法笔记 DAY017
文章目录题目A1062 Talent and Virtue题目A1012 The Best Rank小结题目A1062 Talent and Virtue题意五类人，按高低排序，内部按总分，德分降序，ID升序排序。① 成绩有一门低于L的不参与。② 圣人，德才均>=H。③ 君子，德 >=H, 才 <H。④ 愚人，德才均<H，但德 > 才。⑤ 小人，...
2019-11-21 21:04:41
161
原创 [code] PTA胡凡算法笔记 DAY016
文章目录题目A1035 Password题目A1077 Kuchiguse题目A1082 Read Number in Chinese小结题目A1035 Password题意将输入密码中存在题目需要替换字符的字符替换，并且按要求根据有无替换等情况输出。思路建立替换表，然后利用结构体存储输入数据，设置bool属性表示是否修改。是否需要修改单独利用一个函数去判断，并且需要替换的时候...
2019-11-20 21:24:41
129
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人