文档章节

要求把一个字符串中1存在的位置区间表现出来

hell0cat
 hell0cat
发布于 2016/07/15 21:55
字数 1408
阅读 44
收藏 0

原文地址:http://www.cnblogs.com/JeffreyZhao/archive/2009/04/19/why-i-do-not-like-java.html

用Haskell实现一下:

import Data.List
digit1Length str = filter ( /= "" ) . snd . foldl fx  (0, []::[String]) $ group str
    where fx acc e = let fa = fst acc in 
                     let ix = (length e) + fa in  -- 索引
                     let rs = if (length e) == 1 then show (fa+1) else show (fa+1) ++ "-" ++ show ix in
                     (ix,  (snd acc) ++ (if '1' == head e then [rs] else [""]))
main = do
    print $ digit1Length "00101111110111101110"
-- ["3","5-10","12-15","17-19"]

实现的比较原始,所以比较啰嗦,基本原理是用foldl,传入一个元组,第一个用来记录每一个数组的索引,第二个用来记录实际的区间值。碰到不为1的,记录为空字符串。

2.使用scanl实现

import Data.List
digit1Length' str = filter (\e -> (fst e)>0) .  tail . scanl (\z e -> (if '1'==head e then snd z + 1 else 0, snd z + (length e)) ) (0,0) $ group str

main = do
    print $ digit1Length' "00101111110111101110"
    print $ map (\e -> if fst e == snd e then show $ fst e else show (fst e) ++ "-" ++ show (snd e)) $ digit1Length' "00101111110111101110"

-- 输出:
-- [(3,3),(5,10),(12,15),(17,19)]
-- ["3","5-10","12-15","17-19"]

原理:scanl传入初始化元组(0,0),第一个用来记录开始位置,第二个用来记录结束位置,元组第二个累加长度,实现记录长度作用,元组第一个值在碰到0时候,不记录起始位置,而标记为0,这样可以在filter中过滤掉,tail是需要排除scanl引入的初始化值:(0,0) 元组。

推演过程: 1.导入group包,分组

Prelude> import Data.List
Prelude Data.List> group "00101111110111101110"
-- ["00","1","0","111111","0","1111","0","111","0"]

2.scanl标记索引位置:

Prelude Data.List> scanl (\z e -> (snd z + 1, snd z + (length e)) ) (0,0) $ group "00101111110111101110"
[(0,0),(1,2),(3,3),(4,4),(5,10),(11,11),(12,15),(16,16),(17,19),(20,20)]
-- [(0,0),(1,2),(3,3),(4,4),(5,10),(11,11),(12,15),(16,16),(17,19),(20,20)]
3.将0标记为0,方便后面过滤
```Haskell
Prelude Data.List> scanl (\z e -> (if '1' == head e then snd z + 1 else 0, snd z + (length e)) ) (0,0) $ group "00101111110111101110"
[(0,0),(0,2),(3,3),(0,4),(5,10),(0,11),(12,15),(0,16),(17,19),(0,20)]

剩下的就是过滤0了,因为第一个索引最小也是 snd z + 1 所以第一位为1也不会有问题,因为第一项为(0,0)所以无需tail也可以正常运行,加tail可以更加清晰的看到排除掉了初始化元组值。

运行效果:http://ideone.com/6kQcLw

欢迎haskell高手提供更加精简的算法。

Node.js/Javascript实现:

/* jshint esversion: 6 */
"use strict";

// 基本循环算法
function digit1Length(str) {
  var result = [];
  var size = str.length; // 长度
  var c = 0; // 当前字符,为 '1' 则为数字1,其他情况为 0
  var p = 0; // 上一个字符值。
  var x = 0; // 连续的1长度
  for (var i = 0; i < size; i++) {
    c = str.slice(i, i + 1) === '1' ? 1 : 0;
    if (i === 0) { // 初始化p
      p = c;
    }
    if (c === p) { // 若pc相等,则长度加1
      x++;
    } else { // 不一样的
      if (!c) { // current is 0,prev 则为 1
        result.push(x === 1 ? `${i - x + 1}` : `${i - x + 1}-${i}`);
      } else {
        x = 1;
      }
    }
    p = c;
  }
  if (c) { // 如果最后一个为1,则同样加入
    result.push(x === 1 ? `${i - x + 1}` : `${i - x + 1}-${i}`);
  }
  return result;
}

// match + reduce 解决方法
function digit1Length2(str) {
  return str.match(/0+|1+/g).reduce((s, e) => {
    if (/1/.test(e)) s[1].push(e.length > 1 ? `${s[0] + 1}-${s[0] + e.length}` : s[0] + 1 + '');
    s[0] += e.length;
    return s;
  }, [0, []])[1];
}

// 或者先加入,再过滤
function digit1Length3(str) {
  return str.match(/0+|1+/g).reduce((s, e) => {
    s[1].push(/1/.test(e) ? (e.length > 1 ? `${s[0] + 1}-${s[0] + e.length}` : s[0] + 1 + '') : null);
    s[0] += e.length;
    return s;
  }, [0, []])[1].filter(e => e);
}

console.log(digit1Length("00101111110111101110"));
console.log(digit1Length2("00101111110111101110"));
console.log(digit1Length3("00101111110111101110"));

输出结果:

[ '3', '5-10', '12-15', '17-19' ]
[ '3', '5-10', '12-15', '17-19' ]
[ '3', '5-10', '12-15', '17-19' ]

Ruby 代码和样例方式相同,但稍作修改,使用inject/reduce,而不引入额外变量:

p "00101111110111101110".scan(/0+|1+/).inject([0, []]) { |s, e| 
  s[1] << (e =~ /1/ ?  (e.size==1 ? "#{s[0]+1}" : "#{s[0]+1}-#{s[0]+e.size}") : nil )
  s[0] += e.size
  s
}.last.compact
# => ["3", "5-10", "12-15", "17-19"] 

Ruby这样的写法其实不是“最Ruby”的,最Ruby的方法当是灵活使用slice_when (Ruby2.2新增) 方法。

> "00101111110111101110".chars.each_with_index.map{|x, i| x == '0' ? nil : i+1 }.compact.slice_when{|i, j| i+1 != j }.map{|e| e.size > 1 ? "#{e.first}-#{e.last}" : "#{e.first}" } 
 => ["3", "5-10", "12-15", "17-19"] 

奥妙之处在于,首先将chars中为1的索引标记出来,过滤掉0:

> "00101111110111101110".chars.each_with_index.map{|x, i| x == '0' ? nil : i+1 }
 => [nil, nil, 3, nil, 5, 6, 7, 8, 9, 10, nil, 12, 13, 14, 15, nil, 17, 18, 19, nil]

接着,compact过滤掉nil项:

> "00101111110111101110".chars.each_with_index.map{|x, i| x == '0' ? nil : i+1 }.compact 
 => [3, 5, 6, 7, 8, 9, 10, 12, 13, 14, 15, 17, 18, 19] 

然后slice_when分组:

> "00101111110111101110".chars.each_with_index.map{|x, i| x == '0' ? nil : i+1 }.compact.slice_when{|i, j| i+1 != j }.to_a
 => [[3], [5, 6, 7, 8, 9, 10], [12, 13, 14, 15], [17, 18, 19]] 

到这一步,基本就实现了。

Rust实现,

extern crate regex;
use regex::Regex;

// 返回字符串中数字1的区间数组
fn digit1_length<'a>(s: &'a str) -> Vec<String> {
	Regex::new(r"0+|1+")
		.unwrap()
		.captures_iter(s)
		.map( |c| c.at(0).unwrap() )
		.fold( (0, vec![]), |mut acc, x| {	// 传入 初始化元组 (0, []) 第一个用来记录索引,第二个返回有效区间数组
			if x.contains('1') { // 提取1的字符串
				acc.1.push( // 加入结果集
					if x.len() == 1 { format!("{}", acc.0+1) } else { format!("{}-{}", acc.0+1, acc.0 + x.len()) }
				);
			}
			(acc.0 + x.len(), acc.1)
		}).1
}

fn main() {
	println!("{:?}", digit1_length("00101111110111101110")); // .join(", ") 链接字符串
}
// 输出: ["3", "5-10", "12-15", "17-19"] 

Rust的代码部分需要引用外部包 regex ,暂时没有找到更好的解决办法,还是使用fold(reduce/inject)折叠方式来解决,rust1.5增加了match_indices,可以匹配到的同时记录索引,但好像没有办法传入正则表达式。

Julia实现,依然是最原始的reduce办法:

join(
reduce( (acc, e) -> 
begin 
    if e[1]=='1' 
        push!(acc["v"], length(e)==1 ? "$(acc["i"]+1)" : "$(acc["i"]+1)-$(length(e)+acc["i"])" ) 
    end 
    acc["i"]+=length(e) 
    acc 
end, Dict("i"=>0, "v"=>[]), matchall(r"0+|1+", "00101111110111101110"))["v"], ", ")

输出:"3, 5-10, 12-15, 17-19"

© 著作权归作者所有

共有 人打赏支持
hell0cat
粉丝 37
博文 48
码字总数 24082
作品 0
徐汇
程序员
私信 提问
程序员进阶之算法练习(三十二)LeetCode专场

前言 BAT常见的算法面试题解析: 程序员算法基础——动态规划 程序员算法基础——贪心算法 工作闲暇也会有在线分享,算法基础教程----腾讯课堂地址。 今天是LeetCode专场练习。 正文 Copy L...

落影loyinglin
2018/08/09
0
0
Google 面试题 | 奇怪的打印机

专栏 | 九章算法 网址 | www.jiuzhang.com 题目描述 一个奇怪的打印机打印时遵守以下两个特殊的条件: 每次只能打印同一个字符组成的连续序列。 每次打印可以在任何位置开始,在任何位置结束...

九章算法
2017/12/11
0
0
NKOJ 4151 (TJOI 2016&HEOI 2016)字符串(后缀数组+倍增+主席树)

【Tjoi2016&Heoi2016】字符串 问题描述 佳媛姐姐过生日的时候,她的小伙伴从某东上买了一个生日礼物。生日礼物放在一个神奇的箱子中。箱子外边写了一个长为n的字符串s,和m个问题。佳媛姐姐必...

Mogician_Evian
2017/12/13
0
0
Python学习笔记(7)-字符串Str

字符串(Str) 一对单引号或一对双引号或一对三单引号或一对三双引号引起来的数据叫做字符串(引号均为英文状态下的引号),如图 用途:用来表示一串文字信息如一个名字、一串密码等 注意:字符...

立鼕
2018/08/23
0
0
NOIP2017提高组 模拟赛 27(总结)

NOIP2017提高组 模拟赛 27(总结) 第一题 回文数 (推公式+快速幂) 【题目描述】 【解题思路】   长度为1的字符串,s[1]=9。   长度为3的字符串,s[3]=10*9。   长度为5的字符串,s...

kekxy
2017/10/21
0
0

没有更多内容

加载失败,请刷新页面

加载更多

二进制取反

取反,是Java使用补码来表示二进制数,在补码表示中,最高位为符号位,正数的符号位为0,负数为1。 概念 编辑 补码的规定如下: 对正数来说,最高位为0,其余各位代表数值本身(以二进制表示)...

天王盖地虎626
今天
5
0
OSChina 周一乱弹 —— 可乐进化史

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @-冰冰棒- :#今日歌曲推荐# 分享Radiohead的单曲《Creep》 《Creep》- Radiohead 手机党少年们想听歌,请使劲儿戳(这里) @EdmondFrank :刚...

小小编辑
今天
891
17
容器服务

简介 容器服务提供高性能可伸缩的容器应用管理服务,支持用 Docker 和 Kubernetes 进行容器化应用的生命周期管理,提供多种应用发布方式和持续交付能力并支持微服务架构。 产品架构 容器服务...

狼王黄师傅
昨天
5
0
高性能应用缓存设计方案

为什么 不管是刻意或者偶尔看其他大神或者大师在讨论高性能架构时,自己都是认真的去看缓存是怎么用呢?认认真真的看完发现缓存这一块他们说的都是一个WebApp或者服务的缓存结构或者缓存实现...

呼呼南风
昨天
25
0
寻找一种易于理解的一致性算法(扩展版)

摘要 Raft 是一种为了管理复制日志的一致性算法。它提供了和 Paxos 算法相同的功能和性能,但是它的算法结构和 Paxos 不同,使得 Raft 算法更加容易理解并且更容易构建实际的系统。为了提升可...

Tiny熊
昨天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部