|
|
p*****2
发帖数: 21240 | 3
backtrack我的solution里边有。 |
|
b********g
发帖数: 43 | 4 public void solveSudoku(char[][] board) {
// Start typing your Java solution below
// DO NOT write main() function
solveSudoku(board,0,0);
}
private boolean isConsistent(char[][] board, int col, int row, int n) {
for(int i=0;i<9;i++)
if(board[i][col]==(n+'0'))
return false;
for(int j=0;j<9;j++) {
if(board[row][j]==(n+'0'))
return false;
}
//check small box
int bo... 阅读全帖 |
|
|
p**e
发帖数: 533 | 6 如果一个节点的两个子节点分别是右边的和下面的，感觉BFS或者DFS就可以了，
需要backtracking跟他们相结合吗？一起用的优势是什么？
另外，BFS或者DFS是不是很多节点都被扫过多次？有没有办法保证只扫过一次？ |
|
U*********y
发帖数: 54 | 7 题目: transform one word into another, 1 letter at a time, each step must
be
in the dictionary.
CareerCup的BFS解看起来很麻烦, 既然没要求最短距离转换或得出所有可能转换, 就写
了个DFS+backtracking的解, 请指教!
[code]
unordered_set dict; //dictionary
bool validTran(string &a, string &b, int d, unordered_map
string> &path) {
if(a == b) {
return 1;
}
if(d == b.size()) return 0;
if(a[d] == b[d]) { //no change at this position is needed
return validTran(a, b, d+1, path);
}
for(char ... 阅读全帖 |
|
D********g
发帖数: 650 | 8 20分钟写了大约下面的code，如果要输出string，还要backtrack:
static String word2Anagram(final String word) {
if (word == null) {
return null;
}
int ht[] = new int[256];
for (int i = 0; i < word.length(); ++i) {
int charVal = (int) word.charAt(i);
ht[charVal] ++;
}
StringBuilder anagram = new StringBuilder();
for (int i = 0; i < ht.length; ++i) {
if (ht[i] > 0) {
anagram.append((cha... 阅读全帖 |
|
D********g
发帖数: 650 | 9 加上了backtracking:
static class DPElement {
int value;
int prevCostIdx; // 0-based cost idx
int takenThisElement; // 0/1, indicating whether taking current
element, idx 0 based.
public DPElement() {
value = 0;
prevCostIdx = 0;
takenThisElement = 0;
}
}
static String word2Anagram(final String word) {
if (word == null) {
return null;
}
int ht[] = new int[256];
f... 阅读全帖 |
|
z****h
发帖数: 164 | 10 lz能否透露一下那些签了NDA的面试题的范围是什么？不用很具体，类似 有没有dp, 有
没有backtrack,有没有150, leetcode之外的题？
谢谢先 |
|
t**********h
发帖数: 2273 | 11 这个是dp吧，然后backtracking？
中某 |
|
f*********m
发帖数: 726 | 12 Print All Combinations of a Number as a Sum of Candidate Numbers
（http://www.leetcode.com/2010/09/print-all-combinations-of-number-as-sum.html）
原文如下，稍作修改（把target 从7该为9）：
“To search for all combination, we use a backtracking algorithm. Here, we
use the above example of candidate={2,3,6,7} and target=9.
First, we start with a sum of 0. Then, we iterate over all possibilities
that can be added to sum, which yields the possible set of sum={2,3,6,7}.
Assume now that sum=2, we continue adding all poss... 阅读全帖 |
|
S*******e
发帖数: 379 | 13 把matrix每个格子作为起始点，递归尝试每个方向，用一个extra matrix记录到过的点。
每visit一个点，跟字典比较是不是合法的单词。
如果字典保存在trie里，递归的时候可以terminate的早一点。
有其他更好的解法吗？ |
|
S*******e
发帖数: 379 | 14 顶一下，哪位大牛能帮忙confirm一下？
点。 |
|
S*******e
发帖数: 379 | 15 把matrix每个格子作为起始点，递归尝试每个方向，用一个extra matrix记录到过的点。
每visit一个点，跟字典比较是不是合法的单词。
如果字典保存在trie里，递归的时候可以terminate的早一点。
有其他更好的解法吗？ |
|
S*******e
发帖数: 379 | 16 顶一下，哪位大牛能帮忙confirm一下？
点。 |
|
|
b*******e
发帖数: 217 | 18 Simply backtracking problem? Sure dfs ok for this kind of problem
在 flynewdream (fly) 的大作中提到: 】
all |
|
b*******e
发帖数: 217 | 19 Simply backtracking problem
在 flynewdream (fly) 的大作中提到: 】
all |
|
a*******y
发帖数: 1040 | 20 You have a matrix of size n*n with entries either 1 or 0. 1 means there is a
path, 0 means no path. Find shortest path and print it from (0,0) to (n-1,
n-1)
这个我觉得用backtrack，但是keep那个path有点麻烦，假如你在某一点发现路径走的
cell数目相同，你怎么update那个path？任选一个？ |
|
|
|
f*********m
发帖数: 726 | 23 非常感谢。
是不是有些backtracking的意思？或者树生长的意思？
result恢复到以前的某个状态（对应stack最后一个元素的内容所指的前一个配置），
然后根据stack最后一个元素的内容继续生长树（继续配置）？
1 |
|
g****y
发帖数: 240 | 24 是的，有点backtracking的意思。回复到某个状态就绪生长。 |
|
D**f
发帖数: 439 | 25 愿闻其祥，我觉得只能是backtracking，除了暴力破解没别的方法吧。 |
|
|
c********t
发帖数: 5706 | 27 用backtracking + recursion是O(n)时间，O(1)空间吗？
我的48个case都过了，但是judge large超时了！ |
|
c********t
发帖数: 5706 | 28 用backtracking + recursion是O(n)时间，O(1)空间吗？
我的48个case都过了，但是judge large超时了！ |
|
N*********6
发帖数: 4372 | 29 个人觉得既然正负都无所谓的话，四个象限的情形都可以
映射到第一象限，应该可以证明从其他象限绕的valid path
都可以通过在第一象限走到目的地，而且path相对比较短
所以只考虑第一象限的情形，四个方向可以简化为只能往右
和往上走，这样就和经典的robot moving problem 一样了
用dp可以找出总共有多少条路径，backtracking可以打印或者
计算总共的路径，这道题不需要算总数和打印，只需要算其
中一条valid path的长度，相对简单一些
参见
http://prpds.blogspot.com/2011/07/robot-in-nxn-grid_18.html
以及career cup里面的moving robot 例子
K
到( |
|
N*********6
发帖数: 4372 | 30 个人觉得既然正负都无所谓的话，四个象限的情形都可以
映射到第一象限，应该可以证明从其他象限绕的valid path
都可以通过在第一象限走到目的地，而且path相对比较短
所以只考虑第一象限的情形，四个方向可以简化为只能往右
和往上走，这样就和经典的robot moving problem 一样了
用dp可以找出总共有多少条路径，backtracking可以打印或者
计算总共的路径，这道题不需要算总数和打印，只需要算其
中一条valid path的长度，相对简单一些
参见
http://prpds.blogspot.com/2011/07/robot-in-nxn-grid_18.html
以及career cup里面的moving robot 例子
K
到( |
|
C***U
发帖数: 2406 | 31 如果用的是vector而不是数组的话 无法通过online judge large
哪里可以再优化一下啊？
谢谢了
int placeQueens(int n) {
int count = 0;
int *positions = new int[n];
int p = 0;
positions[p] = 0;
int i = 0;
while(!(p == -1 && i == n)) {
bool flag = true;
while(flag && i < n) {
int j = 0;
while(j < p + 1) {
if(positions[j] == i || positions[j] - i == j - (p + 1)||
positions[j] - i == p + 1 - j) {
break;
}
... 阅读全帖 |
|
C***U
发帖数: 2406 | 32 yes. you can try it.
but not perfect.
used 900 millisecond |
|
c****9
发帖数: 164 | 33 刚刚写的，不知道算是DP还是recursive，基本上是brute force
bool checkpos(vector& cur, int pos)
{
for(int i=0;i
{
for(int j=0;j
{
if(cur[i][j] =='Q')
{
if(j==pos)
{
return false;
}
else if(i+j == pos + cur.size())
{
return false;
... 阅读全帖 |
|
|
C***U
发帖数: 2406 | 35 900 milliseconds
那个judge large总共也没几个例子
我不知道算不算慢 |
|
c********t
发帖数: 5706 | 36 赞，是不是字符的permutation问题一般都是用dfs+backtracking来解决？
pqrs |
|
c********t
发帖数: 5706 | 37 不懂，你是说遍历，并用backtracking的方法存下两个node所在的path (list),
然后在两个list里找最后的共同node吗？
空间复杂度是多少？ |
|
b***m
发帖数: 5987 | 38 来自主题: JobHunting版 - 贡献一道题
参考8皇后backtrack的解法。 |
|
h****n
发帖数: 1093 | 39 来自主题: JobHunting版 - 贡献一道题 写了一个，没测，楼主测测有问题告诉我
bool isWord(string s)
{
if(s=="this") return true;
if(s=="is") return true;
if(s=="desk") return true;
if(s=="top") return true;
if(s=="desktop") return true;
return false;
}
void Helper(string &inputS, int start, string &tmpStr, vector &res)
{
if(start == inputS.size())
{
//删除多余的空格
tmpStr.erase(tmpStr.end()-1);
res.push_back(tmpStr);
//补回来以便正确的backtracking
tmpStr.push_back(' ');
return;
}
int i;
stri... 阅读全帖 |
|
r**d
发帖数: 90 | 40 来自主题: JobHunting版 - 贡献一道题 using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
namespace ConsoleApplication1
{
class Program
{
static private bool isWord(string s)
{
switch (s)
{
case "this":
case "is":
case "a":
case "all":
case "some":
case "allsome":
return true;
}
return fal... 阅读全帖 |
|
k****r
发帖数: 807 | 41 目测的话，我想用recursive＋backtrack
分情况的, 我简单写了下，请指正
bool matchwords(char* word1, char* word2, int index1, int index2) {
if (index1 == strlen(word1)&& index2 == strlen(word2)) return true;
else {
if (word2[index2] == '*') {
if (matchwords(word1, word2, index1+1, index2+1)) return true;
else if (matchwords(word1, word2, index1+1, index2)) return true;
else if (word2[index2] == '?') {
return matchwords(word1, word2, index1+1, index2+1);
else {
... 阅读全帖 |
|
g*******r
发帖数: 44 | 42 思路就是backtracking,做到bug-free有点难啊。 哪位有简洁明了的代码啊？好学习一
下。 |
|
|
c********t
发帖数: 5706 | 44 Backtracking怎么解？
★ 发自iPhone App: ChineseWeb 7.7 |
|
m*******1
发帖数: 77 | 45 把标题改了更符合版上的规范。
————————————————————————————
上周四的onsite， retail 组，四个面试官，前两个是印度人，
第一个让写一个hashmap, 我用linkedlist处理collision, 然后按照cracking code 上
面讲的写了一个非常简单的hash 函数，他说太简单，我后来改了一个复杂些的，用每
一个char * i *13再求和构建。然后问了一些java的基本题目，都答了上来。
第二个让解决一个迷宫，先问我用什么数据结构，我先说数组，他不满意，后来我说可
以用图，然后类似于BFS来进行查找，同时保持一个backtrack map来记录路径。然后写
代码。
后两个是美国人
第三个写populate 同一层的二叉树，可以非常稀疏，我写了出来，无bug。然后问了
2sum, 3sum，都答了上来。然后问了machine learning基本知识，也都答了上来。
第四个是系统设计和分析，包括判断哪里出问题以及策略等。最后一个问题我想了一段
时间，我们出了面试房间到厨房继续，十几分钟后我想了出来，然后就结束了。
今天收到电话，悲... 阅读全帖 |
|
c********t
发帖数: 5706 | 46 嗯，对，DFS, BFS都可以，如果写backtracking+recusion,DFS容易些。
没收官。收了一个电锯，一个面具。 |
|
c********t
发帖数: 5706 | 47 Queens的题都是用backtracking+recursion吧?
N-Queens II与N-Queens 解法有什么不同？除了更简单，因为不用存结果. |
|
M********5
发帖数: 715 | 48 我好心地准备了差不多3个多月了，就等着google的电面，150，leetcode，
geeksforgeeks，差不多都写了一遍，看到题目了都能够马上come up with an idea，
结果这个人，根本就不按照常理出牌！什么都没有考到！什么tree，linkedlist，
graph，string processing，recursion, backtrack, dynamic programming, TCP/IP
，通通没有考，考了几个不知道从哪个犄角旮旯找出来的问题！！！没有天理啊！！！
末了跟我说，你可以去跟recruiter去抱怨？？？？？！！！！！
几个月的辛苦就这样泡汤了。。。
题目就不能剧透了，反正是些很边边角角你从来都没有想到过会复习到那种地方的，关
键是根本就不是algorithm design的题目
如果我挂了，我可以跟recruiter反映了再重新面试一遍吗？我有点觉得这个人就是搞
那种很偏的东西的geek。。。 |
|
f*****7
发帖数: 92 | 49 我个人不喜欢swap的方法，自己没法理解
排序，然后跳过重复元素
希望能帮上你
class Solution {
public:
vector > permuteUnique(vector &num) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
sort(num.begin(), num.end());
int len = num.size();
int* path = (int*) malloc(sizeof(int) * len);
bool* visited = (bool*) malloc(sizeof(int) * len);
memset(visited, false, sizeof(bool) * len);
vector > bigList;
int... 阅读全帖 |
|
c*******r
发帖数: 309 | 50 For example, given candidate set 2,3,6,7 and target 7,
A solution set is:
[7]
[2, 2, 3]
这题如果用backtrack来做的话复杂度是多少？ 感觉是O(N^2) |
|
