c********p
发帖数: 1969 | 1 难道又是jvm的问题？
我用的java。。。求java版的 |
l*****a
发帖数: 14598 | 2 第二行是中文？
我咋看不懂
【在 c********p 的大作中提到】
: 难道又是jvm的问题？
: 我用的java。。。求java版的
|
t**********h
发帖数: 2273 | 3 你老高考语文是不是没及格啊？
第二行明显是中文英文混合啊
【在 l*****a 的大作中提到】
: 第二行是中文？
: 我咋看不懂
|
c********p
发帖数: 1969 | 4 求java代码
【在 l*****a 的大作中提到】
: 第二行是中文？
: 我咋看不懂
|
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 的大作中提到】
: 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 的大作中提到】
: onsite半小时能写完么？这题
:
: end
: HashSet
|
z****e
发帖数: 54598 | 8 白板，没有ide，没有任何提示，就算写完了也是一堆bugs
这题考到了，估计就是看思路，思路对，能写个大概，应该就给过了吧
【在 t**********h 的大作中提到】
: 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 的大作中提到】
: 白板，没有ide，没有任何提示，就算写完了也是一堆bugs
: 这题考到了，估计就是看思路，思路对，能写个大概，应该就给过了吧
|
z****e
发帖数: 54598 | 10 为什么要用q啊？
通过hashcode查找效率是o(1)，用o(n)做什么？
end
>(
【在 c********p 的大作中提到】
: 我的跑不过的。。。
: 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 的大作中提到】
: 为什么要用q啊？
: 通过hashcode查找效率是o(1)，用o(n)做什么？
:
: end
: >(
|
z****e
发帖数: 54598 | 12 不是bfs不要用q
【在 c********p 的大作中提到】
: 你是说哪个q啊，我用了2个q。。。。
|
c********p
发帖数: 1969 | 13 哦你说的是我第2个q吧？
就是放路径的那个q。
【在 z****e 的大作中提到】
: 不是bfs不要用q
|
