今天完成了三道题目，总结一下：
1: Length of last word(细节实现题)
此题有一些细节需要注意(比如 “a_ _” 最后一个单词是a, 而不是遇到空格就直接算成没有)，别的基本就是模拟了。
class Solution {
public:
int lengthOfLastWord(const char *s) {
string str = s;
if(str.empty()) return ;
int index;
// 从后向前扫描到第一个不是空格的字符
for(index = str.size()-;index>=;index--)
{
if(str[index]!=' ')
break;
}
if(index<) return ;
int i;
//从此字符开始，往前遇到空格停止计算或者把字符串扫描完
for(i=index;i>=;i--)
{
if(str[i] == ' ')
break;
}
return (index-i);
}
};
2. Trapping Rain Water
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
这道题目是直方图类题目，贴出的解法是book上的，两轮扫描，第一轮记录左前缀最大值和右前缀最大值； 第二轮扫描，对每个位置，可以积的水是
max(min(max_left,max_right)-height,0) height 是当前位置的格子高度。 这道题目应该算是一道技巧题了。
class Solution {
public:
int trap(int A[], int n) {
if(n<) return ;
int* left_max = new int[n];
int* right_max = new int[n];
// Two pass algorithm
left_max[] = A[];
right_max[n-] = A[n-];
for(int i=;i<n;i++)
{
left_max[i] = max(left_max[i-],A[i]);
right_max[n--i] = max(right_max[n-i],A[n--i]);
}
int water = ;
for(int i=;i<n;i++)
{
water += max(min(left_max[i],right_max[i])-A[i],);
}
return water;
}
};
3.Valid Parentheses
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.
简单的括号匹配题，一般都是用栈来实现。实现细节要注意，错误都犯在控制变量的初始化上了（test 变量每次set成true之后，没有重新初始化）
class Solution {
public:
bool isValid(string s) {
stack<int> st;
bool test=false;int num;
for(int i=;i<s.size();i++)
{
switch (s[i])
{
case '(': num = ;st.push(num);break;
case '[': num = ;st.push(num);break;
case '{': num = ;st.push(num);break;
case ')': num = ;test = true;break;
case ']': num = ;test =true;break;
case '}': num = ;test = true; break;
}
if(test)
{
if(st.empty() || st.top()!=num) return false;
else st.pop();
test =false;
}
}
if(st.empty()) return true;
else return false;
}
};