紅寶石遞歸算法問題

Question

工作的算法：

Given a rows x cols screen and a sentence represented by a list of non-empty words, find how many times the given sentence can be fitted on the screen. 

Note: 

A word cannot be split into two lines. 
The order of words in the sentence must remain unchanged. 
Two consecutive words in a line must be separated by a single space. 
Total words in the sentence won't exceed 100. 
Length of each word is greater than 0 and won't exceed 10. 
1 ≤ rows, cols ≤ 20,000. 
Example 1: 

Input: 
rows = 2, cols = 8, sentence = ["hello", "world"] 

Output: 
1 

Explanation: 
hello--- 
world--- 

The character '-' signifies an empty space on the screen. 
Example 2: 

Input: 
rows = 3, cols = 6, sentence = ["a", "bcd", "e"] 

Output: 
2 

Explanation: 
a-bcd- 
e-a--- 
bcd-e- 

The character '-' signifies an empty space on the screen. 
Example 3: 

Input: 
rows = 4, cols = 5, sentence = ["I", "had", "apple", "pie"] 

Output: 
1 

Explanation: 
I-had 
apple 
pie-I 
had-- 

The character '-' signifies an empty space on the screen. 

這裏是我的代碼：

def words_typing(sentence, rows, cols) 
    count_words(sentence, rows, cols, cols, 0, 0) 
end 

def count_words(sentence, rows, cols, remaining_space, row_num, word_idx) 
    return 0 if row_num == rows #keep going until out of rows, ends the recursion 
    word_idx = 0 if word_idx == sentence.length #reset the word back to the first 

    if remaining_space >= sentence[word_idx].length 
     if remaining_space == sentence[word_idx].length 
      return 1 + count_words(sentence, rows, cols, remaining_space - sentence[word_idx].length, row_num, word_idx + 1) 
     else #greater than 1 
      return 1 + count_words(sentence, rows, cols, remaining_space - sentence[word_idx].length - 1, row_num, word_idx + 1) 
     end 
    else #move to a new line, reset remaining space 
     return count_words(sentence, rows, cols, cols, row_num+1, word_idx) 
    end 
end 

代碼的工作原理如下。 word_idx是句子數組中單詞的索引。剩餘空間最初是列數。每當有足夠的空間放置單詞時，我會在同一行返回1 +函數調用，並保留下一個單詞和空格。如果剩餘空間> = 1 +字長，那麼我將考慮在兩個連續詞之間留有空格（這就是爲什麼我有額外的條件）。

如果word_idx比句子數組長，它會重置爲零。遞歸函數將繼續前進直到row_num現在大於在問題中提供給我們的行數。

但是，此代碼無效。我的輸出通常比正確的答案要大，但從概念上來說，我看起來都很好。任何人看到我的方法有問題？

Answer 1

這是因爲你在計算單詞而不是句子。

def words_typing(sentence, rows, cols) 
    count_words(sentence, rows, cols, cols, 0, 0, 0) 
end 

def count_words(sentence, rows, cols, remaining_space, row_num, word_idx, number_of_sentences) 
    nos = number_of_sentences 
    return nos if row_num == rows #keep going until out of rows, ends the recursion 

    if word_idx == sentence.length #reset the word back to the first 
    word_idx = 0 
    nos = number_of_sentences+1 
    end 
    if remaining_space >= sentence[word_idx].length 

     if remaining_space == sentence[word_idx].length 

      return count_words(sentence, rows, cols, remaining_space - sentence[word_idx].length, row_num, word_idx + 1, nos) 
     else #greater than 1 

      return count_words(sentence, rows, cols, remaining_space - sentence[word_idx].length - 1, row_num, word_idx + 1 , nos) 
     end 
    else #move to a new line, reset remaining space 

     return count_words(sentence, rows, cols, cols, row_num+1, word_idx, nos) 
    end 
end 


rows = 3 
cols = 6 
sentence = ["a", "bcd", "e"] 
words_typing(sentence, rows, cols) 
rows = 4; cols = 5; sentence = ["I", "had", "apple", "pie"] 
words_typing(sentence, rows, cols) 

我已經介紹了一個新的變量/參數（最後一個），它包含句子數（在開始0）。當word_idx == sentence.length這意味着在剩餘空間中裝入新句子，因此nos = number_of_sentences+1。
最後我們返回nos（句數）。

Answer 2

由於您的問題已經確定，我想建議另一種方法來編寫該方法。

def sentences_per_page(rows, cols, sentence) 
    nbr_sentences = 0 
    last_word_index = sentence.size-1 
    loopy = sentence.each_with_index.cycle 
    word, idx = loopy.next 
    rows.times do 
    cols_left = cols 
    while cols_left >= word.size 
     cols_left -= (word.size + 1) 
     nbr_sentences += 1 if idx == last_word_index 
     word, idx = loopy.next 
    end 
    end 
    nbr_sentences 
end 

rows = 4 
cols = 5 
sentence = ["I", "had", "apple", "pie"] 
puts     " rows  sentences" 
(1..12).each { |n| puts "  %d   %d" % 
    [n, sentences_per_page(n, cols, sentence)] } 
rows  sentences 
    1   0 
    2   0 
    3   1 
    4   1 
    5   1 
    6   2 
    7   2 
    8   2 
    9   3 
10   3 
11   3 
12   4 

我已經使用了方法Array#cycle。對於上面定義的sentence，

loopy = sentence.each_with_index.cycle 
    #=> #<Enumerator: #<Enumerator: ["I", "had", "apple", "pie"]:each_with_index>:cycle> 
loopy.first 10 
    #=> [["I", 0], ["had", 1], ["apple", 2], ["pie", 3], 
    # ["I", 0], ["had", 1], ["apple", 2], ["pie", 3], 
    # ["I", 0], ["had", 1]]