y****n 发帖数: 743 | 1 本来想找个比二分法更好的逼近方法,结果写成这下面这样。
用公式推了一下,居然是牛顿迭代的等效变形。居然没跳出牛顿的手掌心。
double Sqrt(double value, double acceptDifference)
{
double root = 1;
double difference = value - root * root;
while (Math.Abs(difference) > acceptDifference)
{
root += difference / 2 / root;
difference = value - root * root;
}
return root;
}
没做输入检查 |
|
y****n 发帖数: 743 | 2 本来想找个比二分法更好的逼近方法,结果写成这下面这样。
用公式推了一下,居然是牛顿迭代的等效变形。居然没跳出牛顿的手掌心。
double Sqrt(double value, double acceptDifference)
{
double root = 1;
double difference = value - root * root;
while (Math.Abs(difference) > acceptDifference)
{
root += difference / 2 / root;
difference = value - root * root;
}
return root;
}
没做输入检查 |
|
c****p 发帖数: 6474 | 3 [f1 f2 f3] = [f0 f1 f2] * A,
A= [0 0 1; 1 0 1; 0 1 1];
这样[fn fn+1 fn+2] = [f0 f1 f2] * A^n
其中A^n可以用二分法算,logn【 在 peking2 (myfacebook) 的大作中提到: 】 |
|
w****o 发帖数: 2260 | 4 问一个数是否是某个整数的平方?
问一个数是否是某个整数的立方?
是不是要用二分法求一下平方根,立方根,然后在看这些平方根,立方根是否是整数?
谢谢! |
|
|
y**********u 发帖数: 6366 | 6 看错了
我以为你写二分法不甚出了个bug,被烙印揪小辫子了。。。 |
|
K*******i 发帖数: 399 | 7 貌似F经常出这个题,除了起始区间的选取,浮点数的相等比较,浮点数平方后可能溢出,迭代何时停止,负数,小于1的数, 判断同侧是用f(a) * f(b) > 0 还是拆分为f(a) > 0, f(b) > 0 或 f(a) < 0, f(b) < 0等等外,还有什么需要注意呢? |
|
h****e 发帖数: 928 | 8 我想如下greedy解法应该是N*N的吧:
从头开始,A[1]到A[K]已经是排好序的。下面看A[K+1]:
有两种可能:
一是删除A[K+1],cost是A[K+1]
二是用二分法找A[1..K]中大于A[K+1]的数,假设是A[M],
那么把A[M]到A[K]中的数减小到A[K+1],cost是
(A[M]-A[K+1]) + ... + (A[K]-A[K+1])
取以上最小的cost,再继续往后遍历直到N为止。
这样复杂度是(log1+1/2)+(log2+2/2)+...(logK+K/2)+...+(logN+N/2) = N*N。
这样做对吗?还有更高效的解法吗? |
|
b*****s 发帖数: 24 | 9 今天拿到offer了...感谢大家的祝福,在本版学了很多,感谢无私帮助别人的同学。祝
找工作的同学都能找到自己喜欢的工作,工作以后也别忘了提携自己的同胞。 :-)。
面的是嵌入式软件工程师的职位。面试过程,面了6个人,大概5个小时,基本都是面试
简历上的问题,c/c++编程题,没有特别难的。很多题在careercup和glassdoor上都有。
特别是电面时候的题目,事后才发现,都在上面。可是准备的时候,没有时间,好几题
只能临时搞定。
1. 求一个int中bit为1的个数(两个人问过);
三中经典的办法: 查表、bit mask、bit shift,并且讨论他们的速度
2. 编写一个函数 void LinkedListInsert(Node* head, int i, int value);
i<0时,插在head之前;
i>0时,如果大于链表长度,插在最后;如果小于,插在相应位置。
3. 一个数组,长度为n,知道最多只有一个peak, 有唯一的最大值,编写一个函数
寻找最大值。int FindPeak(double* array, int arraySize);
... 阅读全帖 |
|
t********e 发帖数: 344 | 10 觉得leetcode上的解挺intuitive的 也不复杂啊 二分法的idea |
|
c********t 发帖数: 5706 | 11 也可以传search(int[] a, int index1, int[] b, int index2, int k), 用recursion
, 代码也就 10来行。
可是如果没有做过,即使知道二分法,也真的很难一次写对 |
|
t********e 发帖数: 344 | 12 觉得leetcode上的解挺intuitive的 也不复杂啊 二分法的idea |
|
c********t 发帖数: 5706 | 13 也可以传search(int[] a, int index1, int[] b, int index2, int k), 用recursion
, 代码也就 10来行。
可是如果没有做过,即使知道二分法,也真的很难一次写对 |
|
c********t 发帖数: 5706 | 14 这道题我想到的是二分法
存水题也很难想,我试图用两边夹,还是没想出,最后想了一个先找出最大数,然后左
右算分别存水量。 |
|
c********t 发帖数: 5706 | 15 这道题我想到的是二分法
存水题也很难想,我试图用两边夹,还是没想出,最后想了一个先找出最大数,然后左
右算分别存水量。 |
|
s********k 发帖数: 6180 | 16 一个数组,比如1,2,3,7,19,8,6,11,34,23,67.
find local min,就是比它左右都小,比如这个里面的6比8,11小,23比34,67小,都是
local min。找到任意一个local min就可以
找出比O(n)更好的办法。二分法找显然是方向,但是这个题的细节考虑可能比较多。 |
|
y****n 发帖数: 743 | 17 这道题,我认为理论上O(n)已经是最佳答案了。
所谓二分法,原数组必定要有些规律,才可以二分,否则分了也白分。
举个极端的例子:
{1,1,1,1, ... ,1,0,1,1, ... ,1,1}
这种情况,找到中间那个0,只可能O(n)。
针对这道题,所有的“优化”方法,不过是调整不同的读数顺序。
但是,无论你怎样调整,你不能保证那个LocalMin会更早被发现。
这句话对于可能有多个LocalMin的情况一样适用。
所以,如果数组是无规律的,算法应该是O(n),几乎没有优化空间。
而在实际工作中,我们有可能根据LocalMin经常实现的位置或频率稍加调整。 |
|
y****n 发帖数: 743 | 18 按照新贴的原题,的确可以logn,二分法,根据中点方向每次折半。 |
|
y****n 发帖数: 743 | 19 二分法:我使用C#,数组范围A[0..n-1],假设输入数组符合条件。
public static int FindLocalMin(int[] arr)
{
int start = 0;
int end = arr.Length - 1;
while (end - start > 2)
{
int mid = (end + start) / 2;
if (arr[mid] < arr[mid + 1])
end = mid + 1;
else
start = mid;
}
return arr[start + 1];
}
]
x] |
|
|
f******p 发帖数: 4 | 21 递归可以解。如果是后序遍历结果,最后一个数x一定是根节点。前面比x小的是左子树
,比x大的是右子树,这个位置可以二分法查找。左右子树可以递归判断。复杂度是n
log n吧。 |
|
r****m 发帖数: 70 | 22 类似二分法
i = m/2
j = n/2
while (i> 0 && j > 0 && i < m-1 && j < n-1) {
if (k > i*j && k < (i+1)*(j+1)) {
mergeSearch(matrix[i][0...j], matrix[0...i][j], k - (i*j));
} else if (k < i * j) {
i = i/2;
j = j/2;
} else {
i = (i+m)/2;
j = (j+n)/2;
}
} |
|
d*********g 发帖数: 154 | 23
这个算法的复杂度不一定比用堆好吧?“给定任意一个数,有办法判断该元素是矩阵中
第几大的”,这一步应该是O(n),n是矩阵的max{长,宽},然后二分法找到恰好大于k
个数的数是O(lgm),其中m是矩阵中的最大值减最小值的大小。所以总复杂度是O(n*lgm
)。而用堆的复杂度是O(k*lgn)。不知道我的理解对么? |
|
m***k 发帖数: 946 | 24 你的回复里感觉有几处不清楚和错误的地方。
1. “Then the complexity in this case is O(column length * \log(row length))“
假设ColumnLength=m, RowLength=n, 你说的复杂度就是m*log(n),这其实比堆解法的
复杂度k*log(n)快得多,因为k可以等于n*m/2. 堆解法的复杂度worst case是O(n*m*
log(n)).
2. "this solution's worst case complexity is greater than O(m*n/2)"
这不是很显然的么: O(k*log(n)) = O(n*m*log(n)) > O(M*n).
>>>总结一下:
1. 堆解法,复杂度是k*log(n), worst case (k=m*n/2, median)时,复杂度为O(m*n*
log(n))
2. 间接二分法,复杂度是O(n*log(max-min)). 具体方法是:
(1) 求一个整数x在矩阵中第几大,O(n)
(2) 在[a, b]范围的整数内,找出一... 阅读全帖 |
|
s********k 发帖数: 6180 | 25 这题我电面第二道题遇到过,当时想到了二分法做,不过时间不多有点紧张没搞定挂了
。我觉得这个given condition (a[0] >= a[1] && a[n-2] <= a[n-1])也不一定需要。
可以自己问这个local的定义
mid |
|
x*******6 发帖数: 262 | 26
没记错的话是用二分法,left=0,right=m*n-1, mid=(left+right)/2,转
化为index是matrix[mid/n][mid%n], O(log(m*n)) |
|
b*********e 发帖数: 26 | 27 楼上说二分法可以能达到log(m+n)的应该是考虑的这种情况:
i-1行的行尾小于第i行的行头,比如
1 2 3 4
5 6 7 8
9 10 11 12
而说只能(m+n)的考虑的是这种情况
1 10 20 30
2 20 30 40
5 50 100 120
这种情况下,同样存在楼主所说的“从左到右升序,从上到下升序”
但是只能m+n |
|
a********3 发帖数: 180 | 28 多谢提醒,我粗心啦。
可能用两个index来实现二分法比较快。算法复杂度差不多是 max(log(m),log(n
))。 |
|
a********3 发帖数: 180 | 29 多谢提醒,我粗心啦。
可能用两个index来实现二分法比较快。算法复杂度差不多是 max(log(m),log(n
))。 |
|
o***d 发帖数: 313 | 30 int同样用二分法么?这个误差可大了点.
要是我就先转成float,算晚了再返回int,这样的结果跟test case的结果不同.... |
|
e****e 发帖数: 418 | 31 Thank you so much. 网上我见到local mim还有个条件a[0] >= a[1] and a[n-1] <= a
[n],没有这个条件题目没法用二分法做吧!
[0 |
|
b*****n 发帖数: 482 | 32 我其实最近才开始做leetcode,一周时间,到现在刚好50题。我先来抛块砖吧,讲讲自
己的体会:
1. 先看思路领会透不透。譬如说peranthese matching, largest rectangle, maximum
rectangle 这些题。还有kth largest, median of two sorted arrays。特别是
median of two sorted arrays,思路和细节吃透了, 再要写一遍的话,bug free并不
算特别难。当然我是指“再写一遍”。我知道peking2的目标可能是没见过面的5分题一
次写对:),那可真得下功夫。
2. 再看固定模式熟不熟。tree的recursive,string matching的dp,math里用的移位
和二分法,数组的左右指针,单链表的双指针traverse/delete。这些基本的东西要有
敏感度。
3. corner case要cover够。空指针,0长度,integer记住有负数,unsigned包括0,
duplicate怎么处理,会不会overflow,out of range,loop能不能... 阅读全帖 |
|
b*****n 发帖数: 482 | 33 我其实最近才开始做leetcode,一周时间,到现在刚好50题。我先来抛块砖吧,讲讲自
己的体会:
1. 先看思路领会透不透。譬如说peranthese matching, largest rectangle, maximum
rectangle 这些题。还有kth largest, median of two sorted arrays。特别是
median of two sorted arrays,思路和细节吃透了, 再要写一遍的话,bug free并不
算特别难。当然我是指“再写一遍”。我知道peking2的目标可能是没见过面的5分题一
次写对:),那可真得下功夫。
2. 再看固定模式熟不熟。tree的recursive,string matching的dp,math里用的移位
和二分法,数组的左右指针,单链表的双指针traverse/delete。这些基本的东西要有
敏感度。
3. corner case要cover够。空指针,0长度,integer记住有负数,unsigned包括0,
duplicate怎么处理,会不会overflow,out of range,loop能不能... 阅读全帖 |
|
w********p 发帖数: 948 | 34 我小小声的认为,这题一定要练习到用类似quick sort的二分法,然后bug-free的写出
来。
这题是基本题。比quicksort 简单。 |
|
l****i 发帖数: 2772 | 35 昨天发了A家onsite杯具的面经,几位同胞建议我要总结一下面试的技巧。我就一次把6
个杯具都简单总结一下,包括一些面筋,也希望版上的大牛指点一下。
基本个人背景,US CS fresh PhD,国内3年国企IT部门经验,国内的工作基本就是天天
写SQL。1月初才是投简历,至今,10+个电面,拿到6个onsite,已全部杯具。
Onsite 1:
某电脑公司美国做cloud的分支。电面一轮,拿到onsite。onsite面了有5轮,有3轮
都很顺。感觉悲剧有2轮,如下:
1.2 国女,拿着一本中文打印的java面试题目,随便翻到一题,就写着版上问我,基本
都是关于java一些属性的题。其中有2道题,我不是很确定,就询问,能否讨论一下结
果,国女每次都很严肃的和我,“This is interview, I cannot tell you true or
false. I cannot tell you anything.”. 拒绝和我讨论任何题目的答案。此国女的态
度,就是interview就是考试。不需要沟通讨论。
1.4 台湾CTO,上来写了一个算法给我,就是常见的二分法求乘积。让... 阅读全帖 |
|
g********E 发帖数: 178 | 36 quick sort还是merge sort?
二分法每次少一半,三分法每次只少了1/3 |
|
b*****t 发帖数: 296 | 37 能让二爷夸奖,实在荣幸啊。呵呵
总是说自己preIPO,who knows.
第一题就是recursive,二分法
第二题就是个先根遍历的dfs |
|
B********t 发帖数: 1321 | 38 读罢本版许多关于转不转CS的争论,深感部分老中匮乏心态之严重,推荐大家看看这本
《高效能人士的七个习惯》:
http://ishare.iask.sina.com.cn/f/22510086.html
“一般人都会担心有所匮乏,认为世界如同一块大饼,并非人人得而食之。假如别人多
抢走一块,自己就会吃亏,人生仿佛一场零和游戏。难怪俗语说:“共患难易,共富贵
难。”见不得别人好,甚至对至亲好友的成就也会眼红,这都是“匮乏心态”(
Scarcity Mentality) 作祟。”
“双赢者把生活看作一个合作的舞台,而不是一个角斗场。一般人看事情多用二分法:
非强即弱,非胜即败。其实世界之大,人人都有足够的立足空间,他人之得不必就视为
自己之失。” |
|
B********t 发帖数: 1321 | 39 读罢本版许多关于转不转CS的争论,深感部分老中匮乏心态之严重,推荐大家看看这本
《高效能人士的七个习惯》:
http://ishare.iask.sina.com.cn/f/22510086.html
“一般人都会担心有所匮乏,认为世界如同一块大饼,并非人人得而食之。假如别人多
抢走一块,自己就会吃亏,人生仿佛一场零和游戏。难怪俗语说:“共患难易,共富贵
难。”见不得别人好,甚至对至亲好友的成就也会眼红,这都是“匮乏心态”(
Scarcity Mentality) 作祟。”
“双赢者把生活看作一个合作的舞台,而不是一个角斗场。一般人看事情多用二分法:
非强即弱,非胜即败。其实世界之大,人人都有足够的立足空间,他人之得不必就视为
自己之失。” |
|
g*******u 发帖数: 107 | 40 Search for a Range - leetcode
Given a sorted array of integers, find the starting and ending position of a
given target value.
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].
很多网上的流形解题是:
用二分法找出第一个位置,如果还有多的,从这个找出的位置向前、向后搜索,直到找
出所有的值。但是,这个解法是O(n)。worst case, 如果所有的值都是要找的值,是不
是所有的数字都要被用来比较?
有没有真正的worst case O(log n)? |
|
g****o 发帖数: 547 | 41 内存是不是应该4Byte*1e7*26 才1GB啊
不过那个矩阵的确有冗余的,把重复的元素去掉,用二分法来找下一元素位置也可以
这样算法复杂度o(S*lgT)
以上解法都是我拍脑袋自己想的
不知道哪位大侠来分享下经典题的标准解法,呵呵 |
|
|
s********u 发帖数: 1109 | 43 二维平面上有很多圆,圆心都在原
点,同时平面上有很多点,问哪两个相邻的圆环之间的点最多
难道不是算所有点离原点的距离,然后看落在哪个范围,对应的count就加1,然后最后
找count数组的最大值?跟subarray和最远距离有何关系。。
就是“看落在哪个范围”没想到好办法,只能将圆环按半径排序后,用二分法去找么 |
|
s********u 发帖数: 1109 | 44 二维平面上有很多圆,圆心都在原
点,同时平面上有很多点,问哪两个相邻的圆环之间的点最多
难道不是算所有点离原点的距离,然后看落在哪个范围,对应的count就加1,然后最后
找count数组的最大值?跟subarray和最远距离有何关系。。
就是“看落在哪个范围”没想到好办法,只能将圆环按半径排序后,用二分法去找么 |
|
w********s 发帖数: 214 | 45 想问下LZ或者其他牛人那个sqrt题目。如果用牛顿迭代法的话代码就非常简单了但是不
是很容易解释。用二分法的话反而代码要复杂很多还有很多情况要考虑。这种情况下大
家会怎么答呢? |
|
w********s 发帖数: 214 | 46 想问下LZ或者其他牛人那个sqrt题目。如果用牛顿迭代法的话代码就非常简单了但是不
是很容易解释。用二分法的话反而代码要复杂很多还有很多情况要考虑。这种情况下大
家会怎么答呢? |
|
f***8 发帖数: 510 | 47 这个我同意。楼主的帖子其实不似乎很明白,到底是应试者两二分法的逻辑也没有,还
是在用具体语言写的时候卡住了。
大陆来的同胞,看看本科学校, 不是文科生的话,只要有人愿意领进们,90%的活是能
干的。一个人要想混的好,有人顶是必须的。中国人在美国生活很不容易的,我老说了
,要得到同样的资源,中国人要付出更大的努力,主要就是单打独斗得多,很幸苦。 |
|
Q****a 发帖数: 296 | 48 我用牛顿迭代法和二分法都试过, precision 最小能设成 1e-15 (或者9e-16),再
小(比如1e-16) 就死循环了 = =
可是我用precision = 1e-15做,返回结果比java里面Math.sqrt() 精度少一位 (比如
sqrt(2.0) 我return 1.414213562373095, 而java math return 1.
4142135623730951)。
请问大牛Math。sqrt怎么能精度多一位的? |
|
c**w 发帖数: 1024 | 49 来自主题: JobHunting版 - 新鲜G面经 其实第一题面试的时候题目描述更隐晦,开始没说知道一个黑子地址。只是我说,这个
题是search problem,要想快,肯定是二分法,然后面试官问怎么搞,之后才把条件改
了,开始就给定一个黑子的地址
★ 发自iPhone App: ChineseWeb 8.2.2 |
|
|