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;
    }
};