Lumia900到底有没有NFC? - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>PDA - 掌中宝

Lumia900到底有没有NFC?

Lumia900到底有没有NFC?# PDA - 掌中宝

x*s2012-04-17 07:04

1 楼

Given a sorted array with duplicates and a number, find the range in the
form of (startIndex, endIndex) of that number. For example, given 0 2 3 3 3
10 10 and 3, return (2,4). Given the same array and 6, return (-1,-1).
Upon further probe:
1. Do better than linear scan, which is O(n). 2. You can just work out how
to find the start index, and I will assume that you know how to find the end.
有没有办法用binary search来找start和end？

w*u2012-04-17 07:04

2 楼

买了Samsung 840 250G 带tool 和 kit的，准备更新2011 MBP。需要工具有：
sata to USB cable (copy HDD to SSD),screwdriver set （除去最普通的philips
set，一定要有 Torx T6）
1）PC的话直接用三星附带的软件就可以，不过三星的SSD对Mac的支持显然不够，附带
软件不支持Mac，firmware的Mac版本更新也很麻烦。先把SSD连到 PC上更新一下
firmware再装到Mac上的。不过不少人反映，update后， SSD性能并没有改进：
http://www.anushand.com/2013/06/samsung-840-series-250gb-firmwa
2）首先网上有不少讲解如何back up和做镜像的tip
https://discussions.apple.com/docs/DOC-4741
http://support.apple.com/kb/ht1553
https://discussions.apple.com/thread/4046538?start=0&tstart=0
3）本来准备按照上述网站介绍，直接restore HDD 到 SSD，可惜我的MBP不行，不知道
是不是系统太老，10.7的lion系统按道理不算老。然后试了先image系统到SSD，然后
scan（应该就是解压）image，可惜Mac实在是太慢了，而且硬盘空间不够，都放弃了。
4）然后下载了流行的Carbon Copy Cloner，有30天免费试用，效果竟然很不错，直接
back up文件到SSD就行。
5）打开后盖换SSD之前一定要先确认一下 SSD 是bootable的，这个大家都熟悉，就是
开机按option
6）拆后盖，换SSD，参见：https://www.youtube.com/watch?v=Xf2Z0XWvuc4
7）我换了之后，开机，机子还是没法启动，心一凉，光传文件就用了大概3小时（
140G的数据），试了几次都不行，最后把换下来的HDD接上Mac，开机按option键，竟然
可以，进去系统之后再把启动首选改为 SSD，然后大功告成，所有的文件和原来HDD都
一模一样。第一次开机，也许不需要查HDD，直接按option也能进，不过显然没法试了。
换上后，速度是搜搜的，10几页带图的word一点就开，MBP重量也略微减小。

n*r2012-04-17 07:04

3 楼

官网上似乎没有啊？

c*o2012-04-17 07:04

4 楼

感觉把binary search的停止条件换一下就可以，找start时为x[i-1]x[i]==value，找end时为x[i]==value && x[i+1]>value。

3 3
how
end.

【在 x*********s 的大作中提到】

: Given a sorted array with duplicates and a number, find the range in the
: form of (startIndex, endIndex) of that number. For example, given 0 2 3 3 3
: 10 10 and 3, return (2,4). Given the same array and 6, return (-1,-1).
: Upon further probe:
: 1. Do better than linear scan, which is O(n). 2. You can just work out how
: to find the start index, and I will assume that you know how to find the end.
: 有没有办法用binary search来找start和end？

h*g2012-04-17 07:04

5 楼

没

【在 n********r 的大作中提到】

: 官网上似乎没有啊？

j*u2012-04-17 07:04

6 楼

先binary找到这个数O(logN)，然后向左找start，向右找end是同样的办法
可以liner也可以继续binary

3
end.

【在 x*********s 的大作中提到】

m*d2012-04-17 07:04

7 楼

没听说nokia的有

【在 n********r 的大作中提到】

: 官网上似乎没有啊？

l*a2012-04-17 07:04

8 楼

当然是继续二分

【在 j*****u 的大作中提到】

: 先binary找到这个数O(logN)，然后向左找start，向右找end是同样的办法
: 可以liner也可以继续binary
:
: 3
: end.

m*t2012-04-17 07:04

9 楼

lumia 610 will have.

【在 n********r 的大作中提到】

: 官网上似乎没有啊？

j*u2012-04-17 07:04

10 楼

取决于logN和重复元素个数哪个大，重复数小的时候liner更好

【在 l*****a 的大作中提到】

: 当然是继续二分

l*a2012-04-17 07:04

11 楼

how to judge that in runtime?

【在 j*****u 的大作中提到】

: 取决于logN和重复元素个数哪个大，重复数小的时候liner更好

j*u2012-04-17 07:04

12 楼

要compile time前面试官告诉，runtime就晚了：）

【在 l*****a 的大作中提到】

: how to judge that in runtime?

l*a2012-04-17 07:04

13 楼

if he doesn't tell u
which one will u write,just write one

【在 j*****u 的大作中提到】

: 要compile time前面试官告诉，runtime就晚了：）

n*y2012-04-17 07:04

14 楼

性格测试？
you have to make the assumption.
ls说的很清楚了。

【在 l*****a 的大作中提到】

: if he doesn't tell u
: which one will u write,just write one

f*g2012-04-17 07:04

15 楼

I like this one:S

【在 c****o 的大作中提到】

: 感觉把binary search的停止条件换一下就可以，找start时为x[i-1]: x[i]==value，找end时为x[i]==value && x[i+1]>value。
:
: 3 3
: how
: end.

n*s2012-04-17 07:04

16 楼

def sSearch(a, v):
tot_len = len(a)
l = 0
r = tot_len-1
while l < r :
m = (l+r) //2
if a[m] > v:
r = m -1
elif a[m] < v:
l = m + 1
else:
r = m # start pointer is saved here
if a[l] is v:
return r
else:
return -1
a = [1,1, 2, 3,3,3,5, 6]
print a
print sSearch(a,3)

【在 l*****a 的大作中提到】

: if he doesn't tell u
: which one will u write,just write one

h*62012-04-17 07:04

17 楼

有现成函数的，lower_bound和upper_bound

j*x2012-04-17 07:04

18 楼

看看stl algorithm 里面的lower_bound equal_range

f*82012-04-17 07:04

19 楼

这是用python写的吗
是不是没有考虑到a[m]第一次正好等于v的情况呢，比如a[9]={0,1,2,3,3,3,4,7,10},v
=3
那么按照你的程序m=(0+8)/2=4,a[m]=3=v,那么一次就决定了r=4,但是实际上endindex=
5，因为后面还有个3，同理对求l来说也存在一样的问题。
我觉得在跳出while循环得到r后还应该再检查一下a[r+1]!=v（如果用a[r+1]>v这个判
断条件的话当v=10也就是数组最后一个数的时候会出现错判），如果a[r]==v&&a[r+1]=
=v,那么还要继续增加r直到找到a[r+1]!=v的那个r

【在 n*s 的大作中提到】

: def sSearch(a, v):
: tot_len = len(a)
: l = 0
: r = tot_len-1
: while l < r :
: m = (l+r) //2
: if a[m] > v:
: r = m -1
: elif a[m] < v:
: l = m + 1

P*l2012-04-17 07:04

20 楼

http://www.sureinterview.com/shwqst/545001

P*l2012-04-17 07:04

21 楼

http://www.sureinterview.com/shwqst/545001
code:
public void findRange(double[] data, double rangeStart, double rangeEnd,
Mutable pStart, Mutable pEnd) {
pStart.setValue(-1);
pEnd.setValue(-1);
if (data == null || data.length == 0)
return;
int posStart = 0, posEnd = data.length - 1;
// find where the data roughly is.
int inRange = 0;
while (posStart <= posEnd) {
inRange = (posStart + posEnd) / 2;
if (data[inRange] < rangeStart) {
posStart = inRange + 1;
} else if (data[inRange] > rangeEnd) {
posEnd = inRange - 1;
} else {
// found: rangeStart <= data[inRange] <= rangeEnd;
break;
}
}
// not found
if (posStart > posEnd)
return;
// Now, data[inRange] is in the range of data.
// We need to find the index that points to rangeStart.
int pEnd2 = inRange;
while (posStart <= pEnd2) {
int n = (posStart + pEnd2) / 2;
if (data[n] < rangeStart) {
posStart = n + 1;
} else {
pEnd2 = n - 1;
}
// note: there is no break when rangeStart was found.
}
// and find the end position in [inRange,posEnd]
int pStart2 = inRange;
while (pStart2 <= posEnd) {
int n = (pStart2 + posEnd) / 2;
if (data[n] > rangeEnd) {
posEnd = n - 1;
} else {
pStart2 = n + 1;
}
// note: there is no break;
}
if (posStart <= posEnd) {
pStart.setValue(posStart);
pEnd.setValue(posEnd);
}

n*s2012-04-17 07:04

22 楼

the return value here is the startIndex,
for endIndex, one can traverse from startIndex

,v
endindex=
]=

【在 f*********8 的大作中提到】

: 这是用python写的吗
: 是不是没有考虑到a[m]第一次正好等于v的情况呢，比如a[9]={0,1,2,3,3,3,4,7,10},v
: =3
: 那么按照你的程序m=(0+8)/2=4,a[m]=3=v,那么一次就决定了r=4,但是实际上endindex=
: 5，因为后面还有个3，同理对求l来说也存在一样的问题。
: 我觉得在跳出while循环得到r后还应该再检查一下a[r+1]!=v（如果用a[r+1]>v这个判
: 断条件的话当v=10也就是数组最后一个数的时候会出现错判），如果a[r]==v&&a[r+1]=
: =v,那么还要继续增加r直到找到a[r+1]!=v的那个r

g*x2012-04-17 07:04

23 楼

void rangeBinarySearch(const vector &vec, const int val, int &range_beg
, int &range_end)
{
range_beg = -1;
range_end = -1;
int beg = 0;
int end = vec.size();
int mid;
while(beg < end)
{
mid = (end - beg) / 2 + beg;
if(vec[mid] == val && (mid == 0 || vec[mid - 1] < val))
{
range_beg = mid;
break;
}
if(vec[mid] >= val)
end = mid;
else
beg = mid + 1;
}
if(range_beg == -1)
return;
beg = mid;
end = vec.size();
while(beg < end)
{
mid = (end - beg) / 2 + beg;
if(vec[mid] == val && (mid == vec.size() - 1 || vec[mid + 1] > val))
{
range_end = mid;
break;
}
if(vec[mid] > val)
end = mid;
else
beg = mid + 1;
}
}

c*n2012-04-17 07:04

24 楼

the
3 3 3
1).
out how
the end.

【在 x*********s 的大作中提到】

c*n2012-04-17 07:04

25 楼

这是很好的一个题，
programming pearl 里面有，就是binary search 升级版。
考的不是你怎么能把code 写出来，考的是怎么能prove correctness.
书里说10% programmer 能写对binary search,
这个估计能有3% 写对。
在chapter 4 的习题里面

the
2 3 3 3
1).
out how
the end.

【在 x*********s 的大作中提到】