b**y
发帖数: 13 | 1 谢谢zhangchitc， 我大概看了一下careerup上的一个解答，它好像有个假设假定只有
两个单词组成
以前没用过trie，不知道你说的我是不是理解对了。如果要从code实现，先要把字典里
所有单词读出来构建一个Trie,然后从最长的单词开始枚举 （有没有比较好的trie的
opensource可以拿来直接用，是不是自己还要实现对Trie的单词长度排序呢？我以前没
用过Trie）
对每个单词用动态规划判断W是否是复合单词
for every position i(except n) in word W
if (W[i+1:n] is a word || isCompositeWord(W[i+1:n]))
return true;
return false
记录下最长的复合单词,可行吗？ |
|
b**y
发帖数: 13 | 2 谢谢peking2指教，看网上有说用trier来解决字典搜索问题效率比hashtable快，另外
还有个疑惑：如果要从最长的单词开始枚举，还需要让hashtable按单词长度排序，不
知道hashtable和trie哪个容易实现排序？ |
|
z********c
发帖数: 72 | 3 我的想法：
假设一个短的单词可以被用多次来组成一个长单词，比如['a', 'aaaa']，如果只用一
次就不会了
如果这样的话，从长到短枚举单词，设W，用动态规划判断W是否是复合单词。
F[i]表示W的前i个字符是否能被分解，true可以，false不行
F[i] = true, 如果存在k，使得F[i - k] = true，并且W[i - k + 1, i]这段字符串在
字典里存在
状态数O(L)
决策数O(L)
判断是否存在字典可以用Trie, O(L)
动态规划复杂度O(L^3)，总复杂度O(NL^3)
可以优化一个地方，就是决策当决策从小到大增加的时候，要不断去Trie检查
W[i, i]
W[i - 1, i]
W[i - 2, i]
...
W[i - k + 1, i]
是不是存在，我们可以把所有单词按照反序插入，比如abcd，那么插入普通Trie的时候
是a是根，那么反序就是d是根，那么当决策k增加的时候，就可以直接在Trie中一边行
走一边判断了，动态规划的总的复杂度可以减少一个L的判断时间，变成O(L^2)，总的
优化成O(NL^2)
CareerCup上好像有个... 阅读全帖 |
|
b**y
发帖数: 13 | 4 谢谢zhangchitc， 我大概看了一下careerup上的一个解答，它好像有个假设假定只有
两个单词组成
以前没用过trie，不知道你说的我是不是理解对了。如果要从code实现，先要把字典里
所有单词读出来构建一个Trie,然后从最长的单词开始枚举 （有没有比较好的trie的
opensource可以拿来直接用，是不是自己还要实现对Trie的单词长度排序呢？我以前没
用过Trie）
对每个单词用动态规划判断W是否是复合单词
for every position i(except n) in word W
if (W[i+1:n] is a word || isCompositeWord(W[i+1:n]))
return true;
return false
记录下最长的复合单词,可行吗？ |
|
b**y
发帖数: 13 | 5 谢谢peking2指教，看网上有说用trier来解决字典搜索问题效率比hashtable快，另外
还有个疑惑：如果要从最长的单词开始枚举，还需要让hashtable按单词长度排序，不
知道hashtable和trie哪个容易实现排序？ |
|
s********0
发帖数: 34 | 6 思路： 先排序，然后枚举i，取p
void three_sum(int *a, int n, int k){
sort(a, a+n);
for(int i = 0; i < n; i++){
int t = k-a[i];
int p = i+1, q = n-1;
while(p < q){
if(a[p] + a[q] == t){
cout<
while(p < q && a[p] == a[p+1]) p++;
p++;// start from next
}
else if(a[p] + a[q] < t) p++;
else q--;
}... 阅读全帖 |
|
D********g
发帖数: 650 | 7 可以基于字典对每一种长度的单词建一个language model + trie，用 prefix 做
pruning
首先把单词按照长度bucket,
LM简单点的就是对每个bucket计算P(char_at_i+1 | char_at_i)。然后按照这个分布来
枚举下一个字母。同时用trie来check prefix是不是正确。
不过这肯定不是理论上最好的解.. |
|
p*****2
发帖数: 21240 | 8
recursion, bruteforce, 枚举各种可能的情况。 |
|
z****e
发帖数: 54598 | 9 http://stackoverflow.com/questions/70689/efficient-way-to-imple
class Foo {
private static volatile Bar bar = null;
public static Bar getBar() {
if (bar == null) {
synchronized(Foo.class) {
if (bar == null)
bar = new Bar();
}
}
return bar;
}
}
1.5之后加一个volatile关键字，也能解决问题
但是牺牲了效率，因为volatile关键字本身就降低了效率
所以double check的完美其实并不完美，本身也降低了效率
既然降低了效率，那还不如直接消费掉那点内存算了
最bitchy的是enum的解决方式
简单说是把class写成enum
public ... 阅读全帖 |
|
H********e
发帖数: 130 | 10 我也贴一个我做的，大数据测试60ms
我的写了一个子函数，可以生成 大小为m的 subset，subset不会因为duplicate
element重复，然后主函数循环调用子函数
class Solution {
public:
vector > subsetsWithDup(vector &S) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector > subsets;
if(S.size()==0)
return subsets;
sort(S.begin(),S.end());
int len=S.size();
int * a=new int[len];
for(int i=0;i
a[... 阅读全帖 |
|
p********s
发帖数: 37 | 11 嗯俺也这么觉得的，只能想到枚举所有的硬币组合然后dp最少需要多少枚。
也考虑过费用流，不过建不出模型 |
|
c**s
发帖数: 159 | 12 NP-hard...
一般做法是dp 枚举之类的 |
|
h*******e
发帖数: 1377 | 13 n&(n-1)可以用在8 皇后问题里面，枚举下一个取得皇后。
-1 |
|
d*k
发帖数: 207 | 14 请问这正常吗？是不是我的算法还不够好？
我用的方法是dfs，逐行枚举能够放下皇后的位置，对于每个位置，需要O(1)的时间判
断是否能够放下皇后。没有其他剪枝。更新buffer是把当前解存下来，是为了做N-
Queens时候用的。代码如下。
class Solution {
public:
void search(int row, int pos, int* buffer, bool* taken, bool* diag_left_
taken, bool* diag_right_taken, int* count, int row_num) {
if (row == row_num) {
*count += 1;
return;
}
if (pos == row_num) {
return;
}
int diag_left = pos - row + row_num;
int di... 阅读全帖 |
|
|
i**********e
发帖数: 1145 | 16 你的算法每次从queue 里取出一个字出来，就要遍历hashtable 里所有的字。
这很不efficient，因为字典内可能含有很多字。还有就是，hashtable 遍历好像很不
efficient，只有查询最适合。
倒过来思考：
把queue 取出来的那个字的所有可能性枚举出来。
如果字的长度是6，那么所有可能性就是 26*6 = 156，远远小于字典内的个数。 |
|
i**********e
发帖数: 1145 | 17 你的算法每次从queue 里取出一个字出来，就要遍历hashtable 里所有的字。
这很不efficient，因为字典内可能含有很多字。还有就是，hashtable 遍历好像很不
efficient，只有查询最适合。
倒过来思考：
把queue 取出来的那个字的所有可能性枚举出来。
如果字的长度是6，那么所有可能性就是 26*6 = 156，远远小于字典内的个数。 |
|
b****g
发帖数: 192 | 18 "把queue 取出来的那个字的所有可能性枚举出来。"
这句是什么意思？ |
|
S******t
发帖数: 151 | 19 假设这两点是u, v，枚举剩下的点w，计算dist(u,w) + dist(w,v)，给出second
shortest就行了
getShortestPath |
|
a*******3
发帖数: 27 | 20
re，枚举中心点是回文O(n^2)算法中最好写，而且是最省空间的。不过要注意回文的长
度可能是奇数也可能是偶数的。 |
|
c****m
发帖数: 179 | 21 5.1？是说尽量把每两个node划分为一个subtree，递归枚举所有情况，寻找valid的
case？ |
|
R******1
发帖数: 58 | 22 你的这个不对吧，反例是E（2） = 161/36 = 4.4722 （leetcode的答案是对的）
暴力枚举就可以：
E（2） = （1*1 + 2*3 + 3*5 + 4*7 + 5*9 + 6*11） / 36
说不上你的逻辑哪里不对，但是3/6*3.5感觉怪怪的。 |
|
p******9
发帖数: 47 | 23 这题可以转化成 在N个数的环形数组中取不相邻的N/3(上取整)，使这些数和最大。我
们可以证明任意这N/3个不相邻的数，必然能对应一种符合原题的取法。
可以用数学归纳法证明这个问题，为了方便，重新定义一下变量名，另M为我会取得到
的比萨数，则N有三种情况，即N=3M - 2 , N = 3M - 1, N = 3M，我们只证明N = 3M -
2这种情况，因为这个时候若能取到，N= 3M - 1或N = 3M 的时候肯定能取到。
（1）基础条件：若M <= 3，我们可以枚举证明以上命题成立。
（2）假设M的时候成立，我们证明M + 1的时候也成立。在M + 1的时候，将会有N = 3
(M + 1) - 2= 3M + 1块比萨。而此时M + 1块比萨之间互不相邻，则在这M + 1块比萨
间将会有M + 2个槽（考虑到比萨时环形的），我们将剩余的2M块比萨放到这M + 2个槽
里，因为M >=3，基于鸽笼原理，必定会有两个比萨落到这个槽里。此时整个序列的形
状如下所示：...PXPXXP... 。我们取定中间的那个P，则对手取定旁边的两个X，形状
变成...PXP...。这个时候问题变... 阅读全帖 |
|
i******r
发帖数: 793 | 24 经典算法题
可以枚举左上和右下两个顶点，复杂度O(n^4)
模仿最大子段和的O(n)算法，可以优化到O(n^3)
请自行google ‘最大子矩阵’ |
|
r**u
发帖数: 1567 | 25 Given a string s, partition s such that every substring of the partition is
a palindrome.
Return all possible palindrome partitioning of s.
For example, given s = "aab",
Return
[
["aa","b"],
["a","a","b"]
]
DFS就是要枚举所有可能的划分，然后检查是否是palindrome吧，中间如果发现划分不
满足palindrome了，就backtrack。这个复杂度应该怎么求？ |
|
r**h
发帖数: 1288 | 26 直观的想法是，四个数permutation，三个运算符枚举4^3，然后逐个尝试
不过复杂度很高。 没有重复数的情况下是 4! * 4^3 次尝试 |
|
r**h
发帖数: 1288 | 27 有N个interval，每个有单独的startTime, endTime和cost
找一个subset，使得其中的interval互不相交，且cost最大
这题感觉不能用greedy呀。。难道只能枚举所有的子集吗？ |
|
f****e
发帖数: 34 | 28 对，不过用数组标记一下的话 对于无界的情况可以尽早结束枚举。 |
|
s*****r
发帖数: 43070 | 29 【 以下文字转载自 WaterWorld 讨论区 】
发信人: rayray81502 (张澍vs老甲), 信区: WaterWorld
标 题: 我在美国混不下去了怎么办? 读CS master啊!
发信站: BBS 未名空间站 (Sat Aug 24 19:21:53 2013, 美东)
[第一次发帖, 不知道是否发错区, 请版主随意移动]
俗话说男怕入错行,女怕嫁错郎,命运难免颠沛流离,家家有本难念的经,邓小平也有三起
三落,刘玄德也要三顾茅庐, 孔孟相见恨晚, 喷子最不待见喷子. 大家漂泊在外寻求美
国梦, 难免偶尔脚下一滑阴沟帆船,诚惶诚恐如履薄冰, 然后赶快上网求助.
本人虽然没有王大师之能, 但是潜伏各大贴吧好几载, 体察民情, 总结体会, 发现了一
个不传之密. 虽然说凡事不能一概而论, 解铃还须系铃人, 但是九九归一万法归宗, 还
真被我小老总结出这么一个金石为开, 快刀披风斩乱麻的手段, 总结起来就一句话, 我
小老这就分享出来, 省去大家以后上网求助之苦:
问: "我在美国***了 怎么办?"
答: "读CS master啊!"
虽然口诀看起来很短, not ... 阅读全帖 |
|
s*****r
发帖数: 108 | 30 2 题数据小枚举就行了
1 << (M*N) 种 |
|
d*k
发帖数: 207 | 31 原帖见
http://www.mitbbs.com/article_t/JobHunting/32529909.html
一个2D matrix,每个cell都是一个灯泡，0表示灭，1表示亮，当一个灯泡发生变化的
时候，他临近的灯泡都要变化，问给你一个board configuration，让你判断是否可以
通过亮灭使得所有的灯泡都熄灭。这个题面试的哥们说他是朋友问他的，他也没做出来
，让我和他一起做，看能做出来不。 结果是大体有了一个solution，但是不知道对不
对。
===================================
我的想法：假设临近指的是上下左右四个。矩阵是m*n的。
枚举第一行每个灯泡的情况（动或者不动），共2^n种可能。对于每一种可能，由于第
一行已经确定，可以根据第一行的状态确定第二行的状态，例如对于mat[0][i]，若为1
，则必须动mat[1][i]，否则必须不动mat[1][i]。这样第二行就确定了。随后依次确定
后面的每一行。总时间复杂度为可耻的m*n*2^n。
大家看有更好的办法吗？ |
|
d*k
发帖数: 207 | 32 O(m*n)的想了很久都不会。只有O(m*n*n）的。更好的算法请大牛来补充吧。
事先计算好对于每个点，向上最多有都少个连续的1，若当前点为0，则记录0。设记录
数组为height。
枚举最优解的底边（0～m-1）和高(1~n-1)，共O(m*n)种。设当前底边为a, 上边为b, h
= b - a + 1。扫描i = 0..n-1。找到连续的a[i] == b[i] == 1的区间。对于每个区
间[p, q]，令l = p, r = q。每次l++, r--，直到找到第一个height[a][l] >= h &&
height[a][r] >= h && l <= r 的l, r。这是一个可行解，面积为(r - l + 1) * h。
如此扫描的时间代价是O(n)。
因此总时间复杂度为m*n*n
height可以优化成一个数组height[n]，用最大全1子矩阵的方法更新，相当于那个“直
方图”。
欢迎大家拍砖。 |
|
e*******8
发帖数: 94 | 33 今天做的。programming的题目。其他的题目都很简单，就这道题没想出来除了枚举有
什么好办法？
4.Additive numbers are defined to be a positive integer whose digits form an
additive sequence. E.g. 11235 (1+1=2, 1+2=3, 2+3=5). What makes it
difficult is that 12,122,436 is also one (12+12=24, 12+24=36). Given a range
of integers, find all the additive numbers in that range. |
|
s*****r
发帖数: 108 | 34 用暴力只做一题肯定挂 你是说用了四个循环？
不是只枚举一次 0 ~ n^(1/3) 就能找到所有 (a, b) ? |
|
|
s*****r
发帖数: 108 | 36 用暴力只做一题肯定挂 你是说用了四个循环？
不是只枚举一次 0 ~ n^(1/3) 就能找到所有 (a, b) ? |
|
|
n*****f
发帖数: 17 | 38 其实还不到O(n^2/3)。枚举了i从1到n^1/3，j就到不了n^1/3了，从中间就跳出了。 |
|
B****D
发帖数: 132 | 39 这题的思路是这样的.
首先, 因为需要罗列, 速度不是问题, 你必须一一枚举所有有效排列. 因为是打印, 你
不必把所有答案都存起来. 产生一个, 打一个.
这题相当于, 你有三个水管喝水, 如何排列组合的问题. 很明显, 递归是最容易想到的
.
举例来说. 如果是2, 2, 2的情况, 假设你走到某一步, 比如说, 你已经各用了一个左
括号, 每种左括号还各剩一个, 你怎么办?
你有四种选择, 取一个左括号(三种), 或者加一个右括号. 右括号必须与最近一次的左
扩号匹配. 因此, 你需要4个参数.
1. 还剩几个 "("
2. 还剩几个 "["
3. 还剩几个 "{"
4. 当前的结果.
下面是用JAVA写的CODE. 为了方便, 多加了一个参数, 所有目前为止的左括号的STACK.
这是为了不用分析当前结果去找下一个右括号.
public class ListP
{
static int count = 0;
public static void main(String args[])
{
int n1 = 2;
int n... 阅读全帖 |
|
B****D
发帖数: 132 | 40 这题的思路是这样的.
首先, 因为需要罗列, 速度不是问题, 你必须一一枚举所有有效排列. 因为是打印, 你
不必把所有答案都存起来. 产生一个, 打一个.
这题相当于, 你有三个水管喝水, 如何排列组合的问题. 很明显, 递归是最容易想到的
.
举例来说. 如果是2, 2, 2的情况, 假设你走到某一步, 比如说, 你已经各用了一个左
括号, 每种左括号还各剩一个, 你怎么办?
你有四种选择, 取一个左括号(三种), 或者加一个右括号. 右括号必须与最近一次的左
扩号匹配. 因此, 你需要4个参数.
1. 还剩几个 "("
2. 还剩几个 "["
3. 还剩几个 "{"
4. 当前的结果.
下面是用JAVA写的CODE. 为了方便, 多加了一个参数, 所有目前为止的左括号的STACK.
这是为了不用分析当前结果去找下一个右括号.
public class ListP
{
static int count = 0;
public static void main(String args[])
{
int n1 = 2;
int n... 阅读全帖 |
|
w*******s
发帖数: 138 | 41 类似于整数分划，前面已经有人贴过code了，先做质因数分解再组合比直接枚举难写。 |
|
s*****n
发帖数: 994 | 42 怎么枚举？
我写的recursive就是无法去处duplication |
|
|
|
k****s
发帖数: 16 | 45 被面试官问的套进去了吧
>> traverse的话最坏情况复杂度就是O(2^n)
traverse树是O(n), 枚举每个字符才是O(2^n).
traverse树的时候，记住左孩子的count就可以，右孩子相同的话，直接加count，不用
一个字符一个字符生成就不是O(2^n). |
|
l******e
发帖数: 54 | 46 可以 DP
一行一行的来
枚举当前行的铺法 累计和上一行相容的方案数 |
|
l******e
发帖数: 54 | 47 就是普通的状态压缩 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 | 48 可以 DP
一行一行的来
枚举当前行的铺法 累计和上一行相容的方案数 |
|
l******e
发帖数: 54 | 49 就是普通的状态压缩 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 ... 阅读全帖 |
|
i******s
发帖数: 301 | 50 枚举所有pair, 一共有n*(n-1) / 2个，然后转化为求2sum。重点是去重，可以在pair
里面记录在原来数组的index。所以最好是O(n^2)吧。你的解法应该是O(n^3) |
|
