月度归档:2013年10月

最小操作数

来自互联网,难度等级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。。。。

如果 有好思路 欢迎 交流