[搜索]奥特曼打怪兽

题目描述

奥特曼是正义的化身,现在奥特曼需要消灭地图中所有怪鲁,该地图由一个M×M的矩阵组成,地图中的怪兽有不同的难度级别。
0表示陷阱,不能进入
1表示陆地,可以通过
大于等于2的正整数表示各种级别的怪兽,数字越大表示怪兽越强。
现在奥特曼需要按照级别从弱到强消灭地图中所有的怪兽,怪兽一旦被消灭,怪兽所在的地方就变回为陆地。
奥特曼从原地开始(0,0)行动,在地图中只能上下左右移动,那么奥特曼最少需要走多少步才能消灭所有怪兽, 如果无法消灭所有怪曽返回-1。
约束:
1.地图中不会有级别一样的怪兽
2.不允许宾特曼经过一个怪兽而不消灭它
输入描述:
一个由M×M构成的炬阵,3≤M≤50,该矩阵每行数字之间用空格隔开
输出描述:
如果奥特曼能够依次消灭所有怪兽,输出最小步数,如果无法全部消灭输出-1。

输入样例

输出样例

思路描述

乍一看,是到搜索题。

等我跑步回来写……

方法一:BFS

方法二:DFS

测试输入用例(不全)

总结

  • 无论是BFS还是DFS都不适用于地图变化的情形,所以要转换为地图不变的问题来处理。比如,明确“起点”、“终点”。
  • 明确好“岔道口”和“死胡同”在题目中的指代,即可转换为搜索问题。当然这道题还算明显。

HashMap 的工作原理是什么?

HashMap 是基于 hashing 的原理
我们使用 put(key, value) 存储对象到 HashMap 中,使用 get(key) 从 HashMap 中获取对象。
当我们给 put() 方法传递键和值时,我们先对调用 hashCode() 方法,计算并返回的 hashCode 是用于找到 Map 数组 bucket 位置来储存 Node 对象。

这里关键点在于指出,HashMap 是在 bucket 中储存键对象和值对象,作为Map.Node

以下是 HashMap 初始化


以下是具体的 put 过程(JDK1.8)
1. 对 Key 求 Hash 值,然后再计算下标
2. 如果没有碰撞,直接放入桶中(碰撞的意思是计算得到的 Hash 值相同,需要放到同一个 bucket 中)
3. 如果碰撞了,以链表的方式链接到后面
4. 如果链表长度超过阀值(TREEIFY THRESHOLD==8),就把链表转成红黑树,链表长度低于6,就把红黑树转回链表
5. 如果节点已经存在就替换旧值
6. 如果桶满了(容量16*负载因子0.75=12),就需要 resize(扩容2倍后重排),rehash的位置只可能在两处


关于具体的 get 过程
考虑特殊情况:如果两个键的 hashcode 相同,你如何获取值对象?

当我们调用 get() 方法,HashMap 会使用键对象的 hashcode 找到 bucket 位置,找到 bucket 位置之后,会调用 keys.equals() 方法逐一比较去找到链表中正确的节点,最终找到要找的值对象。

安装部署KVM虚拟机(四)

Libvirt提供了用户空间的命令行和编程语言绑定来管理虚拟机的build, configure, start, stop,migrate, terminate,etc.

OpenStack的组件中也做了集成。

https://blog.csdn.net/xxfigo/article/details/7590229

Nova是OpenStack云中的计算组织控制器。支持OpenStack云中实例(instances)生命周期的所有活动都由Nova处理。这样使得Nova成为一个负责管理计算资源、网络、认证、所需可扩展性的平台。但是,Nova自身并没有提供任何虚拟化能力,相反它使用libvirt API来与被支持的Hypervisors交互。

安装和配置libvirt

查看libvirt的守护进程是否在执行

修改配置/etc/libvirt/libvirtd.conf

查看配置

Qemu默认用的Selinux策略

查看SELinux状态

如果SELinux status参数为enabled即为开启状态,也可以用getenforce命令检查

我的机器上没有使用SeLinux。

警用QEMU的安全驱动,如果有selinux在运行。

配置监听

重启libvirt守护进程。

验证配置文件

  • libvirt.conf是客户端的配置文件
  • libvirtd.conf是服务器端的配置文件
  • qemu.conf是libvirt使用QEMU的配置文件
  • QEMU/KVM虚拟机一经创建 /etc/libvirt/qemu/目录下就会出现定义相应实例的XML配置文件,/etc/libvirt/qemu/networks/包含网络配置

还有其他配置文件位置

定义KVM实例

列出宿主机上所有的虚拟机

编写XML配置文件,定义KVM实例

<boot dev>指定了虚拟机的启动设备
有关domain XML的文档 https://libvirt.org/formatdomain.html

virsh从XML创建虚拟机

查看虚拟机列表

取消定义,即删除

自己编写XML定义很容易出错,参考使用 virt-install 命令

启动、停止、移除KVM实例

启动

查看运行状态

验证

可以看见同xml中读取传递了大量参数.

停止KVM实例

移除实例

查看和编辑KVM配置

确保虚拟机正在运行

将配置文件dump到标准输出

Dump到文件

编辑kvm1配置

管理KVM中的CPU和内存资源

获取运行实例的信息

更新可用内存大小

关闭虚拟机

调整最大可用内存为2G

重新启动虚拟机

查看更新后的信息

检查XML内存配置

获取CPU信息

列出被客户机使用的CPU

修改vCPU数目

查看修改后的CPU信息

只是配置值改变了,为什么live值不变呢?

重启之后好了。

给虚拟机增加块设备

给虚拟机添加块设备,可以是iSCSI、LVM逻辑卷或者镜像文件

创建1G的镜像文件

将镜像文件作为磁盘,挂载到虚拟机

连接到KVM实例

查看磁盘信息

查看新磁盘的信息

删除磁盘

虚拟机和宿主机共享文件夹

在宿主机上创建共享目录

停止客户机后,编辑配置文件

accessmode有三种:

  • passthrough,默认,使用的客户机中用户的权限
  • mapped,继承自宿主机QEMU用户的权限
  • squash,与passthrough类似,但禁用chmod

登录后查看9p和virto模块都在

如果没有加载,则加载

将共享目录挂载到/mnt

查看宿主机中共享的文件

如何取消挂载呢?重启之后报错。

设置自动启动KVM实例

默认情况下,KVM实例要等宿主机操作系统启动之后,才能运行。

当宿主机操作系统重启时,即使libvirt守护进程运行着,libvirt创建的实例并不会自动运行。

可以设置libvirt守护进程启动时,即启动KVM实例。

停止运行的实例

停止libvirtd守护进程

启动守护进程

查看实例是否自动启动

取消实例自动启动

安装部署KVM虚拟机(三)

使用 virt-install能够生成虚拟机的XML定义文件

查看创建的虚拟机

查看生成的XML定义,文档详见:https://libvirt.org/formatdomain.html

查看kvm1的XML,位于/etc/libvirt/qemu/kvm1.xml


使用virt-install也能安装系统

然后控制台连接

一旦连接上会选择安装配置

通过弹出的文本菜单完成安装。

启动安装的虚拟机

使用VNC客户端连接,这里我用的evnc

安装失败。引导问题,可能是安装的时候没有在grub界面中输入/sda1的分区。

尝试修复,修复过程和使用 qemu-img 和 qemu-system-x86_64 命令行方式安装中安装引导类似。

修复成功。

VNC连接root登录并启动服务

控制台登录

使用Ctrl + ] 断开控制台

停止

查看

以上virt-install安装,使用了两种方式连接。

安装部署KVM虚拟机(二)

使用 qemu-img 和 qemu-system-x86_64 命令行方式安装

验证

有关QEMU支持的格式:

  • raw
  • qcow2
  • qcow
  • dmg
  • nbd
  • vdi
  • vmdk
  • vhdk

继续在上面空白的镜像上创建文件系统

加载nbd内核模块

使用qemu-nbd工具,将空白的镜像连接到/dev/nbd0块设备

在块设备上创建两个分区。一个SWAP交换分区,一个作为客户机的根分区。

查看分区后的块设备。

创建交换分区

在根分区创建EXT4文件系统

充分利用内核末班nbd的提供的功能,用qemu-nbd将一个raw格式的镜像文件关联到块设备/dev/nbd0。

查看nbd内核模块的信息。

块设备的元属性已经被修改了。

同样镜像文件的属性也被改变了

现在该 debian.img 镜像文件包含了两个分区和一个文件系统。

接下来安装客户机的OS系统,以Debian为例。

debootstrap:  Bootstrap a basic Debian system

参考 https://hosxy.github.io/2017/05/03/debootstrap%E5%AE%89%E8%A3%85debian/

将/dev/nbd0p2分区挂载到/mnt,这样就能看见内容了

将根分区挂载到/mnt,挂载点作为安装目标,使用debootstrap从公开仓库安装最新的Debian发行版

Debian全球镜像站点 https://www.debian.org/mirror/list

验证根文件系统创建好了

为个给镜像安装GRUB引导程序,将宿主机的文件系统/dev目录挂载到镜像文件系统/mnt内

使用chroot工具,切换到镜像的根文件系统的命名空间。这样执行的操作就是在客户机系统内的。

检查chroot环境下的发布版本

在已经chroot的环境下,挂载/proc和/sys虚拟文件系统,这是因为GRUB引导程序需要它们

仍然在已经chroot的环境下,安装Debian内核元数据包和grub2工具

在根设备上安装GRUB

更新GRUB配置和initrd镜像。生成GRUB配置文件,更新内存盘镜像

更改密码

在新客户机内部允许访问pseudo 终端,之后就可以登录虚拟机了

更改多用户运行级别

这时fstab还是空的,给fstab增加root挂载点,使它能够启动

取消挂载的文件系统

退出chroot的路径

在宿主机根分区上安装GRUB,关联raw镜像文件

更新GRUB配置文件,反映正确的客户机块设备信息。sda2是客户机内部可见的nbd0p2是当前宿主机可见的。从客户机的角度,第二块分区默认就是sda2。

取消挂载

取消ndb0设备与镜像的关联

再查看宿主机上支持的CPU架构

使用x86-64架构qemu-system-x86_64 启动QEMU虚拟机

启动的是之前的我们安装好的debian.img镜像

安装成功

至此,说明之前的安装是成功的。安装之后可以ping通宿主机,关机重启之后网络就失效了。网络还得学一下如何配置,重点是bridge网络。可以在客户机内使用dhclient <网卡>申请IP地址。

安装部署KVM虚拟机(一)

最近有以特定网络模式,管理KVM虚拟机的需求,先尝试了安装和部署虚拟机。安装KVM虚拟机有四种方式,最近完成读书报告汇报,正逢周末,抽空把这些探索过程分享出来。

安装KVM虚拟机有四种方式:

  • 使用 virt-manager GUI工具
  • 使用 qemu-img 和 qemu-system-x86_64 命令行方式安装
  • 使用 virt-install 命令
  • 使用 libvirt工具集管理虚拟机的生命周期

在安装KVM虚拟机并用libvirt进行管理的时候,有本书对我很有帮助。《KVM Virtualization Cookbook (2017)》,也看见有人称它为KVM虚拟化实践的圣经,但中肯的评价是实践帮助确实很大。


安装环境说明:

软件 版本
Deepin 15.9
virt-top 1.0.8-1+b1 amd64
virt-manager 1.4.3
qemu-system-x86_64 2.12.0
virt-viewer 6.0
libvirtd(libvirt) 4.3.0
virt-install 1.4.3
bridge-utils 1.5-16 amd64

宿主机为Intel CPU,支持Intel虚拟化,确保BIOS里开启VT

KVM是Linux的一个模块

使用 virt-manager GUI工具

命令行输入 virt-manager,打开Virtual Machine Manager窗口页面;

virt-manager GUI

使用 VMM GUI 创建的虚机的xml 定义文件在 /etc/libvirt/qemu/ 目录中。

在操作创建虚拟机过程中遇到了问题:ISO文件所在路径没有搜索权限。

方法一:复制iso镜像到用户目录下。

virt-manager doesn't have permission to access other users' directories and devices. Even when run as root. (you can change this is SElinux, but it's less hassle to just copy the .iso over) 

https://unix.stackexchange.com/questions/409860/virt-manager-the-emulator-may-not-have-search-permissions-for-the-path

方法二:将iso文件所在上层目录改为当前用户和用户组所有。 https://www.reddit.com/r/VFIO/comments/5ti9h2/virtmanager_the_emulator_may_not_have_search/

改为当前用户和用户组所有

继续

Step 1

据说Ubuntu 16.04的iso官方镜像中文安装有问题,换成14.04

Step 2
Step 3
Step 4
Step 4.1
Step 5
开始安装

以下可视化界面安装。

安装中

这样安装好了。

网络使用的default模式,一开始是inactive状态,但安装系统的时候正常。之后重启了,尝试开启,又会遇到default(NAT)模式inactive的问题。

Requested operation is not valid: network 'default' is not active.

管理界面

Virt-manager使用的是Python调用libvirt的API进行GUI管理。

default network未启用
虚拟网络配置

解决方法:

  • 点击左下角启动网络
  • 勾选开机时自动启动
  • 点击应用

这几步图形界面操作,对应的管理命令应该是

default虚拟网络,用的virbr0网卡。

By the way, Kubernetes已经有项目将KVM libvirt集成了,名为kubevirt。有个录屏效果。

在请求virt-manager、virsh等系统管理时,每台虚拟机都会由libvirtd启动一个独立的qemu-kvm进程。

虚拟机的属性如CPU,内存,I/O设备配置都在/etc/libvirt/qemu/下、libvirtd通过读取XML配置文件,获取传给qemu-kvm的参数列表。

以ubuntu14.04.xml为例

default网络XML

Origin Pro 2018C 使用技巧(1)

之前写的论文录用了,要发表了。编辑通知修改,这是第4次修改了。记录一下这次碰到的Origin 绘图使用技巧。

修改坐标轴刻度的朝向

  1. 双击坐标轴,如X轴
  2. 选择标题和样式
  3. 组刻度和次刻度都要朝内

调整刻度朝向

避免数据点的标签重叠

修改某个数据点的标签,按住Ctrl,双击该点

饼状图的引导线

  1. 设置超过0%显示引导线
  2. 勾选直线、线宽等信息

饼状图的引导线绘制