当前位置:网站首页>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 .
边栏推荐
- Windows Auzre 微软的云计算产品的后台操作界面
- 如何实现文字动画效果
- MySQL约束的分类、作用及用法
- [Digital IC hand tearing code] Verilog burr free clock switching circuit | topic | principle | design | simulation
- Senior soft test (Information System Project Manager) high frequency test site: project quality management
- 将MySQL的表数据纯净方式导出
- 2022-07-05 stonedb的子查询处理解析耗时分析
- 在IPv6中 链路本地地址的优势
- Chapter 4: talk about class loader again
- 云原生技术--- 容器知识点
猜你喜欢
Web APIs DOM time object
[linear algebra] determinant of order 1.3 n
Aardio - 利用customPlus库+plus构造一个多按钮组件
Crawler obtains real estate data
LeetCode 练习——剑指 Offer 26. 树的子结构
Sword finger offer question brushing record 1
CocosCreator+TypeScripts自己写一个对象池
(18) LCD1602 experiment
Leetcode: interview question 17.24 Maximum cumulative sum of submatrix (to be studied)
Attack and defense world ditf Misc
随机推荐
Spatial domain and frequency domain image compression of images
自定义 swap 函数
Balanced Multimodal Learning via On-the-fly Gradient Modulation(CVPR2022 oral)
How to use flexible arrays?
Jafka来源分析——Processor
雅思口语的具体步骤和时间安排是什么样的?
Netxpert xg2 helps you solve the problem of "Cabling installation and maintenance"
2014阿里巴巴web前实习生项目分析(1)
UDP programming
sizeof关键字
Aardio - integrate variable values into a string of text through variable names
Heavyweight news | softing fg-200 has obtained China 3C explosion-proof certification to provide safety assurance for customers' on-site testing
网络基础入门理解
[Digital IC hand tearing code] Verilog burr free clock switching circuit | topic | principle | design | simulation
Aardio - 封装库时批量处理属性与回调函数的方法
Self made j-flash burning tool -- QT calls jlinkarm DLL mode
将MySQL的表数据纯净方式导出
(十八)LCD1602实验
MySQL教程的天花板,收藏好,慢慢看
OpenNMS separation database