每个软件工程师都应该在 1 个小时内解决的 5 个编程问题 [悲剧版]

[jacob]

最近很火的讨论，简单整理了一些： http://segmentfault.com/a/1190000002746474

[lincanbin]

美国 圣地亚哥

这不是国内大学生编程课的基础吗？

[lincanbin]

里面可能大学生可能会卡壳的：也就是斐波那契数列前100位的和的值的长度，已经超过了64位整形所能表示的长度。
当然这个问题其实也不是问题，稍微思考一下也能解决。

[semicircle21]

哈哈哈哈, 看到结尾释然了, 第四题的时候, 我也突然心中一凉...

[dangge]

大一狗看完后表示 稍微刷点算法题应该都能写完...
歪果仁是有多弱...
PS：Q4想了一下 只会笨拙的暴力比较...有什么好的算法吗？

[9hills]

@dangge 将正整数队列转换为字符串队列并排序即可

[c742435]

都会但是估计全调完不止一个小时欸。

[dangge]

@9hills 还可以再优化一点，取字符串首位比较

[raincious]

@dangge

何止，你需要用到树。

先转换整个整数到字符串，然后做个解析器，将字符串一个个解析出来，然后转换回整数，用插入排序的方式在插入树的时候就将数字排序好。

用题目上的例子，树应该应该像这样：

[50,2,1,9]

1
2
5 - 0
9

然后迭代这个树就行了。

[9hills]

@dangge 字符串比较就是顺序比较。

@raincious Python one line
a=[50,2,1,9]
print int("".join(sorted(map(str,a), reverse=True)))
>> 95021

[zsx]

@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]);

``

[zsx]

@zsx 效率另说，反正不是算法题（笑

[9hills]

人生苦短，我用Python。楼上 js的世界我真的不懂。

[zsx]

@9hills
对不起我错了……

[50, 2, 9, 1].map(function(a){return a.toString()}).sort().reverse().join("")

[zsx]

@9hills

[50, 2, 9, 1].map(String).sort().reverse().join("")

然而我似乎忘记了String()函数……

[raincious]

@9hills

简单+漂亮。

看到了你的答案我就在PHP里试了一下……

$numbers = [50,2,1,9];

rsort($numbers);

string(5) "50921"

// PHP 你好聪明，知道这是Int，于是还得用usort自己做个比较函数……

[imn1]

我觉得确实是基础
只有斐波那契数列那个不能随手写出来，因为实际工作中没怎么遇到相关的需求，以前写过就忘了

其他四个都在实际工作中（各种业务）不定时遇到
Q2/Q4很常见，尤其是Q4，比价常用，Q2则是分类中、或者多次select后合并常用的

[raincious]

@9hills

等等，这不对啊……

如果用[50,500]来做测试，你看

>>> b=[50,500]
>>> print int("".join(sorted(map(str,b), reverse=True)))
50050

期待的值应该是
50500

[xjx0524]

@9hills 字符串排序［56，50，5］结果就是56505 实际应该是56550

[batman2010]

#!/usr/bin/perl -w
use strict;

sub largest {
my @arr = @_;
my $res;
my @arr2 = sort {$b . $a cmp $a . $b} @arr;
my $iter = 0;
while ($iter < @arr2) {
$res .= $arr2[$iter++];
}
return $res;
}

#main
my @array = (50, 2, 1, 9);
print largest(@array), "\n";

[batman2010]

@batman2010 俺定的 Q4

[batman2010]

@batman2010 s/定/写

[Valyrian]

对于学过算法的，这些题太简单了。只能说搞软件工程的，其实并不涉及复杂的算法。。

[lvfujun]

@zsx 都怪php太聪明要不一样可以这么短.

[lvfujun]

@zsx @错了sorry!

[lvfujun]

@9hills 都怪php太聪明要不一样可以这么短.

[theoractice]

我觉得q4正确的方法应该是把所有的数分别用其个位数字补齐到位数相同，然后直接排序。
比如45,4386,23,3,9,4补成4555,4386,2333,3333,9999,4444
按排序结果就是9 45 4 4386 3 23

[lvfujun]

@raincious php太聪明了+1
@9hills [phpCode] $a = ['"50"','"2"','"1"','"9"'];rsort($a);print_r($a);[/phpCode]

[lvfujun]

js

[50,2,1,9].sort().reverse().join("");
"95021"

[zsx]

@lvfujun 然后根据楼上的回复发现其实这个解法是错的_(:з」∠)_

[theoractice]

我也错了，50和500这种情况无法分辨。不过属于边界情况，单独处理一下也行

[raincious]

@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

（我错了，这其实……是向量组，不是树）

但是貌似不是很优雅。

[raincious]

@raincious 我又错了，应该最终排序是这样

1
2
5 - 0 - 0
5 - 0
9

[lvfujun]

@raincious 原理很简单其实当很多编程语言里面自带的sort里面如果判断不是number 就按字符ascii码排序.其实这样的解法不是很"准”.

[9hills]

@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

[wdhwg001]

@theoractice 不用单独处理，改排序函数也行。

[9hills]

@9hills
@theoractice 想了想不对。。50和501这种其实也是。。50应该比501要大

所以还是自己实现一个compare吧，就是丑了点，Python得七八行

[raincious]

@9hills

楼主心中默想：“嗯，终于，大家发现了这么简单的问题也是有坑的，那么，我也安心了。”

于是楼主微笑着，推开了大门走了出去，消失在一片灿烂的阳光中，深藏功与名……

[9hills]

http://www.v2ex.com/t/189756

这个tip好像以前见过「cmp=lambda x, y: int(x + y) - int(y + x)」，还是自己弱。。<_<

[qwsqwa]

搞过ACM的表示第四题重写一个比较函数就好。

[gelupk]

Leetcode上有Q4这题
https://leetcode.com/problems/largest-number/

[choury]

@qwsqwa 我很怀疑你是否真搞过ACM，如你所说，123,1231,12312，三个数你比下，正确结果为：123123121231

[xudufy]

@theoractice 你的思路差一点就对了，应该是整体重复补齐，50应该补成5050，5位的话是50505之类

[zhyu]

这些题哪用得了一个小时。。20分钟足够了。。。

[zhyu]

Q4是leetcode原题，一行就完了，不过会有点长。。
cmp = lambda x, y: [1, -1][x + y > y + x]
result = ''.join(sorted(map(str, nums), cmp=cmp)).lstrip('0') or '0'

[zhyu]

用python写Q2不能更赞
from itertools import chain
result = list(chain.from_iterable(zip(list1, list2)))

[znoodl]

我敢说看到第三个题的时候肯定有人想把100个数计算出来一个个加一起

[theoractice]

@xudufy 诶，也不对，例如505和5055。看来只能重写compare法了

[xudufy]

@theoractice 刚试了一下要把长的补齐到短的的整倍数 505550 505505 画个图就会发现其实这就是x+y，y+x比较的微观过程

[spacewander]

@zhyu
Ruby只用一行：
list1.zip(list2).flatten

[reeco]

@lincanbin 看到美国圣地亚哥就想到金坷拉了

[zhyu]

@spacewander
因为 Ruby 有 Array.flatten 嘛，不过没想到 Ruby 里 Array.zip 居然返回的是 Array of Arrays 。。
其实能一行搞定的语言有很多，比如 elixir:
[list1, list2] |> List.zip |> Enum.map(&(Tuple.to_list(&1))) |> List.flatten

[qwsqwa]

@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;
}

搞得不好也不用这么打击人吧……

[402645707]

表示Q5死活解不出来

[zafkiel]

q5暴力搜索我只会暴力搜索唉

[zafkiel]

q3直接用Java把

[rushcheyo]

这些题目……冬天太冷用来暖手的吧？