当前位置：网站首页>机试刷题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;
}
寄了。
边栏推荐
- signed、unsigned关键字
- const关键字
- MySQL教程的天花板，收藏好，慢慢看
- i.mx6ull搭建boa服务器详解及其中遇到的一些问题
- 第4章：再谈类的加载器
- （18） LCD1602 experiment
- Heavyweight news | softing fg-200 has obtained China 3C explosion-proof certification to provide safety assurance for customers' on-site testing
- Barcodex (ActiveX print control) v5.3.0.80 free version
- [leetcode] 19. Delete the penultimate node of the linked list
- 如何用程序确认当前系统的存储模式？
猜你喜欢
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
剑指offer刷题记录1
Management background --4, delete classification
RESNET rs: Google takes the lead in tuning RESNET, and its performance comprehensively surpasses efficientnet series | 2021 arXiv
C＃實現水晶報錶綁定數據並實現打印4-條形碼
NetXpert XG2帮您解决“布线安装与维护”难题
基於 QEMUv8 搭建 OP-TEE 開發環境
2500 common Chinese characters + 130 common Chinese and English characters
Attack and defense world miscall
云原生技术--- 容器知识点
随机推荐
Mysql database basic operations DML
Solve project cross domain problems
中国固态氧化物燃料电池技术进展与发展前景报告（2022版）
基于 QEMUv8 搭建 OP-TEE 开发环境
新手程序员该不该背代码？
Pit encountered by handwritten ABA
雅思口语的具体步骤和时间安排是什么样的？
【编译原理】做了一半的LR(0)分析器
自定义 swap 函数
2022-07-05 stonedb sub query processing parsing time analysis
Self made j-flash burning tool -- QT calls jlinkarm DLL mode
NetXpert XG2帮您解决“布线安装与维护”难题
Mise en place d'un environnement de développement OP - tee basé sur qemuv8
LeetCode刷题(十一)——顺序刷题51至55
[线性代数] 1.3 n阶行列式
2500个常用中文字符 + 130常用中英文字符
Assembly and interface technology experiment 5-8259 interrupt experiment
go多样化定时任务通用实现与封装
C＃實現水晶報錶綁定數據並實現打印4-條形碼
LeetCode 练习——剑指 Offer 26. 树的子结构