1 ttu___

尚未进行身份认证

暂无相关简介

等级
TA的排名 9w+

1131 Subway Map (30分)

PAT30分最后一题做完了,????的青春结束了一般最后一题都是dijkstra做,加上之前做的几题刚好是dij找相同最短路径+dfs遍历确认所以第一次做这题的时候绕进去了(那样是24分,一个点WA一个点TLE)。然后参考了一下柳婼大神的思路,一次dfs解决,比想象的要轻松很多dfs过程中记录每个站点到起始点的最短距离。换乘次数的局部最优不能推导全局最优,但是距离是可以的。所以当当前到达该站点的距离大于已有的距离时返回。判断返回的时候不能把换乘次数考虑进去,因为距离才是第一标尺,换乘次数要到搜索到终点时

2020-05-13 23:05:30

1026 Table Tennis (30分)

终!于!过!了!PAT三十分题中行数最多的一道(瘫)或许1131Subway Map的行数也可与之一战(还没AC)今天调了三个来钟头吧可怕考试考到肯定很焦虑 毕竟三个钟头还是按着牛客用例调的==几个注意点:最后等待时间换成分钟,四舍五入如果人在21点前到,但是加上服务时间超过21点,还是要继续输出如果人在21点整及以后到,不算如果有两个人的开始服务时间相等,那么等待时间长的要靠后输出VIP用户的优先选择:VIP空闲桌中号码最小的>所有空闲桌中号码最小的如果playing time超过1

2020-05-12 17:18:57

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

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

1282. 用户分组

有 n 位用户参加活动,他们的 ID 从 0 到 n - 1,每位用户都 恰好 属于某一用户组。给你一个长度为 n 的数组 groupSizes,其中包含每位用户所处的用户组的大小,请你返回用户分组情况(存在的用户组以及每个组中用户的 ID)。你可以任何顺序返回解决方案,ID 的顺序也不受限制。此外,题目给出的数据保证至少存在一种解决方案。就还蛮迷惑的哦 分到贪心类里面官方题解也只有哈希没有贪心 暂时也想不出来贪心做法class Solution {public: vector<vec

2020-05-09 19:33:03

221. 最大正方形

在一个由 0 和 1 组成的二维矩阵内,找到只包含 1 的最大正方形,并返回其面积。暴力法:扫描每一个位置,更新该位置的对应的边长。从现有的最大边长+1开始比较,到到达matrix边界时结束。如果可能的最大边长小于等于现有边长就直接返回。最后返回边长*边长。class Solution {public: int side,wid,hei; void check(vector...

2020-05-08 03:09:43

面试题 02.05. 链表求和

给定两个用链表表示的整数,每个节点包含一个数位。这些数位是反向存放的,也就是个位排在链表首部。编写函数对这两个整数求和,并用链表形式返回结果。正向存放也是一样的,正向逆向来一遍就行了class Solution {public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { int len1=0,len...

2020-05-07 17:57:53

142. 环形链表 II

给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。感觉自己是铁five了vector搜索class Solution {public: ListNode *detectCycle(ListNode *head) { vector<ListNode*> lis; while(head!=NULL){ ...

2020-05-07 17:01:40

98. 验证二叉搜索树

今天的题,验证二叉搜索树。假设一个二叉搜索树具有如下特征:节点的左子树只包含小于当前节点的数。节点的右子树只包含大于当前节点的数。(也就是说[1,1]应该是false)所有左子树和右子树自身必须也是二叉搜索树。一个月前写过,现在的我揣摩不透当时的思维今天的:中序遍历之后验证序列是否递增,应该是比较自然的思路class Solution {public: vector&l...

2020-05-05 00:56:35

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

19. 删除链表的倒数第N个节点

给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。进阶:你能尝试使用一趟扫描实现吗?多趟扫描也不好实现吧难道要一个个从尾元素开始逼近倒数第123…k个元素吗按顺序push进vector,取前面的元素改一下next指针就完了,如果要删除的是头元素就直接返回next。不知道这道题为啥能成中等(也可能是这题目另有玄机我没看懂 )class Solution {public: ...

2020-05-03 04:16:57

42. 接雨水

PAT刷了就剩几题了,开始发一点力扣的解题记录。给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。之前好像看到字节面试题有这道最开始是想,每次都关注最底下那一行,计算完一行的雨水数后将这一行高度降低1,直到所有高度都为0或只有一个高度不为0。显然当高度很大时容易超时,用例最后一个不通过。int trap(vector<int>&...

2020-05-03 04:00:51

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

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

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

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

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

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

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

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

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。