PAT（甲级）2018年冬季考试 7-4 Heap Paths(非递归与递归解法)
非递归解法
1. 前置知识：完全二叉树的属性
1.1 从1开始存储，子节点的下标除以二得到的是父节点的下标
1.2 数组的存放顺序刚好是层序遍历顺序
1.3 从1开始存储，节点的下标i和结点总数n如果满足 i*2>n说明该结点是叶子结点
2. 思路：
2.1 从最右边的叶子结点开始，对每个叶子结点找到祖先，并把祖先插入向量的首个位置，直到根节点停止
最右边的叶子节点如何找？未必是下标最大的那个，是层数(使用getLayer函数)更小且下标最大的那个(体现在排序函数cmp中)
2.2 判断首个序列是非递增(最大堆)还是非递减，对于后面的每个序列都判断(使用judgeType函数)，看是否和首个序列的结论一致，如果有一个不一致，说明这棵树不是堆
3. 纠偏
按照以上思路提交代码上去，得分26/30，这才反应过来自己的判断是什么堆还一个个序列去判断，也太被带沟里了。改成直接写一个判断最大堆、一个判断最小堆的函数，把整棵树当作一个整体来判断，还避免了遇到等号算谁的这种尴尬问题。于是AC。
代码
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<map>
#include<cstring>
#include<set>using namespace std;const int maxn = 1010;
const int SUP = 100000010;int n,A[maxn];struct Node{vector<int> preVi;int layer;int idx;
};Node node[maxn];bool cmp(Node a,Node b){return a.layer!=b.layer?a.layer<b.layer:a.idx>b.idx;
}int getLayer(int idx){int k;for(k=0;k<10;k++){if(idx>pow(2,k)-1&&idx<=pow(2,k+1)-1)break;}return k;
}bool isMaxHeap(){for(int i=1;i*2<=n;i++){//对于每一个非叶子结点，判断其和左右节点的大小关系 if(A[i]<A[i*2])return false;if(i*2+1<=n&&A[i]<A[i*2+1])return false;}return true;
}bool isMinHeap(){for(int i=1;i*2<=n;i++){if(A[i]>A[i*2])return false;if(i*2+1<=n&&A[i]>A[i*2+1])return false;}return true;
} int main(){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&A[i]);}int viNum = 0;//向量的个数 for(int i=n;2*i>n;i--){vector<int> vi;for(int j=i;j>=1;j/=2){vi.insert(vi.begin(),A[j]);}node[viNum].preVi = vi;node[viNum].idx = i;node[viNum].layer = getLayer(i);viNum++;}sort(node,node+viNum,cmp);for(int i=0;i<viNum;i++){for(int j=0;j<node[i].preVi.size();j++){printf("%d",node[i].preVi[j]);if(j!=node[i].preVi.size()-1)printf(" ");}printf("\n"); }if(isMaxHeap())printf("Max Heap\n");else if(isMinHeap())printf("Min Heap\n");else printf("Not Heap\n");return 0;
}递归解法
DFS解法我参考了柳婼仙女的，她说这个是一个先序的镜像问题，也就是先序遍历是父，左子，右子，而这题是要父，右子，左子。
递归的边界是当前结点已经是叶子结点，即满足下标*2>n（这里无需判断右结点了） 。
另外一个收获是，对于最大最小堆的判断，可以用一种否定法的思想，先假设最大和最小堆都成立，对于每一个有父节点的结点，判断其和父节点的关系。代码简洁很多。
AC代码
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<queue>
#include<string>
#include<map>
#include<vector>
#include<set>using namespace std;const int maxn = 1001;int n;
int A[maxn];
vector<int> vi;void DFS(int root){if(root*2>n){if(root<=n){for(int i=0;i<vi.size();i++){printf("%d%s",vi[i],i==vi.size()-1?"\n":" "); }}}else{vi.push_back(A[root*2+1]);DFS(root*2+1);vi.pop_back();vi.push_back(A[root*2]);DFS(root*2);vi.pop_back(); }
}int main(){cin>>n;for(int i=1;i<=n;i++){cin>>A[i];}bool isMaxHeap = true,isMinHeap = true;vi.push_back(A[1]);DFS(1);for(int i=2;i<=n;i++){if(A[i]>A[i/2])isMaxHeap = false;if(A[i]<A[i/2])isMinHeap = false;}if(isMaxHeap)printf("Max Heap\n");else{if(isMinHeap)printf("Min Heap\n");else printf("Not Heap\n");}return 0;
}相关文章：
Request Connection: Remote Server @ 192.229.145.200:80
录制Loadrunner脚本时，提示：Request Connection: Remote Server 192.229.145.200:80 NOT INTERCEPTED!(REASON: User requested to IGNORE connection)；解决方法：1. 打开IE里的Internet选项，单击连接选项卡。单击最…
抽象工厂与工厂模式例子
NativeFactory。java package com;//定义 人有杀日本人 和 杀美国人两个方法interface NativePerson{ public void killAmeria(); public void killJapan();}//中国人实现了人的接口 class NativeChinese implements NativePerson{ //中国人杀美国人 public void killAmeria() …
《疯狂Java讲义》学习笔记（十）异常处理
2019独角兽企业重金招聘Python工程师标准>>> 0、Java的异常体系 1、异常概述 异常机制已经成为判断一门编程语言是否成熟的标准，目前主流的编程语言都提供了成熟的异常机制，增加了异常处理机制后的程序有更好的容错性，更加健壮 Ja…
PAT（甲级）2018年冬季考试 7-1 Google Recruitment
1. 本题是 substrsscanf的绝佳实践。 2. 判断素数使用i*i<n与i<(int)sqrt(0.1*x)的区别是前者可能再n接近10的9次方时溢出，但本题不会。 3. 尽管把字符串转变成了整数，但输出时仍旧输出字符串，如果选择打印整数，会遇到%0K…
MySQL 的“root”用户修改密码
MySQL 的“root”用户默认状态是没有密码的，所以在 PHP 中您可以使用 mysql_connect("localhost","root","") 来连接 MySQL 服务器；如果您想为 MySQL 中的“root”用户设置密码，请在控制台中使用“mysqladmin”…
游戏AI之初步介绍（0）
目录 游戏AI是什么？游戏AI和理论AI智能的假象（更新）游戏AI和机器学习介绍一些游戏AI4X游戏AI《求生之路》系列角色扮演/沙盒游戏中的NPC游戏AI 需要学些什么？自治智能体群体智能感知状态机（重要）行为树&…
Google Adsense实用防踢技巧总结
我们都知道，对个人草根站长来说，Google AdSense是网站收入的主要来源之一，我在这里介绍一些常用的技巧。 希望通过这些技巧能够增加大家的Google AdSense收入，并防止自己的帐号被删除。大家喜欢的话就顶下吧！ 广告的位…
PAT（甲级）2018年冬季考试 7-3 Vertex Coloring
1. 起先我的思路是，对于每一种方案，把相同颜色的下标放到一个集合，对于每一个集合判断里面的元素互相之间是否有着邻接关系。有一个用例超时，20/25。 2. 转变思路，对于每一种方案，遍历邻接关系，…
蚂蚁金服×西安银行 | 西安银行手机银行App的智能升级之路
小蚂蚁说：当前，数字化信号已经逐渐深入到社会的每个角落，影响着用户的心智和行为，来到数字化时代门口的银行，需要注意到数字化信号。西安银行通过引入蚂蚁金服移动开发平台mPaaS，对手机银行进行架构升级&am…
（四十七）Quartz2D引擎初步
Quartz2D是跨平台的，同时支持iOS与Mac。 支持圆型裁剪，可以实现圆形头像等功能，也支持手势解锁、折线图等的制作。 对于复杂的UI界面，还可以通过Quartz2D将控件内部的结构画出来，可用于自定义控件。 实际上iOS大部分控…
PAT（甲级）2018年冬季考试 7-2 Decode Registration Card of PAT
目录 体会 代码(非满分) 改进 AC代码 体会 这题主要是考察对STL中string,map,vector的应用以及自定义sort()应用。 类型1和2的处理很容易。 类型3要求对于指定date，按照每个考场进行分类，记录不同考场的人数，按照人数非升序ÿ…
DOS、Mac 和 Unix 文件格式+ UltraEdit使用
文件格式 区分DOS、Mac 和 Unix分别对应三种系统从文件编码的方式来看，文件可分为ASCII码文件和二进制码文件两种文件模式 区分ASCII模式和Binary模式 通常由系统决定，大多数Linux/UNIX系统只有两种模式：文本模式和二进制模式。文本传输器使用…
灰度图像--图像分割 Scharr算子
学习DIP第46天 转载请标明本文出处：http://blog.csdn.net/tonyshengtan ，出于尊重文章作者的劳动，转载请标明出处！文章代码已托管，欢迎共同开发： https://github.com/Tony-Tan/DIPpro 更多图像处理机器学习…
FileUpload生成图片水印，文字水印(转载)
/** <summary>/// 生成缩略图/// </summary>/// <param name"originalImagePath">源图路径（物理路径）</param>/// <param name"thumbnailPath">缩略图路径（物理路径）</para…
1151 LCA in a Binary Tree (含求LCA的通法)
目录 解法一思路 结果 解法一改进 解法一改进结果 解法二思路 解法一代码 解法一改进代码 解法二代码(AC) 解法一思路 1. 根据先序和中序建树 2. 对树进行深度优先遍历，找到每一个结点的父节点(注意：由于值的范围是int，直接用可…
cf 414B Mashmokh and ACM 动态规划
题目链接：http://codeforces.com/problemset/problem/414/B dp[i][j]表示长度为i、最后一个数字为j的合法序列总数 dp[1][1...2000]都是1 后面用dp[i-1][j] 去更新 dp[i][j*t] (1 < j*t < 2000) 即用因子去更新它的倍数 表面上看是2000^3的复杂度会爆 其实不用…
解决：angularjs radio默认选中失效问题
添加ng-model后checked"checked"失效，可见angularjs也不好，会失效html标准属性解决：添加ng-checked"1"<input type"radio" ng-model"sel_course" value"1" ng-checked"1" /…
在ireport报错 报 jdk5找不到的解决办法
在ireport安装目录下， etc目录下有ireport.conf， 其中有jkdhome设置， 把前面的#（注释）去掉， 换成自己的jdk目录就行 双引号不要去掉 jdk地址放在双引号之间 比如 改成 jdkhome"G:/ACD/jdk1.5.0&quo…
如何通过中序和层序序列建立二叉树
有这样一棵二叉树 根据节点个数 9 层序遍历结果 15 23 8 16 2 32 28 7 11 中序遍历结果 16 23 7 32 11 2 28 15 8 预期先序输出 15 23 16 2 32 7 11 28 8 运行结果 这个过程和建立二叉查找树(BST)的过程是非常相像的，将laSq[laIndex]插入到根为root的子树中&a…
BZOJ 3573 米特运输
Description 米特是D星球上一种非常神秘的物质，蕴含着巨大的能量。在以米特为主要能源的D星上，这种米特能源的运输和储存一直是一个大问题。 D星上有N个城市，我们将其顺序编号为1到N，1号城市为首都。这N个城市由N-1条单向高速通…
[学习笔记]最小割之最小点权覆盖最大点权独立集
最小点权覆盖 给出一个二分图，每个点有一个非负点权要求选出一些点构成一个覆盖，问点权最小是多少 建模： S到左部点，容量为点权 右部点到T，容量为点权 左部点到右部点的边，容量inf 求最小割即可。 证明&…
10分钟学会Google Map API
http://space.itpub.net/14734354/viewspace-374828 前几天玩了玩Google的Map API，感觉还不错，很简单。但凡有过任何编程经验的同学，看完以下的教程，都可以在10分钟内掌握它的主要功能。另外我还做了个简单的小例子，有…
1143 Lowest Common Ancestor(建树与不建两种思路)
目录 解法一 解法二 解法一 这题可以不建树，直接利用BST的性质：左子树<根节点<右子树，对先序序列进行遍历，如果有某个元素大于等于u,v中较小的且小于等于u,v中较大的，则可能是根节点。 这题数据弱࿰…
UIScrollView
UIScrollView（包括它的子类 UITableView 和 UICollectionView）是 iOS 开发中最常用也是最有意思的 UI 组件，大部分 App 的核心界面都是基于三者之一或三者的组合实现。UIScrollView 是 UIKit 中为数不多能响应滑动手势的 view，相比…
MySQL练习题：常用函数
1. 以首字母大写，其他字母小写的方式显示所有员工的姓名2. 将员工的职位用小写字母显示3. 显示员工姓名超过5个字符的员工名4. 用#来填充员工职位job的结尾处，按10个字符长度输出。5. 去除字符串 hello world 两边的空格，并将单词间的空格改…
我的WINCE4.2历程（10）
2010-04-02 今天的主要工作： 1）RTC4513驱动调试，又做了一些尝试（检查GPIO口的第二功能设置是否正常），结果还是不正常，FAINT。 2）回顾了截止到目前取得的进展： aÿ…
1069 The Black Hole of Numbers
注意两点： 1. 不足4位要补足，不仅仅是一开始要考虑，每次得到一个差值，都要考虑 2. 到0也会停下，不仅仅是一开始可能发生，也可能是过程中的某一个差值 另： vector<int> 是可以作为函数…
详解Asp.net MVC DropDownLists
来自网络： Asp.net MVC中的DropDownLists貌似会让一开始从Asp.net Forms转过来的程序员造成不少迷惑.这篇文章讲述了为了使用DropDownLists,你需要在Asp.Net MVC中知道的方方面面. DropDownList,ComboBox,无论你喜欢怎么称呼这些，他们毫无例外的会被生成…
3D中的OBJ文件格式详解（转载）
OBJ文件是Alias|Wavefront公司为它的一套基于工作站的3D建模和动画软件"Advanced Visualizer"开发的一种标准3D模型文件格式，很适合用于3D软件模型之间的互导，也可以通过Maya读写。比如你在3dsMax或LightWave中建了一个模型，想把它…
比特币测试网络搭建
转自 https://blog.csdn.net/yzpbright/article/details/81004202 比特币 一、安装 Docker 二、安装和运行比特币测试网络(bitcoin-testnet) 1.下载比特币测试网络(bitcoin-testnet)的Docker镜像 docker pull freewil/bitcoin-testnet-box 2.运行Docker镜像 docker run -t -i -…