当前位置：网站首页>Machine test question 1
Machine test question 1
2022-07-06 22:34:00 【Tianjin TEDA Master Kang】
1. Binary tree
Given a sequence of integers , Use these numbers to form a complete binary sort tree , Output the sequence traversal sequence of this binary tree .
#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: Number of nodes
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; // Number of numbers
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;
}
Ideas ：
First makeTree Function to build a tree n Complete binary tree of nodes . Then the middle order traversal assigns values to each node . Finally, sequence traversal .
2. Swing the plane
Description of the placement rules of the aircraft bombing game ：
1. stay m That's ok *n Columns are placed randomly in the matrix grid k A plane , Do not overlap each other 、 cross .
…
There is no good idea of pruning , Also failed to run through all test points ,k>=5 Just game over.
Ideas ： Violence enumeration dfs+ Dynamic programming
establish bool Type of two-dimensional matrix S, Indicates the occupancy of the airport .
One plane after another , When setting up each plane , Divide again “ The up and down or so ” In the four cases, take the lattice in the top left corner as the benchmark, move one lattice by one , When overlapping , Then move , No overlap ,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 For possession use-->false For not possessing
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){
// Assign or restore
// Assignment overrides :use=true;
// Restore :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); // initialization
simulation(m,n,k,total);
int kjie = 1;
for(int i=1;i<=k;i++){
kjie *= i;
}
cout<<total/kjie<<endl;
}
return 0;
}
Yes .
边栏推荐
猜你喜欢
网络基础入门理解
Installation and use of labelimg
Leetcode exercise - Sword finger offer 26 Substructure of tree
Unity3d minigame-unity-webgl-transform插件转换微信小游戏报错To use dlopen, you need to use Emscripten‘s...问题
![pytorch_ Yolox pruning [with code]](/img/98/31d6258635ce48ac53819d0ca12d1d.jpg)
pytorch_ Yolox pruning [with code]
Chapter 3: detailed explanation of class loading process (class life cycle)
二分图判定
云原生技术--- 容器知识点
【LeetCode】19、 删除链表的倒数第 N 个结点
Build op-tee development environment based on qemuv8
随机推荐
雅思口语的具体步骤和时间安排是什么样的？
3DMAX assign face map
机试刷题1
Dealing with the crash of QT quick project in offscreen mode
Void keyword
Heavyweight news | softing fg-200 has obtained China 3C explosion-proof certification to provide safety assurance for customers' on-site testing
OpenCV VideoCapture. Get() parameter details
Web APIs DOM 时间对象
Aardio - 通过变量名将变量值整合到一串文本中
枚举与＃define 宏的区别
MySQL教程的天花板，收藏好，慢慢看
UVa 11732 – strcmp() Anyone?
config:invalid signature 解决办法和问题排查详解
Gd32f4xx serial port receive interrupt and idle interrupt configuration
const关键字
Chapter 3: detailed explanation of class loading process (class life cycle)
Plafond du tutoriel MySQL, bien collecté, regardez lentement
void关键字
The SQL response is slow. What are your troubleshooting ideas?
What are the specific steps and schedule of IELTS speaking?