|
w***g
发帖数: 5958 | 2 实际提到backtracking的时候，基本上都是指手工用堆栈实现递归，
不管从性能上还是开销上跟递归都是一样的，控制不好也会stack overflow。
backtracking除了用来虐别人或者自虐（或者练习写白板）以外没有
任何实际上的好处。 |
|
b*********n
发帖数: 1258 | 3 我的理解是
要实现Backtrack至少O(n^2) Space Complexity
不知到对不对? |
|
r**u
发帖数: 1567 | 4 比如用backtracking解决8 queens问题。很多cases都可以prune掉，但是这个复杂度怎
么估计？谢谢 |
|
S*******e
发帖数: 379 | 5 只想到递归backtracking, exponential complexity |
|
|
l***i
发帖数: 1309 | 7 You passed large n=12 by using the backtracking code above? |
|
k*******t
发帖数: 144 | 8 实在弄不明白，比如cc18.7: Find the longest word made of the words in a given
list，或者leetcode中的solve soduku问题，如果用recursive backtracking 时间复
杂度为何为O(2^n)啊？最好解释下，抛link也行。多谢啦。 |
|
t**r
发帖数: 3428 | 9 leetcode里， backtracking的time complexity怎么算，比如permutations这题目
class Solution {
public:
void perm(vector num,int k,int n, vector > &res){
if (k==n){
res.push_back(num);
}else{
for (int i=k;i<=n;i++){
int tmp = num[k];
num[k]=num[i];
num[i]=tmp;
perm(num,k+1,n,res);
tmp = num[k];
num[k]=num[i];
... 阅读全帖 |
|
s**x
发帖数: 7506 | 10 Where is the backtracking ？ |
|
v****a
发帖数: 236 | 11 注意到 for (int i=st;i
对于backtracking 每次递归，n = n-1
复杂度是n*(n-1)*(n-2)...1 = O(n!) |
|
发帖数: 1 | 12 dfs backtracking复杂度到底怎么计算？ |
|
p***c
发帖数: 5202 | 13 我昨晚跟了一下，我记得我下载过几百首backtrack，在bt上找的，忘了哪个site了，
后来我删掉了帖子，因为我找不到那些mp3了，哈哈。。。
这两天正在把几台机器上的东西往NAS上挪，争取找出来，到时候和大家share一下 |
|
|
b*********n
发帖数: 1258 | 15 我的理解是
要实现Backtrack至少O(n^2) Space Complexity
不知到对不对? |
|
g*****u
发帖数: 298 | 16 怎么会呢。backtrack解0-1 knapsack 用O(n)空间就够了。
每个x_i=0 or 1，用1bit表示就够了。
一共有N个，用N bits表示就可以了。 |
|
H*D
发帖数: 35 | 17 用C++要怎么实现？大概就是读入一个cnf文件，用backtracking找出有没有解。
牛人们能帮我讲讲大概的算法就好。。。 |
|
c****e
发帖数: 1453 | 18 Read paper ZChaff, MiniSat. Not hard to implement by your own. Backtracking
is easy to understand. The tricky part is conflict driven learning. |
|
D*******a
发帖数: 3688 | 19 dp是解优化问题的（min／max）
backtracking通常只是搜索某种解 |
|
w*********a
发帖数: 9279 | 20 dp要求问题本身必须具备 optimal substructure。
另外，凡是能用dp解决的问题，都可以不用dp解决。
backtracking，只要是树就可以搞。 |
|
f*********m
发帖数: 726 | 21 A robot is located at the top-left corner of a m x n grid (marked ‘Start’
in the diagram below). The robot can only move either down or right at any
point in time. The robot is trying to reach the bottom-right corner of the
grid (marked ‘Finish’ in the diagram below). How many possible unique
paths are there?
Follow up for "Unique Paths":
Now consider if some obstacles are added to the grids. How many unique paths
would there be?
An obstacle and empty space is marked as 1 and 0 respectively in t... 阅读全帖 |
|
s*****n
发帖数: 994 | 22 dp + backtracking。 之前用了hashtable能过break word I，但是过不了II，可能是
string constructor太耗时了吧
class Solution {
public:
void backTracking (const string& s, vector >&prev, int index
, vector& output){
for (int i=0; i
int prev_index = prev[index][i];
vector prev_output(0);
if (prev_index != 0)
backTracking (s, prev, prev_index, prev_output);
else
prev_output = vector (1, "");
f... 阅读全帖 |
|
r****7
发帖数: 2282 | 23 Java里边默认是传引用吧
C++写了个，看了下和你的逻辑应该一样的，不过我觉得这个叫DFS是不是牵强了点儿。
。。
#include
#include
using namespace std;
int size;
void print(vector arr)
{
for (int i = 0; i < arr.size(); i++) {
printf("%c ", arr[i]);
}
printf("n");
}
void backtracking(vector arr, int len)
{
if (len == size) {
print(arr);
return;
}
int currLen = len;
len ++;
if (arr[currLen - 1] == '*') {
arr[currLen - 1] = '0';
backtracking(arr, len);
arr[currLe... 阅读全帖 |
|
e*****u
发帖数: 67 | 24 #11題正確答案如下 （這個solution也是O(N^2)嗎？為什麽比我的code要好呢？）
def LCS(X, Y):
m = len(X)
n = len(Y)
# An (m+1) times (n+1) matrix
C = [[0] * (n+1) for i in range(m+1)]
print C
for i in range(1, m+1):
for j in range(1, n+1):
if X[i-1] == Y[j-1]:
C[i][j] = C[i-1][j-1] + 1
else:
C[i][j] = max(C[i][j-1], C[i-1][j])
print C
return C
def backTrack(C, X, Y, i, j):
if i == 0 or j == 0:
return ""
... 阅读全帖 |
|
l****z
发帖数: 29846 | 25 Published on CNS News http://www.cnsnews.com
Spanish festival backtracks, re-invites Jewish singer
MADRID (AP) — Following a barrage of criticism, organizers of an
international reggae festival in Spain backtracked Wednesday and apologized
for cancelling a concert by Jewish-American singer Matisyahu because he had
declined to state his position regarding a Palestinian state.
Rototom Sunsplash festival said in a statement that it publicly apologized
for canceling the concert and invites Matisya... 阅读全帖 |
|
Y**3
发帖数: 21 | 26 void BackTrack(vector > &board,int k,bool& bFindOne)
{
if(k>=81)
{
bFindOne=true;//find a solution
return;
}
int row=k/9;
int col=k%9;
if(isdigit(board[row][col]))//already set
BackTrack(board,k+1,bFindOne);
else
{
for(int i=1;i<=9;i++)
{
board[row][col]=i+'0';
if(isValid(board,row,col))
BackTrack(boar... 阅读全帖 |
|
u*****a
发帖数: 9489 | 27 快来看，笑死了，末尾还附变态辣椒的漫画一张
利用环球时报反Trump，是CNN的一大发明
http://www.cnn.com/2016/03/16/world/china-donald-trump/index.ht
Hong Kong (CNN)For months, Republican frontrunner Donald Trump has
repeatedly targeted China on the campaign trail, pledging to put tariffs on
goods produced overseas and bring things like iPhone production back to the
United States.
Trump has even used a broken-English accent at a campaign rally to mock the
negotiating style of Chinese businessmen.
Beijing had previously downplayed any i... 阅读全帖 |
|
s********u
发帖数: 1109 | 28 写了一下，觉得难点主要在回溯写这个path，如果维护不好，很容易出bug。
52ms通过。
class Solution {
public:
void backtracking( int end,const vector >&prev,const string
&s, vector &paths, string &path ){
if(end == -1){
paths.push_back(path);
return;
}
int prev_end;
string word;
const string local = path;
for(int i = 0; i < prev[end].size(); i++){
prev_end = prev[end][i];
... 阅读全帖 |
|
a******e
发帖数: 710 | 29 2.他说他也是听说来的这道题，又是讨论描述了N久才搞明白，还跟我扯你知道为啥美
国分成这48个州么。。。比如给一个矩阵
1 2 2 3 (5)
3 2 3 (4) (4)
2 4 (5) 3 1 Atlantic
(6) (7) 1 4 5
(5) 1 1 2 4
#####请问括号里面的数字是什么意思？
每个数字代表该地区的海拔，然后西边是太平洋，东边是大西洋，让我返回所有path，
每个path能连通大西洋和太平洋，水只能从高处往低处走。
我到最后才发现他这个例子好像有点不对（他说他也不是很清楚，别人给他的。。汗）
，我觉得真正的意思应该是水流是单向的，否则岂不是随便怎么走都能连通？？
#####若问这里提到的backtracking和recursion有何不同？ 我一直不太了解
backtracking
我就用backtracking的方法，有点类似boggle game那题，从西海岸的点出发，往8个方
向走，如果没超出边界或者没用过，就走下去，直到到达东海岸，把这个路径存下来。
电面结束我才发现我有个bug，就是说，到达东海岸的时候不应该return，... 阅读全帖 |
|
s********u
发帖数: 1109 | 30 #####请问括号里面的数字是什么意思？
当时他是在演示一个path。但按照他后来说的这个意思，这根本不是个有效的path，而
且不止一个path。所以你就无视这个吧。我觉得按我的意思理解，就是个有效的题。
#####若问这里提到的backtracking和recursion有何不同？ 我一直不太了解
backtracking
比如最简单的recursion，阶乘，就是从top一直走到down，这个是单向的，只有一个
end那就是n == 1。
backtracking就是回溯，递归的一种，最典型的就是树或者图的DFS和八皇后问题，就
是从一个点出发，往不同的方向走，直到走不通。跟阶乘的区别是，他是多向的，end
有很多。。
### 如果用vector 保存结果，直接push_back
就行了， 这里用list好像没有什么必要？
这里可以用vector，只是他正好提到结果输出lists of points.
的确是可以直接push_back(),因为push_back()传的参数是对象的“复制”而不是“引
用”。我这里clone了一下，主要是因为有时经常用比如 int p... 阅读全帖 |
|
a******e
发帖数: 710 | 31 2.他说他也是听说来的这道题，又是讨论描述了N久才搞明白，还跟我扯你知道为啥美
国分成这48个州么。。。比如给一个矩阵
1 2 2 3 (5)
3 2 3 (4) (4)
2 4 (5) 3 1 Atlantic
(6) (7) 1 4 5
(5) 1 1 2 4
#####请问括号里面的数字是什么意思？
每个数字代表该地区的海拔，然后西边是太平洋，东边是大西洋，让我返回所有path，
每个path能连通大西洋和太平洋，水只能从高处往低处走。
我到最后才发现他这个例子好像有点不对（他说他也不是很清楚，别人给他的。。汗）
，我觉得真正的意思应该是水流是单向的，否则岂不是随便怎么走都能连通？？
#####若问这里提到的backtracking和recursion有何不同？ 我一直不太了解
backtracking
我就用backtracking的方法，有点类似boggle game那题，从西海岸的点出发，往8个方
向走，如果没超出边界或者没用过，就走下去，直到到达东海岸，把这个路径存下来。
电面结束我才发现我有个bug，就是说，到达东海岸的时候不应该return，... 阅读全帖 |
|
s********u
发帖数: 1109 | 32 #####请问括号里面的数字是什么意思？
当时他是在演示一个path。但按照他后来说的这个意思，这根本不是个有效的path，而
且不止一个path。所以你就无视这个吧。我觉得按我的意思理解，就是个有效的题。
#####若问这里提到的backtracking和recursion有何不同？ 我一直不太了解
backtracking
比如最简单的recursion，阶乘，就是从top一直走到down，这个是单向的，只有一个
end那就是n == 1。
backtracking就是回溯，递归的一种，最典型的就是树或者图的DFS和八皇后问题，就
是从一个点出发，往不同的方向走，直到走不通。跟阶乘的区别是，他是多向的，end
有很多。。
### 如果用vector 保存结果，直接push_back
就行了， 这里用list好像没有什么必要？
这里可以用vector，只是他正好提到结果输出lists of points.
的确是可以直接push_back(),因为push_back()传的参数是对象的“复制”而不是“引
用”。我这里clone了一下，主要是因为有时经常用比如 int p... 阅读全帖 |
|
s********u
发帖数: 1109 | 33 嗯，在理论上我是这么总结的：
**Divide and conquer :** 将问题分成几个部分，每一部分问题互相不重叠，假定每
个部分都可以得到解决进行递归调用，合并每一部分的结果。例如Merge Sort,Quick
Sort。
**Dynamic Programming**：对于具备最优子结构以及子问题重叠特性的问题，尽可能
不重复计算每个subproblem，将计算结果存储下来，以确定后驱问题的结果。与贪心算
法的区别是，在计算后驱问题时，可能会reconsider前驱问题的解，从而改变全局path
。
**Greedy Algorithm** : 当前问题的最优解只取决于前驱问题的最优解，即局部最
优解推广至全局最优解。如Dijkstra算法。
**Backtracking**： 一种暴力（穷举）的深度优先搜索法，直至检索到节点空间的尽
头。Tree或Graph的DFS，是backtracking的special case。
但实际上很多问题就算满足dp的条件，用dp却非常繁琐，比如8皇后问题，或path sum
问题。是可以用dp做，但实际上没必要。用b... 阅读全帖 |
|
l*n
发帖数: 529 | 34 图的思路是对的，visited信息可以通过hashmap来记录，相邻节点的联系就是from节点
的后三个字符跟to节点的前三个字符相同。
但是backtracking应该肯定是要的。这图里面环很多，dfs找的时候肯定会陷到某个级
别的环中去，导致最后没办法跟图的剩余部分连接起来。这时候如果不backtrack的话
，就相当于重新开始了，那么得到的结果就肯定不是最优的。
4个数字的密码，最短是10^4+3，每个数都只引入一个新的数字，3是最开始初始化的起
点。
前面有人提到的面经帖中有关环的处理很是tricky，感觉不是cs的路数，cs的搞法很简
单，直接backtrack就是了。 |
|
c****y
发帖数: 749 | 35 来自主题: MusicPlayer版 - 弹一小段 大家好象都是从网上download backtrack.一边play backtrack一边弹琴,类似karaoke.
录video的话一般就是用camcorder上的内置mic录的现场.当然如果接mixer的话也可以
单录个audio,那种情况最简单的是直接mic guitar amp出来的声音,backtrack直接
linein进mixer. |
|
l*********1
发帖数: 2971 | 36 US Senate leader calls Hu Jintao 'a dictator'
Leading Democrat Harry Reid has called Chinese President Hu Jintao "a
dictator" during a television interview before quickly backtracking on his
comment.
The Senate majority leader made the accusation during an outspoken interview
given to a Nevada station.
He said: "I'm going to go back to Washington tomorrow to meet with the
president of China. He is a dictator. He can do a lot of things through the
form of government they have."
Realising the stre... 阅读全帖 |
|
e*******e
发帖数: 9616 | 37 Kiev must clarify what happened to a Russian journalist who went missing in
Ukraine, a US press freedom watchdog said after a Ukrainian police official
said the correspondent was arrested, only to backtrack on his words hours
later.
Andrey Stenin, a photojournalist contributing to several leading Russian and
international news agencies like AP, Reuters, AFP,Rossiya Segodnya (RIA
Novosti) and ITAR-TASS, disappeared in eastern Ukraine last week while
covering the military campaign being conducted ... 阅读全帖 |
|
发帖数: 1 | 38 塌鼻子老酱文盲到张冠李戴说是CNN backtracked，笑死人了，哪个你帝“大公司”用
这么个蠢货，去short它家的stock
https://www.mitbbs.com/article/Military/54916763_0.html
Authorities in the UK initially said that they thought the dead people may
have been Chinese citizens, but later backtracked as the possibility emerged
that at least one of the passengers was Vietnamese. It's not clear what
informed the initial assessment.。
这里没有任何确认有至少一名越南死者的意思，只是说有至少一名越南死者的可能性，
而且也不是被官方确认的，你们理解错了这句话，这话是说，官方最初说他们认为死者
是中国公民，but后面是CNN的看法，而不是前面官方的看法， |
|
发帖数: 1 | 39 老胱还在忙着截屏乱伦人畜恋故事，顺带学习拼图低端猪食，没空道歉，反正那点鸡同
鸭讲的蝇文以后住你帝老人院听得懂黑白护士叫脱裤子洗澡足够了，到底蝇蒂警察
backtracked没有无所谓
https://www.mitbbs.com/article/Military/54916763_0.html
Authorities in the UK initially said that they thought the dead people may
have been Chinese citizens, but later backtracked as the possibility emerged
that at least one of the passengers was Vietnamese. It's not clear what
informed the initial assessment.。
这里没有任何确认有至少一名越南死者的意思，只是说有至少一名越南死者的可能性，
而且也不是被官方确认的，你们理解错了这句话，这话是说，官方最初说他们认为死者
是中国公民，but后面是CNN... 阅读全帖 |
|
发帖数: 1 | 40 老胱先把到底是cnn还是essex警方backtracked舔明白再说
https://www.mitbbs.com/article/Military/54916763_0.html
Authorities in the UK initially said that they thought the dead people may
have been Chinese citizens, but later backtracked as the possibility
emergedthat at least one of the passengers was Vietnamese. It's not clear
what
informed the initial assessment.。
这里没有任何确认有至少一名越南死者的意思，只是说有至少一名越南死者的可能性，
而且也不是被官方确认的，你们理解错了这句话，这话是说，官方最初说他们认为死者
是中国公民，but后面是CNN的看法，而不是前面官方的看法， |
|
i***a
发帖数: 4718 | 41 SB 开始搞威胁了。素质。。。 床铺在这上面玩吸引眼球，backtrack，自打嘴巴过的。
床铺的原话，开始是
“He’s not a war hero,” said Trump. “He was a war hero because he was
captured. I like people who weren’t captured.”
后来被追问，就改口了
At a press availability following his remarks, Trump denied saying that
McCain isn’t a war hero and said, “If somebody’s a prisoner, I consider
them a war hero.”
到你这又要替床铺backtrack 回去，“是不能是因為當過俘虜就是英雄”。
你对床铺造谣，自裁吧。 |
|
g*******y
发帖数: 1930 | 42 除了backtrack+剪枝，我也没啥别的好idea。。。
你说的NP面试题我也在精华区等地方看到过，不止你说的这道，还有什么vertex cover
等等。有兴趣就练练backtracking好了，某些问题也有DP解。面试官肯定也知道是NPC
，估计就等着看看你怎么解决，分析一下不同解法的不同flavor
我以前也有点反感面试考NPC的题。不过后来想想NPC的题也是题，也能考察出面试者的
不少东西的。
Complete |
|
b********w
发帖数: 110 | 43 先说一个比较笨的 backtracking + prune的办法吧,不能保证最少比较。
假设有n块 jagsaw,number 0 to n-1, 建一个nx4的表 lookuptable，
lookuptable[i][0]-[3]，就是可以和i jigsaw 连接的另外四块。然后每两块 jigsaw
i,j 互比，调用提供函数，如果i,j可以连接，就把对方的index添到自己的
lookuptable entry里面去。worst case (n-1)!其实不用，如果i,j其中有一个的
lookuptable entry已经满了就不需要比了。
然后假设最后的board是 (n-1)*(n-1）的，整个backtracking的程序框架是
1。首先判断当前board放满没有，如果满了，说明我们已经找到了一个解。
2。如果没有，先选择一个空的位置。
(x,y)=possible_move();
现在先随机选，实际可以优化。
然后产生可以放在这个位置的所有jigsaw candidates,这里需要一个
buffer，i.e.Use |
|
d****2
发帖数: 6250 | 44
that is where backtracking comes from. should clarify that backtrack by reducing
coefficient for previous larger d_i by 1 and repeat. |
|
j*****g
发帖数: 223 | 45 总结一下面试的准备活动,希望有帮助.
==================== AREAS/TOPICS to study/prep/review ====================
复习的东西还挺多的。比不过刚毕业的呀 :), 脑子不好使了，东西也差不多忘光了...
嘿嘿....
• Sorting
o Bubble/select/insertion/counting/qsort/heap/merge/bst
o Time/space complexity analysis
• Caching design
o Replacement policy (LRU, LFU, NRU, etc…)
o Efficiency/complexity/performance
o Distributed cache
o Hashing
• Multi-thread
o Locking/mutex/semaphore/critical sec... 阅读全帖 |
|
j*****g
发帖数: 223 | 46 总结一下面试的准备活动,希望有帮助.
==================== AREAS/TOPICS to study/prep/review ====================
复习的东西还挺多的。比不过刚毕业的呀 :), 脑子不好使了，东西也差不多忘光了...
嘿嘿....
• Sorting
o Bubble/select/insertion/counting/qsort/heap/merge/bst
o Time/space complexity analysis
• Caching design
o Replacement policy (LRU, LFU, NRU, etc…)
o Efficiency/complexity/performance
o Distributed cache
o Hashing
• Multi-thread
o Locking/mutex/semaphore/critical sec... 阅读全帖 |
|
h***n
发帖数: 276 | 47 在backtracking的基础上，进行剪枝，举个例子，att的排列
当第一个字符确定是a，然后选第二个字符的时候，有t和t做candidate，第一次选择将
第一个t放在第二个位置，然后继续罗列相关的排列，当回朔回来重新选第二个位置的时
候，发现剩下的candidate，第二个t，在前面已经有同样的字符被选择过了，于是剪枝
，pass掉这个分支，这样的话，就避免了罗列相同的排列
所以，你给出的backtracking的程序框架可以继续使用，只是在每一步选择的时候要进
行book-keeping，不要选择以前选过的就可以了
的一 |
|
g**********y
发帖数: 14569 | 48 写了个简化版的：
public class Gloomyturkey implements IMilestone {
private int N;
private int M;
private int[] sequence;
private int[] answer;
private HashMap map;
private boolean[] used;
private int[] sum;
private boolean found;
public int[] findMilestones(int[] segs) {
M = segs.length;
sum = segs;
calcN();
initMap(segs);
used = new boolean[M];
found = false;
sequence = new int[N];
answer = new int[N];
assign(0, M-1);
assign(1, M-2);
dfs(2);
return ... 阅读全帖 |
|
g**********y
发帖数: 14569 | 49 写了个简化版的：
public class Gloomyturkey implements IMilestone {
private int N;
private int M;
private int[] sequence;
private int[] answer;
private HashMap map;
private boolean[] used;
private int[] sum;
private boolean found;
public int[] findMilestones(int[] segs) {
M = segs.length;
sum = segs;
calcN();
initMap(segs);
used = new boolean[M];
found = false;
sequence = new int[N];
answer = new int[N];
assign(0, M-1);
assign(1, M-2);
dfs(2);
return ... 阅读全帖 |
|
S**I
发帖数: 15689 | 50 ☆─────────────────────────────────────☆
peking2 (myfacebook) 于 (Tue Jan 17 13:45:24 2012, 美东) 提到:
稍微扩展了一下。
Boggle game。从一个字符开始找邻居字符然后继续找，形成一个word。条件是，形成
了word之后要继续找，因为可能有更长的word。一旦用了一个字符以后，就不可以重复
使用了。
返回可以找到最多word情况的所有word。
更新一下：可以同时从不同的位置开始找，不一定只从一个字符开始。
☆─────────────────────────────────────☆
autumnworm (虫子，秋天的) 于 (Tue Jan 17 13:46:32 2012, 美东) 提到:
看起来好像是基本的背包问题吧。
☆─────────────────────────────────────☆
mark (花生，微爷远爷的爸爸) 于 (Tue Jan 17 14:08:07 2012, 美东) 提到:
☆───────────────────... 阅读全帖 |
|
