c********p 发帖数: 1969 | 1 难道又是jvm的问题?
我用的java。。。求java版的 |
l*****a 发帖数: 14598 | 2 第二行是中文?
我咋看不懂
【在 c********p 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 难道又是jvm的问题? : 我用的java。。。求java版的
|
t**********h 发帖数: 2273 | 3 你老高考语文是不是没及格啊?
第二行明显是中文英文混合啊
【在 l*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第二行是中文? : 我咋看不懂
|
c********p 发帖数: 1969 | 4 求java代码
【在 l*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第二行是中文? : 我咋看不懂
|
z****e 发帖数: 54598 | 5 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);
}
}
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;
}
} |
t**********h 发帖数: 2273 | 6 onsite半小时能写完么?这题
end
HashSet
【在 z****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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: >();
|
s*******n 发帖数: 305 | 7
同问, 有的题真的写出来不短的说。。。
【在 t**********h 的大作中提到】![](/moin_static193/solenoid/img/up.png) : onsite半小时能写完么?这题 : : end : HashSet
|
z****e 发帖数: 54598 | 8 白板,没有ide,没有任何提示,就算写完了也是一堆bugs
这题考到了,估计就是看思路,思路对,能写个大概,应该就给过了吧
【在 t**********h 的大作中提到】![](/moin_static193/solenoid/img/up.png) : onsite半小时能写完么?这题 : : end : HashSet
|
c********p 发帖数: 1969 | 9 我的跑不过的。。。
import java.util.*;
public class Solution {
public ArrayList> findLadders(String start, String end
, HashSet dict) {
// Start typing your Java solution below
// DO NOT write main() function
ArrayList> ret = new ArrayList>(
);
if(dict.isEmpty()){
return ret;
}
int len = 1;
int len2 = 0;
Queue q = new LinkedList();
HashSet visited = new HashSet();
q.add(start);
// visited.add(start);
Queue> qlist = new LinkedList>();
ArrayList first = new ArrayList();
first.add(start);
qlist.add(first);
boolean flag = false;
while(!q.isEmpty()){
String st = q.poll();
ArrayList arrlist = qlist.poll();
len--;
if(st.equals(end)){
flag = true;
ret.add(arrlist);
}else{
ArrayList list = getWord(st);
for(String cur : list){
boolean f = true;
for(int k = 0; k < arrlist.size(); k++){
if(cur.equals(arrlist.get(k))){
f = false;
break;
}
}
if(dict.contains(cur) && f){
q.add(cur);
// visited.add(cur);
ArrayList temp = new ArrayList(arrlist);
temp.add(cur);
qlist.add(temp);
len2++;
}
}
}
if(len == 0){
if(flag == true){
return ret;
}
len = len2;
len2 = 0;
}
}
return ret;
}
public ArrayList getWord(String st){
ArrayList ret = new ArrayList();
int length = st.length();
char[] ch = st.toCharArray();
for(int i = 0; i < length; i++){
for(int j = 0; j < 26; j++){
ch[i] = (char)('a' + j);
ret.add(new String(ch));
ch = st.toCharArray();
}
}
return ret;
}
}
【在 z****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 白板,没有ide,没有任何提示,就算写完了也是一堆bugs : 这题考到了,估计就是看思路,思路对,能写个大概,应该就给过了吧
|
z****e 发帖数: 54598 | 10 为什么要用q啊?
通过hashcode查找效率是o(1),用o(n)做什么?
end
>(
【在 c********p 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我的跑不过的。。。 : import java.util.*; : public class Solution { : public ArrayList> findLadders(String start, String end : , HashSet dict) { : // Start typing your Java solution below : // DO NOT write main() function : ArrayList> ret = new ArrayList>( : ); :
|
c********p 发帖数: 1969 | 11 你是说哪个q啊,我用了2个q。。。。
【在 z****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 为什么要用q啊? : 通过hashcode查找效率是o(1),用o(n)做什么? : : end : >(
|
z****e 发帖数: 54598 | 12 不是bfs不要用q
【在 c********p 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你是说哪个q啊,我用了2个q。。。。
|
c********p 发帖数: 1969 | 13 哦你说的是我第2个q吧?
就是放路径的那个q。
【在 z****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不是bfs不要用q
|