这是一个创建于 3493 天前的主题，其中的信息可能已经有所发展或是发生改变。
最近很火的讨论，简单整理了一些： http://segmentfault.com/a/1190000002746474
 |
1
lincanbin 2015-05-09 14:15:23 +08:00
美国 圣地亚哥
这不是国内大学生编程课的基础吗？ |
|
2
lincanbin 2015-05-09 14:20:26 +08:00
里面可能大学生可能会卡壳的：也就是斐波那契数列前100位的和的值的长度，已经超过了64位整形所能表示的长度。
当然这个问题其实也不是问题，稍微思考一下也能解决。 |
 |
3
semicircle21 2015-05-09 14:20:56 +08:00
哈哈哈哈, 看到结尾释然了, 第四题的时候, 我也突然心中一凉...
|
 |
4
dangge 2015-05-09 15:41:56 +08:00
大一狗看完后表示 稍微刷点算法题应该都能写完...
歪果仁是有多弱... PS：Q4想了一下 只会笨拙的暴力比较...有什么好的算法吗？ |
 |
6
c742435 2015-05-09 16:06:25 +08:00
都会但是估计全调完不止一个小时欸。
|
 |
8
raincious 2015-05-09 16:30:35 +08:00  1
@dangge
何止，你需要用到树。 先转换整个整数到字符串，然后做个解析器，将字符串一个个解析出来，然后转换回整数，用插入排序的方式在插入树的时候就将数字排序好。 用题目上的例子，树应该应该像这样： [50,2,1,9] 1 2 5 - 0 9 然后迭代这个树就行了。 |
 |
9
9hills 2015-05-09 16:42:52 +08:00 1
|
 |
10
zsx 2015-05-09 16:46:17 +08:00 1
@raincious
第四题不是一个全排列然后排序不就好了吗…… ``javascript (function(arr) { var resultArray = []; (function fn(source, result, callback) { if (source.length == 0) { callback(result); } else { source.forEach(function(item, index) { fn(source.slice(0, index).concat(source.slice(index + 1)), result.concat(item), callback); }) } })(arr, [], function(arr) { resultArray.push(arr.join("")); }); resultArray.sort(); console.log(resultArray[resultArray.length - 1]); })([50, 2, 9, 1]); `` |
|
12
9hills 2015-05-09 16:52:56 +08:00
人生苦短，我用Python。楼上 js的世界我真的不懂。
|
|
13
zsx 2015-05-09 16:58:58 +08:00
|
|
14
zsx 2015-05-09 17:00:21 +08:00
|
|
15
raincious 2015-05-09 17:08:58 +08:00
@9hills
简单+漂亮。 看到了你的答案我就在PHP里试了一下…… $numbers = [50,2,1,9]; rsort($numbers); string(5) "50921" // PHP 你好聪明，知道这是Int，于是还得用usort自己做个比较函数…… |
 |
16
imn1 2015-05-09 17:20:27 +08:00
我觉得确实是基础
只有斐波那契数列那个不能随手写出来，因为实际工作中没怎么遇到相关的需求，以前写过就忘了 其他四个都在实际工作中（各种业务）不定时遇到 Q2/Q4很常见，尤其是Q4，比价常用，Q2则是分类中、或者多次select后合并常用的 |
|
17
raincious 2015-05-09 17:21:29 +08:00
@9hills
等等，这不对啊…… 如果用[50,500]来做测试，你看 >>> b=[50,500] >>> print int("".join(sorted(map(str,b), reverse=True))) 50050 期待的值应该是 50500 |
 |
19
batman2010 2015-05-09 17:30:27 +08:00
|
|
20
batman2010 2015-05-09 17:30:56 +08:00
@batman2010 俺定的 Q4
|
|
21
batman2010 2015-05-09 17:31:58 +08:00
@batman2010 s/定/写
|
 |
22
Valyrian 2015-05-09 17:40:51 +08:00
对于学过算法的，这些题太简单了。只能说搞软件工程的，其实并不涉及复杂的算法。。
|
 |
26
theoractice 2015-05-09 17:47:24 +08:00 1
我觉得q4正确的方法应该是把所有的数分别用其个位数字补齐到位数相同，然后直接排序。
比如45,4386,23,3,9,4补成4555,4386,2333,3333,9999,4444 按排序结果就是9 45 4 4386 3 23 |
 |
27
lvfujun 2015-05-09 17:53:08 +08:00
|
|
28
lvfujun 2015-05-09 17:58:40 +08:00
js
[50,2,1,9].sort().reverse().join(""); "95021" |
|
30
theoractice 2015-05-09 18:10:41 +08:00
我也错了，50和500这种情况无法分辨。不过属于边界情况，单独处理一下也行
|
|
31
raincious 2015-05-09 18:13:11 +08:00
@lvfujun
你上面的解法其实就是强制PHP将值视为字符串。类似于： <?php $a = ['50', '2', '1', '9']; $b = []; foreach ($a as $aa) { $b[] = $aa . '-'; // 在最后加一个非数字的字符 } rsort($b); var_dump( (int)implode('', explode('-', implode('', $b))) ); 但是直接的字符串比较或许……不是解法，因为这样无法避免50500变50050的问题。 拆开再比就没这样的问题了，就像这样： 1 2 5 - 0 5 - 0 - 0 9 （我错了，这其实……是向量组，不是树） 但是貌似不是很优雅。 |
|
33
lvfujun 2015-05-09 18:27:51 +08:00
@raincious 原理很简单其实当很多编程语言里面自带的sort里面如果判断不是number 就按字符ascii码排序.其实这样的解法不是很"准”.
|
|
34
9hills 2015-05-09 18:36:08 +08:00
@raincious
@xjx0524 恩，这个有个bug，可以补一个compare函数，比如 @theoractice 说的那个办法 a=[56,50,5] max_l = max(map(len, map(str, a))) print int("".join(sorted(map(str,a), reverse=True, key=lambda i:i.rjust(max_l, i[-1])))) 56550 |
 |
35
wdhwg001 2015-05-09 18:37:10 +08:00 via iPhone
@theoractice 不用单独处理，改排序函数也行。
|
|
36
9hills 2015-05-09 18:39:18 +08:00
|
|
37
raincious 2015-05-09 18:44:41 +08:00
|
|
38
9hills 2015-05-09 18:45:30 +08:00
|
 |
39
qwsqwa 2015-05-09 19:17:01 +08:00
搞过ACM的表示第四题重写一个比较函数就好。
|
 |
40
gelupk 2015-05-09 19:26:35 +08:00
Leetcode上有Q4这题
https://leetcode.com/problems/largest-number/ |
 |
41
choury 2015-05-09 20:10:51 +08:00
@qwsqwa 我很怀疑你是否真搞过ACM，如你所说，123,1231,12312，三个数你比下，正确结果为：123123121231
|
 |
42
xudufy 2015-05-09 21:24:44 +08:00 via Android 1
@theoractice 你的思路差一点就对了，应该是整体重复补齐，50应该补成5050，5位的话是50505之类
|
 |
43
zhyu 2015-05-09 21:31:23 +08:00
这些题哪用得了一个小时。。20分钟足够了。。。
|
|
44
zhyu 2015-05-09 21:35:59 +08:00
Q4是leetcode原题，一行就完了，不过会有点长。。
cmp = lambda x, y: [1, -1][x + y > y + x] result = ''.join(sorted(map(str, nums), cmp=cmp)).lstrip('0') or '0' |
|
45
zhyu 2015-05-09 21:49:06 +08:00
用python写Q2不能更赞
from itertools import chain result = list(chain.from_iterable(zip(list1, list2))) |
 |
46
znoodl 2015-05-09 22:11:42 +08:00
我敢说看到第三个题的时候肯定有人想把100个数计算出来一个个加一起
|
|
47
theoractice 2015-05-09 22:30:59 +08:00
@xudufy 诶，也不对，例如505和5055。看来只能重写compare法了
|
|
48
xudufy 2015-05-09 23:16:44 +08:00 via Android
@theoractice 刚试了一下要把长的补齐到短的的整倍数 505550 505505 画个图就会发现其实这就是x+y，y+x比较的微观过程
|
 |
49
spacewander 2015-05-10 11:33:16 +08:00
|
|
51
zhyu 2015-05-10 13:55:06 +08:00
@spacewander
因为 Ruby 有 Array.flatten 嘛，不过没想到 Ruby 里 Array.zip 居然返回的是 Array of Arrays 。。 其实能一行搞定的语言有很多，比如 elixir: [list1, list2] |> List.zip |> Enum.map(&(Tuple.to_list(&1))) |> List.flatten |
|
52
qwsqwa 2015-05-10 14:47:58 +08:00
@choury
#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> using namespace std; int n; int a[111]; long long get(const int &a) { long long ret = 1; while(ret < a){ ret *= 10; } return ret; } bool cmp(const int &a, const int &b) { return (long long)a*get(b)+b > (long long)b*get(a)+a; } void solve() { for(int i = 0; i < n; i++){ scanf("%d",&a[i]); } sort(a,a+n,cmp); for(int i = 0;i < n; i++){ printf("%d",a[i]); } puts(""); } int main() { #ifdef ARTHUR_YANG freopen("in.txt", "r", stdin); #endif // ARTHUR_YANG while(~scanf("%d",&n)) { solve(); } return 0; } 搞得不好也不用这么打击人吧…… |
 |
53
402645707 2015-05-10 22:37:04 +08:00
表示Q5死活解不出来
|
 |
54
zafkiel 2015-05-11 00:00:06 +08:00
q5暴力搜索我只会暴力搜索唉
|
|
55
zafkiel 2015-05-11 00:03:39 +08:00 1
q3直接用Java把
|
 |
56
rushcheyo 2016-02-11 19:53:00 +08:00
这些题目……冬天太冷用来暖手的吧？
|
Select Language