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/
: 新手求指点
: 多谢！
|
|
