Tag: LeetCode OJ

题目

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);
	}
};

题目

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

思路1

找两个节点的公共最小祖先，可以利用递归的思想，即假设我们有个函数，能判断root为根节点的子树里有几个符合的节点（0，1或2个），在递归跳出的过程中，一旦我们发现有返回2个节点的，那这个根元素就肯定是p和q的最低公共节点了。

思路2

假设要找的节点是5和1，那么从根节点通往5的路径是3->5，通往1的路径是3->1。可以用递归方法构造一个路径栈，比较容易地找到路径，然后就变成两条路径的最长公共节点的问题了，“分岔”的地方就是LCA.
相比思路1，这个方法实施起来简单一些，但是要遍历两遍树，会稍微慢一点。

代码1

* struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int LCASub(TreeNode* root, TreeNode* p, TreeNode* q, TreeNode*& retNode){
        //If we find p or q, return 1
        //If we find root contains p and q, return 2 and set the retNode to common node
        //Else return 0
        if(root == NULL)
            return 0;
        int leftRet = LCASub(root->left, p, q, retNode);
        if(leftRet == 2)
            return 2;
        int rightRet = LCASub(root->right, p, q, retNode);
        if(rightRet == 2){
            return 2;
        }
        if(leftRet + rightRet == 2){
            retNode = root;
            return 2;
        } else if(root == p || root == q){
            if(leftRet==1 || rightRet == 1){
                retNode = root;
                return 2;
            } else {
                return 1;
            }
        } else {
            return leftRet + rightRet;
        }
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        TreeNode* retVal = NULL;
        LCASub(root, p, q, retVal);
        return retVal;
    }
};

代码2

class Solution {
public:
    bool getPath(TreeNode* root, TreeNode* p, stack<TreeNode*>& path){
        //Get path from root to p
        //If not available, return false
        if(root == NULL || root == p){
            path.push(root);
            return true;
        }
        bool foundPath = false;
        if(root->left != NULL){
            //try left
            foundPath = getPath(root->left, p, path);
            if(foundPath){
                //Mission complete, push current node and return
                path.push(root);
                return true;
            }
        }
        if(root->right != NULL){
            foundPath = getPath(root->right, p, path);
            if(foundPath){
                path.push(root);
                return true;
            }
        }
        return false;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        stack<TreeNode*> pPath;
        stack<TreeNode*> qPath;
        getPath(root, p, pPath);
        getPath(root, q, qPath);
        TreeNode* result = NULL;
        while(!pPath.empty() && !qPath.empty()){
            if(pPath.top() != qPath.top())
                break;
            result = pPath.top();
            pPath.pop();
            qPath.pop();
        }
        return result;
    }
};