leetcode 11-15题解 - dblank

# 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 i is 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.

## 代码:

class Solution {
public:
int maxArea(vector<int>& height) {
int ans = 0, l = 0, r = height.size()-1;
while(l<r)
{
ans = max(ans, min(height[l] , height[r]) *(r - l));
if(height[l] < height[r])
l++;
else r--;
}
return ans;
}
};

# 12. Integer to Roman

Given an integer, convert it to a roman numeral.

Input is guaranteed to be within the range from 1 to 3999.

## 代码：


class Solution
{
public:
string intToRoman(int num)
{
string roman[4][10] = {
{"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"},
{"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"},
{"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"},
{"", "M", "MM", "MMM"}
};
string ans = "";
int cnt = 3, div = 1000;
while(cnt>=0)
{
ans.append(roman[cnt][num/div%10]);
div /= 10;
cnt--;
}
return ans;
}
};

# 13. Roman to Integer

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

## 代码：

class Solution {
public:
int romanToInt(string s) {
unordered_map<char , int> umap
{
{'I', 1}, {'V', 5},
{'X', 10}, {'L', 50},
{'C', 100}, {'D', 500},
{'M', 1000}
};
int ans = 0;
for(int  i = 0; i<s.size(); i++)
{
if(i < s.size() - 1 && umap[ s[i] ] < umap[ s[i+1] ])
{
ans += umap[ s[i+1] ] - umap[ s[i] ];
i++;
}
else ans += umap[ s[i] ];
}
return ans;
}
};

# 14. Longest Common Prefix

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

## 代码：


class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
string ans ="";
if(strs.size()<1)
return "";
for(int i = 0; i<strs[0].size(); i++)
{
if(check(i, strs))
ans.push_back(strs[0][i]);
else break;
}
return ans;
}
bool check(int id, vector<string>& strs)
{
for(int i = 1; i<strs.size(); i++)
{
if(id > strs[i].size() || strs[i][id] != strs[0][id])
return false;
}
return true;
}
};

# 15. 3Sum

Given an array S of n integers, are there elements a, b, c in S 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.

For example, given array S = [-1, 0, 1, 2, -1, -4],

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


## 思路：

1.Two Sum一样，我们先枚举一个元素然后用找二元组的方法找target - nums[i].

## 代码：

class Solution
{
public:
vector< vector<int> > ans;
vector<vector<int> > threeSum(vector<int>& nums)
{
sort(nums.begin(), nums.end());
if(nums.size()<3) return ans;
for(int i = 0; i<nums.size(); i++)
{
if(i>0 && nums[i] == nums[i-1])
continue;
twoSum(i+1, nums.size()-1, i, nums);
}
return ans;
}
void twoSum(int l, int r, int target, vector<int>& nums)
{
vector<int> tmp;
while(l<r)
{
if(nums[l] + nums[r] == -nums[target])
{
tmp.clear();
tmp.push_back(nums[target]);
tmp.push_back(nums[l]);
tmp.push_back(nums[r]);
ans.push_back(tmp);
while(l<r && nums[l+1] == nums[l])
l++;
while(l<r && nums[r-1] == nums[r])
r--;
l++;
r--;
}
else if(nums[l] + nums[r] < -nums[target])
l++;
else r--;
}
}
};