1
chairuosen 2013-06-28 18:11:57 +08:00
不懂phthon,只有思路行不行
|
2
chisj 2013-06-28 18:15:02 +08:00
没有思路就穷举。
所以我第一眼看到就想for循环。。 |
3
best1a 2013-06-28 18:15:47 +08:00
(2)不是隐含(1)了么,直接遍历一遍O(n)不行么?
|
4
chairuosen 2013-06-28 18:18:51 +08:00
拙见:一个一个加,和与之前的和对比,有变多和不变两个状态,
每一次不变到变多,开始记录变多个数。每一次变多到不变,输出之前变多这个状态的个数 第二问不懂 |
5
Saito 2013-06-28 18:40:46 +08:00
r = []
m = [0, 0, 0, 2295, 2295, 1530, 0, 0, 0, 0, 0, 1020, 1530, 1530, 1530, 1530, 2295, 2550, 1785, 0, 0, 0, 0, 0, 1020, 1530, 1530, 1530, 1530, 2295, 2550, 0, 0, 0, 0, 0, 1275, 1530, 1530, 1530, 1530, 1530, 0, 0, 0, 0, 0, 0] lastest = current = 0 m.each_with_index do |n, i| lastest = current current = n if current != 0 if lastest == 0 r << i end else if lastest != 0 r << i - 1 end end end puts r puts r.each_slice(2) {|a| p a} puts r.each_slice(2).map{|a| a[1] - a[0] + 1 } 结果: 3 5 11 18 24 30 36 41 [3, 5] [11, 18] [24, 30] [36, 41] nil 3 8 7 6 [Finished in 0.0s] |
6
Saito 2013-06-28 18:42:43 +08:00
Ruby版
|
7
ruoyu0088 2013-06-28 19:08:55 +08:00
第一个问题可以用如下的一条语句:
[len(list(g)) for v, g in itertools.groupby((bool(x) for x in a)) if v] 第二个问题稍微复杂一点,分第0个元素是否为0,有两种情况: counts = (len(list(g)) for v, g in itertools.groupby((bool(x) for x in a))) acc = itertools.accumulate(counts) acc = itertools.chain([0], acc) if a[0] else acc list(zip(acc, acc)) 这里得到的index范围与Python的切片定义相同,包括start,不包括end。 itertools.accumulate是python 3.2新增加的。 |
8
Perry 2013-06-28 22:03:00 +08:00
|
9
switch 2013-06-28 22:39:29 +08:00
这是 Javascript 版的实现:
var num_arr = []; // 保存连续正整数的数目数组 var idx_arr = []; // 保存每个连接正整数开始位置的索引,如果需要获取第 i 组正整数的结束位置的索引,可以通过 idx_arr[i] + num_arr[i] - 1 来获取 for (var i = 0, num_arr = [], idx_arr = [], len = list.length; i < len; i++) { if (0 == list[i]) continue; idx_arr.push(i); for (var j = i + 1; j < len && list[j]; j++); num_arr.push(j - i); i = j; } |
10
cassyfar 2013-06-28 23:07:53 +08:00
我感觉怎么都要至少遍历一次 时间复杂度 O(n)
坐等能人给出nb算法 |
11
wang2191195 2013-06-29 00:08:10 +08:00
flag = False
res = [] start = -1 end = -1 for i in xrange(len(l)): if l[i] == 0: if i != 0 and flag == True: end = i - 1 flag = False res.append((start,end)) continue if not flag: start = i flag = True 这样应该还好吧?不太麻烦=。= |
12
kylefeng 2013-06-29 00:33:05 +08:00
最近在看Clojrue所以...
<script src="https://gist.github.com/kylefeng/5886031.js"></script> |
13
skydiver 2013-06-29 00:37:35 +08:00
|
14
skydiver 2013-06-29 00:38:20 +08:00
|
15
kylefeng 2013-06-29 00:45:15 +08:00
额,还不太会贴gist,再试试
http://gist.github.com/5886031 |
16
VYSE 2013-06-29 00:47:53 +08:00
bucket = []
[bucket[-1].append(idx) if val > 0 else bucket.append([]) for idx, val in enumerate(A)] [i for i in bucket if i] 底下就好用了呗 |
17
jander 2013-06-29 07:32:45 +08:00
```
A = [0, 0, 0, 2295, 2295, 1530, 0, 0, 0, 0, 0, 1020, 1530, 1530, 1530, 1530, 2295, 2550, 1785, 0, 0, 0, 0, 0, 1020, 1530, 1530, 1530, 1530, 2295, 2550, 0, 0, 0, 0, 0, 1275, 1530, 1530, 1530, 1530, 1530, 0, 0, 0, 0, 0, 0] B = [] def foo(i, data): if data: if i==0 or A[i-1]: B[-1].append([data, i]) else: B.append([[data, i]]) for i, data in enumerate(A): foo(i, data) for m in B: print m ``` |
19
supersheep 2013-06-29 13:52:22 +08:00
就遍历一遍咯,又不麻烦,让人能够一下看明白代码是干嘛的才比较重要。
|
20
IwfWcf 2013-06-29 23:00:27 +08:00
不就是扫一遍就能知道的东西吗,和算法有什么关系了……
|
21
xidianlz 2013-06-30 00:48:33 +08:00
试试couting sort的思想把
|