Leetcode题解（十五）

42、Trapping Rain Water

题目

这道题目参考http://www.cnblogs.com/felixfang/p/3713197.html

观察下就可以发现被水填满后的形状是先升后降的塔形，因此，先遍历一遍找到塔顶，然后分别从两边开始，往塔顶所在位置遍历，水位只会增高不会减小，且一直和最近遇到的最大高度持平，这样知道了实时水位，就可以边遍历边计算面积。

代码如下：

 1 class Solution {
 2 public:
 3     int trap(vector<int>& height) 
 4     {
 5         const int n = height.size();
 6         if(n <= 2) return 0;
 7         int max = -1, maxInd = 0;
 8         int i = 0;
 9         for(; i < n; ++i){//找出最大值所在位置
10             if(height[i] > max){
11                 max = height[i];
12                 maxInd = i;
13             }
14         }
15         int area = 0, root = height[0];
16         for(i = 0; i < maxInd; ++i){
17             if(root < height[i]) root = height[i];
18             else area += (root - height[i]);//与最近的高点的高度差
19         }
20         for(i = n-1, root = height[n-1]; i > maxInd; --i){
21             if(root < height[i]) root = height[i];
22             else area += (root - height[i]);
23         }
24         return area;
25     }
26         
27 };

-----------------------------------------------------------------------------------------分割线-----------------------------------------------------------------------------------

43、Multiply Strings

题目

模拟乘法，代码如下：

 1 class Solution {
 2 public:
 3     string multiply(string num1, string num2) {
 4         int len1 = num1.size(), len2 = num2.size(), len = len1 + len2;
 5         string str(len, '0');
 6         for (int i = len1 - 1; i >= 0; i--)
 7         {
 8             int a = num1[i] - '0';
 9             for (int j = len2 - 1, k = len2 + i; j >= 0; j--, k--)
10             {
11                 int b = num2[j] - '0';
12                 int c = str[k] - '0';
13                 int t = b * a + c;
14                 str[k] = t % 10 + '0';
15                 int d = (str[k-1] - '0') + t / 10;
16                 if (d >= 10)  //开始这里没有等号，检查了很久才发现，细心啊细心
17                     str[k-2] = str[k-2] - '0' + d / 10 + '0';
18                 str[k-1] = d % 10 + '0';
19             }
20         }
21         int x = 0;
22         while (str[x] == '0')
23             x++;
24         if (str.substr(x, len - x) == "")
25             return "0";
26         return str.substr(x, len - x);
27 
28     }
29 };