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 |
|
|
