1、
题目:
问题描述:在某操作系统中打开了 N 个窗口,每个窗口都是一个矩形区域。窗口之间有层次的区别,在多于一个窗口重叠的区域里,只会显示位于顶层的窗口里的内容。当你点击屏幕上一个点的时候,你就选择了处于被点击位置的最顶层窗口,并且这个窗口就会被移到所有窗口的最顶层,而剩余的窗口的层次顺序不变。如果你点击的位置不属于任何窗口,则系统会忽略你这次点击。现在我们希望你写一个程序模拟点击窗口的过程
算法思想:
由于在某一次点开的网页所在的层数我们是不知道的,因此这道题并不方便采用栈或者队列,由于这里涉及到了较多的删除,插入操作,所以最终我决定采用链表来处理这道题,我用了一个链表来进行网页的存储,链表里面包含了网页的层数和位置信息,然后我们来用遍历的方式来判断点击的网页,如果找到了点击的网页,那么我们就将这个网页先从链表中拆下来,然后插入到头节点后面,如果点击的位置没有对应的网页,那么我们就输出IGNORED。
当然我们的输出没有阳按照老师的样例程序进行,因为考虑到,我们在输入信息时,需要一些提示性信息,比如,"请输入网页数量N,和操作次数M: ","请依次输入x1,y1,x2,y2: \n"等等。
我们算法的空间复杂度为:O(n),因为取决于我们所输入的网页的数量n,我们算法的时间复杂度为:O(mn),因为每一次操作都需要遍历这个链表,一共有m次操作,那么最坏的情况就是每一次都是需要完全遍历,那么就是需要比较次mn,因此们算法的时间复杂度为:O(mn)
运行结果:
结果分析:
结果是正确的,除了我的输出结果有一些提示性信息以外,都和老师的要求是吻合的,当然这些提示性信息并不影响。
附源程序:
#include "stdlib.h"
#include "math.h"
#include "stdio.h"
typedef struct node
{
int x1;
int y1;
int x2;
int y2;
int num; //网页的编号
struct node *next;
}LI;
void Get_page(LI *T,int x,int y); //输入链表T,鼠标点击位置x,y得到应该的网页编号,并且改变他的位置
main()
{
LI *A,*q;
int x1,x2,y1,y2; //给网页赋值
int N,M,i; //N为网页数量,M为操作次数,i用来生成N个网页以及遍历所有鼠标点击位置
int x,y; //鼠标点击的位置
A = (LI*)malloc(sizeof(LI));
A->next = NULL;
printf("请输入网页数量N,和操作次数M: ");
scanf("%d%d",&N,&M);
for(i = 1;i <= N; i++)
{
q = (LI*)malloc(sizeof(LI));
printf("请依次输入x1,y1,x2,y2: \n");
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
if(x1>=x2)
{
printf("x2要比x1大!\n");
exit(0);
}
else if(y1>=y2)
{
printf("y2要比y1大!\n");
exit(0);
}
else
{
printf(" \"上方是编号为%d的窗口\"\n",i);
q->x1 = x1;
q->x2 = x2;
q->y1 = y1;
q->y2 = y2;
q->num = i;
}
q->next = A->next;
A->next = q;
}
for(i = 1;i <=M ;i++)
{
printf("请输入鼠标点击位置x,y: ");
scanf("%d%d",&x,&y);
Get_page(A,x,y);
}
}
void Get_page(LI *T,int x,int y)
{
LI *p,*p1;
LI *q;
p1 = T;
p = p1->next;
while(p)
{
if((x >= p->x1 )&&(x <= p->x2 )&&(y >= p->y1 )&&(y <= p->y2 ))
{
printf("%d\n",p->num);
q = p;
p1->next = p->next;
q->next = T->next;
T->next = q;
break;
}
else
{
p1 = p;
p = p->next;
}
}
if(p == NULL)
printf("IGNORED");
}
2、
题目:
利用栈模拟实现N个盘子的汉诺塔问题(非递归算法实现)
算法思想:
1、将1号盘子按照顺时针顺序从当前栈移动到下一个栈(从当前站pop,然后push进下一个栈),sum++,如果sum已经等于,结束;
2、观察没有1号盘子的那两个栈
-如果其中一个为空,那么将另一个非空栈的栈顶盘子移动到这个空栈 上;
-如果两个都不,那么看谁的栈顶的盘子比较小把小盘子移动到栈顶盘子较大的那个栈上;
-之后,sum++,如果sum已经达到数量,结束.否则继续执行第1步
总的思路很简单,就是按照老师ppt上面给的思路写就行了,因为有了老师的思路,所以没有什么难度。空间复杂度为:O(n),取决于汉诺塔中圆盘的数量,算法的时间复杂度为:O(2的n次方),因为我们需要对其中的圆盘进行次2^n-1的移动。
运行结果:
N = 2;
N = 3
N = 4
结果分析:
结构运行非常正确,而且在不是很大的前提下,我们速度还是可以的,但是由于我们的算法的时间复杂度为:,所以当较大时,算法还是比较慢的。
附源程序:
void hanio(ST *T,int n)//移动盘子的时候要输出将几号盘子从哪儿移动到了哪儿
{
int sum=0,k=pow(2,n)-1,i=0;
while(1)
{
sum++;
printf("Step %d : Plate %d From %c To %c\n",sum,gettop(&T[i%3]),T[i].name,T[(i+1)%3].name);
push(&T[(i+1)%3],pop(&T[i]));
i = (i+1)%3;
if (sum==k)
break;
sum++;
if (isempty(&T[(i+1)%3]))
{
printf("Step %d : Plate %d From %c To %c\n",sum,gettop(&T[(i+2)%3]),T[(i+2)%3].name,T[(i+1)%3].name);
push(&T[(i+1)%3],pop(&T[(i+2)%3]));
}
else if (isempty(&T[(i+2)%3]))
{
printf("Step %d : Plate %d From %c To %c\n",sum,gettop(&T[(i+1)%3]),T[(i+1)%3].name,T[(i+2)%3].name);
push(&T[(i+2)%3],pop(&T[(i+1)%3]));
}
else if (gettop(&T[(i+1)%3])<gettop(&T[(i+2)%3]))
{
printf("Step %d : Plate %d From %c To %c\n",sum,gettop(&T[(i+1)%3]),T[(i+1)%3].name,T[(i+2)%3].name);
push(&T[(i+2)%3],pop(&T[(i+1)%3]));
}
else
{
printf("Step %d : Plate %d From %c To %c\n",sum,gettop(&T[(i+2)%3]),T[(i+2)%3].name,T[(i+1)%3].name);
push(&T[(i+1)%3],pop(&T[(i+2)%3]));
}
}
}
题目:(关于迷宫四个情况判断的写法是在王铭宇同学的帮助下写出来的,因为在写这道题的时候还没有讲队列和这种题目的思路,所以询问了他人,但是现在我可以自己独立写出来了)
根据给定的迷宫入口和出口位置,利用队列,输出迷宫中的所有最短路径,以及路径长度(路径中包含的点的数量)
算法思想:
我用队列来寻找最短路径,我的队列中存储点的坐标,以及该队列的头部和尾部,让后开始从初始位置开始走,他有四个方向可以选择,我们就把可行的都存到队列中去,然后找出最先到达目标位置的,然后我们之前用了一共数组来存储每一步的上一步的标号,我们只需要遍历一下这个数组就可以得到我们的最短路径了。由于我们需要存储我们的位置坐标,而他们的数量由点的个数来确定,所以我们的空间复杂度为:O(n2),我们的时间复杂度为:O(n2),因为可能会遍历迷宫中所有的点。
运行结果:
结果分析:
运行结果是正确的,就是我们的最短路径,我所采用的算法可以找到这条最短路径,但是存在一共问题,就是如果最短路径不唯一,那么我们如何找到所有的最短路径呢,我想我们可以用栈来解决,由于这道题要求是队列,所以就不往下考虑了。
附源代码:
#include "stdio.h"
#include "stdlib.h"
#include "math.h"
#define start_x 1//入口行号
#define start_y 1//入口列号
#define end_x 8//出口行号
#define end_y 8//出口列号
#define N 100
int mg[10][10]={
{
1,1,1,1,1,1,1,1,1,1},
{
1,0,0,1,0,0,0,1,0,1},
{
1,0,0,1,0,0,0,1,0,1},
{
1,0,0,0,0,1,1,0,0,1},
{
1,0,1,1,1,0,0,0,0,1},
{
1,0,0,0,1,0,0,0,0,1},
{
1,0,1,0,0,0,1,0,0,1},
{
1,0,1,1,1,0,1,1,0,1},
{
1,1,0,0,0,0,0,0,0,1},
{
1,1,1,1,1,1,1,1,1,1},
};//用二维数组表示迷宫,“0”表示该点可行,“1”表示该点不可行
typedef struct queue
{
int x[N],y[N];
int front;
int rear;
}MG;
void initial(MG *M); //初始化队列MG
void Queue(MG *M);
void Push(MG *M,int i,int j); //入队操作
void show(int a[],int b[],int n);
int main()
{
MG M; //队列
initial(&M);
Queue(&M);
}
void initial(MG *M)
{
M->x[0]=start_x;
M->y[0]=start_y;
M->front=0;
M->rear=M->front+1;
mg[start_x][start_y]=1;
}
void Push(MG *M,int i,int j)
{
if(M->front==(M->rear+1))
{
printf("队列已经满了,不能再插入数据!");
exit(0);
}
M->x[M->rear]=i;
M->y[M->rear]=j;
M->rear++;
}
void Queue(MG *M)
{
int i,j,i1,j1; //i,j来遍历整个迷宫;i1,j1用来判断行走的四个方向
int next,step=-1,active=0;
int save_x[N],save_y[N]; //保存路径
for(i=start_x,j=start_y;i!=end_x || j!=end_y;)
{
if(step==-1 || active!=0)
M->front=M->rear; //第一步和上一步寻找到可行点时更新队头元素
active=0;
if(save_x[step]!=i || save_y[step]!=j) //当此时的路径与上一步的路径不一样时保存路径
{
step++;
save_x[step]=i;
save_y[step]=j;
}
else //否则说明上一步路径出错,删除上一步的路径
step--;
for(next=0;next<4;next++)
{
switch(next)
{
case 0: //向前
i1=i;
j1=j+1;
break;
case 1: //向后
i1=i;
j1=j-1;
break;
case 2: //向上
j1=j;
i1=i-1;
break;
case 3: //向下
j1=j;
i1=i+1;
break;
}
if(mg[i1][j1]==0) //某个方向可行时将其加入队列
{
Push(M,i1,j1);
mg[i1][j1]=1;
active=1;
}
}
if(active==1) //若有可行方向则选取最后一个可行方向前进
{
i=M->x[(M->rear)-1];
j=M->y[(M->rear)-1];
}
else //未找到可行方向就将队头回溯到上一条路径
{
M->front--;
i=M->x[M->front];
j=M->y[M->front];
}
}
step++;
save_x[step]=end_x; //最后将出口加入队列
save_y[step]=end_y;
step++;
show(save_x,save_y,step);
}
void show(int a[],int b[],int n)
{
int i;
printf("走出迷宫的最短路径为:\n");
for(i=0;i<n;i++)
{
printf("(%d,%d) ",a[i],b[i]);
if(i<n-1)
printf("-->");
}
printf("\n结点数为%d",n);
printf("\n\n");
}
文章浏览阅读3.8k次,点赞9次,收藏28次。直接上一个工作中碰到的问题,另外一个系统开启多线程调用我这边的接口,然后我这边会开启多线程批量查询第三方接口并且返回给调用方。使用的是两三年前别人遗留下来的方法,放到线上后发现确实是可以正常取到结果,但是一旦调用,CPU占用就直接100%(部署环境是win server服务器)。因此查看了下相关的老代码并使用JProfiler查看发现是在某个while循环的时候有问题。具体项目代码就不贴了,类似于下面这段代码。while(flag) {//your code;}这里的flag._main函数使用while(1)循环cpu占用99
文章浏览阅读347次。idea shift f6 快捷键无效_idea shift +f6快捷键不生效
文章浏览阅读135次。Ecmacript 中没有DOM 和 BOM核心模块Node为JavaScript提供了很多服务器级别,这些API绝大多数都被包装到了一个具名和核心模块中了,例如文件操作的 fs 核心模块 ,http服务构建的http 模块 path 路径操作模块 os 操作系统信息模块// 用来获取机器信息的var os = require('os')// 用来操作路径的var path = require('path')// 获取当前机器的 CPU 信息console.log(os.cpus._node模块中有很多核心模块,以下不属于核心模块,使用时需下载的是
文章浏览阅读10w+次,点赞435次,收藏3.4k次。SPSS 22 下载安装过程7.6 方差分析与回归分析的SPSS实现7.6.1 SPSS软件概述1 SPSS版本与安装2 SPSS界面3 SPSS特点4 SPSS数据7.6.2 SPSS与方差分析1 单因素方差分析2 双因素方差分析7.6.3 SPSS与回归分析SPSS回归分析过程牙膏价格问题的回归分析_化工数学模型数据回归软件
文章浏览阅读7.5k次。如何利用hutool工具包实现邮件发送功能呢?1、首先引入hutool依赖<dependency> <groupId>cn.hutool</groupId> <artifactId>hutool-all</artifactId> <version>5.7.19</version></dependency>2、编写邮件发送工具类package com.pc.c..._hutool发送邮件
文章浏览阅读867次,点赞2次,收藏2次。docker安装elasticsearch,elasticsearch-head,kibana,ik分词器安装方式基本有两种,一种是pull的方式,一种是Dockerfile的方式,由于pull的方式pull下来后还需配置许多东西且不便于复用,个人比较喜欢使用Dockerfile的方式所有docker支持的镜像基本都在https://hub.docker.com/docker的官网上能找到合..._docker安装kibana连接elasticsearch并且elasticsearch有密码
文章浏览阅读1.3w次,点赞57次,收藏92次。整理 | 郑丽媛出品 | CSDN(ID:CSDNnews)近年来,随着机器学习的兴起,有一门编程语言逐渐变得火热——Python。得益于其针对机器学习提供了大量开源框架和第三方模块,内置..._beeware
文章浏览阅读7.9k次。//// ViewController.swift// Day_10_Timer//// Created by dongqiangfei on 2018/10/15.// Copyright 2018年 飞飞. All rights reserved.//import UIKitclass ViewController: UIViewController { ..._swift timer 暂停
文章浏览阅读986次,点赞2次,收藏2次。1.硬性等待让当前线程暂停执行,应用场景:代码执行速度太快了,但是UI元素没有立马加载出来,造成两者不同步,这时候就可以让代码等待一下,再去执行找元素的动作线程休眠,强制等待 Thread.sleep(long mills)package com.example.demo;import org.junit.jupiter.api.Test;import org.openqa.selenium.By;import org.openqa.selenium.firefox.Firefox.._元素三大等待
文章浏览阅读3k次,点赞4次,收藏14次。Java软件工程师职位分析_java岗位分析
文章浏览阅读2k次。Java:Unreachable code的解决方法_java unreachable code
文章浏览阅读1w次。1、html中设置标签data-*的值 标题 11111 222222、点击获取当前标签的data-url的值$('dd').on('click', function() { var urlVal = $(this).data('ur_如何根据data-*属性获取对应的标签对象