|
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岁要不会,那老师要打屁屁了,这种初中的多项式 |
|