|
l*****a
发帖数: 559 | 2 硬币种类越多，backtracking复杂度越高。
想请教，exponential是怎么算出来的。 |
|
h***n
发帖数: 276 | 3 应该用backtracking吧，它能够罗列所有满足要求的组合
DP一般用来解优化问题的 |
|
d****2
发帖数: 12 | 4 How about this DP:
/*Solution:
total # of one way trip (from start): t = (N-1)/C+1
move i km (from start), the total left nuts: x(i) = N - t*2*i*F
move from j km to i km (j
so apply DP,
for i := [2,D]
for j := [1,i)
xij = x(j) - [(x(j)-1)/C+1] * 2 * (i-j) * F;
if(x(i) < xij)
x(i) = xij;
laststop[i] = j; //backtrack
*/
int GetMaxNuts(int D/*distance*/, int N /*# of nuts*/, int F /*fuel per km*/
, int C /*carry... 阅读全帖 |
|
j*****u
发帖数: 1133 | 5 题目没有说就是没有父指针，而且计算树的高度也是要遍历所有节点的。
这个题没有tricky的解法，就是要么
DFS w/ backtracking，维护两个stack，一个记录root到当前节点的path，另一个记录
max，每次到了叶节点比较两个stack的节点数目并update max if necessary
要么BFS，queue node里面包含从root到该节点的path，返回queue最后一个node里的
path
时间都是O(n)，空间DFS好一些 |
|
i**9
发帖数: 351 | 6 前面有朋友onsite遇到的，print all permutations of a given string, 比较简洁的一
种backtrack解法
permute(char a[],int i,int n){
if(i==n){
//print string;
return;
}
for(int j=i;j
swap(a[i],a[j]);
permute(a,i+1,n);
swap(a[j],a[i]);
}
}
但是这个算法对于有重复字母的会输出很多重复的permutations,比如string "att"
会有这些个permutations
att
att
tat
tta
tta
tat
有很多重复的，被问到如何去掉重复的，有什么好的解法在打印出之前解决掉重复的吗？ |
|
i**9
发帖数: 351 | 7 看样子把 backtracking algorithm 改造成没有duplicate output有点困难，根据大家
的建议谢了一个简易版的 next_permutation (参考了 PuTTYshell 的 link
http://code.google.com/p/sureinterview/source/browse/src/lib/co
)
void next_permutation(char a[],int n,bool & next,bool &first){
int k=n-2;
if(first){
first = false;
print(a,n);
return;
}
next = false;
for(;k>=0;k--){
if(a[k] < a[k+1]){
next = true;
break;
}
}
if(!next){
return;
}
int l=n-1;
for(;a[k]>=a[l];l--){
}
swap(a[k],a[... 阅读全帖 |
|
h***n
发帖数: 276 | 8 对backtracking的改造不难，贴段代码把
void set_all_permutations_with_duplicates_helper(int a[], int n, int l, int
s[])
{
int i, first;
int flag[n];
if (l == n) {
for (i = 0; i < l; i++)
printf("%d\t", a[s[i]]);
printf("\n");
return;
}
for (i = 0; i < n; i++)
flag[i] = 0;
for (i = 0; i < l; i++)
flag[s[i]] = 1;
for (first = -1, i = 0; i < n; i++) {
if (flag[i] == 0) {
if (first < 0) {
first = i;... 阅读全帖 |
|
i**********e
发帖数: 1145 | 9 我写的代码供参考：
void permute(string out, string word, bool used[]) {
int n = word.length();
if (out.length() == n) {
cout << out << endl;
return;
}
for (int j = 0; j < n; j++) {
if (used[j]) continue;
used[j] = true;
permute(out+word[j], word, used);
used[j] = false;
// skip through duplicate characters
while (j+1 < n && word[j] == word[j+1])
j++;
}
}
void permute(string word) {
sort(word.begin(), word.... 阅读全帖 |
|
J******8
发帖数: 132 | 10 All hard algorithm questions. don't care about what you did before:
Ask for blessing....
===================================
1) Find missing number
A file contains 2^40 32-bit integers,
Given 15MB memory. Which which number is missing.
2) Target coins
Given a list of coins such as 25, 10, 5, 1
find the minimum number of coins for a target value such as 95.
3) Extended dictionary lookup
boolean arewords(char *words)
For example:
catdog, catsdog: both return TRUE
catzdog: return FALSE
4... 阅读全帖 |
|
i**d
发帖数: 357 | 11
N ≤
你这个应该算backtracking。 |
|
|
d**e
发帖数: 6098 | 13 都遍历了吧,而且backtracking还会重复计算某些点. |
|
y******5
发帖数: 43 | 14 In your example:
Level 1: A(val:1, Tree1) B(val:1, Tree2)
Level 2: F(val:2), B(val:2), C(val:3)
Level 3: X(val:3), Y(val:4), Z(val:5)
So, we backtrack: Z -> F -> A (or B). Then, we can get the largest match
subtree:
A (or B) -> F -> (X, Y, Z), right?
Probably I did not express my thought clearly. |
|
y******5
发帖数: 43 | 15 Level 1: A(val: 1)
Level 2: F(val: 2), B(val: 2), C(val:3)
Level 3: X(val:3), Y(val:4), Z(val:5)
So, the maximum value is 5, and we backtrack from Z. |
|
g***x
发帖数: 494 | 16 你算法的主要思想是topsort+backtracking来打印出所有的topsort的可能性。我的理
解对吗？ |
|
B*******1
发帖数: 2454 | 17 哪里看出backtracking啊？
就是topsort吧。 |
|
c*******n
发帖数: 72 | 18
哪里看出backtracking啊？就是topsort吧。
★ Sent from iPhone App: iReader Mitbbs 7.28 - iPad Lite |
|
|
g*****k
发帖数: 623 | 20 我个人交得好像第3题不对。
请考虑这个例子。
lista: &A &C
listb: &A &D
listm: &A &D &A &C
明显listm是lista 和 listb 的valid merge。
但是你的code将会返回false
其实从后往前作也一样会有这样的问题。
应该用backtracking来解这题。
lista.get(i)==listb.get(j)==listm.get(k),
那么就是返回剩下的子数组匹配的问题。
lista[i+1..]
listb[j..]
listm[k+1..]
当如上子数组不匹配时，我们将检测如下子数组
lista[i..]
listb[j+1..]
listm[k+1..]
就是算法效率不高。
期待高人指点
PixelClassic说的基本都对。
补充下：
3. 我开始说就是merge sort的变种，
if ( lista.get(i) == listm.get(k) ) {
i++; k++;
} else if ( listb.get(j) == listm.get(k) ) {
j++; k++;
} else {
re... 阅读全帖 |
|
|
i**********e
发帖数: 1145 | 22 Here is the code using Trie and backtracking. The code is not optimized for
speed and is optimized for clarity. It is extremely fast due to trie cutting branches.
Using the word list here:
http://www.itasoftware.com/careers/work-at-ita/PuzzleFiles/WORD
with a total of 173,528 words, the answer is found less than one second. The longest word that can be formed by two or
more other shorter words is:
"ethylenediaminetetraacetates" --> "ethylene" "diamine" "tetra" "ace" "tates"
Interesting?
Note: Th... 阅读全帖 |
|
m**q
发帖数: 189 | 23
1. 你有一种语言的dictionary,你有一大串string,没有delimit,你如何interpret成字
典中的字呢？
http://www.mitbbs.com/article/JobHunting/31488093_3.html
这个刚讨论过，就是把一个句子分拆成单词，既可以用Trie, 也可以DP。去search
ihasleetcode的帖子。
=> 收到，多谢啦
应该是trie + backtracking 或者 trie + DP吧
2. 给你一个字典array of strings (you may preprocess it if necessary)
任意一个单词，求最小的edit distance
一个单位的distance定义为:
a. replace a letter
b. delete a letter
c. insert a letter (also at any position)
这个我不知道有什么高效的办法，我就brutal force: 反复调用minimumEditDistance(
String a, String b)，求最小值。
... 阅读全帖 |
|
m**q
发帖数: 189 | 24
1. 你有一种语言的dictionary,你有一大串string,没有delimit,你如何interpret成字
典中的字呢？
http://www.mitbbs.com/article/JobHunting/31488093_3.html
这个刚讨论过，就是把一个句子分拆成单词，既可以用Trie, 也可以DP。去search
ihasleetcode的帖子。
=> 收到，多谢啦
应该是trie + backtracking 或者 trie + DP吧
2. 给你一个字典array of strings (you may preprocess it if necessary)
任意一个单词，求最小的edit distance
一个单位的distance定义为:
a. replace a letter
b. delete a letter
c. insert a letter (also at any position)
这个我不知道有什么高效的办法，我就brutal force: 反复调用minimumEditDistance(
String a, String b)，求最小值。
... 阅读全帖 |
|
s*****y
发帖数: 897 | 25 recursive + backtracking. |
|
|
s**x
发帖数: 405 | 27 But wait a minute, this is still not completely solved. If only given O(1)
space, then you can't easily backtrack. When you encounter the loop, how do
you go back to find the place where two nodes point to the same node? |
|
h******3
发帖数: 351 | 28 1373 blogged the question "unique paths" using backtracking recursion, top
down memoization, bottom-up dynamic programming.
There is also a follow up question: enumerate all possible paths.
For example, n = m = 2, all possible paths = 6, which are
(2,2)->(1,2)->(0,2)->(0,1)->(0,0)
(2,2)->(1,2)->(1,1)->(0,1)->(0,0)
(2,2)->(1,2)->(1,1)->(1,0)->(0,0)
(2,2)->(2,1)->(2,0)->(1,0)->(0,0)
(2,2)->(2,1)->(1,1)->(1,0)->(0,0)
(2,2)->(2,1)->(1,1)->(0,1)->(0,0)
is this a NP-Complete problem? |
|
h******3
发帖数: 351 | 29 I think it is hard to record paths if implemented using dp or memoization,
looks like backtracking is the best way to enumerate. Maybe I can persist
each nodes on the recursion tree. And enumerate all the root to leaf paths
using some algorithm. |
|
m**q
发帖数: 189 | 30 感觉第一个是trie + backtracking或者DP啊？
直接brute force貌似是指数级的吧，hash table怎么做？ |
|
j********x
发帖数: 2330 | 31 我用正规的backtracking
构造trie，比如我要填x,y位置的字母，搜索trie，决定这个位置可选的单词，然后递归
说实话应该用你这种方法的，要求其实挺低的，最多200个单词
200^3
要求3秒钟做出来。。。傻逼了傻逼了 |
|
|
|
H*M
发帖数: 1268 | 34 觉得妮答得都挺好的阿
为什么拒了？
2 用backtracking吧
is
the |
|
H*M
发帖数: 1268 | 35 觉得妮答得都挺好的阿
为什么拒了？
2 用backtracking吧
is
the |
|
q********c
发帖数: 1774 | 36 My 2 cents:
If it's difficult for you to write the code then it means you don't have a
clear idea/algorithm. You probably know, as you said, you can solve this
using DP, MST, etc, but what the interviewer is looking for is your real
problem-solving skills, not your knowledge from classroom/textbook.
You think it's easy? Try to start from a binary search and keep working on
it until it's perfect. If you think 思路简单, that means you only have a
general idea which is far from enough. Think of backtr... 阅读全帖 |
|
A**u
发帖数: 2458 | 37 来自主题: JobHunting版 - 算法题求教 这个题目我刚好练过
这里有介绍
http://www.geeksforgeeks.org/archives/14469
用backtracking.
关键是，这个树的有些node, 可以不用访问
比如 你要找9.
假设从1开始那么，到达(1,2,4)node.
(1,2,4)的和 加上 {5,7,8}的最小值 > 9.
所以不用考虑 包含1，2，4的node了，这样可以可以排序不少点
这是我的算法
#include
#include
#include
using namespace std;
void re(int depth, int sum, vector selected,int w[], int N, int target){
if ( depth == N )
{
if ( sum == target )
{
for(vector::iterator it = selected.begin(); it != selecte... 阅读全帖 |
|
k***t
发帖数: 276 | 38 Given a sorted array of n integers, pick up k elements so that the minimum
difference between consecutive elements is maximum (that is choose the
elements to maximize the quantity min(a[i+1] - a[i]))
==============================
Recursive backtracking? 不过好像是brute-force的方法。
感觉上是从n个柱子里选n-k个拔掉，选C(n, n-k)种里使k-1个区间中最小的最大。 |
|
v***n
发帖数: 562 | 39 下面那个is_free方法是什么作用？谢谢！
下面第四版的解答：
Imagine a robot sitting on the upper left hand corner of an NxN
grid. The robot can
only move in two directions: right and down. How many possible paths are
there for
the robot?
FOLLOW UP
Imagine certain squares are “o$ limits”, such that the robot can not
step on them.
Design an algorithm to get all possible paths for the robot.
pg 64
Part 1: (For clarity, we will solve this part assuming an X by Y grid)
Each path has (X-... 阅读全帖 |
|
e****r
发帖数: 581 | 40 search with backtracking, remember what you have been through |
|
H***e
发帖数: 476 | 41 第二题其实也一样吧
假想有一个这样的tree,每次在一个node expand, 只有两种情况 （或者 ）。
秋虫说的那个数字作为值传，
然后分别看如果expand (和), 值还满足条件不，满足则expand.
也就是backtracking了。
到最后长度为N则打印。 |
|
P***P
发帖数: 1387 | 42 第一题不简单额, dfs + backtracking 怎么也的搞个30分钟吧 而且这还是第一面的第
一题?
吧！ |
|
y*****n
发帖数: 243 | 43 一定要写出最优算法么= =可不可以。每次用b = b+b 并存到一个数组c里。 C[1] = b
C[2] = 2b c[3] =4b 然后到c[n]的时候c[n]>a这时再backtracking一路加回去. 如果C
[n-1]+C[n-2]>a那么就跳过去找c[n-3]这样最后就找到C[n0]+c[n1]+C[n2]...C[nm]= a
。那么结果就是2^n0+2^n1....2^nm
方法是一样的，我觉得这样比较好想一点。 |
|
y*****n
发帖数: 243 | 44 一定要写出最优算法么= =可不可以。每次用b = b+b 并存到一个数组c里。 C[1] = b
C[2] = 2b c[3] =4b 然后到c[n]的时候c[n]>a这时再backtracking一路加回去. 如果C
[n-1]+C[n-2]>a那么就跳过去找c[n-3]这样最后就找到C[n0]+c[n1]+C[n2]...C[nm]= a
。那么结果就是2^n0+2^n1....2^nm
方法是一样的，我觉得这样比较好想一点。 |
|
H***e
发帖数: 476 | 45 来自主题: JobHunting版 - 一道面试题 backtracking 吧
directions
( |
|
i**********e
发帖数: 1145 | 46 恩 很基本的 DFS + backtrack，四个方向轮流走，遇到障碍回溯。
生成 maze 在本科 CS data structure 的 final project，还算很有挑战性。
当时算是用到了 C++ 比较深奥的 OO-design，还有 union find 的算法，不过都还给老师了，真惭愧。 |
|
H***e
发帖数: 476 | 47 建议增加backtracking,
这个算非常高频了 |
|
w****x
发帖数: 2483 | 48
backtracking就是recursion吧 |
|
w****x
发帖数: 2483 | 49
哦, 我的分类里recursion大概有30个, 和binary tree相关的题很多是recursion, 你
解释一下backtracking和recursion的区别?? |
|
k***t
发帖数: 276 | 50 a. k. a. recursive backtracking. |
|
