leetcode 42, 58, 14(*)

42. Trapping Rain Water

1.暴力解法（未通过）

class Solution {
public:int trap(vector<int>& height) {int n = height.size();int res = 0;for(int i=0; i<n; i++){int r_max = 0, l_max= 0;for(int j = i; j<n; j++)r_max = max(r_max, height[j]);for(int j=i; j>=0; j--)l_max = max(l_max, height[j]);res += min(r_max, l_max) - height[i];}return res;}
};

解法的基本思路：

要把每一段拆分出来

某一竖条的储水量怎么求？ 他的高度是左边最大 和 右边最大 取的最小值，然后再减去自身的高度

2.备忘录

class Solution {
public:int trap(vector<int>& height) {int n = height.size();int res = 0;vector<int> r_max(n, 0);vector<int> l_max(n, 0);l_max[0] = height[0];r_max[n-1] = height[n-1];for(int i=1; i<n; i++)l_max[i] = max(height[i], l_max[i-1]);for(int i=n-2; i>=0; i--)r_max[i] = max(height[i], r_max[i+1]);for(int i=0; i<n; i++){res += min(r_max[i], l_max[i]) - height[i];}return res;}
};

这里就是把每一次的最大最小值都记录下来，就不用每次都遍历了，跟上一个思想没有区别

3.双指针法

class Solution {
public:int trap(vector<int>& height) {int n = height.size();int l_max = 0, r_max = 0;int res = 0;int left = 0, right = n-1;while(left < right){l_max = max(l_max, height[left]);r_max = max(r_max, height[right]);if(l_max < r_max){res += l_max - height[left];left++;}else{res += r_max - height[right];right--;}}return res;}
};

这里的l_max是【0， left】的最大值，r_max是【right, n-1】的最大值

为什么这样可以呢？因为其实只要一边找到最大值了，无论另一边是不是最大值，只要比它大，那么一定能兜住他

58. Length of Last Word

class Solution {
public:int lengthOfLastWord(string s) {int res = 0;int tail = s.size()-1;while(tail >= 0 && s[tail] == ' ') tail--;while(tail >=0 && s[tail] != ' '){res++;tail--;}return res;}
};

因为最后也有可能有空格，所以从后面开始

14. Longest Common Prefix

class Solution {
public:string longestCommonPrefix(vector<string>& strs) {int n = strs.size();string res = "";sort(strs.begin(), strs.end());string a = strs[0];string b = strs[n-1];int i=0;while(i<a.size() && i<b.size()){if(a[i] != b[i]) break;res += a[i];i++;}return res;}
};

这里用到sort, sort的最前和最后是最不相关的两个string