题目

Given an index k, return the k^th row of the Pascal’s triangle.
For example, given k = 3,
Return [1,3,3,1].
Note:
Could you optimize your algorithm to use only O(k) extra space?

思路

交替使用两个数组即可。

代码

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        rowIndex++;
        if(rowIndex < 1){
            return vector<int>();
        }
        vector<int> temp0(rowIndex, 0);
        vector<int> temp1(rowIndex, 0);
        vector<int>* pCurrRow = &temp0;
        vector<int>* pLastRow = &temp1;
        for(int i=0; i<rowIndex; i++){
            (*pCurrRow)[0] = 1;
            for(int col=1; col<=i; col++){
                (*pCurrRow)[col] = (*pLastRow)[col-1] + (*pLastRow)[col];
            }
            vector<int>* pTemp = pLastRow;
            pLastRow = pCurrRow;
            pCurrRow = pTemp;
        }
        return (*pLastRow);
    }
};

题目

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 n^th sequence.
Note: The sequence of integers will be represented as a string.

思路

好几题没刷leetcode手痒痒，又没太多时间，就选了个Easy的题啦…这个题目确实挺简单的，统计一下前面是不是重复就行了。在句末加一个特殊符号可以避免多写几行代码的样子~

代码

class Solution {
public:
    string countAndSay(int n) {
        string nStr = "1$";
        string nextStr = "";
        while(n > 1){
            char lastChr = '$';
            int lastCount = 0;
            for(int i=0; i<nStr.size(); i++){
                if(nStr[i] == lastChr){
                    lastCount++;
                } else {
                    if(lastCount > 0){
                        string tempStr;
                        while(lastCount > 0){
                            tempStr += (lastCount%10 +'0');
                            lastCount /= 10;
                        }
                        reverse(tempStr.begin(), tempStr.end());
                        nextStr += tempStr;
                        nextStr += lastChr;
                    }
                    lastCount = 1;
                    lastChr = nStr[i];
                }
            }
            nStr = nextStr + "$";
            nextStr = "";
            n--;
        }
        return nStr.substr(0, nStr.size()-1);
    }
};

如家网络实在太卡了，不过还好没有人劫@!$#@W…
稍微说一下思路把，这个问题就是判断某一层上的节点它的孩子会不会“溢出”，或者第一层的节点有没有完全闭合。我用一个栈来保存每一层的孩子数目（包括null）：

• 当碰到数字的时候，压一层计数为0的栈，表示新开了一层并且这一层的孩子数为0
• 当碰到#号时，说明多了一个空孩子，当前栈顶的计数+1，并且判断当前栈顶的计数是否>=2了，如果是的话，那说明这一层已经满了，那就退栈，然后再继续给新栈顶计数+1，继续判断是否满….如此往复

由于有了#表示空节点所以层级变得明确，举个例子：一个叶节点读入两个#，当前层的计数等于2后就退栈，并且给父亲层的计数器+1（表示下一层已经结束了，父亲多了一个左/右孩子）。
代码（好久没有纯手打一遍AC了）

class Solution {
public:
    bool isValidSerialization(string preorder) {
        int size = preorder.size();
        stack<int> working;
        int i = 0;
        while(i < size){
            int end = preorder.find(',', i);
            if(end == string::npos)
                end = size;
            if(preorder[i] != '#'){
                //number
                working.push(0);
            } else {
                //'#'
                if(i == 0){
                    //The null root?!
                    if(size > 1) return false;
                    else return true;
                }
                working.top() += 1;
                while(working.size()>1 && working.top() >= 2){
                    working.pop();
                    working.top() += 1;
                }
            }
            if(working.size() == 1 && working.top() > 2)
                return false;
            i = end+1;
        }
        return (working.size()==1) && (working.top()==2);
    }
};

BTW,苏州的交通状况和路面比杭州好多了。

题目

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
For example, given
s = "leetcode",
dict = ["leet", "code"].
Return true because "leetcode" can be segmented as "leet code".

思路1

写的第一个版本是超时的，但是思路应当是正确的，反正就是动态规划，但我用的是递归方法。
就是如果找到s[start,end]是单词表中的单词时，有两种处理，一种是算入然后往后走；另一种是忽略这次匹配成功，继续往后寻找。
代码大概这样：

class Solution {
public:
	int findNextWord(const string& s, int start, int curr, unordered_set<string>& wordDict) {
		//Find the end position of next possible word, or return -1
		string word = s.substr(start, curr - start + 1);
		for (int i = curr + 1; i < s.size(); i++) {
			word += s[i];
			if (wordDict.count(word) > 0) {
				return i;
			}
		}
		return -1;
	}
	bool parseSeq(const string& s, unordered_set<string>& wordDict, int start, int end, map<int, bool>& cache) {
		//Judge s[start...end]
		if (end >= s.size())
			return false;
		if (cache.count(start) > 1)
			return cache[start];
		string word = s.substr(start, end - start + 1);
		if (wordDict.count(word) > 0) {
			bool withThisWord = parseSeq(s, wordDict, end + 1, end + 1, cache);
			if (end + 1 == s.size() || withThisWord) {
				cache[start] = true;
				return true;
			}
		}
		int nextPos = findNextWord(s, start, end, wordDict);
		if (-1 != nextPos) {
			bool appendWord = parseSeq(s, wordDict, start, nextPos, cache);
			if (appendWord) {
				cache[start] = true;
				return true;
			}
		}
		cache[start] = false;
		return false;
	}
	bool wordBreak(string s, unordered_set<string>& wordDict) {
		map<int, bool> cache;
		return parseSeq(s, wordDict, 0, 0, cache);
	}
};

但是如果这里出现了超级多的单字，比如字符串是

aaaaaaaaaaaaaaaaaaaaaaa

然后字典是

{a,aa,aaa,aaaa}

这就搞笑了，得匹配死，所以肯定是超时。

思路2

这个是讨论组里看来的，突然发现一般来说DP递归能做的，就可以从后往前用非递归的方法写。对于这个问题来说，从后往前并不像做LCS那样时要完全倒着写。举个例子，有字符串str=thisisawesome 和字典{this, is, a, we, some, awesome} 的时候，可以用一个缓存cache来记录是否在str[i]位置有单词结束，比如str[3]位置就是”this”这个词结束的地方。当顺着继续搜索的时候，往前查找缓存记录，可以知道如果cache[i]=true的话，那才有可能从i这个位置往后到当前位置组成新单词，接着去查找字典看看有没有这个单词，如果没有的话，就得继续往前找到新的可用的开头i。这里加黑的“才有可能”是比较关键的。
代码大概是这样

bool wordBreak(string s, unordered_set<string>& wordDict) {
		if (wordDict.empty())
			return false;
		vector<bool> cache(s.size() + 1, false); //If a word ends at i, cache[i] = true
		cache[0] = true;
		for (int i = 0; i <= s.size(); i++) {
			for (int j = i - 1; j >= 0; j--) {
				if (cache[j]) {
					//Look backward and start at the end place of previous word
					string word = s.substr(j, i - j); // s[j...i-1]
					if (wordDict.find(word) != wordDict.end()) {
						cache[i] = true;
						break;
					}
				}
			}
		}
		return cache[s.size()];
	}

这里面向前迭代不断寻找cache[i]并尝试的情况，对应于之前思路1里面找到可用单词后的决定是否使用的分支情况。但是由于减少了一大堆递归调用，所以实际情况下的复杂度降低了不少。

题目

Given an input string, reverse the string word by word.
For example,
Given s = “the sky is blue“,
return “blue is sky the“.
Update (2015-02-12):
For C programmers: Try to solve it in-place in O(1) space.

思路

一！定！要！考！虑！各！种！情！况！比如

" "//一个空格
"   What am   I doing     "

然后这种倒转问题的原地处理思路应该都明白的，先把整个字符串倒转一遍，然后按照单词再倒转回来，拿”the sky is blue”为例：

1. “eulb si yks eht“
2. “blue si yks eht”
3. “blue is yks eht”
4. …
5. “blue is sky the”

代码

class Solution {
public:
	void reverseWordsSub(string &s, int start, int end) {
		//[start,end]
		char c;
		int count = 0;
		const int maxInd = (end - start - 1) / 2 + start;
		for (int i = start; i <= maxInd; i++) {
			c = s[i];
			s[i] = s[end - count];
			s[end - count] = c;
			count++;
		}
	}
	void clearStr(string &s) {
		//Clear unnecessary spaces
		int validIndex = -1;
		bool spaceFlag = false;
		for (int i = 0; i<s.size(); i++) {
			if (s[i] != ' ') {
				s[++validIndex] = s[i];
				spaceFlag = false;
			}
			else if (!spaceFlag) {
				if (validIndex < 0) {
					continue;
				}
				spaceFlag = true;
				s[++validIndex] = s[i];
			}
		}
		if (spaceFlag)
			validIndex--;
		if (validIndex < 0)
			s = "";
		else
			s = s.substr(0, validIndex + 1);
	}
	void reverseWords(string &s) {
		clearStr(s);
		int strSz = s.size();
		reverseWordsSub(s, 0, strSz - 1);
		int start = 0;
		for (int i = 0; i<strSz; i++) {
			if (s[i] == ' ') {
				reverseWordsSub(s, start, i - 1);
				start = i + 1;
			}
		}
		reverseWordsSub(s, start, strSz - 1);
	}
};