亚麻Onsite

soupsoup88

xxw289 发表于 2019-5-4 03:57
楼主能讲下第二轮你用的循环是怎样的么？我只能想到O(nlogn)的做法。已加米！！！

请问O(nlogn)的做法是怎么样的啊，我只能想到暴力dfs.

xxw289

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

wsx247

楼主方便给timeline吗

soupsoup88

xxw289 发表于 2019-5-7 23:46
我的想法是存一个Map, 字母的话只存在单词中出现过的，这个map用了O(n + m)。然后建一个class叫LetterToC ...

后来问了下别人，好像也可以用最大匹配做，会比dfs复杂度低

yegou

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

sj1456

感谢楼主分享，第三轮没太看明白，大概意思是不是和leetcode上那个vertical遍历二叉树类似？

xxw289

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

yegou

xxw289 发表于 2019-5-9 07:45
要记录一下用过的硬币，用过的就不能用了。用一个boolean[] used标记己经用过的，后面poll出来的要是用过 ...

靠谱，是这么个道理！

害群之蚂蚁

public class Coin_Word_Backtracking {
public boolean find(String[] coins, String word){
HashMap<String, List<Integer>> hm = new HashMap<>();
for (int i = 0; i < coins.length; i++){
String coin = coins[i];
String[] co = coin.split(",");
for (String c : co){
hm.putIfAbsent(c, new ArrayList<>());
hm.get(c).add(i);
}
}
return backtrack(0, word.toCharArray(), hm, new HashSet<>());
}
public boolean backtrack(int idx, char[] word, HashMap<String, List<Integer>> hm, HashSet<Integer> set){
if (idx >= word.length)
return true;
String cur = String.valueOf(word[idx]);
for (int i : hm.get(cur)){
if (set.add(i)){
if (backtrack(idx + 1, word, hm, set))
return true;
else
set.remove(i);
}
}
return false;
}
}

复制代码

第二题我觉得用backtracking

Galileo_Galilei

可否麻烦LZ详细说下第二轮的思路已加米拜托啦