logo
Redian新闻
>未名空间
>PennySaver - 省钱一族
>
出售G家2段奶票
avatar
出售G家2段奶票# PennySaver - 省钱一族
b*z
1 楼
代码如下：
基本思路是，用queue 进行BFS，记录了每个node的parent，找到之后，通过parent来
recover path。感觉没有任何冗余计算啊！！！为什么过不了？
谢谢各位！！
import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;
public class Solution {
public List> findLadders(String start, String end, Set<
String> dict) {

List> res = new ArrayList>();
Set visited = new HashSet();

Queue queue = new LinkedList();
queue.add(new Wrapper(start, null));
queue.add(null);
boolean flag = false;
boolean find = false;

visited.add(start);
Set curLayer = new HashSet();

while (!queue.isEmpty()) {
Wrapper cur = queue.poll();
if (cur == null) {
if (flag || find) break;
queue.add(null);
flag = true;

visited.addAll(curLayer);
curLayer.clear();

continue;
}

flag = false;

List list = getAllNeighbours(cur.cur, dict, visited);
for (String itr : list) {
if (visited.contains(itr)) continue;
if (itr.equals(end)) find = true;
queue.add(new Wrapper(itr, cur));
curLayer.add(itr);
}
visited.addAll(curLayer);
}

if (find) {
for (Wrapper wrapper : queue) {
if (wrapper.cur.equals(end)) {
List temp = formPath(wrapper);
res.add(temp);
}
}
}

return res;
}

public static List getAllNeighbours(String s, Set dict,
Set visited) {
List res = new ArrayList();
for (int i = 0; i < s.length(); i++) {
for (char j = 'a'; j <= 'z'; j++) {
if (j == s.charAt(i)) continue;
StringBuilder builder = new StringBuilder(s);
builder.setCharAt(i, j);
String temp = builder.toString();
if (dict.contains(builder.toString())) {
if (visited.contains(temp)) continue;
res.add(temp);
}
}
}
return res;
}

public List formPath(Wrapper wrapper) {
List res = new ArrayList();
Wrapper cur = wrapper;
while (cur != null) {
res.add(cur.cur);
cur = cur.parent;
}
Collections.reverse(res);
return res;
}

public class Wrapper {
String cur;
Wrapper parent;
Wrapper(String cur, Wrapper parent) {
this.cur = cur;
this.parent = parent;
}
}
}
avatar
X*7
2 楼
出售/交换物品的名称:
GOOD START 2段奶票5$2张，
gerber果泥果汁零食coupon若干
物品类别（coupon：mfc等；血糖仪等）:
check
物品来源（报纸夹页，厂家邮寄等）:
厂家邮寄
可接受的价格（必须明码标价，必填）:
5折
邮寄损失方式哪方承担（若需邮寄，必填）:
买方负责
付款方式说明:
paypal
本贴有效期（必填）:
open until sold out
联系方式（例： 站内）:
站内
avatar
a*l
3 楼
TLE?我的也是，不同的版本，一个几周前过了，一个昨天的就没有。你可一先local
debug 一下。。。
avatar
P*L
4 楼
这个题用 Java 写很难过，但同样的算法 C++ 过很容易。

【在 b****z 的大作中提到】
: 代码如下：
: 基本思路是，用queue 进行BFS，记录了每个node的parent，找到之后，通过parent来
: recover path。感觉没有任何冗余计算啊！！！为什么过不了？
: 谢谢各位！！
: import java.util.ArrayList;
: import java.util.HashSet;
: import java.util.LinkedList;
: import java.util.List;
: import java.util.Queue;
: import java.util.Set;
avatar
b*z
5 楼

本地都是对的。但是不知道为什么过不了大数据

【在 a******l 的大作中提到】
: TLE?我的也是，不同的版本，一个几周前过了，一个昨天的就没有。你可一先local
: debug 一下。。。
avatar
b*z
6 楼

但是也看到有人 java过得，所以想问问是不是自己算法有问题

【在 P*******L 的大作中提到】
: 这个题用 Java 写很难过，但同样的算法 C++ 过很容易。
avatar
A*L
7 楼
这个事我以前开的帖子。
http://www.mitbbs.com/article_t0/JobHunting/32682961.html
代码如下：
public class Solution {
public class Ladder {//Define Ladder class it's important
public ArrayList parentList;
public String word;
public Ladder(String w, Ladder parent) {word=w; parentList = new
ArrayList(); parentList.add(parent);}
}
ArrayList> ladders=new ArrayList>();;
public ArrayList> findLadders(String start, String end
, HashSet dict) {
Ladder endLadder = new Ladder(end,null), startLadder=null;
Queue q = new ArrayDeque();
q.add(endLadder);//Here we look from end to start because we need to
reverse the output
int count=1,len = start.length(); //count the number of words for
each level
while(!q.isEmpty() && startLadder==null) {
HashMap map = new HashMap();
int cur=0;
for(int i=0;iLadder curLadder = q.poll();
for(int j=0;jof 26 letters
char[] wordChar = curLadder.word.toCharArray();
for(char c='a';c<='z';c++) {
wordChar[j]=c;
String s = new String(wordChar);

if(s.equals(start)) {//found
if(startLadder!=null) startLadder.parentList.add
(curLadder); // if this is not the first time found
else startLadder = new Ladder(start, curLadder);
}
else if(dict.contains(s) && !s.equals(curLadder.word
)) {//filter those not in dict
Ladder newLadder = new Ladder(s,curLadder);
q.add(newLadder);
map.put(s,newLadder);
cur++;// increase the number of nodes of the
next level
dict.remove(s);
}
else if(map.containsKey(s)) map.get(s).parentList.
add(curLadder); //Same level then reuse the revious existing
}
}
}
count=cur;
}
if(startLadder!=null) buildLadders(new ArrayList(),
endLadder, startLadder);
return ladders;
}
public void buildLadders(ArrayList list,Ladder end, Ladder cur) {
list.add(cur.word);
if(cur==end) ladders.add(new ArrayList(list));
else for(Ladder l:cur.parentList) buildLadders(list,end,l);
list.remove(list.size()-1);
}
}

【在 b****z 的大作中提到】
: 代码如下：
: 基本思路是，用queue 进行BFS，记录了每个node的parent，找到之后，通过parent来
: recover path。感觉没有任何冗余计算啊！！！为什么过不了？
: 谢谢各位！！
: import java.util.ArrayList;
: import java.util.HashSet;
: import java.util.LinkedList;
: import java.util.List;
: import java.util.Queue;
: import java.util.Set;
avatar
b*z
8 楼
代码如下：
基本思路是，用queue 进行BFS，记录了每个node的parent，找到之后，通过parent来
recover path。感觉没有任何冗余计算啊！！！为什么过不了？
谢谢各位！！
import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;
public class Solution {
public List> findLadders(String start, String end, Set<
String> dict) {

List> res = new ArrayList>();
Set visited = new HashSet();

Queue queue = new LinkedList();
queue.add(new Wrapper(start, null));
queue.add(null);
boolean flag = false;
boolean find = false;

visited.add(start);
Set curLayer = new HashSet();

while (!queue.isEmpty()) {
Wrapper cur = queue.poll();
if (cur == null) {
if (flag || find) break;
queue.add(null);
flag = true;

visited.addAll(curLayer);
curLayer.clear();

continue;
}

flag = false;

List list = getAllNeighbours(cur.cur, dict, visited);
for (String itr : list) {
if (visited.contains(itr)) continue;
if (itr.equals(end)) find = true;
queue.add(new Wrapper(itr, cur));
curLayer.add(itr);
}
visited.addAll(curLayer);
}

if (find) {
for (Wrapper wrapper : queue) {
if (wrapper.cur.equals(end)) {
List temp = formPath(wrapper);
res.add(temp);
}
}
}

return res;
}

public static List getAllNeighbours(String s, Set dict,
Set visited) {
List res = new ArrayList();
for (int i = 0; i < s.length(); i++) {
for (char j = 'a'; j <= 'z'; j++) {
if (j == s.charAt(i)) continue;
StringBuilder builder = new StringBuilder(s);
builder.setCharAt(i, j);
String temp = builder.toString();
if (dict.contains(builder.toString())) {
if (visited.contains(temp)) continue;
res.add(temp);
}
}
}
return res;
}

public List formPath(Wrapper wrapper) {
List res = new ArrayList();
Wrapper cur = wrapper;
while (cur != null) {
res.add(cur.cur);
cur = cur.parent;
}
Collections.reverse(res);
return res;
}

public class Wrapper {
String cur;
Wrapper parent;
Wrapper(String cur, Wrapper parent) {
this.cur = cur;
this.parent = parent;
}
}
}
avatar
a*l
9 楼
TLE?我的也是，不同的版本，一个几周前过了，一个昨天的就没有。你可一先local
debug 一下。。。
avatar
P*L
10 楼
这个题用 Java 写很难过，但同样的算法 C++ 过很容易。

【在 b****z 的大作中提到】
: 代码如下：
: 基本思路是，用queue 进行BFS，记录了每个node的parent，找到之后，通过parent来
: recover path。感觉没有任何冗余计算啊！！！为什么过不了？
: 谢谢各位！！
: import java.util.ArrayList;
: import java.util.HashSet;
: import java.util.LinkedList;
: import java.util.List;
: import java.util.Queue;
: import java.util.Set;
avatar
b*z
11 楼

本地都是对的。但是不知道为什么过不了大数据

【在 a******l 的大作中提到】
: TLE?我的也是，不同的版本，一个几周前过了，一个昨天的就没有。你可一先local
: debug 一下。。。
avatar
b*z
12 楼

但是也看到有人 java过得，所以想问问是不是自己算法有问题

【在 P*******L 的大作中提到】
: 这个题用 Java 写很难过，但同样的算法 C++ 过很容易。
avatar
A*L
13 楼
这个事我以前开的帖子。
http://www.mitbbs.com/article_t0/JobHunting/32682961.html
代码如下：
public class Solution {
public class Ladder {//Define Ladder class it's important
public ArrayList parentList;
public String word;
public Ladder(String w, Ladder parent) {word=w; parentList = new
ArrayList(); parentList.add(parent);}
}
ArrayList> ladders=new ArrayList>();;
public ArrayList> findLadders(String start, String end
, HashSet dict) {
Ladder endLadder = new Ladder(end,null), startLadder=null;
Queue q = new ArrayDeque();
q.add(endLadder);//Here we look from end to start because we need to
reverse the output
int count=1,len = start.length(); //count the number of words for
each level
while(!q.isEmpty() && startLadder==null) {
HashMap map = new HashMap();
int cur=0;
for(int i=0;iLadder curLadder = q.poll();
for(int j=0;jof 26 letters
char[] wordChar = curLadder.word.toCharArray();
for(char c='a';c<='z';c++) {
wordChar[j]=c;
String s = new String(wordChar);

if(s.equals(start)) {//found
if(startLadder!=null) startLadder.parentList.add
(curLadder); // if this is not the first time found
else startLadder = new Ladder(start, curLadder);
}
else if(dict.contains(s) && !s.equals(curLadder.word
)) {//filter those not in dict
Ladder newLadder = new Ladder(s,curLadder);
q.add(newLadder);
map.put(s,newLadder);
cur++;// increase the number of nodes of the
next level
dict.remove(s);
}
else if(map.containsKey(s)) map.get(s).parentList.
add(curLadder); //Same level then reuse the revious existing
}
}
}
count=cur;
}
if(startLadder!=null) buildLadders(new ArrayList(),
endLadder, startLadder);
return ladders;
}
public void buildLadders(ArrayList list,Ladder end, Ladder cur) {
list.add(cur.word);
if(cur==end) ladders.add(new ArrayList(list));
else for(Ladder l:cur.parentList) buildLadders(list,end,l);
list.remove(list.size()-1);
}
}

【在 b****z 的大作中提到】
: 代码如下：
: 基本思路是，用queue 进行BFS，记录了每个node的parent，找到之后，通过parent来
: recover path。感觉没有任何冗余计算啊！！！为什么过不了？
: 谢谢各位！！
: import java.util.ArrayList;
: import java.util.HashSet;
: import java.util.LinkedList;
: import java.util.List;
: import java.util.Queue;
: import java.util.Set;
avatar
m*2
14 楼
贴块砖，感觉是我见到的最容易理解好记的版本了
而且能够过最新的test （好多解法之前能过，最新的容易Memory超，感觉leetcode的
判断更严格了）
public class Solution {
public List> findLadders(String start, String end, Set<
String> dict) {
List> result = new ArrayList>();
if (start == null || end == null || start.length() != end.length() |
| dict.size() == 0) {
return result;
}

HashMap> visited = new HashMapHashSet>();
HashMap level = new HashMap();
Queue queue = new LinkedList();
HashSet path = new HashSet();
visited.put(start,path);
queue.offer(start);
level.put(start,1);
int min = Integer.MAX_VALUE;
dict.remove(start);
dict.add(end);

while (!queue.isEmpty()) {
String str = queue.poll();
for (int i = 0; i < str.length(); i++) {
char original = str.charAt(i);
for (char c = 'a'; c <= 'z'; c++) {
if (c != original) {
String newStr = replace(str,i,c);
if ((dict.contains(newStr) && !visited.containsKey(
newStr))
|| (visited.containsKey(newStr) && level.get(newStr)
> level.get(str))) {
if (visited.containsKey(newStr)) {
visited.get(newStr).add(str);
}
else {
HashSet path1 = new HashSet(
);
visited.put(newStr,path1);
path1.add(str);
level.put(newStr,level.get(str) + 1);
queue.offer(newStr);
}

if (newStr.equals(end)) {
if (level.get(str) < min) {
ArrayList entry = new ArrayList<
String>();
entry.add(end);
result.addAll(back_trace(str,visited,
entry));
min = level.get(str) + 1;
}
}

}
}
}
}
}
return result;
}

private String replace (String s, int i , char c) {
char[] ch = s.toCharArray();
ch[i] = c;
return new String(ch);
}

private ArrayList> back_trace(String s, HashMap, HashSet> visited, ArrayList path) {
ArrayList> result = new ArrayList>>();
ArrayList entry = new ArrayList(path);
entry.add(0,s);
if (visited.get(s).size() < 1) {
result.add(entry);
return result;
}
for (String ss: visited.get(s)) {
result.addAll(back_trace(ss,visited,entry));
}
return result;
}
}

【在 b****z 的大作中提到】
: 代码如下：
: 基本思路是，用queue 进行BFS，记录了每个node的parent，找到之后，通过parent来
: recover path。感觉没有任何冗余计算啊！！！为什么过不了？
: 谢谢各位！！
: import java.util.ArrayList;
: import java.util.HashSet;
: import java.util.LinkedList;
: import java.util.List;
: import java.util.Queue;
: import java.util.Set;
avatar
t*t
15 楼
我第一次做也是用了一个类似lz的wrapper class来记录状态然后TLE了，后来发现如果
是要记录之前状态的话可以用level order traversal的思路，queue里面放List<
String>，每次都针对List中最后一个String进行操作。在while循环内部用一
个for循环遍历一整层的节点，这样的话只需要一个HashSet来记录哪些点被访问过用来
去重就好，不需要针对每个路径专门记录。
avatar
d*n
16 楼
我一开始也没过。但是注意到不是所有parent都要记录。BFS里面同级之间的parent不
要记录，就可以了。
这是我写的python 解法。
#! /usr/bin/python
import collections
class Solution:
# @param start, a string
# @param end, a string
# @param dict, a set of string
# @return a list of lists of string
def findLadders(self, start, end, dict):
alphabet = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n',
'o','p','q','r','s','t','u','v','w','x','y','z']
dict = dict | set([end])
dict = dict | set([start])
level = 0
leveldict = {}
q = collections.deque()
q.append((start, level))
parent = {}
level = 0
leveldict = {}
parent[start] = []
visited = {}
leveldict[start] = 0
for s in dict:
visited[s] = 'W'
# BFS to build parent list
while q:
(s, level) = q.popleft()
visited[s] = 'D'
if s == end:
break
l = len(s)
for i in range(l):
for c in alphabet:
if s[i] != c:
stemp = s[:i] + c + s[i + 1:]
if stemp in dict and visited[stemp] == 'W': # if
first time see the node
visited[stemp] = 'G' # color the node as gray
q.append((stemp, level + 1)) # push the node
and its level to the queue parent[stemp] = [s] #
record its parent node leveldict[stemp] = level +
1 # record its level elif stemp in dict and visited[
stemp] == 'G': # if seen it again, but it is not finished (colored as black
if leveldict[stemp] == leveldict[s] + 1: # if its
level is one level more than the current level
parent[stemp].append(s) # add its new parent to its parentlist
else:
pass
# finish building parent list
return self.findLadders_dfs(start, end, parent)
def findLadders_dfs(self, start, end, parent):
'''DFS to get the path'''
if start == end:
return [[end]] # if start equals end, the path just contains one
element
res = []
if end in parent: # if end has parent
for p in parent[end]: # iterate through its parent
subres = self.findLadders_dfs(start, p, parent) #recursively
solve the smaller problem
for list in subres:
res.append(list + [end]) # concatenate to solve the
original problem
return res

【在 b****z 的大作中提到】
: 代码如下：
: 基本思路是，用queue 进行BFS，记录了每个node的parent，找到之后，通过parent来
: recover path。感觉没有任何冗余计算啊！！！为什么过不了？
: 谢谢各位！！
: import java.util.ArrayList;
: import java.util.HashSet;
: import java.util.LinkedList;
: import java.util.List;
: import java.util.Queue;
: import java.util.Set;
相关阅读
Share Amazon Prime Membership 至2/12/2016 $15 (转载)target 好像又贴新打折标了如果今天去JCP的可以去童装看看DOLLAR GENERAL有home kitchen 50% off的coupon问个很弱的问题，怎么拿到奶票？kmart可以Price Match吗？已发出：回馈省版，奉送一个coach oulet 实体店coupon。活跃的ID优先。Olay的精华Walmart Family Mobile Samsung Galaxy S III Cell Phone 这个国内可以用吗？nokia 520自带的卡哪里买一摞情人节卡片？娃学校要求给班里同学CVS 的Loreal revitalift volume filler这周价钱不错请问邮寄国内的香水润唇膏要交关税吗？东西就1件2件而已，不是那种整箱的有人用过瑞天快递寄东西到中国吗？usps包裹不见收到怎么办？Omron BP785N 10 Series Upper Arm Blood Pressure MonitorGPS？？？明天target的lindt打折吗包子求教staple感恩节买kindle返的staple 的debit卡，怎么用？请教Kohl's的code加到wallet后
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。