mk802语音输入搞定了。 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>PDA - 掌中宝

mk802语音输入搞定了。

mk802语音输入搞定了。# PDA - 掌中宝

g*s2012-07-20 07:07

1 楼

那个实在太长了。我提炼了一下。似乎很难啊。
啥是soduko test？
最长回文的算法到底是啥？
sum of square是哪个经典算法？
发信人: evaeva (evaeva), 信区: JobHunting
标题: 生物PHD 转行找CS，报Offer和罗嗦的面经
发信站: BBS 未名空间站 (Sat Mar 19 06:10:37 2011, 美东)
背景: 生物phd, WSN, 计算机 master.毫无工作经验，无实际project经验
不在Google总部，面了５个人，
第一个负责论文讨论，ＥＥ背景，写底层code, 工作性质类似于打杂。
第二个问了简单的SODUKO　ＴＥＳＴ。　我写了一白板，和他讨论了下各种方法的复杂
度，就混过
去了。他自己做的东西也很简单，不懂ＭＬ，就做做数据库，写C 的。
第三个ＡＵＴＯＭＡＴＩＯＮ背景，做ADword。做题找最长回文。反转找最长相同加
suffix tree
不对。用简单的方法，n2 和n3。最好方法就是suffix tree。
第四个是JAVA person. 问把整数分成 sum of square的经典问题。递归解法。然后优
化，我给
了greedy的想法，他提示说可以用greedy 的解做bound。
第5个写了个 iterator 里iterator方法的实现。他自己随便定义了一个iterator让
我接着
写。

m*x2012-07-20 07:07

2 楼

看中一个新房子，那个builder是所谓的green home builder.
也看不出有啥特殊的，在东北部，房子还开了很多窗子。
大家有谁有经验吗？有啥需要注意的吗？
green home会不会用很多recycled materials and engineered material呀？

u*r2012-07-20 07:07

3 楼

发信人： baron8(白鲨), 信区： TVChinese
标题：美味奇缘这种片子已经没有市场了
发信站： BBS未名空间站(Sat Sep 23 23:36:38 2017,GMT)
话说中国的偶像剧市场刚开始是纯引进台湾的，后来又变成韩国的。最后呢，就自己编
自己演，有时候也改一改韩国的电视剧。不过，经过多年的反复拍摄。偶像剧的剧情，
和一些夸张的情节能够拍的，能够想到的基本上全部都出现过，并且是反复出现过。
像美味奇缘这种傻瓜偶像剧简直又是出来拉低人们的智商的，比如说一位企业继承人天
天想着做饭的事情。另一个漂亮但又平庸的女孩子，经常在生活中突然灵光一现的解决
很多事情。然后呢，这个姑娘又跟剧情中其他男人有关联，这个男人和男主又有一些恩
怨。
感觉有没有像是其他的什么剧，亲爱的翻译官什么的。总之，感觉真的太俗套。相信这
也是中文电视剧为何出现了像人民的名义啊，还有琅琊榜这样的片子的时候会让人觉得
眼前一亮。因为他们这些片子都很有特点，都不落俗套。

u*r2012-07-20 07:07

4 楼

发信人： samedog(狗之怒), 信区： Apple
标题：升级iOS 11后你的还好吗？
发信站： BBS未名空间站(Fri Sep 22 11:49:32 2017,GMT)
从昨天凌晨开始，苹果陆续为符合升级条件的iPhone和iPad等设备用户推送了iOS 11更
新。全新的iOS 11更多的考虑到了用户的使用感受，功能方面增强了不少，尤其是通知
中心可以自定义，果粉们期待已久的蜂窝网络快捷开关终于出现了。此外，苹果还针对
国内用户在iOS 11增加了特定功能，主要是二维码扫描、诈骗短信识别、拼音键盘以及
上海话语音识别等等。
在升级iOS 11之后，外媒发现了一个非常有意思的问题：在控制中心中，你点击了
WiFi和蓝牙图标之后，这两个功能其实并没有被关闭。
具体来说，当你在通知中心点击了正在使用中蓝牙和WiFi图标之后，它们确实变成了灰
色。但此时，系统只是断开了当前WiFi和蓝牙设备的连接，这两个功能其实并没有被
关闭。
这是一个Bug吗？其实苹果就是这么设计的，在iOS 11官方文档中，外媒发现苹果有详
细的说明：如果你想彻底关闭这两个功能，只能在设置中实现。
此外，一个需要注意的细节是：当你在通知中心关闭蓝牙或者WiFi功能，当地时间凌晨
5点过后或者你重启了设备之后，这两项功能会自动恢复。

e*m2012-07-20 07:07

5 楼

要搬家了，打算买个好点的路由器，请问这三个应该买哪个呢？个人现在倾向于
airport extreme，据说可以不折腾，但是另两个可能性价比更高一些，大家有什么推
荐么？

w*g2012-07-20 07:07

6 楼

刷了新的固件以后。mk802可以用麦克风了。花了一些时间把语音输入考定了。这篇文
章就是用语音输入法发表的。讯飞语音的表现不错。我觉得mk802真是神机。
-----发自我的74刀小安猪机mk802

s*n2012-07-20 07:07

7 楼

这个好，那个确实长

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

: 那个实在太长了。我提炼了一下。似乎很难啊。
: 啥是soduko test？
: 最长回文的算法到底是啥？
: sum of square是哪个经典算法？
: 发信人: evaeva (evaeva), 信区: JobHunting
: 标题: 生物PHD 转行找CS，报Offer和罗嗦的面经
: 发信站: BBS 未名空间站 (Sat Mar 19 06:10:37 2011, 美东)
: 背景: 生物phd, WSN, 计算机 master.毫无工作经验，无实际project经验
: 不在Google总部，面了５个人，
: 第一个负责论文讨论，ＥＥ背景，写底层code, 工作性质类似于打杂。

m*y2012-07-20 07:07

8 楼

Windows used to be the leak, but now they can get even higher R-value than
stud walls.

z*e2012-07-20 07:07

9 楼

都还不错。

c*l2012-07-20 07:07

10 楼

R8000还有几天就出了

★ 发自iPhone App: ChineseWeb 8.6

【在 e**********m 的大作中提到】

: 要搬家了，打算买个好点的路由器，请问这三个应该买哪个呢？个人现在倾向于
: airport extreme，据说可以不折腾，但是另两个可能性价比更高一些，大家有什么推
: 荐么？

b*e2012-07-20 07:07

11 楼

今上说，不折腾

【在 w*****g 的大作中提到】

: 刷了新的固件以后。mk802可以用麦克风了。花了一些时间把语音输入考定了。这篇文
: 章就是用语音输入法发表的。讯飞语音的表现不错。我觉得mk802真是神机。
: -----发自我的74刀小安猪机mk802

z*e2012-07-20 07:07

12 楼

顶！

g*62012-07-20 07:07

13 楼

很赞。感觉快了不少。

a*c2012-07-20 07:07

14 楼

airport跟另外两个根本不是一个级别的东东，相比之下另外两个都是beast。。。家用
都不需要折腾。

【在 e**********m 的大作中提到】

T*n2012-07-20 07:07

15 楼

你还真折腾上瘾了。好玩么？

【在 w*****g 的大作中提到】

e*a2012-07-20 07:07

16 楼

1 就是test是不是满足 soduko， careercup 150 上有
2 最优解我知道的是 suffix tree 加 LCA, o(n), 也是比较原来的和反转的string,
不过有点复杂。
3 题目出自：一个任意的长方形如何分成最少的正方形
除了3 我遇到的都是很基本的题，应该是要给出最优解写无bug代码 3也许不难，不过
我没见过。

F*y2012-07-20 07:07

17 楼

SE，升了感觉挺好的。升级的主要原因是为了手表的watch os4

e*m2012-07-20 07:07

18 楼

貌似已经出了？我看amazon上已经有卖了，请问这个比r7000还强很多么？

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

: R8000还有几天就出了
:
: ★ 发自iPhone App: ChineseWeb 8.6

w*g2012-07-20 07:07

19 楼

好玩，有点成就感。要知道我这是成功的山寨了个iTV！

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

: 你还真折腾上瘾了。好玩么？

g*s2012-07-20 07:07

20 楼

三个三个求和？
有链接吗？
还是不一样吧。比如1x5的长方形只能分解成5个1x1，但5=1^2+2^2。
这个应该用dp，类似find min coin combo。可以O(N)，但要假定sqrt(N)是const。

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

: 1 就是test是不是满足 soduko， careercup 150 上有
: 2 最优解我知道的是 suffix tree 加 LCA, o(n), 也是比较原来的和反转的string,
: 不过有点复杂。
: 3 题目出自：一个任意的长方形如何分成最少的正方形
: 除了3 我遇到的都是很基本的题，应该是要给出最优解写无bug代码 3也许不难，不过
: 我没见过。

s*y2012-07-20 07:07

21 楼

以前是显示还有多少storage可用，比如2G...现在变成了用了多少，10/16。。看上去
多出好多，不过就不知道还有多少能用的了，

e*m2012-07-20 07:07

22 楼

我看参数好像也差了不是太多。。。不过经常能看到说airport比另外两个还是稳定一
些，这个说法对么？

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

: airport跟另外两个根本不是一个级别的东东，相比之下另外两个都是beast。。。家用
: 都不需要折腾。

h*a2012-07-20 07:07

23 楼

mic是usb的?

【在 w*****g 的大作中提到】

e*a2012-07-20 07:07

24 楼

哦是不一样不过面试官给我这么说的呵呵可能我没记清楚
DP很容易不是最优的如果数很大可能会溢出什么的好像

m*s2012-07-20 07:07

25 楼

手机里settings里的general列出的about下面的available呢？

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

: 以前是显示还有多少storage可用，比如2G...现在变成了用了多少，10/16。。看上去
: 多出好多，不过就不知道还有多少能用的了，

a*c2012-07-20 07:07

26 楼

airport是1750，另外两是1900.实测airport差的更远，自己去看吧 http://www.smallnetbuilder.com/rankers/router/view。

【在 e**********m 的大作中提到】

: 我看参数好像也差了不是太多。。。不过经常能看到说airport比另外两个还是稳定一
: 些，这个说法对么？

w*g2012-07-20 07:07

27 楼

是一个LOGITECH WEBCAM上自带的.

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

: mic是usb的?

g*s2012-07-20 07:07

28 楼

even O(N) not optimal?
how could it trigger overflow if the input N not overflow? all numbers we
use are less than N.

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

: 哦是不一样不过面试官给我这么说的呵呵可能我没记清楚
: DP很容易不是最优的如果数很大可能会溢出什么的好像

s*y2012-07-20 07:07

29 楼

available 5G,,total 16G,
跟11G/16G对上了。。那就是升级完了又多了些storage???话说升级成为了16G的福音啊
。。

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

: 手机里settings里的general列出的about下面的available呢？

b*t2012-07-20 07:07

30 楼

R7000很稳定，除了升级firmware，从没重启过

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

:
: airport是1750，另外两是1900.实测airport差的更远，自己去看吧 http://www.smallnetbuilder.com/rankers/router/view。

l*y2012-07-20 07:07

31 楼

How to use dp? Did not figure it out.

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

: even O(N) not optimal?
: how could it trigger overflow if the input N not overflow? all numbers we
: use are less than N.

m*s2012-07-20 07:07

32 楼

其实，果子解决了前一版本的容量计算问题。

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

: available 5G,,total 16G,
: 跟11G/16G对上了。。那就是升级完了又多了些storage???话说升级成为了16G的福音啊
: 。。

k*h2012-07-20 07:07

33 楼

实在没想到airport这么弱，我的asus RT-66U居然完爆airport。会不会是和windows不
兼容？
不过RT-66U前段时间的那个安全漏洞，搞得我都不敢用他们家的aicloud了。
还有RT-66U的usb还是2.0，速度也不够快。当时真应该再等等，直接上RT-68U或者
R7000就好了。

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

:
: airport是1750，另外两是1900.实测airport差的更远，自己去看吧 http://www.smallnetbuilder.com/rankers/router/view。

l*y2012-07-20 07:07

34 楼

第四个是JAVA person. 问把整数分成 sum of square的经典问题。递归解法。然后优
化，我给
了greedy的想法，他提示说可以用greedy 的解做bound。
Could you please elaborate the question and solution?
Is this a classic question?
Thanks.

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

s*i2012-07-20 07:07

35 楼

靠，你们丫的是在joking么？苹果和果粉真的这么傻逼么？16G是16000000000，实际就
是14.9G，现在为了将就傻逼，给标成16G了？

a*e2012-07-20 07:07

36 楼

airport一向除了价格强大没有强的
那个时间机器也是

【在 k*h 的大作中提到】

: 实在没想到airport这么弱，我的asus RT-66U居然完爆airport。会不会是和windows不
: 兼容？
: 不过RT-66U前段时间的那个安全漏洞，搞得我都不敢用他们家的aicloud了。
: 还有RT-66U的usb还是2.0，速度也不够快。当时真应该再等等，直接上RT-68U或者
: R7000就好了。

g*e2012-07-20 07:07

37 楼

how come dp is O(n)? I think it's O(n^2)

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

: even O(N) not optimal?
: how could it trigger overflow if the input N not overflow? all numbers we
: use are less than N.

m*s2012-07-20 07:07

38 楼

同意，三星、华为都不这么标16G

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

: 靠，你们丫的是在joking么？苹果和果粉真的这么傻逼么？16G是16000000000，实际就
: 是14.9G，现在为了将就傻逼，给标成16G了？

a*c2012-07-20 07:07

39 楼

果果的东西向来就是骗果轮的。。。。。。

【在 k*h 的大作中提到】

g*s2012-07-20 07:07

40 楼

O(n) 不最优。例如： n=1000000000.
这题就是剪枝搜索。
1. 从大往小
2. 如果当前最优解的长度是k,
- 搜到深度k就返回
- 当前需要搜索的最大数字大于n div (k-当前深度）。n 是当前的值。

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

: even O(N) not optimal?
: how could it trigger overflow if the input N not overflow? all numbers we
: use are less than N.

m*h2012-07-20 07:07

41 楼

iPhone 6 Plus就是特么一个字—慢。

k*h2012-07-20 07:07

42 楼

也不是。果果的东西，大部分是9分的货，卖12分的价格。
但从这个评测来看，airport是5分的货，卖12分的价格，不太像果果的风格。

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

: airport一向除了价格强大没有强的
: 那个时间机器也是

g*s2012-07-20 07:07

43 楼

It is very quick even for n = Integer.MAX_VALUE;
public static void main(String arg[]){
preprocess();
int n=Integer.MAX_VALUE;
System.out.println("squares sum of " + n + " : ");
for (int num : getSquaresSum(n)){
System.out.print(" " + num);
}
System.out.println("\ntotal callCount= " + callCount);
}
public static Collection getSquaresSum(int n){
Stack cur = new Stack();
Stack result = new Stack();
findSquares(n, cur, result);
return result;
}
static int M = 10000;
static int p[] = new int[M];
static void preprocess(){
p[0] = 0;
ArrayList squares = new ArrayList();
for (int i =1 ; i<=getMaxSquare(M); i++) squares.add(i*i);
for (int i= 0 ;i < M ; i++){
for (int square : squares){
if (i+square>=M) break;
if ( p[i+square]==0 || p[i+square]>p[i]+1)
p[i + square] = p[i] + 1;
}
}
}
static long callCount = 0;
private static void findSquares(int n, Stack cur, Stack> result) {
callCount++;
if (cur.size()>=result.size() && result.size()>0)
return; //cut edges
if (n==0){
result.clear();
result.addAll(cur);
return;
}
if (cur.size()==result.size()-1) return;
if (result.size() !=0 && (n= result.size() - cur.size()))
return; //cut edges

int v = Math.min(cur.isEmpty() ? Integer.MAX_VALUE : cur.peek() ,
getMaxSquare(n)) ;
int m = (int) Math.sqrt(v+0.5);
while (v > 0 ) {
if (result.size() >0 && (v * (result.size() - cur.size() - 1) <
n) )
break; //cut edges
cur.push(v);
findSquares(n - v, cur, result);
cur.pop();
v -= (m--<<1) - 1;
}
}
private static int getMaxSquare(int n) {
int t = (int) Math.sqrt(n+0.5);
return t*t;
}

s*y2012-07-20 07:07

44 楼

那我就不懂了啊。。。
之前只有2G，现在显示有5G，，那到底低之前显示的少了呢？还是这回显示的多了呢？

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

: 其实，果子解决了前一版本的容量计算问题。

e*m2012-07-20 07:07

45 楼

感谢各位建议，已入R7000，$140，感觉还算值了。。。

【在 e**********m 的大作中提到】

l*y2012-07-20 07:07

46 楼

I think it is O (n^2) too.

【在 g**e 的大作中提到】

: how come dp is O(n)? I think it's O(n^2)

m*s2012-07-20 07:07

47 楼

少了3G呗

呢？

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

: 那我就不懂了啊。。。
: 之前只有2G，现在显示有5G，，那到底低之前显示的少了呢？还是这回显示的多了呢？

s*d2012-07-20 07:07

48 楼

我的AC66u VPN总连不上，或者连上了，再断掉，再连就不行了。你有这问题么

★ 发自iPhone App: ChineseWeb 8.7

【在 k*h 的大作中提到】

g*s2012-07-20 07:07

49 楼

关键是即使是O(n），也太大。
空间也溢出（是说你没法开那么大的数组）。

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

: I think it is O (n^2) too.

d*e2012-07-20 07:07

50 楼

之前有3G是留给iOS upgrade用的

呢？

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

: 那我就不懂了啊。。。
: 之前只有2G，现在显示有5G，，那到底低之前显示的少了呢？还是这回显示的多了呢？

k*h2012-07-20 07:07

51 楼

VPN我用的不多，以前给国内的朋友开过一段时间，没听他们说有问题。
我自己测试的时候也没遇到过连不上的

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

: 我的AC66u VPN总连不上，或者连上了，再断掉，再连就不行了。你有这问题么
:
: ★ 发自iPhone App: ChineseWeb 8.7

l*y2012-07-20 07:07

52 楼

#include
#include
#include
using namespace std;
int square[1000000];
int result[1000000];
int main()
{
int M = 1000000;
int limit = sqrt(M);
fill_n(result, 1000000, numeric_limits::max());
for (int i = 0; i <= limit; i++) {
square[i] = i * i;
result[i*i] = 1;
}
for (int i = 1; i <= M; i++) {
for (int j = 1; j <= limit; j++) {
if (i - square[j] >= 0) {
result[i] = min(result[i], result[i-square[j]] + 1);
} else {
break;
}
}
}
cout << result[M] << endl;
return 0;
}
O(n^2) It runs like a snail.

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

: 关键是即使是O(n），也太大。
: 空间也溢出（是说你没法开那么大的数组）。

x*e2012-07-20 07:07

53 楼

我的6s升级了，没问题

l*y2012-07-20 07:07

54 楼

剪枝搜索 I agree your program is much faster. what about complexity?
BTW, could anyone tell me how to do O(n) in dp?

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

: O(n) 不最优。例如： n=1000000000.
: 这题就是剪枝搜索。
: 1. 从大往小
: 2. 如果当前最优解的长度是k,
: - 搜到深度k就返回
: - 当前需要搜索的最大数字大于n div (k-当前深度）。n 是当前的值。

g*s2012-07-20 07:07

55 楼

DP is O(n ^ (3/2) ) .
减枝不好算。不过，即使是Math.Int, 大于2B的数值，访问的node也不超过10万个（不记得是4千还
是4万多）。
我程序里面统计了访问次数

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

: 剪枝搜索 I agree your program is much faster. what about complexity?
: BTW, could anyone tell me how to do O(n) in dp?

l*y2012-07-20 07:07

56 楼

Thanks very much!!!!

不记得是4千还

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

: DP is O(n ^ (3/2) ) .
: 减枝不好算。不过，即使是Math.Int, 大于2B的数值，访问的node也不超过10万个（不记得是4千还
: 是4万多）。
: 我程序里面统计了访问次数

f*i2012-07-20 07:07

57 楼

That is not correct, the DP can be O(nlgn)
however, it need O(n) space, that is a problem.
The idea of DP goes like it:
int num = Integer.MAX_Value;
for(int i=1;i*iif(num > a[i*i]+a[n-i*i])
num = a[i*i]+a[n-i*i]
}
a[n] = num;
a[1]=1,a[2] =2,a[3] = 3, then use DP from n>=4
For each n, it need to compare logn times, overall time complexity is O(
nlogn) which is less than O(n^(3/2))

DP is O(n ^ (3/2) ) .
减枝不好算。不过，即使是Math.Int, 大于2B的数值，访问的node也不超过10万个（不
记得是4千还
是4万多）。
我程序里面统计了访问次数

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

g*s2012-07-20 07:07

58 楼

yours is same, O(n ^ (3/2)
a[n] = a[i*i]+a[n-i*i]
a[i*i] is always 1, so a[n] = 1 + a[n-i*i]
i range from 1 to sqrt(n).
key point is that you can not create a huge a[] to do it.
I calculated all num<10000 using DP for cut-edges.

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

: That is not correct, the DP can be O(nlgn)
: however, it need O(n) space, that is a problem.
: The idea of DP goes like it:
: int num = Integer.MAX_Value;
: for(int i=1;i*i: if(num > a[i*i]+a[n-i*i])
: num = a[i*i]+a[n-i*i]
: }
: a[n] = num;
: a[1]=1,a[2] =2,a[3] = 3, then use DP from n>=4

l*y2012-07-20 07:07

59 楼

#include
#include
using namespace std;
int square[1000000];
int best = 4;
int result[4];
void RecurSearch(int count, int target, int start)
{
count ++;
if (count > best) return;
for (int i = start; i >= 1; i --) {
int value = target - square[i];
if (value < 0) continue;
if (square[i] < (target / (best - count))) continue;
result[count - 1] = square[i];
if (value == 0) {
if (count <= best) {
best = count;
cout << " best " << best << endl;
for (int i = 0; i < best; i++) {
cout << result[i] << '\t';
}
cout << endl;
}
return;
}
RecurSearch(count, value, i);
}
}
int main()
{
int M = 1000000000;
int limit = sqrt(M);
for (int i = 0; i <= limit; i++) {
square[i] = i * i;
}
RecurSearch(0, M, limit);
return 0;
}
I implement a c++ version according to your idea, thanks a lot!
Indeed it is much faster.

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

j*a2012-07-20 07:07

60 楼

ding

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

g*e2012-07-20 07:07

61 楼

有div 0的问题。换成乘法吧
if (square[i] < (target / (best - count))) continue;

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

: #include
: #include
: using namespace std;
: int square[1000000];
: int best = 4;
: int result[4];
: void RecurSearch(int count, int target, int start)
: {
: count ++;
: if (count > best) return;

k*j2012-07-20 07:07

62 楼

请问sum of square 那题限定只能转换成2个数的square吗？有没有原题有完整的描述
的？

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

s*y2012-07-20 07:07

63 楼

同求,标准的题描述是咋样的阿.

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

: 请问sum of square 那题限定只能转换成2个数的square吗？有没有原题有完整的描述
: 的？

g*e2012-07-20 07:07

64 楼

给定一个正整数n，要求找到最少的几个正整数，使得他们的平方和等于n
根据拉格朗日定理，任意一个自然数都可以表示成4个自然数的平方和，所以最多4个数
，可能更少

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

: 同求,标准的题描述是咋样的阿.

k*j2012-07-20 07:07

65 楼

为什么要把start做为函数来pass？不能每次就算一下sqrt(target)作为start?

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

: #include
: #include
: using namespace std;
: int square[1000000];
: int best = 4;
: int result[4];
: void RecurSearch(int count, int target, int start)
: {
: count ++;
: if (count > best) return;

g*s2012-07-20 07:07

66 楼

牺牲空间来换时间。不过，减枝效果好的话，没有必要来节约这点时间了。

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

: 为什么要把start做为函数来pass？不能每次就算一下sqrt(target)作为start?

c*t2012-07-20 07:07

67 楼

我在careercup　１５０题的第四版上只找到了检查 tic-tac-toe的题目，没有找到
soduko的题 :(

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

s*y2012-07-20 07:07

68 楼

Yes. I have the same question.

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

: 我在careercup　１５０题的第四版上只找到了检查 tic-tac-toe的题目，没有找到
: soduko的题 :(

r*e2012-07-20 07:07

69 楼

http://www.careercup.com/question?id=7737673

string,
不过

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

: 我在careercup　１５０题的第四版上只找到了检查 tic-tac-toe的题目，没有找到
: soduko的题 :(

e*a2012-07-20 07:07

70 楼

问题就是给一个整数,表示成n个整数的平方和,n最小, 要求这几个整数. brute force
是先找
n的平方根,然后递归. 如果整数很大, 如何提高效率一些case是 12=4+4+4
10017=10000+4+1,好像如果是像前者比较平均的,用递归效率就不高? 到这肯定是算法
题了,应该和写程序无关了吧. 现在我也不care了,什么乱七八糟的 :)
NND 拉格朗日定理我要是知道还可以和他扯扯..... 不过这题应该不怎么普遍,原来
没见过.

g*s2012-07-20 07:07

71 楼

知道拉格朗日定理，可以进一步优化。
不知道的，用现有的知识递归做效率也可以达到很高。（感觉减枝都应该可以减到1万
个结点以下）
因为再大的数字（32bit整数），第一个找到的解其实就是贪心的解，基本也就是6，7
左右。
BTW：为啥和写程序无关了？

force

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

: 问题就是给一个整数,表示成n个整数的平方和,n最小, 要求这几个整数. brute force
: 是先找
: n的平方根,然后递归. 如果整数很大, 如何提高效率一些case是 12=4+4+4
: 10017=10000+4+1,好像如果是像前者比较平均的,用递归效率就不高? 到这肯定是算法
: 题了,应该和写程序无关了吧. 现在我也不care了,什么乱七八糟的 :)
: NND 拉格朗日定理我要是知道还可以和他扯扯..... 不过这题应该不怎么普遍,原来
: 没见过.

e*a2012-07-20 07:07

72 楼

我的意思是说只要能说出正确的算法, 应该就基本达到要求了

c*t2012-07-20 07:07

73 楼

请问evaeva， sudoku那道题，判断一个输入是否valid的时候，sudoku是不是已经
complete了？还是说判断某个input最后能否导致一个正确的sudoku solution？

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

: 我的意思是说只要能说出正确的算法, 应该就基本达到要求了

k*p2012-07-20 07:07

74 楼

我觉得应该是
if (square[i] < (target / (best - count + 1))) break;
应该考虑当前这个i，然后没必要再continue到0了

【在 g**e 的大作中提到】

: 有div 0的问题。换成乘法吧
: if (square[i] < (target / (best - count))) continue;