z****e 发帖数: 54598 | 1 这题也够坑爹的
public class Solution {
public ArrayList> findLadders(String start, String end
, HashSet dict) {
// Start typing your Java solution below
// DO NOT write main() function
dict.add(start);
dict.add(end);
HashMap> routs = new HashMap
>();
this.generateRouts(dict, routs);
ArrayList> result = new ArrayList
>>();
LinkedList queue = new LinkedList();
queue.add(new Node(null, 0, start));
int previousLevel = 0;
Map visited = new HashMap();
while(!queue.isEmpty()){
Node node = queue.pollFirst();
if(node.val.equals(end)){
if(previousLevel == 0 || node.level == previousLevel){
this.generateResults(node, result);
}else{
break;
}
}else{
Set values = routs.get(node.val);
if(values == null || values.size() == 0) continue;
Set removeSet = new HashSet();
for(String value:values){
if(visited.containsKey(value)&&node.level+1>visited.get(
value)){
removeSet.add(value);
}else{
queue.add(new Node(node, node.level+1,value));
visited.put(value,node.level+1);
if(routs.containsKey(value)) routs.get(value).remove
(node.val);
}
}
values.removeAll(removeSet);
}
}
return result;
}
private void generateResults(Node node, ArrayList>
result){
ArrayList list = new ArrayList();
while(node!=null){
list.add(0,node.val);
node = node.parent;
}
result.add(list);
}
public void generateRouts(HashSet set, HashMap
String>> routs){
for(String string:set){
char[] c = string.toCharArray();
for(int i=0;i
char old = c[i];
for(char t = 'a';t<='z';t++){
if(t==old) continue;
c[i] = t;
String temp = new String(c);
if(set.contains(temp)){
HashSet s = routs.get(string);
if(s == null){
s = new HashSet();
routs.put(string, s);
}
s.add(temp);
}
}
c[i] = old;
}
}
}
}
class Node{
Node parent;
int level;
String val;
public Node(Node parent, int level, String val){
this.parent = parent;
this.level = level;
this.val = val;
}
} | c********p 发帖数: 1969 | | c********e 发帖数: 186 | 3 米高兄给点解释?
end
【在 z****e 的大作中提到】 : 这题也够坑爹的 : public class Solution { : : public ArrayList> findLadders(String start, String end : , HashSet dict) { : // Start typing your Java solution below : // DO NOT write main() function : dict.add(start); : dict.add(end); :
| z***e 发帖数: 209 | 4 Mark,晚一点有时间也来写一下.
end
【在 z****e 的大作中提到】 : 这题也够坑爹的 : public class Solution { : : public ArrayList> findLadders(String start, String end : , HashSet dict) { : // Start typing your Java solution below : // DO NOT write main() function : dict.add(start); : dict.add(end); :
| z*******3 发帖数: 13709 | 5 这是新的代码
建 route 的时候,不从字典里面找,而是挨个替换字符串的char,换成其他char,组
建成新字符串,然后再去看字典里有没有,有的话,放到set里去,再把set放到map里
,每个pair表示从key string出发,能够转换的点的集合
然后从start开始找,用linkedlist,不用queue,queue是二叉树,效率低,用
linkedlist快,bfs都用linkedlist,先进先出,linkedlist的pollfirst效率高
然后建立一个类,node,这个node记录当前的string,以及上一个string,还有当前
路径长度
然后方法主体,每次把当前string对应的点取出来,然后看能走到那些点,挨个对比这
些点,看是不是end string,如果是,则表示找到,那就记录当前长度,因为还有可能
有相同长度的解,然后继续,如果不是end string,则查找visitedmap,看是否访问过
,如果访问过,比较当前路径长度跟上次访问的长度,如果上次访问的长度更短,则把
set里面这个node给移除,要不然会产生死循环,这里还要避开并发修改的问题,如果
跟上次访问的长度相同或者没有访问过,则把这些点加到queue最后,直到queue为空
感觉这题是leetcode oj里面最难的了,不过大oj不用jit就能过,这倒是比其他题要好点
public class Solution {
public ArrayList> findLadders(String start, String end,
HashSet dict) {
// Start typing your Java solution below
// DO NOT write main() function
dict.add(start);
dict.add(end);
HashMap> routs = new HashMap
String>>();
this.generateRouts(dict, routs);
ArrayList> result = new ArrayList
>();
LinkedList queue = new LinkedList();
queue.add(new Node(null, 0, start));
int previousLevel = 0;
Map visited = new HashMap();
while(!queue.isEmpty()){
Node node = queue.pollFirst();
if(node.val.equals(end)){
if(previousLevel == 0 || node.level == previousLevel){
this.generateResults(node, result);
}else{
break;
}
}else{
Set values = routs.get(node.val);
if(values == null || values.size() == 0) continue;
Set removeSet = new HashSet();
for(String value:values){
if(visited.containsKey(value)&&node.level+1>visited.get(
value)){
removeSet.add(value);
}else{
queue.add(new Node(node, node.level+1,value));
visited.put(value,node.level+1);
}
}
values.removeAll(removeSet);
}
}
return result;
}
private void generateResults(Node node, ArrayList>
result){
ArrayList list = new ArrayList();
while(node!=null){
list.add(0,node.val);
node = node.parent;
}
result.add(list);
}
public void generateRouts(HashSet set, HashMap
String>> routs){
for(String string:set){
char[] c = string.toCharArray();
for(int i=0;i
char old = c[i];
for(char t = 'a';t<='z';t++){
if(t==old) continue;
c[i] = t;
String temp = new String(c);
if(set.contains(temp)){
HashSet s = routs.get(string);
if(s == null){
s = new HashSet();
routs.put(string, s);
}
s.add(temp);
}
}
c[i] = old;
}
}
}
}
class Node{
Node parent;
int level;
String val;
public Node(Node parent, int level, String val){
this.parent = parent;
this.level = level;
this.val = val;
}
}
【在 c********e 的大作中提到】 : 米高兄给点解释? : : end
| z*******3 发帖数: 13709 | 6 这题用了pass by reference和linkedlist
最近讨论的几个topic这题里面做了一个小汇总,呼呼 | c********e 发帖数: 186 | 7 感谢啊!
【在 z*******3 的大作中提到】 : 这是新的代码 : 建 route 的时候,不从字典里面找,而是挨个替换字符串的char,换成其他char,组 : 建成新字符串,然后再去看字典里有没有,有的话,放到set里去,再把set放到map里 : ,每个pair表示从key string出发,能够转换的点的集合 : 然后从start开始找,用linkedlist,不用queue,queue是二叉树,效率低,用 : linkedlist快,bfs都用linkedlist,先进先出,linkedlist的pollfirst效率高 : 然后建立一个类,node,这个node记录当前的string,以及上一个string,还有当前 : 路径长度 : 然后方法主体,每次把当前string对应的点取出来,然后看能走到那些点,挨个对比这 : 些点,看是不是end string,如果是,则表示找到,那就记录当前长度,因为还有可能
| w**n 发帖数: 122 | 8 代码写这么长的,面试不太会考到吧。只有一小时而已
不好意思,顺便问问leetcode 129是什么意思?
题目没有序号啊
你们说的刷leetcode, 是主页上的70多道题,
leetcode.com
还是也包括discussion里的200多个问题
http://discuss.leetcode.com/
新手求指点
多谢!
【在 z*******3 的大作中提到】 : 这是新的代码 : 建 route 的时候,不从字典里面找,而是挨个替换字符串的char,换成其他char,组 : 建成新字符串,然后再去看字典里有没有,有的话,放到set里去,再把set放到map里 : ,每个pair表示从key string出发,能够转换的点的集合 : 然后从start开始找,用linkedlist,不用queue,queue是二叉树,效率低,用 : linkedlist快,bfs都用linkedlist,先进先出,linkedlist的pollfirst效率高 : 然后建立一个类,node,这个node记录当前的string,以及上一个string,还有当前 : 路径长度 : 然后方法主体,每次把当前string对应的点取出来,然后看能走到那些点,挨个对比这 : 些点,看是不是end string,如果是,则表示找到,那就记录当前长度,因为还有可能
| t****a 发帖数: 1212 | 9 楼主说的这题实际上是第127题
刚做了个clojure的解法,比java要短小很多。
可惜不能在leetcode上测试大数据,真心希望leetcode支持C/C++/Java以外的语言。
(defn word-map [dict]
(let [g (group-by first (for [word1 dict
word2 dict
:let [wd (word-dist word1 word2)]
:when (== wd 1)]
[word1 word2]))
ks (keys g)
vs (map (partial mapv second) (vals g))]
(zipmap ks vs)))
(defn word-dist [word1 word2]
(reduce + (map (fn [ch1 ch2] (if (= ch1 ch2) 0 1)) (vec word1) (vec word2)
)))
(defn next-step [path word-map]
(let [node (peek path)
neighbors (vec (clojure.set/difference (set (get word-map node)) (
set path)))
new-paths (map (partial conj path) neighbors)]
new-paths))
(defn batch-next-step [paths word-map]
(mapcat #(next-step % word-map) paths))
(defn bfs [start end dict]
(let [wm (word-map (concat dict [start end]))
bns #(batch-next-step % wm)
last-steps (first (drop-while (fn [paths]
(and (not (empty? paths))
(not (contains? (set (map peek
paths)) end)))) (iterate bns [[start]])))]
(filter #(= end (peek %)) last-steps)))
(bfs "hit" "cog" ["hot","dot","dog","lot","log"]) ; (["hit" "hot" "dot" "dog
" "cog"] ["hit" "hot" "lot" "log" "cog"]) | z*******3 发帖数: 13709 | 10 所以说某些人脑袋里就知道比代码行数
只有一个维度,哪里能比得上车板
人家好歹还有两个维度:安全和价格
【在 t****a 的大作中提到】 : 楼主说的这题实际上是第127题 : 刚做了个clojure的解法,比java要短小很多。 : 可惜不能在leetcode上测试大数据,真心希望leetcode支持C/C++/Java以外的语言。 : (defn word-map [dict] : (let [g (group-by first (for [word1 dict : word2 dict : :let [wd (word-dist word1 word2)] : :when (== wd 1)] : [word1 word2])) : ks (keys g)
| z*******3 发帖数: 13709 | 11 这题完全是用来对付leetcode用的
平常不太会写成这样
leetcode上的难度比面试时候要难,尤其是难题
当作练习蛮好
online judge,按照日期降序排列
第一题是最下面那题
【在 w**n 的大作中提到】 : 代码写这么长的,面试不太会考到吧。只有一小时而已 : 不好意思,顺便问问leetcode 129是什么意思? : 题目没有序号啊 : 你们说的刷leetcode, 是主页上的70多道题, : leetcode.com : 还是也包括discussion里的200多个问题 : http://discuss.leetcode.com/ : 新手求指点 : 多谢!
|
|