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

原创
2016/07/15 21:55
阅读数 155

原文地址: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"

展开阅读全文
加载中
点击引领话题📣 发布并加入讨论🔥
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部