leetcode究极刷题笔记（11~15）
（11）盛最多水的容器（中等）
实现思路：
定义两个指针（a,b），分别指向数组的前后位置，如果此时a的值小于b的话，就将a右移一位，如果此时b指向的值小于a的话，就将b向左边移动一位。
具体实现代码如下：
class Solution {
public:
int maxArea(vector<int>& height) {
int res=0;
for(int i=0,j=height.size()-1;i<j;)
{
res=max(res,min(height[i],height[j])*(j-i));
if(height[i]<height[j]) i++;
else j--;
}
return res;
}
};(12)整数转化罗马数字（中等）
实现思路：
此题就是一个模拟实现，我们将对应的每一种特殊情况拿出来进行对比参照，将数字以此减少并加上对应的罗马数字即可解决本题
具体代码如下：
class Solution {
public:
string intToRoman(int num) {
int values[]={
1000,
900,500,400,100,
90,50,40,10,
9,5,4,1
};
string reps[]={
"M",
"CM","D","CD","C",
"XC","L","XL","X",
"IX","V","IV","I"
};
string res;
for(int i=0;i<=12;i++)
{
while(num>=values[i])
{
num-=values[i];
res+=reps[i];
}
}
return res;
}
};（13）罗马数字转整数（简单）
实现思路：
与上题类似，具体看代码即可
代码实现如下：
class Solution {
public:
int romanToInt(string s) {
unordered_map<char,int> count;
count['I']=1,count['V']=5;
count['X']=10,count['L']=50;
count['C']=100,count['D']=500;
count['M']=1000;
int res=0;
for(int i=0;i<s.size();i++)
{
if(i+1<s.size() && count[s[i]]<count[s[i+1]])
{
res-=count[s[i]];
}
else
{
res+=count[s[i]];
}
}
return res;
}
};（14）最长公共前缀（简单）
实现思路：
本题实现比较简单，具体看代码即可。
代码实现如下：
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
string res;
if(strs.empty()) return res;
for(int i=0;;i++)
{
if(i>=strs[0].size()) return res;//对应的就是最后的结束条件
char c=strs[0][i];
for(auto& str:strs)
{
if(str.size()<=i || str[i]!=c)
{
return res;
}
}
res+=c;
}
return res;
}
};（15）三数之和（中等）
实现思路：
主要的思路就是利用双指针算法，首先我们先排序，因为有序是双指针算法的必要条件，之后我们定义三个指针，确定其中一个i，然后让j与k进行遍历查找三者和为0的组合，如果此时i，j，k各自前后互相相同的话，直接跳过即可。
具体实现代码如下：
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(),nums.end());
vector<vector<int>> res;
for(int i=0;i<nums.size();i++)
{
if(i && nums[i]==nums[i-1])continue;//continue函数的意思就是下面的带啊吗不进行，但是整体的循环并未停止，相当于循环了一次但是不做任何事
for(int j=i+1,k=nums.size()-1;j<k;j++)
{
if(j>i+1 && nums[j]==nums[j-1]) continue;
while(j<k-1 && nums[i]+nums[j]+nums[k-1]>=0) k--;
if(nums[i]+nums[j]+nums[k]==0)
{
res.push_back({nums[i],nums[j],nums[k]});
}
}
}
return res;
}
};