标签归档:计算机

Dropbox And Google

两段新闻

Dropbox的成功大部分归功于 Python,这个语言可以使我们快速迭代开发。然而,为了支持日益增长的用户量,我们的基础设施日渐成熟,这时我们开始寻找一种更为高效的方式来改变系统规模。大约在一年前,我们作出决定,把对于性能要求很苛刻的后台部分从Python迁移到了Go语言,以提供更好的并发支持和更快的运行速度。一个规模很小的工程师团队做出了大量的努力,这背后大约是200,000(二十万)行Go语言代码。此时,我们成功地把架构的大部分迁移到了Go语言。

还记得 朱老师谈到未来的计算模式,是无限输入(输入不会停止,如互联网数据)的。今年的Google I/O大会上,宣布 Google已停用MapReduce计算模式(框架),改用 Cloud Dataflow。“Cloudflow 处理整个数据流,而MapReduce 处理单一的流”。具体参见下面 引用。

新的事物总是层出不穷。。。 加油

Dropbox 来自 http://blog.jobbole.com/71414/

Google 来自 http://blog.jobbole.com/72145/

Use SSH Secure Shell login QingCloud

在青云上创建主机后,为了安全,平台默认使用公私钥的方式登录主机。

青云 ssh设置的方法参考 http://www.chenshake.com/page/8/

设置好后,可以从网站上下载一个私钥文件。这个私钥文件是OpenSSH格式的,SSH Secure Shell和 Putty 客户端无法使用。因为 SSH Secure Shell只能使用SSH格式,用不了 OpenSSH格式,需要转换并导入。

解决办法如下:

1 下载一个工具 puttygen 

2 运行puttygen , 点击load按钮,导入从青云上下载的私钥文件

如果给Putty用,点击“Save Private key” ,保存为 newfile.ppk ,然后通过该文件来使用putty

如果给 SSH Secure Shell用,点击菜单栏的 “Conversions”,然后 “export ssh.com key”, 会生成一个私钥文件,文件名自己取 如 newsshfile. 生成好后,还需要一个公钥文件。点击界面上的 “Save public key” 即可生成一个 公钥文件。注意文件名为 刚才的私钥文件名后面加.pub后缀, 如 newsshfile.pub.  公私钥文件要放在同一个文件夹。

3 打开 SSH Secure Shell , 点击菜单栏的 Edit,子菜单 Settings,然后是 Global Setting下的User Authentication下的Keys项,打开后 点击 “Import”按钮,选择 newsshfile.pub 文件 即可 导入。

4 登录,选择 public key即可。

ps:

收费软件 XShell 直接支持 OpenSSH 和 SSH两种格式。

Linux下登录根本不用考虑该问题。。。 ssh -i private_file username@host 即可

参考:

http://unix.stackexchange.com/questions/84060/convert-openssh-private-key-into-ssh2-private-key

使用python启动一个最简单的web服务器

【1】从官网下载python的安装包  https://www.python.org/downloads/ (有两个版本 python2, python3)

【2】进入到文件(文件夹)所在的目录,打开一个命令行窗口

python2 :  python -m SimpleHTTPServer 8080

python3:  python -m http.server [8000]

【3】打开浏览器即可访问 localhost:8080/path/to/staticfile

html5 and file upload

前段时间比较了各种计算文件摘要的算法,发现还是MD5和SHA1两个算法在低碰撞、高速率两方面做的好一点,一般来说选择MD5就可以了,SHA1慢一点。通过计算文件Hash不仅可以减少服务器的文件数,还可以加快用户上传文件的速度,可谓一举两得。但是由于HTML的原因,通过浏览器上传文件是需要在服务器计算该Hash值(除非使用插件)。不仅占用服务器资源,也造成服务器长时间无响应的“假死”状态。

通过HTML5的File API可以读取文件内容,Worker对象可以建立JavaScript线程,完美实现浏览器端文件Hash计算。例:https://md5file.com/calculator。而且,支持HTML5 Worker的浏览器还支持文件拖拽,具有非常好的用户体验。

对于公有云存储而言,是一个不错的选择。

PS:连JavaScript都有线程了,PHP什么时候会有了。。。。

sqlite

SQlite 作为 著名的 嵌入式 数据库,被广泛采用。OpenStack/Swift 就使用 sqlite作为元数据存储方式。(不过 由于对大数据处理出现丢失情况,正在考虑其他方案)。支持的语言、平台(操作系统)众多。对于数据量小的结构化数据不适为一个好的方案。

一、 工具

截止 目前(2014-1-7) 最新 sqlite 版本为 3.8。在 windows操作系统, 除了官网提供的命令行工具,还有一些开源/免费的GUI工具。如 SQLite Expert(个人版)、Sqliteadmin、SQLite Database Browser、SQLiteSpy。

sqlite expert 需要安装。支持 unicode。

sqliteadmin 绿色版(免安装),不支持 unicode,数据库文件路径含有中文字符是会打开失败。

sqlite database brower 绿色版,支持 unicode。

sqlitespy 绿色版,支持 unicode。小而精巧,个人比较喜欢这个软件。要是支持文件拖拽就好了,毕竟写路径比较麻烦。

综上: 推荐 使用 SQLite Database Browser 。下载地址:http://sourceforge.net/projects/sqlitebrowser/

sqlitespy 下载地址:http://www.yunqa.de/delphi/doku.php/products/sqlitespy/index

二、元数据

python 中包含 sqlite的标准库。所以可以直接使用python来操作sqlite数据库。

除了操作表记录外,有时我们也需要查询表结构等元数据信息,这些信息保存在 sqlite_master 表中。 包含5个字段(参考2):type 类型名 如 table、index等;name 名字(表名、索引名等);tbl_name 表名; rootpage 结构的页号; sql 存储对应的sql语句。

Python 代码:

 

参考:

http://www.oschina.net/news/43608/5-popular-and-free-sqlite-management-tools

http://www.sqlite.org/fileformat2.html

Swift Object Storage

分布式存储系统 有几个重要功能 features:

1 集群管理
2 名字空间
3 分布与查找
在详细讨论之前,先引入几个基本概念。
node, drive , device, disk , backend 这几个出现在好多文档里面。它们都是一个意思。简称 dev. 即指一块磁盘,也就是 挂载在 /srv/node 下的目录。因为 这些 目录即挂载点分别对应着一个磁盘。当然也可以将一个物理磁盘划分为多个分区,挂载在/srv/node下的多个目录。或者是 /srv/[num]/node 目录下。注意与物理主机节点相区别,有时也会用Node。
partition ,指一致性哈希中vnode,也就是 虚结点,简称 part。
replica,副本,也就是 一份数据或对象的多份拷贝,但是各个拷贝的副本号不同。
1 集群管理
   先介绍一下,主机架构。swift集群中分为 proxy主机和 storage主机。当然一个主机也可以同时具有这两种角色。
   如下图:
          
注意 图中 的 Node 和上面 提到的不是一个意思,指的是 Host,即物理主机节点。
一个集群 可以 有 多个 proxy ,在 多个 proxy间 负载 ,可以使用 LVS 或 f5 等 各种 软硬件方式。
下面讨论 devices 的管理。
  swift 采用 分层 tier 管理所有的dev。
   在1.8.0 即 H版 中  加入region 概念。也就是 区域,来支持一个全球的swift集群。
   然后是 zone ,是 node 的一个集合,可以是 几台 物理主机,或 一个 机架 或 一个机房,甚至一个数据中心。
   然后是 物理主机 Host。
   最后是 物理设备 即 dev。
   如下所示: 来源 swift/swift/common/ring/utils.py
    Example:

region 1 + zone 1 + 192.168.101.1:6000 + device id 0
               |                     |                                        |
               |                     |                                        + device id 1
               |                     |                                        |
               |                     |                                        + device id 2
               |                     |
               |                     + 192.168.101.2:6000 + device id 3
               |                                                               |
               |                                                               + device id 4
               |                                                               |
               |                                                               + device id 5
               |
               + zone 2 + 192.168.102.1:6000 + device id 6
                                    |                                        |
                                    |                                        + device id 7
                                    |                                        |
                                    |                                        + device id 8
                                    |
                                    + 192.168.102.2:6000 + device id 9
                                                                              |
                                                                              + device id 10

region 2 + zone 1 + 192.168.201.1:6000 + device id 12
                                     |                                        |
                                     |                                        + device id 13
                                     |                                        |
                                     |                                        + device id 14
                                     |
                                     + 192.168.201.2:6000 + device id 15
                                                                               |
                                                                               + device id 16
                                                                               |
                                                                               + device id 17

从上面可以看到, 每一个 dev 都有 一个 全局(整个集群)唯一的ID。在 分配 part 的 replicas 时 会尽可能将 不同的region或zone上,官方文档 原文 (来源 github/CHANGELOG ):
The ring builder now supports as-unique-as-possible partition
      placement, unified balancing methods, and can work on more than one
      device at a time.
该变化 在 1.5.0 即 F版中,在 F版之前,同一个part的各个replica 不能在 一个 zone 中。因为 一个 dev只能在一个zone中,所以 不同的zone肯定意味着不同的device。
刚才 提到了 part 的 replica,part 也就是 vnode 是 虚结点。所有的数据 都存储在虚结点中,每个数据都有一个数据ID(通常是 HASH)。一个数据ID 被 映射到 一个 vnode 上,因为 每个 vnode 有多份,所以 每个数据也就有多份。此处 可以参见 源代码文件 swift/swift/common/ring/builder.py
 在 类 RingBuilder 有一个重要的属性 _replica2part2dev, 申明如下
                  # _replica2part2dev maps from replica number to partition number to

        # device id. So, for a three replica, 2**23 ring, it's an array of
# three 2**23 arrays of device ids (unsigned shorts). This can work a
# bit faster than the 2**23 array of triplet arrays of device ids in
# many circumstances. Making one big 2**23 * 3 array didn't seem to
# have any speed change; though you're welcome to try it again (it was
# a while ago, code-wise, when I last tried it).
self._replica2part2dev = None

  使用时,如下(文件同上):
                 dev_id = self._replica2part2dev[replica][part]
另外,replica 还可以是个大于1的小数。来源如下 类 RingBuilder:
  方法: __init__ 中
                 if replicas < 1:

            raise ValueError("replicas must be at least 1 (was %.6f)"
% (replicas,))

  方法: _adjust_replica2part2dev_size 中
                 “”

        Make sure that the lengths of the arrays in _replica2part2dev
are correct for the current value of self.replicas.

Example:
self.part_power = 8
self.replicas = 2.25

self._replica2part2dev will contain 3 arrays: the first 2 of
length 256 (2**8), and the last of length 64 (0.25 * 2**8).

Returns a 2-tuple: the first element is a list of (partition,
replicas) tuples indicating which replicas need to be
(re)assigned to devices, and the second element is a count of
how many replicas were removed.
"""

也就是 说 在 二维数组 _replica2part2dev 中 首先是 不同的 replica 的 part。然后是 part 与 dev 的映射。因为 replica 可能为小数,所以 每个 part的 replica 数是不一样的。准确的说,part号小的replica多。因为是用 列表保存的映射关系 也就是 数组下标是part号,值是dev的ID。下标从0开始的。
综上: 集群中共有 2^part_power 个 part,标号 为 0 ~ 2^part_power-1 。
            因为 replica的原因 part 与 dev 是一个 多对多的关系。也就是 一个 part 会保存到多个dev上。
            一个对象(数据)对应一个part,一对多的关系。
            part的数目是固定的,也就是 集群一旦建立是不能改变的。
            变化的是 dev,所以要改变part与dev的映射。详细 内容 参考 builder.py 文件。
附:根据 deploy_guide , 虚结点个数 最好为 未来最大物理磁盘设备数的100倍。如下所述:

The first step is to determine the number of partitions that will be in the ring. We recommend that there be a minimum of 100 partitions per drive to insure even distribution across the drives. A good starting point might be to figure out the maximum number of drives the cluster will contain, and then multiply by 100, and then round up to the nearest power of two.

For example, imagine we are building a cluster that will have no more than 5,000 drives. That would mean that we would have a total number of 500,000 partitions, which is pretty close to 2^19, rounded up.

It is also a good idea to keep the number of partitions small (relatively). The more partitions there are, the more work that has to be done by the replicators and other backend jobs and the more memory the rings consume in process. The goal is to find a good balance between small rings and maximum cluster size.

The next step is to determine the number of replicas to store of the data. Currently it is recommended to use 3 (as this is the only value that has been tested). The higher the number, the more storage that is used but the less likely you are to lose data.

It is also important to determine how many zones the cluster should have. It is recommended to start with a minimum of 5 zones. You can start with fewer, but our testing has shown that having at least five zones is optimal when failures occur. We also recommend trying to configure the zones at as high a level as possible to create as much isolation as possible. Some example things to take into consideration can include physical location, power availability, and network connectivity. For example, in a small cluster you might decide to split the zones up by cabinet, with each cabinet having its own power and network connectivity. The zone concept is very abstract, so feel free to use it in whatever way best isolates your data from failure. Zones are referenced by number, beginning with 1.

2 名字空间
    swift上有 account,container,object 三种类型的对象。
    有 记录 account , container,object 的 元数据文件,记录 object 内容的 数据文件。
    元数据文件 为 sqlite格式的db文件,数据文件 为 原始数据流保存的字节文件,.data结尾。
    data 文件 的 保存路径:
        dev_dirpath/dev/type_name/partition/suffix_path/name_hash/filename
       dev_dirpath 是 dev 挂载点的目录,一般 为 /srv/node ,写在配置文件 object-server.conf 中
       dev 挂载目录名,如 sdb1,sdb2 等, 在 用 swift-ring-builder 添加 device时 会用到
        type_name 即 类型名,上面提到的三种 data文件属于 object,故为 object
        partition 即 分区号,也就是 该 文件 被分到的  part。
                    因为 part的数目是2的次方,所以可以直接使用移位来计算。
                    代码 ( 文件 swift/swift/common/ring/ring.py):
                         def get_part(self, account, container=None, obj=None):

        """
Get the partition for an account/container/object.

:param account: account name
:param container: container name
:param obj: object name
:returns: the partition number
"
        Get the partition for an account/container/object.
        :param account: account name        :param container: container name        :param obj: object name        :returns: the partition number        """        key = hash_path(account, container, obj, raw_digest=True)        if time() > self._rtime:            self._reload()        part = struct.unpack_from('>I', key)[0>> self._part_shift        return part

       suffix_path 即 计算出来的 name_hash 的 后 3位。
       name_hash 即 hash_path 计算出来值
       filename 不同的 文件方法 不一样,对于 data文件 使用 时间戳加上后缀即扩展名。
                        对于元数据文件一般是name_hash加上 .db。
      例如:
/srv/node/sdb1/objects/109486/8fd/c7a68547b5aefe34c3e1371bcebbb8fd/1381454264.75078.data
/srv/node/sdb1/accounts/47305/82a/3323e66c399c5f6230030e493e6b082a/3323e66c399c5f6230030e493e6b082a.db
account,container,object的名字:
  account 长度 对于 UTF8 编码和URL Encode,不操过 256 字节,最好不要包含冒号。
  container 长度同上,不能包括 斜杠 即 /
  object 长度 对于 UTF8编码和 URL Encode 不操作 1024 字节,可以包含 斜杠 /
另外:系统在 大文件分片上传时,会自动创建一个 contianer,名字为 原container名加上  _segments 用来保存各分片对象。
因为 swift 是 对象 存储,所以是 不支持 目录的。不过 swift支持前缀查询,所以可以指定 一部分 前缀来 当作目录。如
   object        d/a/c.txt
   object        d/a/1/2.txt
   object        s/5
 上面三个 object 中 前两个 有同样的前缀 d/a/ ,故而 可以当作在同一个目录下。也就是 在 list object时 使用 prefix参数。
  格式: GET /<api version>/<account>/<container>[?parm=value]
所以:理论上限 为 8^256 个 account,8^512 个 container ,8^1536 个 object。
           每个 account 有 8^1270 个 object。
3  分布与查询
     节点分布 : 集群信息保存在 ring 文件中。ring 文件 维护了 part 到 节点的映射。
     文件分布 :  每个 account 都有一个自己独立的元数据文件。account中保存账户信息和 container 列表。
                           container 元数据文件 保存 object 列表。
                          元数据文件 保存了 与用户有关的,如名字等的元数据信息。
                          元数据文件内容 可以参考【牛皮糖】, 或 源文件 swift/swift/account/backend.py 旧版本在 swift/swift/common/db.py
    分布时,首先将 文件 根据 HASH 得到的 ID映射到 集群中的 part,然后根据part找到所有replica,再 以 replica号 和 part 号 从 ring 文件中 找到 dev_id 和 dev 信息。完成 数据文件 的 分布,并写入到 元数据文件中。
    查询时,直接 查找 元数据文件。而元数据文件的位置根据 分布算法 和 ring文件 即可找到。
   注意: swift 的 客户端 是没办法 计算 元数据文件的位置的。也就是 swift 客户端不能直接和 storage host 通信。
References:
swift 官方文档 github, deploy_guide , develop_guide , administrator_guide : http://docs.openstack.org
swiftstack :  http://swiftstack.com/
gholt(swift core developer): http://greg.brim.net/
launchpad/swift:     https://launchpad.net/swift
Google: google
others: www.chenshake.com ,http://www.openstack.cn  。。。
对以上组织或个人,以及其他没有写上的 表示感谢!
=======================================
swift 看了 好久, 前些时间 都是 零零碎碎的,其实现在也是,整理了些笔记,没有写 博客。由于每次查找资料 都有找到网上的博客。所以也整理一份。顺便自己也理一理。只要是 数据文件是如何 保存在 集群上的。一致性 和 容错方面没有提到。可以查看上面参考的资料。

 

肖微

2013 年 12 月 4 日

肖微

开源的世界,也有很多奇怪的事情。记得前些天面试还被问到异步编程,虽然用的不多,但是还是了解过libev,libevent ,libuv 这几个库。今天看微博,看到 nodejs 和 libuv 的 核心开发人员,最大贡献者之一:Ben Noordhuis 被迫 离开。原因 是 某个人修改了 源码的注释 从 him 改为 them,commit 注释如下。被 Ben 拒绝了 pull request 请求,理由是该提交带来的麻烦大于其价值,详细内容见下面链接。然后 项目管理者 joyent 不满意。。。然后 。。。。最后就这样(Ben 宣布离开这两个项目)了。nodejs发表公告表示感谢ben的贡献,遗憾 他的离开。

Removed use of gendered pronoun

具体文件修改内容 参见:https://github.com/joyent/libuv/pull/1015/files

Ben Noordhuis 本人的 说明:https://github.com/joyent/libuv/pull/1015#issuecomment-29568172

Nodejs 的 公告:http://blog.nodejs.org/2013/12/03/bnoordhuis-departure/

某个网站的讨论:https://news.ycombinator.com/item?id=6845286

我想这会伤很多开源贡献者的心吧。。。。

想起大学讲计算机仿真的老师的话,大意:开源无疑是未来主流,但是开源没有保障的服务,所以商业软件依然会存在下去。。。。 哎 , 就这样 因为 “ 性别” 的原因 。。。。

农历日历 我的周六

又一次想起农历的日历系统,这次是用python。
网上下了个Python的阳历和阴历转换的程序(代号ccal),为了验证正确性,于是有了这篇日志。
计划,先从网上找靠谱的日历统计已有数据对比。
感觉 中国科学院国家授时中心的 时间科普网的在线万年历 应该比较靠谱。
首先分析了下时间科普网站的日梭万年历网络版,其JS被压缩优化。
并且在chrome和IE下不能执行,语法错误。要使用IE兼容模式才可以。
看了下代码,找出了一些JS函数,分析了HTML结构。但是实在难以统计。
想到 Google日历也显示农历,于是爬取Google日历数据。
计划 先统计基本信息,再弄好数据进行对比。
Google 日历 从 2000年 到 2050 年有显示农历数据。
先用 JS 在 chrome 的 console 中 把数据 从 HTML中简单解析出来。
然后 再保存数据到文本中 用 python 解析为日期。
悲剧的是 从网上下的Python程序即ccal是基于 python2,而且 空格 和 Tab 不分,执行不了。
于是 伤心了。开始 思考 如何 有效的对比。对比的关键自然是农历数据。
只好只保存ccal的农历数据,自己解析。突然想到,QQ 日历也是有农历数据的。
虽然 QQ 网站的 JS 也是 被压缩过的,但 只要语法没问题,可以格式化 解析,以前就分析过QQ的JS。比较好弄。
果然,用 chrome 没到1分钟,就找到了 QQ 日历的农历数据。
简单的分析了下JS代码,两者保存农历数据的格式是一致的,只要对比大小 就可以了。
对比发现 有4处不同,分别是农历的1916年、1954年、1956年和1978年的数据 有差异。
谁是错的呢? 自然 查找第三方,人工检索 在线万年历。
如果 手头有本万年历也不错,但印刷也有可能出错。
这个东西 采取 少数服从多数比较好,大家总不会错的一样的吧。后面发现还真有可能~ ,错的人多了 就三人成虎。。。 真理在少数人手中吗?还是先对比数据。
首先 看了下 百度APP 万年历,Nokia的 日历 和 网易邮箱日历(只对比不同之处):
公历1916年1月1日 是 农历1915年冬月二十六日。农历年从公历1916年2月3日到1917年1月22日。
从数据分析有:NETEase 与 QQ 完全相同
农历1916年数据 APP与QQ相同 , Nokia 与 QQ相同
农历1954年数据 APP与ccal相同, Nokia 与 ccal相同
农历1956年数据 APP与ccal相同, Nokia 与 ccal相同
农历1978年数据 APP与ccal相同, Nokia 与 ccal相同
既然 这样 只好 去看 时间科普网站, 发现与 APP,Nokia是相同的。初步认为 这几个是靠谱的。所以。。。其他的就是错的。。。
网易和腾讯错都错的一样,谁抄谁的呢?哈哈。。。不知道
相比之下ccal只错了一个还是很靠谱的。赞一个,特此链接:http://cxterm.sourceforge.net/ccal.html
数据 和 相关代码,整理后 会 发到 github网站上,按 python, javascript ,Java,PHP 的 顺序实现。
先实现基本日历转换,再加上 二十四节气、天干地支纪年法、十二生肖等。
对农历总算掌握了一部分数据,有空的时候再充到2100年。

BTW,因为google的JS和HTML混在一起,弄不清,也不好设断点,只好直接AJAX翻页,然后解析HTML。
还是 灰常感谢 Google 没有屏蔽我,虽然 每次间隔2秒,但也集中请求了600次。
NETEase 的 JS 写的像教科书一样,很好阅读,只进行了压缩,没有进行代码混淆处理。农历日历系统还用了单例模式。卡哇伊~~~

最小操作数

来自互联网,难度等级4,较难

题目详情
给了A、B两个单词和一个单词集合Dict,每个的长度都相同。我们希望通过若干次操作把单词A变成单词B,每次操作可以改变单词中的一个字母,同时,新产生的单词必须是在给定的单词集合Dict中。求所有行得通步数最少的修改方法。

举个例子如下:
Given:
A = “hit”
B = “cog”
Dict = [“hot”,”dot”,”dog”,”lot”,”log”]
Return
[
[“hit”,”hot”,”dot”,”dog”,”cog”],
[“hit”,”hot”,”lot”,”log”,”cog”]
]

即把字符串A = “hit”转变成字符串B = “cog”,有以下两种可能:
“hit” -> “hot” -> “dot” -> “dog” -> “cog”;
“hit” -> “hot” -> “lot” -> “log” ->”cog”。
答题说明

A和B相同的情况下不需要做转换,此时直接返回空集;
main函数是为方便你在提交代码之前进行在线编译测试,可不完成。

思路 :分析问题的本质, 单词连线即可得到一个无向 无权图,问题即是求图中两个节点的所有最短路径。因为最短路径 很容易想到 广度优先,或者 Dijstra算法。

① 分层搜索
② 逐层统计路径

广度优先,分层搜索,起始层 为 start 节点,下一层为上一层 所有节点 一步变化 可以得到 的 所有节点。直到 没有节点剩余,或已经可以变成end节点 结束 分层遍历。
由于 在计算路径时 要使用 前一层的节点的路径,则需要 保存 被转化关系。如 单词A 转化到单词B 即 B的前一个节点为A。即保存B由A转化,可以由多个单词转化而来。
这样, 遍历 刚才得到的 层,从start节点,到层中每个节点的路径,为该节点的所有被转化的节点的路径 加上自己。

Python:

 

java 源码 见 http://www.cnblogs.com/i2u9/p/min_op_numbers.html

数组排序,求交换次数

原题 来自 庞果网 http://hero.pongo.cn/Question/Details?ID=94&ExamID=92 ,难度等级 容易。开发语言:C++,Java

题目详情

给定一个包含1-n的数列,我们通过交换任意两个元素给数列重新排序。求最少需要多少次交换,能把数组排成按1-n递增的顺序,其中,数组长度不超过100。

例如:

原数组是3,2,1, 我们只需要交换1和3就行了,交换次数为1,所以输出1。

原数组是2,3,1,我们需要交换2和1,变成1,3,2,再交换3和2,变为1,2,3,总共需要的交换次数为2,所以输出2。

代码如下:

 

思路:

首先,如果某个数字在正确的位置 ,肯定 不用 交换了。然后 剩余的数字,肯定 可以通过相互交换 排好顺序。要交换次数最少,就要 将 最好占据 各自位置的数字 交换。这样 可以最快达到目的。

比如 4 , 3,1,2 交换次数 比 2,1,4,3 要多。前者 整个数字参与相互交换,而后者 是分割成两部分 相互交换即可。

如果 我们把 交换的索引作为节点,交换作为有向边,则可构成一个图。每次找图中边最少的环。因为环内的数字 可以通过交换 达到 最终位置。每次 找到后 从图中 删除 这些 节点 和 这些节点的边。从而找到所有的交换路径。

步骤:

1 通过对比排序后的数据,先将排序前 要移动的元素的索引,和可以放置的位置找出来。

2 以 这些 待 排序的 索引 为节点,以 目前元素的索引为出发点和目的索引为终结点 构成边。构成图

3 从图中 找 构成环 且 边最少的 节点,统计每个环中节点的个数。

3.1  BFS 计算 每个 节点 到 其他 节点的 最短路径,找出 每个 节点 所在的 最短环 (肯定每个节点至少有一个环)

3.2 对得到的环 排序 (有重复的,只是开始 查找的节点不一样)

3.3 对这些环进行统计,但每个已统计过的环中的节点,所在的其他环 忽略

4 交换 次数 记为 所统计过的环的节点数和 减去 统计的环的个数

或者 每个统计的环的节点数减一之和

开始 是用Python写的,但题目要求 选C++ 或 Java。。。。

如果 有好思路 欢迎 交流