6. ZigZag Conversion\38. Count and Say

• ZigZag Conversion
  • 題目描述
  • 代碼實作
• Count and Say
  • 題目描述
  • 代碼實作

6. ZigZag Conversion

題目描述

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R
And then read line by line: "PAHNAPLSIIGYIR"
Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);
convert("PAYPALISHIRING", ) should return "PAHNAPLSIIGYIR".
           

這個題目表面上說的是Z字形，其實就是把一維字元串從上到下，從下到上這樣往複排列，然後把每一行拼接起來。

代碼實作

class Solution {
public:
    string convert(string s, int numRows) {
        int slen = s.length();
        string res;
        if(slen <= numRows || numRows <= ) return s;
        vector<vector<char>> str(slen);
        bool dir = true;
        int ind = ;
        for(int i = ; i < slen; i++) {
            str[ind].push_back(s[i]);
            if(ind >= numRows - ) {
                dir = false;
                ind--;;
            }
            else {
                if(!dir && ind) ind--;
                else{ ind++; dir = true; }
            }
        }
        for(int j = ; j < numRows; j++) 
            res += string(str[j].begin(), str[j].end());
        return res;
    }
};
           

38. Count and Say

題目描述

The count-and-say sequence is the sequence of integers beginning as follows:

1, 11, 21, 1211, 111221, …

• 1 is read off as “one 1” or 11.
• 11 is read off as “two 1s” or 21.
• 21 is read off as “one 2, then one 1” or 1211.
• Given an integer n, generate the nth sequence.

Note: The sequence of integers will be represented as a string.

這道題目的題目意思比較難費解，其實就是這樣的：

如果n =1， 那麼就是“1”。 n=2，對前面的“1”進行描述就是一個1，那就是“11”。n = 3的時候，對“11”進行描述就是“21”，前面一個數字表示這個數字連續有幾個，後面一個數字表示是什麼數字。然後“21”就是“1211”。下一個就是“111221”，再下一個就是“312211”

代碼實作

class Solution {
public:
    string countAndSay(int n) {
        string res = "1";
        int count = ;
        for(int i = ; i < n-; i++) {
            int fstlen = res.length();
            string tmp;
            for(int j = ; j < fstlen; j++) {
                count = ;
                while(j+ < fstlen && res[j] == res[j+]) {j++; count++;}
                tmp.push_back(char('0'+count));
                tmp.push_back(res[j]);
            }
            //cout << tmp << endl;
            res = tmp;
        }
        return res;
    }
};