【Leetcode Summary】11-15题总结

11. Container With Most Water

Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line iis at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

 

The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

solution:

首先想到的是暴力解法，遍历搜索最大盛水量，果然算法时间2340ms.。。。  时间复杂度是O(N平方)

第二个比较简单的算法：让两个指针分别指在水桶的水桶的两边，i,j.

如果height[i]<height[j]，那么i向中心移动，否则j向中心移动。因为只有水桶容量受限制于短边，只有移动短边，才可能找到更大 的容量。这样移动比较小的水桶边，可以找到最大container

算法时间复杂度是O(N/2)

12.

12. Integer to Roman

Medium

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

For example, two is written as II in Roman numeral, just two one's added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

• I can be placed before V (5) and X (10) to make 4 and 9. 
• X can be placed before L (50) and C (100) to make 40 and 90. 
• C can be placed before D (500) and M (1000) to make 400 and 900.

Given an integer, convert it to a roman numeral. Input is guaranteed to be within the range from 1 to 3999.

Example 1:

Input: 3
Output: "III"

Example 2:

Input: 4
Output: "IV"

Example 3:

Input: 9
Output: "IX"

Example 4:

Input: 58
Output: "LVIII"
Explanation: L = 50, V = 5, III = 3.

Example 5:

Input: 1994
Output: "MCMXCIV"
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

solution：这道题还是比较简单的。因为给出了数字上限。我们只需要从1000开始逐层考虑即可，需要注意的是，在考虑9 时，要在5之前考虑 比如，应该先考虑是否为900  再考虑是否大于500.  然后每次输入相应字符后，数字也减去相应的大小。

代码实现如下

class Solution {
public:
    string intToRoman(int num) {
        string result = "";
        if (num / 1000 != 0) {
            for (int i = 0; i < num / 1000; i++)
                result += "M";
            num = num % 1000;
        }
        if (num / 100 == 9) {
            result += "CM";
            num = num % 900;
        }
        if (num / 500 !=0) {
            result += "D";
            num = num % 500;
        }
        if (num / 100 == 4) {
            result += "CD";
            num = num % 400;
        }
        if (num / 100 != 0) {
            for (int i = 0; i < num / 100; i++)
                result += "C";
            num = num % 100;
        }
        if (num / 10 == 9) {
            result += "XC";
            num = num % 90;
        }
        if (num / 50 !=0) {
            result += "L";
            num = num % 50;
        }
        if (num / 10 == 4) {
            result += "XL";
            num = num % 40;
        }
        if (num / 10 != 0) {
            for (int i = 0; i < num / 10; i++)
                result += "X";
            num = num % 10;
        }
        if (num == 9) {result += "IX";num-=9;}
        if (num / 5 != 0) {
            result += "V";
            num = num % 5;
        }
        if (num == 4) {result += "IV";num-=4;}
        for (int i = 0; i < num; i++)
            result += "I";

        return result;
    }
};

13.Roman to Integer

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

For example, two is written as II in Roman numeral, just two one's added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

• I can be placed before V (5) and X (10) to make 4 and 9. 
• X can be placed before L (50) and C (100) to make 40 and 90. 
• C can be placed before D (500) and M (1000) to make 400 and 900.

Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.

Example 1:

Input: "III"
Output: 3

Example 2:

Input: "IV"
Output: 4

Example 3:

Input: "IX"
Output: 9

Example 4:

Input: "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.

Example 5:

Input: "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

solution:相对来说这道题也比较容易，对字符串进行遍历，当遇到特殊字符  如 I 时，考虑后面是否是X/V。如果是就+4/+9 否则加1 依次类推，由于太简单了 这里就不贴出代码了。

14. Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

Input: ["flower","flow","flight"]
Output: "fl"

Example 2:

Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

solution:求最长公共前缀。 思路是 首先把第一个字符当成最长公共前缀res。 然后从第二个字符开始，设一个新的空字符str。如果第二个字符和res有相同的字符，则加入str。但是必须小于res的长度，因为要保证是公共前缀。直到找到不相等字符或者遍历结束为之。把str赋值给res。

代码实现如下：

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        int length=0;
        string result;
        
        for(int k=0;k<strs.size();k++)
        {
            if(k==0) result = strs[0];
            if(strs[k] ==result) continue;
            string tmpstr;
            
            int i=0;
            while(i<result.size()&&i<strs[k].size())
            {
               if(result[i]==strs[k][i]) 
                   tmpstr+=result[i];
                else
                    break;
                i++;
            }
            result=tmpstr;
        }
        return result;
    }
};

15. 3Sum

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

solution:求三个数字的和为0  对应的三个数字，而且不能重复。 

第一个思路是对数组进行三重遍历，第一重确定第一个数字。~二~二。~三~三

但是会出现重复结果，所以我们把内层设置为vector，并且进行排序。外层设置为set，这样最终结果就不会有重复。

这样的时间复杂度是O(N立方）

但是最终会出现TLE ，说明题目不是想让我们暴力运算

第二个思路：首先对输入的字符进行排序，我们先确定三个数字中的第一个，那么第二个+第三个为 第一个数字的相反数

如果第一个数字就>0那么直接返回（因为后面的数字都大于0，没有可能找到相反数）

如果最后一个数字就<0同理

然后开始对数组进行遍历：

当循环到i时，在i+1处   和size -1处设置指针。令j=I=1;k=size-1,target=相反数

看nums[j]和Nums[k]相加是否为target，如果小于，则j++;大于则k--；

为了避免重复结果，如果等于，则加入result,并且对j和k进行判断，如果j=j+1 那么一直j++

如果k=k-1那么一直k-- 直到找到不同数字

代码实现如下：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        sort(nums.begin(), nums.end());
        if (nums.empty() || nums.back() < 0 || nums.front() > 0) return {};
        for (int k = 0; k < nums.size(); ++k) {
            if (nums[k] > 0) break;
            if (k > 0 && nums[k] == nums[k - 1]) continue;
            int target = 0 - nums[k];
            int i = k + 1, j = nums.size() - 1;
            while (i < j) {
                if (nums[i] + nums[j] == target) {
                    res.push_back({nums[k], nums[i], nums[j]});
                    while (i < j && nums[i] == nums[i + 1]) ++i;
                    while (i < j && nums[j] == nums[j - 1]) --j;
                    ++i; --j;
                } else if (nums[i] + nums[j] < target) ++i;
                else --j;
            }
        }
        return res;
    }
};