- 博客(127)
- 收藏
- 关注
RSS订阅原创 UVA - 12563 Jin Ge Jin Qu hao
很久没发做题记录了，明天有个机试今天临阵磨枪……某实验室好像非常钟爱背包，面试和机试都常考。紫书的背包题只有这一道，随便做做8总时间t其实不会超过180*50（不包括劲歌金曲）不用考虑自选歌总时间等于t的情况，因为所有歌都比劲歌金曲短，也就是说，最优解的最后一首歌总是劲歌金曲。所以时间限制到t-1就行。用-1来标记在那个时间点不能唱歌。#include<bits/stdc++.h>using namespace std;int main(){ int casenum;
2020-09-16 21:08:55
134
原创 UVA - 297 Quadtrees
夏令营暂告一段落 目前0offer状态继续随心刷几题吧#include <bits/stdc++.h>using namespace std;bool g[1124];void buildTree(int level,int base){ char c; scanf("%c",&c); if(c=='p'){ int perbloc=pow(2,level-2); buildTree(level-2,base);
2020-07-28 22:50:54
98
原创 UVA - 514 Rails
okk 买了紫书 没事刷一刷UVaUVa打开挺慢的 这里用的是virtual judge 感觉还好记得PAT甲级里面有道跟这个意思差不多的 模拟一下进出栈顺序 碰到和栈顶数字一样的就出栈 最后栈空就是对的顺序 不空就是不对#include <bits/stdc++.h>using namespace std;int main(){ int n; while(1){ cin>>n; while(n!=0){
2020-06-15 23:52:41
140
原创 1009 Product of Polynomials (25分)
最后一题了！一直拖着没做是因为之前一直看不懂题目……数个数和输出的时候要判断非零项，不能判断大于0因为可能有负数系数。#include <bits/stdc++.h>using namespace std;vector<double> a(1001,0.0),b(1001,0.0),c(2001,0.0);int main(){ int n; cin>>n; for(int i=0;i<n;i++){ int ex
2020-06-15 01:28:00
116
原创 1033 To Fill or Not to Fill (25分)
大概想法是找在可达范围内第一个油价比当前油价低的站点开到那里 更新参数如果范围内没有油价更低的站点把油加满 并把参数更新到范围内油价最低的站点第二个点卡了好久 发现是要加一个对起始点是否为0的判断#include <bits/stdc++.h>using namespace std;struct Node{ double price,distance; bool friend operator <(Node a,Node b){
2020-06-15 01:05:41
110
原创 1015 Reversible Primes (20分)
决定要考这次pat了 就把剩下的都刷刷完吧因为进制在2-10之间 所以转换函数就自己写了 而且atoi strtol那些参数大概率我记不住另外1不是素数#include <bits/stdc++.h>using namespace std;bool isPrime(long long num){ if(num==2)return true; else if(num<2)return false; long long sq=sqrt(num)+1;
2020-06-14 00:19:38
72
原创 1131 Subway Map (30分)
PAT30分最后一题做完了，????的青春结束了一般最后一题都是dijkstra做，加上之前做的几题刚好是dij找相同最短路径+dfs遍历确认所以第一次做这题的时候绕进去了（那样是24分，一个点WA一个点TLE）。然后参考了一下柳婼大神的思路，一次dfs解决，比想象的要轻松很多dfs过程中记录每个站点到起始点的最短距离。换乘次数的局部最优不能推导全局最优，但是距离是可以的。所以当当前到达该站点的距离大于已有的距离时返回。判断返回的时候不能把换乘次数考虑进去，因为距离才是第一标尺，换乘次数要到搜索到终点时
2020-05-13 23:05:30
146
原创 1026 Table Tennis (30分)
终！于！过！了！PAT三十分题中行数最多的一道（瘫）或许1131Subway Map的行数也可与之一战（还没AC）今天调了三个来钟头吧可怕考试考到肯定很焦虑 毕竟三个钟头还是按着牛客用例调的==几个注意点：最后等待时间换成分钟，四舍五入如果人在21点前到，但是加上服务时间超过21点，还是要继续输出如果人在21点整及以后到，不算如果有两个人的开始服务时间相等，那么等待时间长的要靠后输出VIP用户的优先选择：VIP空闲桌中号码最小的>所有空闲桌中号码最小的如果playing time超过1
2020-05-12 17:18:57
139
原创 1108 Finding Average (20分)
一个拖了蛮久的题……是之前一直没发现用scanf读string有问题的时候写的，找了很久是不是输出不对，后来发现应该是resize之后string的end就应该不是有效位数的结尾了。反正以后都记着只用cin读string了今天力扣一直没刷新每日一题……#include <bits/stdc++.h>using namespace std;int n;bool isint(string str){ if(str[0]=='-') str.erase(0,1); auto
2020-05-11 01:55:55
89
原创 236. 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”PAT上都是给遍历序列推LCA，所以其实用指针做还是第一次记录父节点，找到根节点上第一个重复的节点。class Solution {public: unordered_map<TreeNode*,TreeNode*> mp; vo
2020-05-10 00:50:27
93
原创 1282. 用户分组
有 n 位用户参加活动，他们的 ID 从 0 到 n - 1，每位用户都 恰好 属于某一用户组。给你一个长度为 n 的数组 groupSizes，其中包含每位用户所处的用户组的大小，请你返回用户分组情况（存在的用户组以及每个组中用户的 ID）。你可以任何顺序返回解决方案，ID 的顺序也不受限制。此外，题目给出的数据保证至少存在一种解决方案。就还蛮迷惑的哦 分到贪心类里面官方题解也只有哈希没有贪心 暂时也想不出来贪心做法class Solution {public: vector<vec
2020-05-09 19:33:03
123
原创 221. 最大正方形
在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。暴力法：扫描每一个位置，更新该位置的对应的边长。从现有的最大边长+1开始比较，到到达matrix边界时结束。如果可能的最大边长小于等于现有边长就直接返回。最后返回边长*边长。class Solution {public: int side,wid,hei; void check(vector...
2020-05-08 03:09:43
114
原创 面试题 02.05. 链表求和
给定两个用链表表示的整数，每个节点包含一个数位。这些数位是反向存放的，也就是个位排在链表首部。编写函数对这两个整数求和，并用链表形式返回结果。正向存放也是一样的，正向逆向来一遍就行了class Solution {public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { int len1=0,len...
2020-05-07 17:57:53
77
原创 142. 环形链表 II
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。感觉自己是铁five了vector搜索class Solution {public: ListNode *detectCycle(ListNode *head) { vector<ListNode*> lis; while(head!=NULL){ ...
2020-05-07 17:01:40
72
原创 98. 验证二叉搜索树
今天的题，验证二叉搜索树。假设一个二叉搜索树具有如下特征：节点的左子树只包含小于当前节点的数。节点的右子树只包含大于当前节点的数。（也就是说[1,1]应该是false）所有左子树和右子树自身必须也是二叉搜索树。一个月前写过，现在的我揣摩不透当时的思维今天的：中序遍历之后验证序列是否递增，应该是比较自然的思路class Solution {public: vector&l...
2020-05-05 00:56:35
54
原创 34. 在排序数组中查找元素的第一个和最后一个位置
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。你的算法时间复杂度必须是 O(log n) 级别。如果数组中不存在目标值，返回 [-1, -1]。就……二分class Solution {public: int findleft(int l,int r,int target,vector<int>&am...
2020-05-03 04:33:44
123
原创 19. 删除链表的倒数第N个节点
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。进阶：你能尝试使用一趟扫描实现吗？多趟扫描也不好实现吧难道要一个个从尾元素开始逼近倒数第123…k个元素吗按顺序push进vector，取前面的元素改一下next指针就完了，如果要删除的是头元素就直接返回next。不知道这道题为啥能成中等（也可能是这题目另有玄机我没看懂 ）class Solution {public: ...
2020-05-03 04:16:57
95
原创 42. 接雨水
PAT刷了就剩几题了，开始发一点力扣的解题记录。给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。之前好像看到字节面试题有这道最开始是想，每次都关注最底下那一行，计算完一行的雨水数后将这一行高度降低1，直到所有高度都为0或只有一个高度不为0。显然当高度很大时容易超时，用例最后一个不通过。int trap(vector<int>&...
2020-05-03 04:00:51
167
原创 1122 Hamiltonian Cycle (25分)
Hamiltonian Cycle：首尾相连，经过所有元素，且必须是可行路径。依次判断。有时候过不过还挺玄妙的，经常是一些不涉及逻辑的小改动……#include <bits/stdc++.h>#define INF 9999999using namespace std;const int maxn=210;int m,n,query;//int path[maxn];这里...
2020-05-02 19:17:44
125
原创 1112 Stucked Keyboard (20分)
一个字符重复m次将被视为坏键。如果一个字符被扫描到k次且k整除m，那k就可判定为坏键。但当某字符重复出现k1(k1%m==0)和k2次(k2%m!=0)时，该字符将不视作坏键。注意最后要根据扫描的顺序输出坏的键#include <bits/stdc++.h>using namespace std;int main(){ int n1; cin>>n...
2020-05-02 03:30:08
114
原创 1124 Raffle for Weibo Followers (20分)
第一行给出三个正整数M（≤1000）、N和S，分别是转发总数、跳过的赢家数和第一个赢家的索引（索引从1开始）如果有重复就跳过#include <bits/stdc++.h>using namespace std;int main(){ int n1,n2,n3; cin>>n1>>n2>>n3; vector<...
2020-05-02 02:31:40
133
原创 1137 Final Grading (25分)
因为cin有时候会超时所以总是倾向于用scanf，但是string要先resize才能用scanf，导致用在map里的时候可能会导致查找错误即使resize的值都一样，所以string还是cin比较保险#include <bits/stdc++.h>using namespace std;int p,m,n;struct Node{ string name; i...
2020-05-02 02:30:39
98
原创 1140 Look-and-say Sequence (20分)
11223344->12223242（2个1 2个2 2个3 2个4）#include <bits/stdc++.h>using namespace std;int main(){ char c; int k; cin>>c>>k; string s; s.push_back(c); for(int i...
2020-05-02 01:49:45
63
原创 1153 Decode Registration Card of PAT (25分)
折腾了一会，把每个查询分成函数调用错了，写在主函数里面又AC了……我感觉我写的都一样#include <bits/stdc++.h>using namespace std;int m,n,query;struct Node{ string name; int val; friend bool operator <(Node a,Node b){ ...
2020-05-02 00:51:30
136
原创 1128 N Queens Puzzle (20分)
n皇后问题里要求每行、每列、每条对角线上不能有一个以上的皇后。用set来看有没有重复的数。这里只测试了从左上到右下的对角线#include <bits/stdc++.h>using namespace std;int main(){ int n1,n2; scanf("%d",&n1); for(int i=0;i<n1;i++){ ...
2020-05-02 00:08:40
71
原创 1051 Pop Sequence (25分)
模拟一下出栈顺序就行。1~N顺序进栈，和序列匹配上就出栈。如果过程中栈大小大于给定大小就退出循环。循环结束栈为空就是yes。#include <bits/stdc++.h>using namespace std;int main(){ int sz,range,num; scanf("%d%d%d",&sz,&range,&num);...
2020-05-01 23:05:14
81
原创 1055 The World's Richest (25分)
老排序题了，但是这里排序应在读取之后，如果在查询时再对每个排序有一个点会超时。#include <bits/stdc++.h>using namespace std;struct Node{ string name; int age,money; bool friend operator <(Node a,Node b){ if(a...
2020-05-01 22:50:13
59
原创 1077 Kuchiguse (20分)
就从最后开始比较，注意要用getline，而且要把第一个数字后面的回车读掉。#include <bits/stdc++.h>using namespace std;int main(){ string s; int len; scanf("%d\n",&len); vector<string> vec(len); i...
2020-05-01 22:15:58
195
原创 1073 Scientific Notation (20分)
三个情况，前面补0，后面补0，中间移小数点#include <bits/stdc++.h>using namespace std;int main(){ string s; cin>>s; bool neg=false; int b; auto posE=s.find('E'); string s1=s.substr...
2020-05-01 22:04:37
77
原创 1067 Sort with Swap(0, i) (25分)
要求只能将0和其它元素交换，达到排序的目的。将初始序列第i个元素和目标序列第i个元素视作有联系的，因为经过数次交换后目标序列第i个元素必将到第i个的位置上。这里用并查集做，最后求环的个数。//初始序列3 5 7 2 6 4 9 0 8 1//目标序列0 1 2 3 4 5 6 7 8 9这里有三个环：0-3-2-7-0、5-4-6-9-1-5和8。这里8本来就在目标位置，所以不计入最...
2020-05-01 20:12:35
99
原创 1084 Broken Keyboard (20分)
要求是按照检测的顺序输出，因此输出顺序应当和第一条字符串中字符出现的顺序一致#include <bits/stdc++.h>using namespace std;int main(){ string s1,s2; cin>>s1>>s2; string res; map<char,bool> mp; ...
2020-04-29 22:45:48
76
原创 1144 The Missing Number (20分)
如果序列最小的正数是2，那应该输出1。简单版，排序然后找。#include <bits/stdc++.h>using namespace std;int main(){ int num; cin>>num; vector<int> vec; for(int i=0;i<num;i++){ int n...
2020-04-29 22:26:29
105
原创 1079 Total Sales of Supply Chain (25分)
供应商系列题，father数组依旧超。遍历到每个子节点，求出每个零售商所有的商品销售价格。#include <bits/stdc++.h>using namespace std;int main(){ int num; double rootprice,rate; cin>>num>>rootprice>>rate;...
2020-04-29 21:58:55
72
原创 1106 Lowest Price in Supply Chain (25分)
刚开始想存father数组，然后第6点超时，所以改了bfs输出一定要用double，float就错，还挺奇怪#include <bits/stdc++.h>using namespace std;int main(){ int num; double rootprice,rate; cin>>num>>rootprice>...
2020-04-29 21:38:56
91
原创 1075 PAT Judge (25分)
如果成绩是-1，输出的时候要输出0而不是-1。（在他能被输出的时候）如果没提交过输出-。要注意一下，考题的编号是从1开始的，所以数组要开够，要注意下标的取值。#include <bits/stdc++.h>using namespace std;struct Node{ int id,total=0,cnt=0,rk; int grade[6]; bo...
2020-04-29 20:36:11
94
原创 1074 Reversing Linked List (25分)
按顺序读进来然后reverse，输出的时候输出下一个条目的地址。PAT链表题特别爱搞的一个case是可能会有那么几项是多的，不在待排序的链里。所以要重新计算链表长度，不能直接用给的项数。#include <bits/stdc++.h>using namespace std;struct Node{ int add,val,next;}node[100010];ve...
2020-04-29 19:39:49
112
原创 1089 Insert or Merge (25分)
力扣上有题是判断堆排序还是插排，都是要写两个排序算法然后比较序列。偷懒做法是可以不直接写具体如何插入如何归并，只要每次定好排序的边界然后sort就行。但是如果给的第二个中间序列和初始序列完全相同的话，应该视作归并排序。题目的意思是插入排序的第一步是给前两个排序#include <bits/stdc++.h>#include <bits/stdc++.h>using...
2020-04-29 19:12:26
144
原创 1083 List Grades (25分)
PAT特别多的成绩分类排序，输出在给定范围内的学生名字和id。#include <bits/stdc++.h>using namespace std;struct Node{ string name,id; int grade; bool friend operator <(Node a,Node b){ return a.gr...
2020-04-29 18:18:20
76
原创 1100 Mars Numbers (20分)
进制转换和字符串13->tam(不是tam tret)，余数为0时后面的tret不加。#include <bits/stdc++.h>using namespace std;vector<string> s1={"","tam", "hel", "maa", "huh", "tou", "kes", "hei", "elo", "syy", "lok", "...
2020-04-29 14:11:14
62
原创 927. 三等分
算1的个数，和最后一个1的位置（算1后面应该跟几个0），然后从头开始分割，然后比较是不是每个部分都一样。class Solution {public: vector<int> threeEqualParts(vector<int>& A) { vector<int> res={-1,-1}; int count...
2020-04-23 11:20:40
91
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人