|
l*******s
发帖数: 1258 | 2 所以说那玩意nb 虽然太费事 但是速度比其他的那些迭代快不少 |
|
l*****a
发帖数: 14598 | 3 我很好奇的是面世官真的希望以数学公式作为码工的衡量标准？
这东西能反映出工作中哪方面的能力呢 |
|
l*******s
发帖数: 1258 | 4 肯定不会让当场实现牛顿法的
那玩意在白板上能写到吐血。 |
|
c*****a
发帖数: 808 | 5
public static double sqrt(double x){
if(x==1 || x==0) return x;
if(x<0)return -1;
double stopCase = 0.00001;
double left = 0, right = x<1? 1:x;
while(right-left>stopCase){
double mid = left + (right - left)/2;
double midSqr = mid * mid;
if(midSqr ==x)return mid;
else if(midSqr > x) right = mid;
else left = mid;
}
return (left+right)/2.0;
}
这样行不行
算不出来的double就return接近的 |
|
r**h
发帖数: 1288 | 6 每个数列都看成一个pi次多项式，他们的积的最高次项就是(d1^p1*d2^p2*...*dn^pn)
，求sum(pi)阶导数再加上一个阶乘项
最后三个全部超时
尝试着先暂存一些阶乘的中间结果来减少每次阶乘的次数，结果完全不顶用- -； |
|
g****y
发帖数: 2810 | 7 我想不用考虑数字的个数。直接从第一个数字开始深搜，然后第二个，第三个…知道其
和大于等于所求数就跳出。
可以的优化就是每次记一下前面的数都算过了，剩下的值有多少，如果没有数列的最大
值大，就不再算了，返回到数列的倒数第二个值。
这样不会有很大的消耗。毕竟这本就是不是一个多项式级的问题。
把N |
|
H****r
发帖数: 2801 | 8 现在面试题都到这难度了？
1） 01背包 （伪多项式服擦度）
2）dp + bst + augment data? （O(N*logN))
等大牛来讲讲标准解
find
..
★ 发自iPhone App: ChineseWeb 7.8 |
|
|
u******g
发帖数: 89 | 10 两个array存这两个多项式，
index i的地方存x^i的系数，然后跟用计算机模拟人类做。。 |
|
r******r
发帖数: 700 | 11 记得以前好像做过练习，但是忘了用什么数据结构来存多项式。 |
|
b****g
发帖数: 192 | 12 你楼上的意思是说访问过的grid就不能在访问了，所以每个grid就被使用一次。你的理
解可能是从每个grid向四个方向递归访问，如果不考虑访问过的不再访问，那确实是4^
N。但是你楼上使用了剪枝，所以时间复杂度会下降，所以每个grid最多被用一次，所
以“对每个起始点来说，顶多遍历整个range每个点一次“。你如果不问这个问题我也
意识不到剪枝能把复杂度从指数降到多项式。
with |
|
b***e
发帖数: 1419 | 13 这个等价于旅行商问题(travelling salesman problem)。NP完全问题，多项式时间内
误解。 |
|
a********m
发帖数: 15480 | 14 浮点的话是麻烦，毕竟是伪多项式。不过一般价格位数有限，弄成整数也还能做。 |
|
a**********0
发帖数: 422 | 15 wiki上说DP是把大问题变成小问题 但我觉得这不能体现DP的特点 难道recursion不是
把大问题变小问题吗？ 我觉得差别是 DP一般从base case 到complicate case
递归反之 比如Fibonacci如果用递归 则指数复杂度 如果用循环 就是多项式 循环当然
也需要从简单到复杂而不是反之 DP相比递归就是减少了重复的计算
其实dp有点像随机过程里的马克夫过程或者martingale一样的 就是一点一点的算 |
|
l*n
发帖数: 529 | 16 他说的的overflow是因为rolling hash是个多项式，每次roll的时候是lastHash*base+
newChar-firstChar*power(base, n)。overflow其实也无所谓的。rolling hash没有
rehash这一说。
这一题用rolling hash就只是在计算hash的时候节省一点，但还是需要像普通的hash
table那样处理collision，需要存所有unique字串。这么一来，感觉就需要自己搞一个
hashmap了，更麻烦。也许是我不知道有什么好办法能让rolling hash跟hashmap直接无
缝连接。 |
|
c*********l
发帖数: 3438 | 17 【 以下文字转载自 NewYork 讨论区 】
发信人: Vesper8 (天使在人间), 信区: NewYork
标 题: 今天看到的 - 你有进华尔街的资格吗？
发信站: BBS 未名空间站 (Thu Dec 19 19:10:26 2013, 美东)
很多天过去，当我回想起来这噩梦般的6个小时，都依然觉得神情恍惚，无法思考。
一个很平凡的下午，收到Morgan Stanley邮件说，Quantitative Finance Program希望
你来跟我们Securitized Product Group的一个Manager进行一个on-site interview.
于是我来美的处女面就华丽地献给了华尔街最quant的一个公司的最quant的一个组的一
个大boss。
其实on site一面的时候，与Managing director相谈甚欢，给MD发follow up邮件，回
信热情洋溢，最后说I look forward to coming back to you with next steps.
回想起来，MD的问题确实是很简单的，只问到了fixed income和比较基... 阅读全帖 |
|
s********o
发帖数: 3783 | 18 面试遇到的题目有非常多都是leetcode原题
比如我上面提到的2sum，跟leetcode一模一样
下面是一些题，不分先后，不分公司，全混在一起说
1，leetcode 2sum，用O(nlogn)和O(n)怎么做
2，leetcode 2sum，如果是小于不是等于怎么做，3sum怎么做，小于x怎么做
4sum怎么做，小于x怎么做，只输出符合条件（小于x）的总个数但是不需要输出具体数
怎么做，不但输出总个数还要输出具体答案怎么做，k sum 小于x怎么做，
k sum有没有多项式解？证明之
3，一个城市的地图（mxn矩阵），求从左上到右下一共有多少种可能的路线（只能向右
和向下）。先用程序写（利用通项公式递推），然后让我在白板上写close form公式
其实close form非常非常简单，只不过我没见过这道题，当场没有看出来。但是我硬挺
着从通项公式开始用矩阵分解去求解close form，最后在面试官的一点帮助下还是写出
来了公式，最后面试官表示我的数学基本功非常令他吃惊。（我心里想好歹也是学过几
门数学课的）。。。
4，还是数学题，求k个数的最大公约数。其实就几行代码，辗转相... 阅读全帖 |
|
s********o
发帖数: 3783 | 19 面试遇到的题目有非常多都是leetcode原题
比如我上面提到的2sum，跟leetcode一模一样，一模一样的我就不说了。
下面是一些题，不分先后，不分公司，全混在一起说
1，leetcode 2sum，用O(nlogn)和O(n)怎么做
2，leetcode 2sum，如果是小于不是等于怎么做，3sum怎么做，小于x怎么做
4sum怎么做，小于x怎么做，只输出符合条件（小于x）的总个数但是不需要输出具体数
怎么做，不但输出总个数还要输出具体答案怎么做，k sum 小于x怎么做，
k sum有没有多项式解？证明之
3，一个城市的地图（mxn矩阵），求从左上到右下一共有多少种可能的路线（只能向右
和向下）。先用程序写（利用通项公式递推），然后让我在白板上写close form公式
其实close form非常非常简单，只不过我没见过这道题，当场没有看出来。但是我硬挺
着从通项公式开始用矩阵分解去求解close form，最后在面试官的一点帮助下还是写出
来了公式，最后面试官表示我的数学基本功非常令他吃惊。（我心里想好歹也是学过几
门数学课的）。。。
4，还是数学题，求k个数的最大公约数... 阅读全帖 |
|
r****s
发帖数: 1025 | 20 那是computational geometry的算法，和combinatorial optimization（求多项式最优
解）一样都是CS graduate level的课程。stackoverflow的那哥们正在读研估计。 |
|
r**a
发帖数: 31 | 21 我很怀疑第一题有没有多项式解法。因为似乎可以从图的最小支配集问题（一个NPC）
归约到它。 |
|
r**a
发帖数: 31 | 22 我很怀疑第一题有没有多项式解法。因为似乎可以从图的最小支配集问题（一个NPC）
归约到它。 |
|
|
|
M*******a
发帖数: 1633 | 25 就是两个vector A(a1, a2, a3....an), B(b1, b2, b3... bn)，a1..an和b1..bn都可
以为负数。
然后可以调整各项a1..an/b1..bn的位置，求A和B乘积A*B = a1*b1 + a2*b2... an*bn
的最大值 |
|
e********2
发帖数: 495 | 26 Max weight matching, polynomial time complexity
bn |
|
M*******a
发帖数: 1633 | 27 这么神奇？
是更什么bipartite matching一个意思么？ |
|
h*******e
发帖数: 1377 | 28 怎么感觉感觉排序 之后 正数部分大的乘大的，负数 也是最小的乘最小的。。然后中
间乘中间，贪心就行呢 |
|
l******6
发帖数: 340 | 29 agree
sort(A.begin() , A.end())
sort(B.begin() , B.end())
sum(A[i] * B[i]) |
|
|
l******6
发帖数: 340 | 31 I can think of a proof:
for any A[i] <= A[j] , B[i] <= B[j]
A[i](B[i] - B[j]) >= A[j](B[i] - B[j])
A[i]B[i] + A[j]B[j] >= A[i]B[j] + A[j]B[i]
this hold for every pair in A[] and B[] and we can always optimize a pair
by switch if A[i] <= A[j] and B[i] >= B[j]
lead to the final result to sorted A[] and B[] |
|
|
|
b*****t
发帖数: 296 | 34 maxMultiplication(A[n], B[n]) {
return maxMultiplication(A[n-1], b[n-1])+getMaxValue(A)*getMaxValue(B);
} |
|
m*********a
发帖数: 3299 | 35 这个不就是这个吗
agree
sort(A.begin() , A.end())
sort(B.begin() , B.end())
sum(A[i] * B[i]) |
|
A*****i
发帖数: 3587 | 36 错了应该是初中奥数题，多项式展开还是怎么来着，以前一定做过 |
|
M*******a
发帖数: 1633 | 37 不用几条船，如果就一条船的情况下就已经NP了，只有伪多项式算法。 |
|
M*******a
发帖数: 1633 | 38 不用几条船，如果就一条船的情况下就已经NP了，只有伪多项式算法。 |
|
b********7
发帖数: 3 | 39 只能dfs吗? 感觉和后缀数组有点关系. 但没想出来.
那位大牛能给个多项式复杂度的算法吗? |
|
b********7
发帖数: 3 | 40 只能dfs吗? 感觉和后缀数组有点关系. 但没想出来.
那位大牛能给个多项式复杂度的算法吗? |
|
w*****d
发帖数: 105 | 41 3题，是否还有限制每个单词只能用一次？否则，如果字典里有一个回文单词w，那么无
限个w连接起来还是回文。
不过即使加这个限制，这个题貌似也没有多项式时间的解法。 |
|
w*****d
发帖数: 105 | 42 3题，是否还有限制每个单词只能用一次？否则，如果字典里有一个回文单词w，那么无
限个w连接起来还是回文。
不过即使加这个限制，这个题貌似也没有多项式时间的解法。 |
|
r****7
发帖数: 2282 | 43 可是knapsack是NP问题啊。。。哪儿有多项式解法
0
,
, |
|
N******G
发帖数: 33 | 44 只能搜，如果hoppercount不大（比如2、3）可以动态规划，但是复杂度是
maxHoppersize^hopperCount
本身这题是NP完全的，因为假设存在多项式算法，那么下面这个问题可解：
给定N个数，是否可以分两组，使得和一样
maxHopperSize=SUM/2
hopperCount=2
而这个partition problem是NP完全的
https://en.wikipedia.org/wiki/Partition_problem |
|
c*******t
发帖数: 123 | 45 1.求解一个例子不等于求解一个问题。
2.你可能没有受过工程训练，对指数增长和多项式增长的差别没有概念。
3.去看看任何一本算法书，看看np-completeness你就知道了。 |
|
s******c
发帖数: 1920 | 46 查了一下 用来定义np的非确定性图灵机和量子图灵机还不是一回事儿。np难问题是否
能在多项式时间内被量子图灵机解决依然未知。 |
|
l*3
发帖数: 2279 | 47 另外一个方法是 De Bruijn sequence
不过这个方法用到一些数学知识，不如我上面说的欧拉回路那个那么好理解。我也至今
没有看懂细节。
De Bruijn sequence 是O(n) 的算法。
上面的欧拉回路做不到 O(n)， 不过也是多项式的，对于这个问题来说，我觉得欧拉回
路的算法已经够巧妙了。 |
|
n******6
发帖数: 1829 | 48 【 以下文字转载自 Military 讨论区 】
发信人: WangMaZi (王二小), 信区: Military
标 题: 重大喜讯，放军教授成功解决世界第一难题P=NP
发信站: BBS 未名空间站 (Thu May 19 00:05:54 2016, 美东)
国防科大教授姜新文微博
http://blog.sina.com.cn/s/blog_54de27b80102vgyf.html
5年前我们正式投稿推出一个32页文章，讲述为一个图论问题设计的算法。文章
内容属于算法设计与分析的范畴，文章结构遵循算法设计与分析教科书中提出问题、设
计算法、分析证明的俗套，采用的方法、技术、手法都来自基本的教科书。理解文章需
要的知识背景被计算机、数学、信息安全等本科专业覆盖。但是因为明确指出了该算法
是一个NP完全问题的多项式算法，所以，如果算法对了，NP就等于P了。这意味着同时
具备重大理论意义和现实意义的世界第一困难问题被解决，意味着人类认识世界的自动
化过程现实可行，意味着非确定性变成确定性，意味着密码学崩溃和密码学可能成为皇
帝新装，意味着哲学上支持世界可知。于是一个... 阅读全帖 |
|
i*****9
发帖数: 3157 | 49 当总状态空间大小是多项式时，BFS和DP没有本质区别。
：当题目看不出任何规律，既不能用分治、贪心，也不能用动规，这时候万能方法--搜
索就派上用场了。搜索分为广搜和深搜，广搜里面又有普通广搜，双向广搜，A*搜索等
。深搜里面又有普通深搜，回溯法等。
： |
|
S*********g
发帖数: 5298 | 50 15岁要不会，那老师要打屁屁了,这种初中的多项式 |
|
