集团数在该范围的数字的总和等于1

Question

我有一些数据是这样的：

[3, 3, 2, None, None, None, None, None, None, 1, None, 1, None] 

如果我分配1 - x到列表中的每个非无值，或1每个没有价值，我得到这些数字：

[-2, -2, -1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1] 

我给你从指数i数字来j一组，如果在该范围的数字的总和等于1，在这种情况下，这是分组名单看起来像：

[<-2, <-2, <-1, 1, 1>, 1, 1>, 1, 1>, <0, 1>, <0, 1>] 

或者，如果原来的数字被放在：

[<3, <3, <2, None, None>, None, None>, None, None>, <1, None>, <1, None>] 

每个非无值给予评分基于它是如何深嵌套，从0开始。例如，在2<2, None, None>组的分数为2.我想做一个函数来计算每个数字的分数，返回一个数字列表，其中每个数字对应于原始列表中的下一个非无值。在上面的例子，那结果将是：

[0, 1, 2, 0, 0] 

两个解决方案，我能想到的：

创建各组的开始和结束的索引列表，并且为每一个，看看有多少其他它落在里面。

创建一个递归函数，在遇到非-non值时调用它自己。

其中任何一个的实现将是非常有用的，否则我可以使用一些技巧来创建另一个解决方案。

Answer 1

不要使用递归;只需使用正向传球与堆叠。

• 保留一堆“打开”的括号和预计有多少None。
• 当您看到一个None时，请输入一个循环。每次迭代，递减数组的末尾;如果它达到0，则弹出它，否则退出循环。
  • 或者，这相当于只弹出数组末尾的所有1，然后递减数组的末尾。
• 当您看到一个数字时，将结果的堆栈深度写出来，并将该数字添加到堆栈的末尾。
• 当您到达输入末尾时，确认堆栈已空。

Here's code to do this:

let mut scores = Vec::new(); 
let mut stack = Vec::new(); 

for x in data { 
    let depth = stack.len(); 

    if let Some(v) = x { 
     scores.push(depth); 
     stack.push(v); 
    } else { 
     while let Some(&1) = stack.last() { 
      stack.pop(); 
     } 
     if let Some(last) = stack.last_mut() { 
      *last -= 1; 
     } 
    } 

    println!("{:?}", scores); 
} 

assert!(!scores.is_empty());