m****t
发帖数: 23 | 1 can I ask why we can not do this problem using backtracking? as long as I
found a position when the 1st player picked at first will win, I can just
return that position.
not sure if that will work. |
|
S********t
发帖数: 3431 | 2 G家那题是
https://leetcode.com/problems/flip-game-ii/
不过放心，G家interviewer的水平没有大家想象的那么高，知道sprague-grundy
theory的不多。expectation就是做出普通backtracking的方法。除非是专门做游戏理
论的，普通人谁知道这个定理啊。我做这道题的时候是凭几年前做过nim的回忆，花了1
个小时凭感觉才推出sprague-grundy的解法，然后才去看讨论学习了这个理论。
的。 |
|
r******y
发帖数: 21 | 3 的确是类似n-queens，dfs解法也叫backtracking，其实是一样的。dfs的意思是depth
first search，深度优先搜索 |
|
g****w
发帖数: 523 | 4 只求存不存在的话，用动态规划n*m吧，因为不需要把所有解列出来不需要dfs
[在 rogerbay (rogerbay) 的大作中提到：]
：的确是类似n-queens，dfs解法也叫backtracking，其实是一样的。dfs的意思是
depth first search，深度优先搜索
：【 在 ItachiUchiha (仙人掌) 的大作中提到: 】
：........... |
|
r*******7
发帖数: 11 | 5 1. 只想到了backtracking。输入字符串从头至尾每次提取一个子串，分配给pattern里
的一个字母（如果这个字母还没有被分配的话；否则检查是否符合）。复杂度太高，c(
n,k)，如果认为字符串比较是constant time的话。
2. 这个把正负号展开之后，和leetcode 的distinct subsequences好像没区别？用dp
做。
3. lz能在具体解释下‘到其他所有点的距离最近的点’的意思吗？是说到其他所有点
的距离的sum最小？
抛砖引玉，还请大牛指点。。 |
|
l******s
发帖数: 3045 | 6 visit过的在本分支DFS后还会被backtrack回来，visit只是针对本次DFS的树枝有意义
，换个分支还是non-visited |
|
I*******g
发帖数: 7600 | 7 用stack做 backtrack 是最好的方法， |
|
d******e
发帖数: 2265 | 8 这个用经典的stack backtrack
第一次进入标记并加入path stack
第二次弹出
用两个stack |
|
C*7
发帖数: 234 | 9 follow up的话，是不是backtracking好一些，不确定dp怎么搞 |
|
C*7
发帖数: 234 | 10 backtracking的话，得先找到所有要删的位置，然后分段求组合，最后再来个所有段求
组合，有没有好点的办法？ |
|
l******s
发帖数: 3045 | 11 So far what I thought is it. And so probably it needs dfs + backtracking to
deal with cases of all types on the current cell occurs 3 same type in a row. |
|
n****5
发帖数: 81 | 12 geeksforgeeks 这个算法是O（N）的吗？swap 后对后面的做完递归，就backtrack不了
，除非把swap前的vector保留一个local拷贝，那这样递归函数的参数就不是传array的
引用而是传值了。大牛说说看我的理解错了吗？谢谢！ |
|
|
d****m
发帖数: 1008 | 14 这题不用dp
backtrack(array[], currentIndex, currentMoney)
大概这样 |
|
j*****8
发帖数: 3635 | 15 最标准的backtracking题把
去lc上随便找一道试试就可以了 |
|
p*******n
发帖数: 2697 | 16 是同样类型的经典题。你backtracking都没听说过就去onsite也就算了，但做码农还是
要自己google，而不是上论坛让人debug |
|
j*****8
发帖数: 3635 | 17 最标准的backtracking题把
去lc上随便找一道试试就可以了 |
|
p*******n
发帖数: 2697 | 18 是同样类型的经典题。你backtracking都没听说过就去onsite也就算了，但做码农还是
要自己google，而不是上论坛让人debug |
|
I******c
发帖数: 163 | 19 backpack是什么算法？
我说的dfs就是backtracking. |
|
发帖数: 1 | 20 楼主去年12月从中西部某村校毕业，现在来到加州找工作，已经快2月了，工作还没着
落，心里非常焦虑。。。
简单介绍一下，LZ从14年秋季入学开始刷题，一门心思要找份好工作，到现在leetcode
已经刷过五遍，都做好详尽的总结，看过geeksforgeeks里面一半的topic。。。无奈村
里学校career fair质量不行，今年形势不行，上学期只拿到了微软，google, tableau
和bloomberg的面试。
微软校招遇到一个烙印，问题非常简单，但是LZ紧张不小心犯了一个极其傻逼的错误，
然后就挂了。
tableau onsite面试有四轮，第一轮OOD 设计电梯，第二轮很简单的迷宫题 DFS, BFS
，backtracking，第三轮看一份代码找不足， 第四轮manager面。。。由于LZ对
behavior question准备得不是很充分，结果面完之后第三天就收到了reject phone
call。
google面试相对比较简单，但是最后两轮是阿三，尤其最后一轮三姐，一道简单的二维
字符表找字符串数量的问题，LZ一开始就知道用DFS，当时脑子秀逗了想直接最优，搞
了... 阅读全帖 |
|
发帖数: 1 | 21 楼主去年12月从中西部某村校毕业，现在来到加州找工作，已经快2月了，工作还没着
落，心里非常焦虑。。。
简单介绍一下，LZ从14年秋季入学开始刷题，一门心思要找份好工作，到现在leetcode
已经刷过五遍，都做好详尽的总结，看过geeksforgeeks里面一半的topic。。。无奈村
里学校career fair质量不行，今年形势不行，上学期只拿到了微软，google, tableau
和bloomberg的面试。
微软校招遇到一个烙印，问题非常简单，但是LZ紧张不小心犯了一个极其傻逼的错误，
然后就挂了。
tableau onsite面试有四轮，第一轮OOD 设计电梯，第二轮很简单的迷宫题 DFS, BFS
，backtracking，第三轮看一份代码找不足， 第四轮manager面。。。由于LZ对
behavior question准备得不是很充分，结果面完之后第三天就收到了reject phone
call。
google面试相对比较简单，但是最后两轮是阿三，尤其最后一轮三姐，一道简单的二维
字符表找字符串数量的问题，LZ一开始就知道用DFS，当时脑子秀逗了想直接最优，搞
了... 阅读全帖 |
|
g*******y
发帖数: 1930 | 22 干货不多，大家有兴趣打发时间的话就看看吧。这贴也许对fresh grad没啥意义吧，对
experienced或许更有用些。
＊＊＊＊＊＊＊ 我是小广告的分割线 ＊＊＊＊＊＊＊＊＊＊
帮ld求好心朋友帮忙内推下三番或者中半岛的轻松养老型的马工职位，ld在某软某办公
软件里呆了若干年，现在才发现没有积累到什么流行的技术，现在想找工作背景上比较
吃亏。不过ld底子和学习能力都很好的。
＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
背景是在西雅图地区的G干了五年多主要做backend。最近一两年前，身边朋友纷纷跳槽
，现在比较后悔的就是，早知道两年前刚拿到卡就该挪一挪，拖到现在算有点晚了。另
外一方面，在G干的活，现在也越来越提不起兴趣。朋友的怂恿和激励下，去年10月终
于下决心要跳了。
==> take away: 要跳趁早，时机不等人。
当时也没想要跳湾区，差不多就是一心想去打车公司的西雅图分店。其实去年夏天就有
些蠢蠢欲动了，刷了几道题后懒了又不了了之。10月份开始认真刷lc，刷的也不快，到
12月才勉强刷一遍。后来回想，浪费很多时间，其实各个种类挑着做50~100道应该就差... 阅读全帖 |
|
j********3
发帖数: 33 | 23 convert keypad numbers to all possible words.
input: str. return: list of string
for example:
'8474833' -> [ ['VISITED'], ['THRIVED'], ... ]
问时间复杂度：exponential time.O(3^n) or O(4^n)
follow up 1：返回list of breakable words.
for instance:
'3278227' -> [ ['FAST','CAR'], ['DART', 'BAR'], ['EAR', 'TABS'], ... ]
时间来不及了，没来得及做。应该就是dfs+backtracking.
follow up 2: 如何优化。答 用prefix/trie
不出意外 基本是挂了，之前没做过这题，确实有点生疏。
其实并不难。 |
|
j********3
发帖数: 33 | 24
如果当作是word break，那要对每一条dfs路径 再做word break
这样解法效率太低。
我觉得用dp＋backtracking, 然后把dictionary转成prefix tree |
|
j*******l
发帖数: 1066 | 25 请问LZ如果过几年准备跳槽重新刷题的时候 是重点看自己写的思路 还是所有题从零开
始再刷一遍？
刷题是痛苦的 我更希望重新再刷的时候有一个对300道题的高度总结概括（比如DP里有
哪些常见类型 哪几个道题是经典需要重点训练 DFS/backtracking适合哪些类型 大概
的coding workflow是什么）
总结这个的目的是能在一周时间内恢复自己当年刷题80%的水平 甚至当以后题库到了
1000道的时候 80%的题型特征已经被自己总结归纳 看一遍就明白思路 只需要重新写个
10/20道经典题型就可面试 |
|
L*******k
发帖数: 42 | 26 不过戳气球这种题，算是dp里面有难度的了。这个题比戳气球还更难些。关键你没做过
戳气球更难往哪个方向想。
不过按照我对g家面试的了解，这题interviewer估计自己都不一定会做dp的解，expect
你能写个工整的backtracking就给过了。当然了，也说不准是哪个练过acm的菜鸟
noogler刚开始面试拿来刷人的。 |
|
o******y
发帖数: 446 | 27 用链表和backtrack:
public int getMaxSum(int[] arr){
LinkedList q = new LinkedList<>();
for(int n: arr) q.add(n);
int[] res = new int[1];
res[0] = Integer.MIN_VALUE;
helper(res, q, 0);
return res[0];
}
void helper(int[] res, LinkedList q, int sum){
if(q.isEmpty()){
res[0] = Math.max(sum, res[0]);
return;
}
int size = q.size();
while(size-->0){
int v = q.rem... 阅读全帖 |
|
S********t
发帖数: 3431 | 28 backtrack: weak hire
DP: strong hire |
|
C******x
发帖数: 91 | 29 有一个村庄，流传着两种statement：
1. A 死了之后 B出生。
2. A和B有overlap。
现在有很多这样的statements，要你判断有没有inconsistency.
应该是个图相关的题，拆点建图，但是第二个条件实在是不住到怎么建模。overlap有
四种情况，只能backtracking每个都试一遍吗？ |
|
g*******d
发帖数: 73 | 30 第一题有点意思!
前面也分析了, 先排序, 然后我们要找的subset sum S1 = S*L1/L, 而如果S/L总平均
数可能不是整数, 那么需要检查一下S*L1%L是否为0, 是的话才能继续做, 进化版的
CombinationSum3 (L1, S*L1/L)
可以限制L1<=L/2. 如果到L/2还没找到就算失败.
由于已经排过序了, 那么找到的第一个组合就是长度最短,且topological最前的答案.
(所以也不用费神排除重复答案了)
原题链接: https://leetcode.com/problems/combination-sum-iii/
DFS+backtracking
感觉可以加进Leetcode成CombinationSum4, 难度的话算Hard里的中档题
PS: 刚开始找工作, 求各位前辈内推...CS fresh grad, 目标SDE, 会点ML |
|
g*******d
发帖数: 73 | 31 第二题由于没排序, 那就用个unordered_map> map
map存的是值->idx的映射, 由于一个可能值对应多个idx, 所以用个set
然后就开始DFS+backtracking. 由于题目确定了lexicographically的顺序
所以先确定A, B, C, (然后删掉对应的idx, 不删也行) 再进map查询D=A-C+B (注意
overflow), 有的话就检查D的idx是否符合条件
总的O(n^3)时间, O(n)空间
应该有更好的解法, 望指教 |
|
w*****1
发帖数: 6807 | 32 今天FB烙印面试官，连我一个最简单的backtracking的代码都没看懂，才10行不到，就
一直说我错了，跟我扯了半天，也没明白他要干嘛。我回头一跑，错TMLGB
烙印黑国人的招数是越来越有新意了。。。 |
|
w*****1
发帖数: 6807 | 33 我电面FB的时候，三哥也不懂我的backtracking，只好找Recruiter解释了一下，加面
了一轮 |
|
|
c********t
发帖数: 5706 | 35 backtracking, it removes node value from list |
|
s**********g
发帖数: 14942 | 36 backtracking一般都要repair
不然下一个尝试怎么做
这个就是repair |
|
W***o
发帖数: 6519 | 37 来自主题: JobHunting版 - 求3题思路 backtracking |
|
c********t
发帖数: 5706 | 38 第一题 dfs + backtracking
第二题 每次都peek很多次？如果不能peek,取出放heap里？ |
|
s**********g
发帖数: 14942 | 39 backtrack的复杂度向来都高
指数级不是梦 |
|
s**********g
发帖数: 14942 | 40 表面上看 的确是backtrack的长相啊。。 |
|
b***e
发帖数: 383 | 41 来自主题: JobHunting版 - 这题如何破 难道不是DFS+backtracking? |
|
|
k****r
发帖数: 807 | 43 backtracking啊，另外建一个array纪录每个被抢的房子之前抢的房子的index （为保
证组合抢的max）。iterate之后反着读这个array来建立结果。 |
|
k****r
发帖数: 807 | 44 backtracking啊，另外建一个array纪录每个被抢的房子之前抢的房子的index （为保
证组合抢的max）。iterate之后反着读这个array来建立结果。 |
|
a****i
发帖数: 1182 | 45 这是 DP的题吧？backtracking只能得到能不能抢 |
|
k****r
发帖数: 807 | 46 backtracking是用来记录当前sub－result基于的前一个房子的index。
hours： 2 1 3 7
IdxRecord： －1 －1 0 1
IdxResult： ［3， 1］ |
|
n*****x
发帖数: 686 | 47 就是说只做一次BFS，就求出所有的路径
我好像有点思路了，用hashmap，对每个坐标点p，要存有几个点能到达p，和p能到达几
个点，每次遇到一个路径就backtrack，选degree of freedom尽量少的点往回走，然后
尽量选非对角的方向（避免相交）。 |
|
j*********5
发帖数: 362 | 48 Permutation；
Given N nums find all the combinations that sum to K；
还有类似变体。
擦把冷汗。 |
|
j*********5
发帖数: 362 | 49 Permutation should be O(n!)
when n is the length of the input array? |
|
z*********n
发帖数: 1451 | 50
这题不是DP入门题么？我人生第一个DP就是这题啊。后来才知道背包。 |
|
