2016年10月21日星期五

418. Sentence Screen Fitting



Say sentence=["abc", "de", "f]rows=4, and cols=6.
The screen should look like
"abc de"
"f abc "
"de f  "
"abc de"
Consider the following repeating sentence string, with positions of the start character of each row on the screen.
"abc de f abc de f abc de f ..."
 ^      ^     ^    ^      ^
 0      7     13   18     25
Count the valid characters


" abc de f abc de。。。。“
当碰到 s[count % s.length()]==‘ ’的时候,eg.  count =7的时候,s[7] == ' ',说明这行没有取到这个‘ ’,我们要加上这个count。
在前面加‘ ’更加好算。
int wordsTyping(vector<string>& sentence, int rows, int cols) {
        string s = "";                                          // s is the formatted sentence to be put to our screen
        for (string word : sentence) { s += " " + word; }
        
        int count = 1;                                          // skip the very first space char ' '
        for (int r = 0; r < rows; r++, count ++) {               // advance count by one so s[count % s.length()] != ' '
            count += cols;                                      // full fill current collumn, so start advance by cols
            while (s[count % s.length()] != ' ') { count--; }   // make sure s[start % s.length()] == ' '
        }
        
        return --count / s.length();                            // we began with start == 1, so (start-1) is the valid length
}

  • if count%s.length() map to begin of some word, this word actually hasn't been added to count,
  • thus, the begin of some word score is 0, ' 'score is 1, other place(filled with words, need roll back) score is map[i-1]-1
 public int wordsTyping(String[] sentence, int rows, int cols) {  
     String s = String.join(" ", sentence)+" ";  
     int len = s.length();  
     int count = 0;  
     int[] map = new int[len];  
     for(int i = 1; i < len; i++){  
       map[i] = s.charAt(i) == ' '? 1 : map[i-1]-1;  
     }  
     for(int i = 0; i < rows; i++){  
       count += cols;  
       count += map[count%s.length()];  
     }  
     return count/len;  
   }  

没有评论:

发表评论