编程日记，尽可能保证每天最少3道leetcode题，仅此记录学习的1些题目答案与思路，尽可能用多种思路来分析解决问题，不足的地方还望指出。标红题为以后还需要再看的题目。
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
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
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
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;
}
};结果：4ms
程序员人生，我编程，我富裕，记住wfuyu网，php教程，php学习，php手册，CMS模版制作
声明：本站大部分内容是作者原创，少部分收集于互联网供大家一起学习，原版权很多不明，如有侵权请联系本站，谢谢！
粤ICP备14040726号-1 2015-2020 程序员人生 版权所有
