M*******a
发帖数: 1633 | 1 我一上来就直着排呢？
DP你写个递推式来看看，不要好像碰到个难题就说DP两个字母就算把问题解决了 |
|
|
l******e
发帖数: 54 | 3 就是普通的状态压缩 DP 或者递推
我都把算法描述出来了 看不懂只好丢给你个程序了
int mask = (1 << m) - 1;
f[0][0] = 1;
// 一行一行的来
for (int i = 0; i < n; ++i) {
FILL(f[(i + 1) & 1], 0);
// 枚举本行的铺法
for (int j = 0; j <= mask; ++j) {
// 上一行的铺法
for (int k = 0; k <= mask; ++k) {
// 检查相容
if (check(j, k, mask)) {
// 累加
f[(i + 1) & 1][j] += f[i & 1][k];
}
}
}
}
// 输出解
cout << f[n & 1][0] << endl;
bool check(int ... 阅读全帖 |
|
|
l******e
发帖数: 54 | 5 递推式不是在 code 里吗
f[(i + 1) & 1][j] += f[i & 1][k];
i, j, k 已经解释了的
这个我做空间优化了 你把 & 1 都忽略掉好了 |
|
|
c*******y
发帖数: 98 | 7 我没有明白楼上大牛们的思路，我画了个表
0 1 0 1 0 1 0 1
1 2 3 4 5 6 7 8
0 3 0 7 0 11 0 15
1 4 7 14 21 32 43 58
初始化第一行0 1 0 1 ...
第一列0 1 0 1...
递推公式f(row, col) = f(row-1, col-1) + f(row-1, col) + f(row, col-1)
中间遇到(row+1)*(col+1)为奇数的，设为0。
不知道对不对。 |
|
c*******y
发帖数: 98 | 8 我没有明白楼上大牛们的思路，我画了个表
0 1 0 1 0 1 0 1
1 2 3 4 5 6 7 8
0 3 0 7 0 11 0 15
1 4 7 14 21 32 43 58
初始化第一行0 1 0 1 ...
第一列0 1 0 1...
递推公式f(row, col) = f(row-1, col-1) + f(row-1, col) + f(row, col-1)
中间遇到(row+1)*(col+1)为奇数的，设为0。
不知道对不对。 |
|
c*******y
发帖数: 98 | 9 我没有明白楼上大牛们的思路，我画了个表
0 1 0 1 0 1 0 1
1 2 3 4 5 6 7 8
0 3 0 7 0 11 0 15
1 4 7 14 21 32 43 58
初始化第一行0 1 0 1 ...
第一列0 1 0 1...
递推公式f(row, col) = f(row-1, col-1) + f(row-1, col) + f(row, col-1)
中间遇到(row+1)*(col+1)为奇数的，设为0。
不知道对不对。 |
|
l******e
发帖数: 54 | 10 楼上大牛介绍的是“刷表法” 由上一行刷下一行
我给出的例程其实是从当前行找上一行的“填表法” 可自行 Google 这两种方法的更
多信息
更喜欢刷表法 加 continue 是一个很大的优化 另外还需要改的是递推式里的 j 和 k
要换一下位置其他不变
f[(i + 1) & 1][k] += f[i & 1][j];
最后变成：
int mask = (1 << m) - 1;
f[0][0] = 1;
for (int i = 0; i < n; ++i) {
FILL(f[(i + 1) & 1], 0);
for (int j = 0; j <= mask; ++j) {
if (f[i & 1][j] == 0) continue;
for (int k = 0; k <= mask; ++k) {
if (check(j, k, mask)) {
f[(i + 1) & 1][k] += f[i & 1][j];
}
... 阅读全帖 |
|
u****z
发帖数: 43 | 11 看到一个Game Economist的opening。想看看班上有没有人在里边工作可以帮忙递一下
简历。 |
|
|
|
l******e
发帖数: 54 | 14 一样思路改成递推就行了 空间是还可以优化的
class Solution {
public:
vector generateParenthesis(int n) {
vector f[n + 1][n + 1];
f[0][0] = vector {""};
for (int left = 0; left <= n; ++left) {
for (int right = 0; right <= left; ++right) {
for (const string& s : f[left][right]) {
if (left < n) {
f[left + 1][right].push_back(s + "(");
}
if (right < left) {
f[left][right + 1].push_back(s + ")");
}
... 阅读全帖 |
|
i*x
发帖数: 137 | 15 大家抓紧了。recuriter递来的都是老印的简历。
还有我们需要有mobile QA experience的candidate。
/* */ |
|
r*****e
发帖数: 30 | 16 好吧，我明白你的意思了
第4题括号匹配是一个Catalan Number的问题
你看下http://en.wikipedia.org/wiki/Catalan_number#Applications_in_combinatorics里面有个浅蓝色的图
就是有箭头的那张，每个向右的箭头对应一个‘（’，每个向上的箭头对应一个‘）’
,同时要满足任何时候'（'的数量>=')'的数量
所以递推式就是 f(i,j) = (j-1>=i?f(i,j-1):0) + （i-1>=0?f(i-1,j):0),其中i是
行，j是列,行对应‘）’，列对应‘（’
算完整个矩阵后，n对括号，第k大的问题就是从f(n,n)开始往f(0,0)走，走的过程中比
较f(i,j)和k的关系，从而决定该往下走，还是往左走，同时加上括号，如果当前在(i,
j）的位置，如果i-1>=0&&f(i-1,j)>=k,就向下走同时加一个'(',否则向左走同时加一
个‘）’，并且更新k-=f(i-1,j) |
|
d***e
发帖数: 193 | 17 一个猎头两个多月之前在monster上看了我的简历，联系说有公司招人，还告诉了我公
司的名字和job description，工作内容正是我想做的，很高兴，就给他发了我最新的
简历。过了三个星期问他怎么样，回复说对方准备phone interview了。
又过了一周，让我填了关于skill set的表，当天就说要约电面时间，问我接下来一周
的availability，给他说了几个时间，结果一直没回复，后来催，说还在等公司那边的
答复，过了两天说我给的时间对方公司没空，要周五或者下周，我说周五我没时间，就
下周一或者周二早上吧，又没消息了。
这不，现在周五了，猎头还没回复到底下周能不能电面。
大家说，这猎头到底靠谱吗？话说这家公司我还真认识一个人，不过不在我申请的这个
部门，不知道要不要找认识的人推一下公司里呢？谢谢 |
|
b******g
发帖数: 3616 | 18 sort by base area的原因是
当A1*A2 > B1*B2时，必然意味着A1>B1 || A2>B2，也就是说排除了A可以叠在B上面的
可能性。所以如果以base area排序以后。对于box B来说，排在它后面的所有盒子都无
法叠在它上面，而只需要检验排在它前面的那些盒子是否都符合两边同时小于B1 & B2。
这也就是为什么2楼大牛给的递推公式是：
f[j] = max{f[i]}+Hj (i
f[j]表示box j为最底下时的最大高度。依次检查排在j前(i
，如果A1i
box i为底的最大高度 f[i] + box j本身的高度 Hj。
如果sort by A1或A2道理也是一样的。
假如sort by A1，那么在检查candidate box i的时候，只要判断 A2i |
|
b******g
发帖数: 3616 | 19 也看过不少KMP的讲解，觉得确实是matrix67讲得最清楚。CLRS讲得太生涩。之前刷lc
的strStr()这题是用土办法2 points做的，今天也跟风写了个KMP版的strStr()过了下
lc.
BTW: 今天才发现lc这题的interface改了，以前是返回指针，现在变成返回起始index
了。
vector KMPpreprocessing(char *needle) {
int m = strlen(needle);
// assume j = match[i]: needle[i-j:i] == needle[0:j]
vector match(m,-1);
int j = -1;
for(int i=1; i
while(j>=0 && needle[i]!=needle[j+1]) j = match[j];
if(needle[i]==needle[j+1]) j++;
... 阅读全帖 |
|
a********r
发帖数: 217 | 20 这个递推的精髓就是要能看懂 CLRS那个引理的证明, 即集合PI*(i) 是P_i所有的
suffix的集合。花半个小时, 好好看看书上证明。各种符号都在那个章节第一页定义了。
lc
index |
|
w***w
发帖数: 84 | 21 DP 其实就是递归。 设c(i,j)是从i-th cut 到j-th cut的线段的最小cost, 就有递归
式，c(i,j) = min_{i
不能直接递归去解，否则会指数爆炸。DP 的trick就是递归过程中记住所有见过的解，
每次递归先去查解是否已存在。或者是通常看到的递推的自底而上的填表式的解法。
至于Huffman编码，假设题目是切出要求长度的一些木块但并不限定order的话，这样你
可以把长度看成是概率 （设木板总长是1)，那么这里的cost定义就等价于平均码字长
度, 因为每一小段contribute的cost就是把它切出来需要的cut数。 |
|
s********a
发帖数: 206 | 22 哥们组里招人，帮忙递了简历，HM根据我的简历，重改了广告，使我完全符合。但这样
一来，别人符合的就少了。
这种情况，第一次碰见，很有压力。 |
|
r*****3
发帖数: 27 | 23 可以dp的, 不过LZ代码没给全吧
就是i对括号的可以这样考虑, 最左边的做括号对应的右括号有i种情况, 对于每一种情
况, 这对括号里面的j对括号已经在之前被计算过, 因为j
i-j-1对括号也已经在之前被计算过, 因为i-j-1
递推式
buff[i]中的元素 = '(' + buff[j]中的任意一个 + ')' + buff[i-j-1]中的任意一个
, 枚举j就行了, 0 <= j <= i-1 |
|
D*********G
发帖数: 193 | 24 更新
"We have a big push for Level5+ candidates, and Mobile is definitely a plus"
*****************************************************
@new graduate, 有HR系统的screening(我感觉他们主要看学校)，这个我帮不了太多
@有经验的，如果是infra，big data，machine learning的，我可以强力推荐
@mobile的bar会低点，有实际产品经验都容易拿到面试
@其他的，如果是Data science或者非SDE的职位，我只能帮你递简历，无法reach out
HR
最近推荐的所有的有相关经验的，都拿到面试了：
1. 大的软件公司过来的，肯定都有面试
2. 之前不是软件公司，但是你自己做过相关的project(学校或者open source)，也没
问题
*****************************************************
******************************... 阅读全帖 |
|
D*********G
发帖数: 193 | 25 更新
"We have a big push for Level5+ candidates, and Mobile is definitely a plus"
*****************************************************
@new graduate, 有HR系统的screening(我感觉他们主要看学校)，这个我帮不了太多
@有经验的，如果是infra，big data，machine learning的，我可以强力推荐
@mobile的bar会低点，有实际产品经验都容易拿到面试
@其他的，如果是Data science或者非SDE的职位，我只能帮你递简历，无法reach out
HR
最近推荐的所有的有相关经验的，都拿到面试了：
1. 大的软件公司过来的，肯定都有面试
2. 之前不是软件公司，但是你自己做过相关的project(学校或者open source)，也没
问题
*****************************************************
******************************... 阅读全帖 |
|
|
|
M**********7
发帖数: 378 | 28 非大神，上面有人说的不错。
说说自己的理解：
DP的一大要素是子问题最优解可以应用到所有包含该子问题的最优解中。
贪心如果满足这个要素，就是DP，或可以转化成DP；如果不满足，就是因为没有更好的
方法而找一个近似的，这种情况下就不是DP。
三种方法广义来说都是将问题降规模求解，只是我们一般说分治一般都是logN级的降，
例如那个MxN走矩阵或者LIS的方法是一个个递推，一般不叫分治。 |
|
d*********5
发帖数: 53 | 29 一月初面的FB电面。
电面过程：一个三哥面的我，但是题时两道leetcode题。两道题写的代码都能过
leetcode。 其中第二题 稍微有点难度(会不会这里出了问题，求分析)，decode ways
， 我先说
了下 如果dfs的话（画了一颗树），会有一些重复子问题，考虑用dp。然后讲了讲递推
式，中间口误说错了下标的意思，但是很快自己纠正过来了。接下来，说了下依赖的问
题 和分析 边界条
件。最后就直接写代码了，写的时候说了一下’0’的问题什么的， 我写的是o(n) 空
间的。最后让我分析时间空间复杂度的时候，我提了可以优化到constant memory，大
概描述了下怎么搞，面试官没让我写代码。后来还测了三四个数据，都是ok的。电面就
这样愉快的结束了。
一周过去了，没有结果。我有点急，就去催hr了。发了3封邮件，都没有得到回复。然
后打了几个电话给他，第一个留了voice message，但是一个都没接通，很奇怪。最后
我找了coordinator帮我联系hr，hr半小时多点就给了我一封拒信。醉了。后来跟hr沟
通下了，他说是因为competition 比较激烈，有点无话可说... 阅读全帖 |
|
M**********7
发帖数: 378 | 30 麻烦大神写一下递推式。
想了一下总觉得子问题不独立，因为假设子问题某区排好序但元素又不一定固定。
加上像下面这种需要把一对情侣都换出来的情况实在是想不清楚了。
（同字母代表一对情侣，空格不是空位，只是为了看起来方便，D 是分开的情侣，X Y
单身）
AABBCC D EEFFGG D HHIIJJKKLLMM X Y
多谢！ |
|
l*******i
发帖数: 57 | 31
我勒个去，没想到这题这么复杂，本来想问个DP的递推公式的。
GG店面都是这种难度了，丧心病狂 |
|
C**R
发帖数: 16 | 32 碰到过一个前google的员工，
电话面试给hr的feedback是，他开始几行code我不知道他写的什么。
我在一开始就跟人家说了，这个问题要用recursive的方式解，这是解的递推公式，放
在开头的comment里。
我确认他没问题了，才开始写code。
结果feedback就是“他开始几行code我不知道他写的什么” |
|
t**********h
发帖数: 2273 | 33 我擦
就帮忙递个简历而已，又不做啥，有啥不乐意的 |
|
t**********h
发帖数: 2273 | 34 我擦
就帮忙递个简历而已，又不做啥，有啥不乐意的 |
|
c****8
发帖数: 76 | 35 大家好，reverse string: abcd --> dcba. 其实方法很简单，就是two pointers，一
个从头开始扫，一个从尾开始扫，然后swap就行。复杂度为：O(n)。但被问及是否可以
做到O(logn)，我怎么想也没有想出O(logn)的方法，就算是divide and conquer 或者
类似 binary search的方法，最后的复杂度也是O(n)。因为递推公式是：T(n)=2T(n/2)
+1。
想问问大家有没有O(logn)的算法？谢啦。 |
|
|
l******9
发帖数: 217 | 37 感谢楼主已经把简历递上去了，神速！
等有面试了再来汇报
//
com
uber |
|
|
w*********e
发帖数: 49 | 39 楼主非常nice，很快就帮忙把简历递上去了，万分感谢！ |
|
b*******r
发帖数: 41 | 40 楼主很神速的帮助把简历给递上去了。十分感谢。
不过Recruitor也很神速的来信说背景不符。。。请问这种情况是还可以申请其它的不
同职位吗？还是直接进小黑屋了？ |
|
|
|
l******9
发帖数: 217 | 43 感谢楼主已经把简历递上去了，神速！
等有面试了再来汇报
//
com
uber |
|
|
w*********e
发帖数: 49 | 45 楼主非常nice，很快就帮忙把简历递上去了，万分感谢！ |
|
|
l********r
发帖数: 7 | 47 每一片可以刷两种颜色，相临三片不能同色这题，组合数学还是别的递推？
1.离散化+线段树（多个值域记次数，query走到底求和），构造O(n)，每次query O(
log n)
2.一个hashmap存所有边，一个邻接表存对数的边和数量。
删点O（n），其他O（1）
4.A）递归dfs，O（n） B和C）堆性质向上走，O(log n)
有啥猫腻么？ |
|
i****7
发帖数: 26 | 48 好像有点像，不太记得了，反正就是分成最后两片一样和最后两片不一样，
然后递推就很明朗了。 |
|
w*********e
发帖数: 49 | 49 递推公式大概长这样：
f(n) = min_{1<= i <= sqrt(n)}{f(n - i*i)} +1
f(0) = 0
O(n^1.5) |
|
w*******z
发帖数: 39 | 50 这个复杂度应该是pseudo polynomial吧
有真正p的解法吗
递推公式大概长这样：f(n) = min_{1 |
|
