g*******y
发帖数: 1930 | 1 这两天写了几十道题目的code，挑几个有疑惑的问问大家
1.Find the largest rectangular matrix with 1's
//网上倒是有个Dr.***的网页上有解答。不过个人认为这题做为面试题过于难了。
2.Wildcard string matching(suffix tree)
//同样觉得面试做suffix tree的题过于难了。
3.怎么组织字典，使得在解cross puzzle时可以很快得到满足条件的所有单词.比如所
有第二个字母是o，第5个是H的单词。
//感觉找不到很好的预处理/加速的方法
4.coding test. 两个不同的link list, node buffer size不一样. 从一个link list
的node考贝到另一个list.
//理解不了题意
5.Write the code to print a Binary tree level by level STARTING FROM THE
LEAF LEVEL
//同时用栈和队列很简单，找一个比同时用栈和队列更好的方法？
6.Give three methods to c |
H*****L
发帖数: 5705 | |
g*******y
发帖数: 1930 | 3 unsigned char BitSetCountTable256[256]
{
# define B2(n) n, n+1, n+1, n+2
# define B4(n) B2(n), B2(n+1), B2(n+1), B2(n+2)
# define B6(n) B4(n), B4(n+1), B4(n+1), B4(n+2)
B6(0), B6(1), B6(1), B6(2)
};
wow，这个太赞了！
【在 H*****L 的大作中提到】
: 6. 这个不错，写起来有点小复杂
: http://graphics.stanford.edu/~seander/bithacks.html
|
k***e
发帖数: 556 | 4 楼主水平和我差不多 ：）基本上答案都一样，你不会的我也不会，哈哈
安装level打印树那题，可以就用一个vector模拟栈和队列，再用一个vector记住没层
的长度应该就可以了。似乎少点时间。
1234那题，除了穷举加backtracking似乎没有更好的方法。
list
【在 g*******y 的大作中提到】
: 这两天写了几十道题目的code，挑几个有疑惑的问问大家
: 1.Find the largest rectangular matrix with 1's
: //网上倒是有个Dr.***的网页上有解答。不过个人认为这题做为面试题过于难了。
: 2.Wildcard string matching(suffix tree)
: //同样觉得面试做suffix tree的题过于难了。
: 3.怎么组织字典，使得在解cross puzzle时可以很快得到满足条件的所有单词.比如所
: 有第二个字母是o，第5个是H的单词。
: //感觉找不到很好的预处理/加速的方法
: 4.coding test. 两个不同的link list, node buffer size不一样. 从一个link list
: 的node考贝到另一个list.
|
r****o
发帖数: 1950 | 5 请问，用递归打印树的level的方法是不是没有栈和队列的方法好？
【在 k***e 的大作中提到】
: 楼主水平和我差不多 ：）基本上答案都一样，你不会的我也不会，哈哈
: 安装level打印树那题，可以就用一个vector模拟栈和队列，再用一个vector记住没层
: 的长度应该就可以了。似乎少点时间。
: 1234那题，除了穷举加backtracking似乎没有更好的方法。
:
: list
|
k***e
发帖数: 556 | 6 貌似这个题目用不了递归吧，至少不能简单的按照左子树右子树来divide，因为左右子
树的结果是纠结在一切
不能分离的。谁有递归方法请指点。 |
r****o
发帖数: 1950 | 7 o,这里是binary tree,但是binary search tree可以用递归把。
【在 k***e 的大作中提到】
: 貌似这个题目用不了递归吧，至少不能简单的按照左子树右子树来divide，因为左右子
: 树的结果是纠结在一切
: 不能分离的。谁有递归方法请指点。
|
f*********r
发帖数: 68 | 8 1. 用DP就可以了时间O(MN), 空间O(MN), 贴一个我写的代码
// [11/7/2009 by Fairylander]
// 最大子矩形
#include
#include
const int N = 201;
int d[N][N]; // '0', '1'
int ht[N][N], lf[N][N], rt[N][N]; //
int m, n;
inline void solve() {
int res = 0;
int i, j;
for(i=1; i<=n; i++) { // init;
ht[0][i] = 0; lf[0][i] = 1; rt[0][i] = n;
}
for(i=1; i<=m; i++) {
int k = 1, tmp;
// 从左向右扫描, (i, j)为长方型的底边上一点, 依次求出对应长方型的高
度ht[i][j],
// 和这个长方型向左最远能延伸到的地方lf[i][j]
|
w********p
发帖数: 948 | 9 为啥我看着它发晕阿？太困了？ 解释一下吧
【在 g*******y 的大作中提到】
: unsigned char BitSetCountTable256[256]
: {
: # define B2(n) n, n+1, n+1, n+2
: # define B4(n) B2(n), B2(n+1), B2(n+1), B2(n+2)
: # define B6(n) B4(n), B4(n+1), B4(n+1), B4(n+2)
: B6(0), B6(1), B6(1), B6(2)
: };
: wow，这个太赞了！
|
g*******y
发帖数: 1930 | 10 你很牛啊！
感觉你以前是搞过竞赛的？
【在 f*********r 的大作中提到】
: 1. 用DP就可以了时间O(MN), 空间O(MN), 贴一个我写的代码
: // [11/7/2009 by Fairylander]
: // 最大子矩形
: #include
: #include
: const int N = 201;
: int d[N][N]; // '0', '1'
: int ht[N][N], lf[N][N], rt[N][N]; //
: int m, n;
: inline void solve() {
|
|
|
y*******g
发帖数: 6599 | 11 suffix tree 的确太复杂。不过suffix array 还可以吧 |
t******e
发帖数: 1293 | 12 2.Wildcard string matching
非suffix tree，而用递归的代码，希望有帮助
这个题目有几个变种：
第一个变种：类似DOS文件名的Wildcard string matching，代码在
http://xoomer.virgilio.it/acantato/dev/wildcard/wildmatch.html
他们能做到的是满足以下条件的match
# Character matching is case insensitive.
# The metacharacter '*' matches any sequence of zero or more characters.
For instance "*.ZIP" matches ".zip", "A*.bbb" matches "A.bbb" or "Axyz.BBB".
# The metacharacter '?' matches exactly one character unless that character
is a period ('.').
# File name matching
【在 g*******y 的大作中提到】
: 这两天写了几十道题目的code，挑几个有疑惑的问问大家
: 1.Find the largest rectangular matrix with 1's
: //网上倒是有个Dr.***的网页上有解答。不过个人认为这题做为面试题过于难了。
: 2.Wildcard string matching(suffix tree)
: //同样觉得面试做suffix tree的题过于难了。
: 3.怎么组织字典，使得在解cross puzzle时可以很快得到满足条件的所有单词.比如所
: 有第二个字母是o，第5个是H的单词。
: //感觉找不到很好的预处理/加速的方法
: 4.coding test. 两个不同的link list, node buffer size不一样. 从一个link list
: 的node考贝到另一个list.
|
t******e
发帖数: 1293 | 13 7. 4x4的正方形，有一些空格已经填入数字(1~4)，条件：每行每列以及每个2x2的小矩
形(只考虑边缘4个小矩形)，1~4四个数字只能出现1次。设计算法
//写出来code很长，而且效率不高（虽然4这个数字很小）。有人能给出简洁的code/高
效的方法的思路吗？
这个题目，其实就是一个简单版的sudoku吧。在MSRA出的编程之美一书里面，有
讲怎么解sudoku的思路。我觉得可以参考里面的思路。
大致如下：先固定左上角的2x2矩阵，里面第一行放12，第二行放34，然后求出所有
的解。有了这些解之后，可以进行变换，比如说，全部的2都换为3，3换为2，得到
另外一套解。
不过要写出code来，还是有点麻烦。
list
【在 g*******y 的大作中提到】
: 这两天写了几十道题目的code，挑几个有疑惑的问问大家
: 1.Find the largest rectangular matrix with 1's
: //网上倒是有个Dr.***的网页上有解答。不过个人认为这题做为面试题过于难了。
: 2.Wildcard string matching(suffix tree)
: //同样觉得面试做suffix tree的题过于难了。
: 3.怎么组织字典，使得在解cross puzzle时可以很快得到满足条件的所有单词.比如所
: 有第二个字母是o，第5个是H的单词。
: //感觉找不到很好的预处理/加速的方法
: 4.coding test. 两个不同的link list, node buffer size不一样. 从一个link list
: 的node考贝到另一个list.
|
t******e
发帖数: 1293 | 14 5.Write the code to print a Binary tree level by level STARTING FROM THE
LEAF LEVEL
//同时用栈和队列很简单，找一个比同时用栈和队列更好的方法？
我想到的算法，先找出树的高度，
然后用类似Iterative deepening depth-first search的算法
来level traverse，回头试试看行不行。
list
【在 g*******y 的大作中提到】
: 这两天写了几十道题目的code，挑几个有疑惑的问问大家
: 1.Find the largest rectangular matrix with 1's
: //网上倒是有个Dr.***的网页上有解答。不过个人认为这题做为面试题过于难了。
: 2.Wildcard string matching(suffix tree)
: //同样觉得面试做suffix tree的题过于难了。
: 3.怎么组织字典，使得在解cross puzzle时可以很快得到满足条件的所有单词.比如所
: 有第二个字母是o，第5个是H的单词。
: //感觉找不到很好的预处理/加速的方法
: 4.coding test. 两个不同的link list, node buffer size不一样. 从一个link list
: 的node考贝到另一个list.
|
f*********r
发帖数: 68 | 15 竞赛没搞过. 要是我们专业工作好找, 也不会IT靠拢了. 唉!没办法.
【在 g*******y 的大作中提到】
: 你很牛啊！
: 感觉你以前是搞过竞赛的？
|
g*******y
发帖数: 1930 | 16 呵呵，你也不是CS出身的么？
【在 f*********r 的大作中提到】
: 竞赛没搞过. 要是我们专业工作好找, 也不会IT靠拢了. 唉!没办法.
|
s*******e
发帖数: 174 | 17 如果是从ROOT开始 level by level print, 是可以用 recursion 做。。
【在 k***e 的大作中提到】
: 貌似这个题目用不了递归吧，至少不能简单的按照左子树右子树来divide，因为左右子
: 树的结果是纠结在一切
: 不能分离的。谁有递归方法请指点。
|
