作为学习新的Java 11的Streams的练习,我想将一些简单的Codility实现转换为Stream解决方案。
例如,BinaryGap问题..使用Streams的一个简单的班轮解决方案将类似于:
public static int solution(int N) {
return Integer.toBinaryString(N).chars().
filter(x -> x == 1).whichIndexes().diff().max();
}
尽管只是问题,whichIndexes
和diff
不存在。我需要一种方法来获取已过滤元素的索引,然后计算它们的成对差异,这对于基于Streams的单线解决方案将是一个很好的起点。
获取索引很简单;流一个整数范围,而不是字符串中的字符。
String s = Integer.toBinaryString(N);
IntStream.range(0, s.length())
.filter(i -> s.charAt(i) == '1')
. // more stream operations
计算最大差值比较困难,因为这取决于流中的连续对,而不是单个元素。任何依赖于流中多个元素(而不是一次)的操作都必须在collect
阶段完成。这样做有点棘手:IntStream.collect方法采用三个参数:
Supplier<R>
提供类型为R
的新对象以收集结果,ObjIntConsumer<R>
累积类型为R
的一个对象,并且具有一个以上的int,BiConsumer<R, R>
在非并行流中不执行任何操作。类型R
将需要跟踪当前的最大差异以及所看到的最后一个数字,以便可以计算与下一个数字的差异。一种方法是让两个数字组成List
,其中索引0保持到目前为止的最大差值,索引1保持先前看到的数字(如果有)。
String s = Integer.toBinaryString(N);
int maxDiff = IntStream.range(0, s.length())
.filter(i -> s.charAt(i) == '1')
.collect(
// supply a new list to hold intermediate results
() -> {
List<Integer> acc = new ArrayList<Integer>();
acc.add(0); // initial max diff; and result if no "gap" exists
return acc;
},
// accumulate one more number into the result
(List<Integer> list, int num) -> {
if(list.size() == 1) {
// this is the first number, no diffs yet
list.add(num);
} else {
int max = list.get(0);
int lastNum = list.get(1);
int diff = num - lastNum;
list.set(0, diff > max ? diff : max);
list.set(1, num);
}
},
// combine two accummulators; shouldn't be called
(List<Integer> list1, List<Integer> list2) -> {
throw new RuntimeException("combiner shouldn't be called");
}
)
.get(0); // max diff is at index 0 in the list
几乎可以肯定,这比尝试使用流之前的解决方案要差,但是...嗯,您想要一个流解决方案,所以就在这里。
您无法获得单个流中元素的索引(IntStream
技巧还可以做其他事情,并且您不能对连续元素进行操作,您所看到的(在collect阶段之外)是元素(手工艺品除外,如下所示)。
首先,这里最终是一个真正的单面纸,现在可以正常工作,首先修剪前导零和尾随零(0$|^0
)。
Arrays.stream(Integer.toBinaryString(n).replaceAll("0$|^0", "").split("1"))
.reduce("", (a, b) -> a.length() > b.length() ? a : b)
.length();
但是我认为,这是最接近您(没有zipping)最初想法的方法,它从@ Kaya3和this有趣的技巧中清除了元素,以便从连续元素({1,2,3,4} -> {{1,2},{2,3},{3,4}}
)中获取配对。您也可以在map-to-pair的步骤中进行比较,也许省去了另一行,但是像这样很奇怪:
String st = Integer.toBinaryString(N);
Integer max = IntStream.range(0, st.length() - 1)
.filter(i -> st.charAt(i) == '1')
.boxed()
.map(new Function<Integer, Pair>() {
Integer previous;
@Override
public Pair apply(Integer i) {
Pair p = new Pair(previous, i);
previous = i;
return p;
}
}).skip(1) //first element is {null, smthg}
.map(i -> (i.right - i.left) - 1)
.max(Integer::compareTo)
.orElse(0);
但是mind you:“此[map hack]与流框架的设计完全相反,因为匿名函数不是无状态的,因此直接违反了map API的约定。请尝试使用并行流运行以及更多的数据,因此流框架将创建更多的工作线程,您将看到结果:很少的随机“错误”几乎无法重现,并且难以检测,除非您有足够的数据(正在生产中?)。这可能是灾难性的。” >
[我认为,与parallelStream()
一起使用,它将为您提供保证是错误的结果,因为那么与流的分区一样多的对丢失了。