当前位置：网站首页>机试刷题1
机试刷题1
2022-07-06 14:55:00 【天津泰达康师傅】
1.二叉树
给定一个整数序列，用这些数构成一个完全二叉排序树，输出此二叉树的层序遍历序列。
#include<iostream>
#include<math.h>
#include <stack>
#include <algorithm>
#include <queue>
using namespace std;
struct TreeNode{
int val;
TreeNode* lchild;
TreeNode* rchild;
TreeNode():lchild(nullptr),rchild(nullptr){
};
TreeNode(int v):val(v),lchild(nullptr),rchild(nullptr){
}
};
TreeNode* makeTree(int n,int* arr){
//n:结点数
queue<TreeNode*> q;
TreeNode* root = new TreeNode();
q.push(root);
n -= 1;
TreeNode* tmp;
while(true){
if(n == 0){
break;
}
tmp = q.front();
q.pop();
tmp->lchild = new TreeNode();
q.push(tmp->lchild);
n--;
if(n == 0){
break;
}else{
tmp->rchild = new TreeNode();
q.push(tmp->rchild);
n--;
}
}
tmp = root;
int index = 0;
stack<TreeNode*> s;
while(tmp) {
s.push(tmp);
tmp = tmp->lchild;
}
while(!s.empty()||tmp->rchild){
while(tmp) {
s.push(tmp);
tmp = tmp->lchild;
}
tmp = s.top();
s.pop();
tmp->val = arr[index++];
cout<<tmp->val<<endl;
tmp = tmp->rchild;
}
return root;
}
void LevelTraverse(TreeNode* root){
queue<TreeNode*> q;
q.push(root);
while(!q.empty()){
TreeNode* front = q.front();
q.pop();
cout<<front->val<<" ";
if(front->lchild!= nullptr){
q.push(front->lchild);
}
if(front->rchild!= nullptr){
q.push(front->rchild);
}
}
}
using namespace std;
int main(){
int num; //数字个数
while(cin>>num){
int* arr = (int*)malloc(sizeof(int)*num);
for(int i=0;i<num;i++){
cin>>arr[i];
}
sort(arr,arr+num);
TreeNode* root = makeTree(num,arr);
LevelTraverse(root);
}
return 0;
}
思路：
首先makeTree函数建立一棵n个结点的完全二叉树。然后中序遍历把各结点赋值。最后再层序遍历。
2.摆飞机
炸飞机游戏摆放规则描述：
1.在m行*n列的矩阵方格中随机摆放k架飞机，互相不得重叠、交叉。
…
没有剪枝好思路，也没有成功地跑通所有测试点，k>=5就game over。
思路：暴力枚举dfs+动态规划
建立bool类型的二维矩阵S，表示机场的占用情况。
一架一架飞机往上摆，摆每架飞机的时候，又分“上下左右”四种情况以最左上角的格为基准一个格一个格挪，当重叠的时候，接着挪，不重叠，dfs。
#include<iostream>
using namespace std;
#define MAXN 11
bool S[MAXN][MAXN];
void Initial(int m,int n) {
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
S[j][i] = false;
}
}
}
bool JudgeUp(int start_x,int start_y,int m,int n){
bool flag = true;
//use --> true为占有 use-->false 为不占有
if(start_x+4>n-1 || start_y+3>m-1){
flag = false;
}else{
for(int i=0;i<4;i++){
if(S[start_x+2][start_y+i]== true){
flag = false;
}
}
for(int i=0;i<5;i++){
if(S[start_x+i][start_y+1]== true){
flag = false;
}
}
for(int i=0;i<3;i++){
if(S[start_x+1+i][start_y+3]== true){
flag = false;
}
}
}
return flag;
}
void Up(int start_x,int start_y,int m,int n,bool use){
//赋值或还原
//赋值覆盖:use=true;
//还原:use = false;
for(int i=0;i<4;i++){
if(S[start_x+2][start_y+i]== !use){
S[start_x+2][start_y+i] = use;
}
}
for(int i=0;i<5;i++){
if(i == 2){
continue;
}else{
if(S[start_x+i][start_y+1]== !use){
S[start_x+i][start_y+1] = use;
}
}
}
for(int i=0;i<3;i++){
if(i==1){
continue;
}else{
if(S[start_x+1+i][start_y+3]== !use){
S[start_x+1+i][start_y+3] = use;
}
}
}
}
bool JudgeDown(int start_x,int start_y,int m,int n){
bool flag = true;
if(start_x+4>n-1 || start_y+3>m-1){
flag = false;
}else{
for(int i=0;i<4;i++){
if(S[start_x+2][start_y+i]== true){
flag = false;
}
}
for(int i=0;i<3;i++){
if(S[start_x+1+i][start_y]== true){
flag = false;
}
}
for(int i=0;i<5;i++){
if(S[start_x+i][start_y+2]== true){
flag = false;
}
}
}
return flag;
}
void Down(int start_x,int start_y,int m,int n,bool use){
for(int i=0;i<4;i++){
if(S[start_x+2][start_y+i]== !use){
S[start_x+2][start_y+i] = use;
}
}
for(int i=0;i<3;i++){
if(i == 1){
continue;
}else{
if(S[start_x+1+i][start_y]== !use){
S[start_x+1+i][start_y] = use;
}
}
}
for(int i=0;i<5;i++){
if(i == 2){
continue;
}else{
if(S[start_x+i][start_y+2]== !use){
S[start_x+i][start_y+2] = use;
}
}
}
}
bool JudgeLeft(int start_x,int start_y,int m,int n){
bool flag = true;
if(start_x+3>n-1 || start_y+4>m-1){
flag = false;
}else{
for(int i=0;i<4;i++){
if(S[start_x+i][start_y+2]== true){
flag = false;
}
}
for(int i=0;i<5;i++){
if(S[start_x+1][start_y+i] == true){
flag = false;
}
}
for(int i=0;i<3;i++){
if(S[start_x+3][start_y+1+i] == true){
flag = false;
}
}
}
return flag;
}
void Left(int start_x,int start_y,int m,int n,bool use){
for(int i=0;i<4;i++){
if(S[start_x+i][start_y+2]==!use){
S[start_x+i][start_y+2] = use;
}
}
for(int i=0;i<5;i++){
if(i == 2){
continue;
}else{
if(S[start_x+1][start_y+i] == !use){
S[start_x+1][start_y+i] = use;
}
}
}
for(int i=0;i<3;i++){
if(i == 1){
continue;
}else{
if(S[start_x+3][start_y+1+i] ==!use){
S[start_x+3][start_y+1+i] = use;
}
}
}
}
bool JudgeRight(int start_x,int start_y,int m,int n){
bool flag = true;
if(start_x+3>n-1 || start_y+4>m-1){
flag = false;
}else{
for(int i=0;i<4;i++){
if(S[start_x+i][start_y+2]== true){
flag = false;
}
}
for(int i=0;i<3;i++){
if(S[start_x][start_y+1+i] == true){
flag = false;
}
}
for(int i=0;i<5;i++){
if(S[start_x+2][start_y+i]==true){
flag = false;
}
}
}
return flag;
}
void Right(int start_x,int start_y,int m,int n,bool use){
for(int i=0;i<4;i++){
if(S[start_x+i][start_y+2]==!use){
S[start_x+i][start_y+2] = use;
}
}
for(int i=0;i<3;i++){
if(i == 1){
continue;
}else{
if(S[start_x][start_y+1+i] == !use){
S[start_x][start_y+1+i] = use;
}
}
}
for(int i=0;i<5;i++){
if(i == 2){
continue;
}else{
if(S[start_x+2][start_y+i]==!use){
S[start_x+2][start_y+i] = use;
}
}
}
}
void output(int m,int n){
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
cout<<S[j][i]<<" ";
}
cout<<endl;
}
cout<<"---------------------------"<<endl;
}
void simulation(int m,int n,int k,int& total){
if(k<=0){
return;
}else{
for(int p=0;p<=3;p++) {
if (p == 0) {
//up
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if(k>1){
if(JudgeUp(i,j,m,n)){
Up(i,j,m,n,true);
simulation(m,n,k-1,total);
Up(i,j,m,n, false);
}
}else if(k == 1){
if(JudgeUp(i,j,m,n)){
total += 1;
}
}
}
}
} else if (p == 1) {
//Down
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if(k>1){
if(JudgeDown(i,j,m,n)){
Down(i,j,m,n,true);
simulation(m,n,k-1,total);
Down(i,j,m,n,false);
}
}else if(k==1){
if(JudgeDown(i,j,m,n)){
total += 1;
}
}
}
}
} else if (p == 2) {
//Left
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if(k>1){
if(JudgeLeft(i,j,m,n)){
Left(i,j,m,n, true);
simulation(m,n,k-1,total);
Left(i,j,m,n, false);
}
}else if(k==1){
if(JudgeLeft(i,j,m,n)){
total+=1;
}
}
}
}
} else if (p == 3) {
//Right
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if(k>1){
if(JudgeRight(i,j,m,n)){
Right(i,j,m,n, true);
simulation(m,n,k-1,total);
Right(i,j,m,n, false);
}
}else if(k==1){
if(JudgeRight(i,j,m,n)){
total+=1;
}
}
}
}
}
}
}
}
int main(){
int m,n,k;
int total = 0;
while(cin>>m>>n>>k){
total = 0;
Initial(m,n); //初始化
simulation(m,n,k,total);
int kjie = 1;
for(int i=1;i<=k;i++){
kjie *= i;
}
cout<<total/kjie<<endl;
}
return 0;
}
寄了。
边栏推荐
- 如何用程序确认当前系统的存储模式？
- go多样化定时任务通用实现与封装
- [sdx62] wcn685x will bdwlan Bin and bdwlan Txt mutual conversion operation method
- 枚举与＃define 宏的区别
- Dealing with the crash of QT quick project in offscreen mode
- Aardio - 不声明直接传float数值的方法
- Netxpert xg2 helps you solve the problem of "Cabling installation and maintenance"
- Should novice programmers memorize code?
- GD32F4XX串口接收中断和闲时中断配置
- Data storage (1)
猜你喜欢
2022-07-04 the high-performance database engine stonedb of MySQL is compiled and run in centos7.9
labelimg的安装与使用
墨西哥一架飞往美国的客机起飞后遭雷击 随后安全返航
Hardware development notes (10): basic process of hardware development, making a USB to RS232 module (9): create ch340g/max232 package library sop-16 and associate principle primitive devices
PVL EDI project case
UE4蓝图学习篇（四）--流程控制ForLoop和WhileLoop
Leetcode question brushing (XI) -- sequential questions brushing 51 to 55
新手程序员该不该背代码？
C＃實現水晶報錶綁定數據並實現打印4-條形碼
Export MySQL table data in pure mode
随机推荐
（18） LCD1602 experiment
sizeof关键字
Notes de développement du matériel (10): flux de base du développement du matériel, fabrication d'un module USB à RS232 (9): création de la Bibliothèque d'emballage ch340g / max232 SOP - 16 et Associa
C # réalise la liaison des données du rapport Crystal et l'impression du Code à barres 4
MySQL约束的分类、作用及用法
0 basic learning C language - interrupt
变量与“零值”的比较
Chapter 4: talk about class loader again
Web APIs DOM 时间对象
2022年6月国产数据库大事记-墨天轮
Advantages of link local address in IPv6
General implementation and encapsulation of go diversified timing tasks
SQL server generates auto increment sequence number
墨西哥一架飞往美国的客机起飞后遭雷击 随后安全返航
Classification, function and usage of MySQL constraints
CCNA Cisco network EIGRP protocol
中国VOCs催化剂行业研究与投资战略报告（2022版）
HDR image reconstruction from a single exposure using deep CNN reading notes
What are the interface tests? What are the general test points?
China 1,4-cyclohexanedimethanol (CHDM) industry research and investment decision-making report (2022 Edition)