c********t
发帖数: 5706 | 1 找工作不用读吗，那太太好了。你读的是哪本数据结构算法书啊？
我读了一本，偏重数据结构，都没有讲divide and conquer, greedy, backtracking，
top down, bottom up...所以我总是不能总结好自己的编程思路是什么类型，基本上靠
野球拳。 |
|
|
c********t
发帖数: 5706 | 3 恭喜恭喜！！
85 without overlap
假如windows可以overlap，但不完全cover each other，
一共又要用多少个windows？不懂什么意思，85个以上？
directed graph cycle，可不可以用DAG做？无解既是有cycle.
n-sum是用DP吗？还是recursion+backtracking? 复杂度是多少？
看了一下大文件那道题，我怎么觉得不对呢，有的词在，分的5000个文件非常平均分布
，在所有里面都没到前100的频率，但5000文件合起来后，就有可能进前100啊。还有就
是第一个文件里前100的词，在其他文件里可能是100以后，那他的出现频率就不会被其
他文件统计，没有到生成的小文件里，影响merge结果正确性。
同理十道海量数据处理面试题第一题也有这个问题啊。
是我哪里想的不对吗？ |
|
c********s
发帖数: 817 | 4 长，宽方向各overlap一个cell. 第一个layer，15x15windows。 第二个
layer14x14windows。keep going like this.
只要算法work就行。
记得当时写的的是recursion+backtracking。 |
|
p*****p
发帖数: 379 | 5 http://leetcode.com/onlinejudge#question_79
思路就是DFS，递归实现backtrack
large case超时，不知是剪枝不对还是递归费时
代码感觉没大问题
求帮忙看看，谢谢
class Solution {
public:
bool exist(vector > &board, string word) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if (word.empty()) return true;
int m = board.size();
int n = board[0].size();
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (board[i]... 阅读全帖 |
|
e******i
发帖数: 106 | 6
你说的对，所以是她题目说的不清楚。我觉得解法是backtrack |
|
m*****n
发帖数: 204 | 7 有个思路不知道对不对, 就是递归去分析
M sentences, U unique words, N word counts. Build mapping from word to set
of sentences: O(M*N)
Put unique words in any order. Loop from 1..U, maintain the current best
and second best subsets.
May need backtrack to find previous third best to promote but I haven't
figured out this part. |
|
c*****r
发帖数: 108 | 8 Hi,
没明白你说的back track。 么有parent link怎样backtrack啊？ |
|
s******c
发帖数: 99 | 9 问题在于recursive call的时候，你每次都重新生成left_path和right_path，然后拷
贝整个path到里面，这样就会慢，不需要这两个额外的arraylist,就用path一个就可，
backtrack就是你走完left child和 right child 之后都回到parent就可，其实就是把
path最后一个element去掉就行。
public class Solution {
public ArrayList> pathSum(TreeNode root, int sum) {
// Start typing your Java solution below
// DO NOT write main() function
ArrayList> results=new ArrayList
Integer>>();
ArrayList path=new ArrayList<... 阅读全帖 |
|
e******i
发帖数: 106 | 10 有比用backtracking更优化的算法么？ |
|
p*****2
发帖数: 21240 | 11
想了一下 最短路径 确实bfs + backtrack |
|
o******3
发帖数: 91 | 12 不用backtrack, BFS存着路径就好了。
问题是要30分钟把这个无bug写出来。
我跪了。。。
这有点儿难度啊。。。 |
|
|
p*****2
发帖数: 21240 | 14
想了一下 最短路径 确实bfs + backtrack |
|
o******3
发帖数: 91 | 15 不用backtrack, BFS存着路径就好了。
问题是要30分钟把这个无bug写出来。
我跪了。。。
这有点儿难度啊。。。 |
|
|
z****p
发帖数: 18 | 17 I guess this problem is not about algorithm. It asks for the number of min
swaps. It's more like a math problem. As long as we give N-K, our job is
done, and we don't have to implement any algorithm.
Think this problem in another way:
-There is a large graph, where each node is a permutation of the given list
of data; there is an edge points from node i to node j if we can move from
permutation-i to permutation-j by using one "swap".
-Now the question is I pick two nodes i and k in the graph, wh... 阅读全帖 |
|
r**h
发帖数: 1288 | 18 backtrack，由于是全正数因此可以剪枝
dp的话可以判断是否存在subset但是输出所有可能结果不方便 |
|
c*******r
发帖数: 309 | 19 多谢各位了......想起来以前看到leetcode的题是用backtrack来解的。 这个DFS我再
消化消化 |
|
r*********n
发帖数: 4553 | 20 Given a string s, partition s such that every substring of the partition is
a palindrome.
Return all possible palindrome partitioning of s.
是这个题吧。
bool check(const string& s, int j, int i){
while( j <= i && a[j++] == a[i--] );
if( j > i ) return true;
return false;
}
int PalinPartition(const string& s){
if( s.empty() ) return -1;
vector T(s.size(),numeric_limits::max());
for( int i = 0; i < s.size(); ++i ){
if( check(s,0,i) ){
T[i] = 0;
... 阅读全帖 |
|
b*******e
发帖数: 217 | 21 is not this typical backtracking problem? |
|
a******3
发帖数: 113 | 22
是的。但是感觉backtracking时间复杂度太高了，因为1 <= N <= 10的9次幂，test
case应该过不了 |
|
r**h
发帖数: 1288 | 23 我用python写的，用backtrack方法，不算I/O也就50行左右啊 |
|
l*******A
发帖数: 209 | 24 N*N棋盘， 输入一个棋子坐标。求这个棋子能跳出的最远距离。
棋子只能斜着跳。
规则应该就是跳棋的规则。 可以越过对方的棋子并吃掉对方棋子。
怎么解?
DFS?
Backtracking?
好像有点模糊的idea但是又没法清楚写出pseudo code来.
高手指教一下吧 |
|
f*********m
发帖数: 726 | 25 给一个count and say的结果，确定有多少种可能的输入。比如，"1211" 可以解释成1
个2，1个1，121个1,12个11或者121个1。所以有四种可能的输入。
这个题是glassdoor上看到的，当时作者只是给了2，1个1，121个1这两个例子。
我有个backtracking的想法。
int numberOfWays(string& s, int index)
{
if (index == s.size())
return 1;
int num = 0;
for (int i = index; i < size(); ++i)
{
for (int j = i+1; j < size(); ++j)
{
if (s.substr(index, i) can be the count && s.substr(i+1, j) can
be the number)
num += numberOfWays(s, j+1);
}
}
... 阅读全帖 |
|
r**u
发帖数: 1567 | 26 Given a string s, partition s such that every substring of the partition is
a palindrome.
Return all possible palindrome partitioning of s.
For example, given s = "aab",
Return
[
["aa","b"],
["a","a","b"]
]
DFS就是要枚举所有可能的划分，然后检查是否是palindrome吧，中间如果发现划分不
满足palindrome了，就backtrack。这个复杂度应该怎么求？ |
|
l*n
发帖数: 529 | 27 第二题只能backtracking暴力搞吧？从算式最后一个数开始。 |
|
w******j
发帖数: 185 | 28 来自主题: JobHunting版 - f 的面经 最后一道就是leetcode上的Wildcard Matching吗？
和regular expression matching 差不多吧，用backtracking recursion +
memorization 当然也可以用dp.... |
|
r*******e
发帖数: 7583 | 29 我用的dijkstra+backtracking可以过large，不过也1000ms了 |
|
v*****k
发帖数: 7798 | 30 每走一步都需要backtrack重新算到当前为止的总weight和最优路径吧，除非这个
weight有什么规律可以压缩判断时间 |
|
r*******e
发帖数: 7583 | 31 剪枝：pruning
回溯：backtracking |
|
g*********e
发帖数: 14401 | 32 典型backtracking
8 queens problem. 当你resursion到一半，发现当前的6个queen已经要互相打架的时
候，就不需要再放第7个queen，而是直接return。 |
|
l*******0
发帖数: 63 | 33 backtracking就是回溯，在每一步都尝试所有可能的分支，递归下去。
剪枝大概是指fail-fast吧。就是当你在中间某一step，就知道某些分支是走不通的，
所以就不去尝试这些分支了。这样就避免了后来的无必要的递归。。。 |
|
s*********s
发帖数: 318 | 34 我的体会还是要自己琢磨，这样在面试的时候，interviewer变换题目的时候才能对他
如流。
1）有没有重复的元素？
2）需要backtracking吗？ |
|
x*********s
发帖数: 2604 | 35 可以看成一个换零钱的问题，给一个面额是n的钞票，和一组可以重复使用的零钞{1,2,
3,...,n-1}，问一共有多少种换法。一个backtracking就解决了 |
|
j*m
发帖数: 17 | 36 马甲，主旨造福本版。认出来的拜托别出声，谢谢！
本人绝对的烂校master，7年经验，6年都是在打杂放屁，实在不是牛人。后面会介绍复
习强度。
按顺序面了polyvore，houzz，box，f，g。除了g还没面完houzz跪了，别的都拿了
offer。
box： base 160, 15koptions。
f：base140,红包2万5,19万worth of rsu4分4年给。
polyvore早给巨了，package也差不多。
3月初开始复习，cc150看了2.5遍，边看边在白纸上写code那种。leetcode刷了1遍又
random刷了23题（后期onsite阶段练手），有几道最后都没能过oj，惭愧。版上面筋、
讨论有很仔细地看，收获良多。onsite之前会去glassdoor上把该公司6个月内的题都看
过默念过，没有写code但大体有个数。careerup网站我不推荐，答案大多是错的，重题
也很多。
houzz面筋：
Q1: print out prime factors. e.g., 20=2x2x5, 90=2x3x3x5
How to get a list of pr... 阅读全帖 |
|
u*****o
发帖数: 1224 | 37 LZ你好，谢谢你分享面试经历
想问问这两道题具体是哪里？
read-out number up to 1 million。cc150原题
char[][] matrix, find word. Can only go straight lines, no turns。leetcode原
题，典型的backtrack
可以告诉我具体的题号吗我找了半天没找到。。。 |
|
s****p
发帖数: 124 | 38 同问，请问下面这是哪题？能否给出链接？谢谢！
char[][] matrix, find word. Can only go straight lines, no turns。leetcode原
题，典型的backtrack。 |
|
p*****2
发帖数: 21240 | 39 看了一下这题。跟LZ面G碰到的好像不是一个题。
这题倒是应该用dp＋backtrack。 |
|
j*t
发帖数: 184 | 40 >1.2 How many 0s tailing in N!
这题是数1...N中末尾数是5或0的个数吗？
>2.1 10 buttons passcode with 4 digitals. Generate a sequence to
> brute force it. Upper bound and lower bound of length, code to
> generate an optimal one.
>
>If we start from 0000 and use minimum digits if the number doesn't >appear
previously, we get 0000100020003000400050006000700080009 and >it will form a
cycle and stop generating new numbers.
backtracking? 如何证明soultion接近10k+3? |
|
l*******0
发帖数: 63 | 41 这不是针对fresh grad的吧？不懂设计模式啊。。。
不过第二题你的基本思路是对的。要想少一点空间的话，可以把string先转成char
array. FYI:
char[] p=str.toCharArray();
static void dfs(char[] p, int idx, ArrayList sol){
if(idx==p.length){ //find one string
sol.add(new String(p));
}else{ //replace ? to either 0 or 1
if(p[idx]=='?'){
p[idx]='0';
dfs(p,idx+1,sol);
p[idx]='1';
dfs(p,idx+1,sol);
... 阅读全帖 |
|
h**o
发帖数: 548 | 42 Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell,
where "adjacent" cells are those horizontally or vertically neighboring. The
same letter cell may not be used more than once.
我知道有人问过了。没答案。
我觉得time 复杂度是m*n*4^(k-1). 也就是m*n*4^k.
m X n is board size, k is word size.
space 复杂度 是： 4^k (recursive)+ m*n (to mark visited board cell)
是这样吗？ |
|
a*****u
发帖数: 1712 | 43 时间复杂度我跟你想的一样。
空间复杂度好像不对，recuision最深是k层，recursive部分空间复杂度应该是O(k)
★ 发自iPhone App: ChineseWeb 7.8 |
|
|
h**o
发帖数: 548 | 45 Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell,
where "adjacent" cells are those horizontally or vertically neighboring. The
same letter cell may not be used more than once.
我知道有人问过了。没答案。
我觉得time 复杂度是m*n*4^(k-1). 也就是m*n*4^k.
m X n is board size, k is word size.
space 复杂度 是： 4^k (recursive)+ m*n (to mark visited board cell)
是这样吗？ |
|
a*****u
发帖数: 1712 | 46 时间复杂度我跟你想的一样。
空间复杂度好像不对，recuision最深是k层，recursive部分空间复杂度应该是O(k)
★ 发自iPhone App: ChineseWeb 7.8 |
|
|
l*******t
发帖数: 79 | 48 能不能解释一下那个4^(k-1)是怎么来的 谢谢！ |
|
h**o
发帖数: 548 | 49 Given a string s, partition s such that every substring of the partition is
a palindrome. Return all possible palindrome partitioning of s.
For example, given s = "aab", Return
[
["aa","b"],
["a","a","b"]
]
知道是用backtracking + DP. 但只知道判断是否Palindrome 可以DP. 不知道为何有贴
说有两个地方可以DP？
复杂度如何求？
time: 每个node 分成 n 支， 有n 层树， 难道 是 time = n^n?
space: n (recursive)+ n^2 (存 isPalindrome 的结果） = n^2? |
|
h**o
发帖数: 548 | 50 请问你哪里用到DP了？
我看着就是一般的backtracking recursive, 没存下什么可以再利用的结果啊？
我是吧bool isPalindrome(string s, int start, int end)第一次的结果存在一个
array 里， 省得老算老算的，我觉得这叫DP. |
|
