您當前位置：首頁 > php開源 > 綜合技術 > leetcode題解日練--2016.6.27

leetcode題解日練--2016.6.27

來源：程序員人生發布時間：2016-07-06 13:44:06 閱讀次數：2969次

編程日記，盡可能保證每天最少3道leetcode題，僅此記錄學習的1些題目答案與思路，盡可能用多種思路來分析解決問題，不足的地方還望指出。標紅題為以后還需要再看的題目。

本日題目：1、括號匹配合法判斷；2、count and say；3、最后1個詞的長度；4、2叉樹的路徑

20. Valid Parentheses | Difficulty: Easy

Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.

The brackets must close in the correct order, “()” and “()[]{}” are all valid but “(]” and “([)]” are not.
題意：給點3種括號，判斷1個括號的組合是不是合法。
思路：
1、括號匹配問題，用1個棧保存所有的括號。如果是左半邊括號，直接入棧，如果是右括號，判斷是不是與左括號相匹配，匹配直接彈出元素，不匹配返回false。
代碼：
C++

class Solution {
public:
    bool isValid(string s) {
        stack<char> brackets;
        for(int i=0;i<s.length();i++)
        {
            if(s[i]!='(' && s[i]!=')' && s[i]!='[' && s[i]!=']' && s[i]!='{' && s[i]!='}')
                 return false;
            else
                {
                    if(s[i]=='(' || s[i]=='[' ||  s[i]=='{')
                        brackets.push(s[i]);

                    else
                    {
                        if(brackets.empty() || (s[i] - brackets.top()!=1  &&  s[i] - brackets.top()!=2))    return false;
                        else    brackets.pop();
                    }
                }
        }
        return brackets.size()==0;
    }
};

結果：0ms

38. Count and Say | Difficulty: Easy

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.

題意：1種計數的讀法，1讀作1個1，所以下1個是11,11讀作兩個1，所以下1個是21,21讀作1個2，1個1，所以下1個是1211,1211讀作1個1，1個2，兩個1，所以下1個是111221.
思路：
這個序列有甚么規律呢？連續的數字（大于1個）不會產生新的數位，其他的單個字符會增加1個數位。
比如給定1211,最高位的1、2 不是連續，相應會變成11、 12、即在最高位再加1個1,11則會變成21，也是最高位加1。
從1開始分析，1不連續，變成11；
11連續，最高為位加1，變成21；
21,2不連續，變成12,1不連續，變成11。
1211,1不連續，變成11；2不連續，變成12；1連續，變成21

那末就遍歷1次這個字符串，默許的是不連續前面加1，連續的
c++

class Solution {
public:
    string countAndSay(int n) {
    if (n == 0) return "";
    string res = "1";
    while (--n) {
        string cur = "";
        //遍歷1次字符串
        for (int i = 0; i < res.size(); i++) {
            //默許的count是1，連續的時候就還需要1個循環去判斷究竟是連續了多少個數字
            int count = 1;
             while ((i + 1 < res.size()) && (res[i] == res[i + 1])){
                count++;    
                i++;
            }
            cur += to_string(count) + res[i];
        }
        res = cur;
    }
    cout<<res<<endl;
    return res;
}
};

結果：4ms

58. Length of Last Word | Difficulty: Easy

Given a string s consists of upper/lower-case alphabets and empty space characters ’ ‘, return the length of last word in the string.

If the last word does not exist, return 0.

Note: A word is defined as a character sequence consists of non-space characters only.

For example,
Given s = “Hello World”,
return 5.

題意：找到字符串最后1個單詞的長度
思路：
1、用流來處理，代碼非常簡單易懂，每次讀入1個單詞，然后更新長度，返回最后的長度便可。

class Solution {
public:
int lengthOfLastWord(string s) {
    if(s.length()==0) return 0;
    istringstream in(s);
    int i = 0;
    for(string word;in>>word;)
    {
        i = word.length();
    }
    return i;
}
};

結果：4ms
2、用python來寫1下,依照空格切開，返回最后1個元素的值就能夠了。
代碼：
python

class Solution(object):
    def lengthOfLastWord(self, s):
        """
        :type s: str
        :rtype: int
        """
        return len(s.strip().split(' ')[-1])

結果：44ms

257. Binary Tree Paths | Difficulty: Easy

Given a binary tree, return all root-to-leaf paths.

For example, given the following binary tree:

1
/ \
2 3
\
5
All root-to-leaf paths are:

[“1->2->5”, “1->3”]
題意：給定1棵2叉樹，找出所有從根節點到葉節點的路徑。
思路：
1、可以斟酌DFS思想遞歸去做，每次找到最深的那條路徑。原本的參數只有1個根節點，遞歸肯定是需要我們新寫1個函數，這個函數又需要哪些參數呢？明顯需要1個用來存返回結果的vector，其次需要傳入的下1個節點，最后需要寫入vector的元素，即之前寫好的字符串+”->”+”下1個節點的值”。
代碼：
C++

class Solution {
public:
    void binaryTreePaths(vector<string>&result,TreeNode* root,string t)
    {
     if(!root->left&&!root->right)
     {
         result.push_back(t);
     }
     if(root->left) binaryTreePaths(result,root->left,t+"->"+to_string(root->left->val));
     if(root->right) binaryTreePaths(result,root->right,t+"->"+to_string(root->right->val));


    }

    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> result;
        if(!root)   return result;
        binaryTreePaths(result,root,to_string(root->val));
        return result;
    }
};

結果：4ms
2、與11樣的思想，創建1個棧來保存每次的信息，需要保存的是當前的節點和當前的字符串。

class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> res;
        TreeNode *curNode;
        string curPath;
        //創建1個棧，存包括兩個元素的對，1個是節點，另外一個是到當前節點之前的字符串
        stack<pair<TreeNode*, string>> liveNodes;
        if(root) liveNodes.push(make_pair(root, ""));
        while(!liveNodes.empty())
        {
            curNode = liveNodes.top().first;
            curPath    = liveNodes.top().second;
            liveNodes.pop();
            if(!curNode->left && !curNode->right)
            {
                res.push_back(curPath + to_string(curNode->val));
            }
            else
            {
                if(curNode->right) liveNodes.push(make_pair(curNode->right, curPath + to_string(curNode->val)+ "->"));
                if(curNode->left)  liveNodes.push(make_pair(curNode->left, curPath + to_string(curNode->val)+ "->"));
            }
        }
        return res;
    }
};

結果：4ms
3、BFS用1個隊列，每次逐層掃描，看是不是有符合條件的節點。

class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        queue<pair<TreeNode*, string>> liveNodes[2];
        int cur=0, next=1;
        TreeNode* curNode;
        string curPath;
        vector<string> res;
        //還是1樣用1個queue來寄存1個節點，字符串對，每次1層的節點放在1個隊列，然后將這層的子節點（包括節點和加了當前節點以后的字符串）放在下1個隊列。如果cur隊列有滿條件的點（這個點1定是沒有子節點放入next中去的）。循環結束的條件是當前隊列為空。
        if(root) liveNodes[cur].push(make_pair(root, ""));
        while(!liveNodes[cur].empty())
        {
            curNode = liveNodes[cur].front().first;
            curPath = liveNodes[cur].front().second;
            liveNodes[cur].pop();
            if(!curNode->left && !curNode->right) res.push_back(curPath + to_string(curNode->val));
            else{
                if(curNode->left)  liveNodes[next].push(make_pair(curNode->left,  curPath + to_string(curNode->val) + "->"));
                if(curNode->right) liveNodes[next].push(make_pair(curNode->right, curPath + to_string(curNode->val) + "->"));
            }
            if(liveNodes[cur].empty()) swap(cur, next);
        }
        return res;
    }
};