集團數在該範圍的數字的總和等於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());