3 dantahejichi

尚未进行身份认证

暂无相关简介

等级
TA的排名 40w+

pat甲级1107 并查集

并查集在findFather()函数中进行压缩路径,陷阱是这里只压缩该结点以上到根的路径,其以下的路径不压缩,这里不搞清楚会有三个测试点过不去#include <cstdio>#include <vector>#include <algorithm>using namespace std;int N;vector<int> hobby...

2020-02-16 15:36:14

pat甲级1066 平衡二叉树的实现

平衡二叉树的构建,做个笔记吧#include <cstdio>#include <algorithm>struct node{ int data, height; node *left, *right;};node* newNode(int e);int getHeight(node *a);void updateHeight(node *...

2020-02-15 18:00:39

pat甲级1064 完全二叉树静态实现

要求用给定的序列构造完全二叉搜索树,先构造完全二叉树,再往里填数使其成为二叉搜索树。vector的resize()函数不仅会改变容器大小,还会修改元素值#include <cstdio>#include <vector>#include <queue>#include <algorithm>using namespace std;i...

2020-02-15 14:51:59

pat甲级1086 二叉树遍历

push的次序就是先序序列,pop的次序就是中序序列,据此获取后序序列#include <cstdio>#include <cstring>#include <stack>#include <vector>using namespace std;stack<int> s;vector<int> pre_ord...

2020-02-14 15:21:48

pat甲级1043

以给出的序列为插入序列,构造树,然后对比。二叉搜索树的构造,先、后序遍历的递归写法。#include <cstdio>#include <vector>using namespace std;struct node{ int data; node *left, *right;};vector<int> pre;vector&...

2020-02-14 11:03:53

pat甲级1053

二叉树的静态实现。深度优先遍历,在每一个多叉点,逐个进入下层递归,return时要注意还原一步,到初始状态#include <cstdio>#include <vector>#include <algorithm>using namespace std;struct node{ int weight; vector<int&...

2020-02-12 14:34:20

pat甲级1020

考察后序、中序序列递归地还原二叉树,层次遍历。比较基础。#include <cstdio>#include <queue>using namespace std;struct node{ int data; node *left, *right;};int N;int post[30], in[30];//根据后序、中序序列构造二叉树...

2020-02-11 17:55:30

pat甲级1091

用一个三维数组模拟空间直角坐标系,接收输入文件。再逐个点地访问,如果是未入过队的1,那么以它为起点进行广度优先遍历,统计该块中所有未入过队的1的数目。#include <cstdio>#include <queue>using namespace std;const int maxN = 128;const int maxM = 1286;const int...

2020-02-11 15:33:34

pat甲级1103

有技巧地枚举所有选数的可能,形成二叉树,再通过递归实现深度优先遍历,每次到达叶子节点就进行一次结果比较,确定是否更新最终结果。算法笔记上写的很好,一个数只能选一次的情况,与一个数可以选多次,稍微更改即可。备选数的最大值为P次根号下N,从最大值开始选会更快。另外就是预处理的技巧,遍历时涉及到重复计算一个数的P次方,提前用一个数组保存下来,可以节省时间。#include <cstdio>...

2020-02-10 21:50:00

pat甲级1063

练习使用set_intersection()和set_union()求交集和并集,代码会超时,只是练习而已#include <cstdio>#include <set>#include <algorithm>using namespace std;int main(){ int N, K; scanf("%d", &N);...

2020-02-03 17:46:32

pat甲级1039

办法一:各种容器直接上,代码量小,但会超时。办法二:把名字hash,只用数组。#include <iostream>#include <map>#include <vector>#include <string>#include <algorithm>using namespace std;int main(){ ...

2020-02-03 15:52:42

pat甲级1069

思路:核心是找到数值与字符串互相转化的方法,还要考虑高位补0。cstdio中天然有一个利器,那就是sprintf()和sscanf()两个函数。数值有4位,转换时,字符数组大小要定为5,因为要接收最后的 ‘\0’,否则提交后会出现运行时错误。#include <cstdio>#include <algorithm>int num_to_dec(int a);int...

2020-02-01 17:35:51

pat甲级1101

思路:主元的特征是大于左侧元素,小于右侧元素。方法一,需三次遍历。从左到右遍历一次,得到各位置左侧最大数的数组,再从右到左遍历得到各位置右侧最小数的数组。最后遍历判断是否是主元。方法二,需一次遍历。先把序列sort得到各元素在有序序列中的最终位置,再从左到右遍历,若该元素在最终位置,且大于其左侧所有元素,那么他就可以是主元。代码如下:#include <cstdio>#incl...

2020-02-01 16:12:12

pat甲级1093

思路:对特定位置的A,PAT组合数量等于其前面P的数量乘以其后面T的数量。对所有的A计算一遍求和即得答案。只需要对字符串遍历一遍,且不需要存储该字符串。逐个字符地读取输入文件,每读到一个字母计算一次该位之前(包括其本身)分别有多少个P,T字母,如果是A就记录它的位置。#include <cstdio>const int max_n = 100001;int main(){...

2020-01-31 21:31:38

pat甲级1089

以趟为单位分割排序过程,每进行一趟排序后就和结果对比一次。涉及到插入排序,归并排序非递归的写法:#include <cstdio>#include <algorithm>bool isSame(int a[], int b[], int n);void printArray(int a[], int n);//一趟插入排序void insertionSort...

2020-01-31 19:48:29

pat甲级1044

手写二分查找:#include <cstdio>#include <climits>int main(){ int N, M; scanf("%d%d", &N, &M); int diamonds[N+1], ends[N+1], pays[N+1], sum[N+1]; sum[0] = 0; for(in...

2020-01-30 22:49:58

pat甲级1085

代码:#include <cstdio>#include <algorithm>using namespace std;int main(){ int N, p; scanf("%d%d", &N, &p); int nums[N]; for(int i=0; i<N; i++) scanf("%d", &a...

2020-01-30 15:16:25

pat甲级1038

代码:#include <iostream>#include <string>#include <algorithm>using namespace std;bool cmp(string, string);int main(){ int N; cin>>N; string s[N]; for(int...

2020-01-30 13:25:51

用cin输入string的问题

问题来自pat乙级1033,代码如下#include <iostream>#include <string>#include <cctype>using namespace std;int main(){ string broken_keys, sentence; cin>>broken_keys>>sent...

2020-01-21 16:20:09

改变cin分隔符的简单方法

网上找了一些方法都比较复杂,可以取巧,把你想指定的分隔符接收下来,但不使用。#include <iostream>using namespace std;int main(){ int a, b, c; char comma; cin>>a>>comma>>b>>comma>>c; cout<<...

2020-01-19 17:16:40

查看更多

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