11. 盛最多水的容器

给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器，且 n 的值至少为 2。

图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

输入：[1,8,6,2,5,4,8,3,7]
输出：49

暴力枚举

class Solution {
public:
    int maxArea(vector<int>& height) {
       int res=0;
       int n=height.size();
       for(int i=0;i<n;i++){
           for(int j=i+1;j<n;j++)
            res=max(res,min(height[i],height[j])*(j-i));
       }
       return res;
    }
};

贪心

算法描述 
双指针 ij分别指向头尾 先计算此时的面积 去更新res 
然后比较height[i]和height[j] 将小的一个指针向内移动直到指针重合

时间复杂度O(N) 一次遍历整个数组

算法正确性说明
假设最优解的位置是 x和y 那么两个指针ij肯定有一个先到最优解的位置 假设i先到了x 那么j会一直往中间靠拢直到到达y处
原因:因为j此时的位置y1到y的这一段 都是比height[x]下的 所以j会一直-- ,这里可以采用反证法 若是j从y1移动到y的过程中 有出现height[y1]>height[x]的那么显然此时的面积肯定大于最优解 显然与假设矛盾了

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

贪心(优化)

class Solution {
public:
    int maxArea(vector<int>& height) {
        int res=0;
        int i=0,j=height.size()-1;
        while(i<j){
            int h=min(height[i],height[j]);
            res=max(res,h*(j-i));
            while(i<j && height[i]<=h) i++;
            while(i<j && height[j]<=h) j--;
        }
        return res;
    }
};

12. 整数转罗马数字

罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给定一个整数，将其转为罗马数字。输入确保在 1 到 3999 的范围内

输入: 3
输出: “III”

输入: 1994
输出: “MCMXCIV”
解释: M = 1000, CM = 900, XC = 90, IV = 4.

模拟

class Solution {
public:
    string intToRoman(int num) {
        int nums[] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        string romans[] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        string  res;
        for(int i=0;i<13;i++){
            while(num>=nums[i]){
                res+=romans[i];
                num-=nums[i];
            }
        }
        return res;
    }
};

13. 罗马数字转整数

罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。

输入: “III”
输出: 3

输入: “MCMXCIV”
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.

模拟

分析 判断一下当前是+数值还是-数值就好了 因为减的时候特征很明显 就是当前字符对应的数字小于下一个字符对应的数字的时候

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

14. 最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 “”。

输入: [“flower”,“flow”,“flight”]
输出: “fl”

算法描述：以第一个字符串为基础 分别将他的所有字符与剩下的字符做比较 满足就加上 不满足就直接返回

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(i>=str.size() || str[i]!=c) return res;
            }
            res+=c;
        }
        return res;
    }
};

15. 三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。

给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]

二分

算法描述  先对数组排序 然后三个指针i j k i固定 j和k就是双指针的做法
		这里就直接i<j<k了 即当i固定之后 j和k双指针扫描i之后的元素就能得到结果
一些原因：i<j<k而不是i固定 j k枚举所有元素：因为当存在nums[i]+nums[j]+nums[k]=0的时候 i固定了 i和k要不就是在i的两侧 要不就是都在i的右侧 针对在i两侧的情况 假设是j1 i1 k1 （j<i<j） 那么这种情况显然在i=j1的时候得到过了 所以不抛弃了，即jk在i右侧的情况是我们需要的		
		while(j<k-1 && nums[i]+nums[j]+nums[k]>0) k--;j<k-1是为了防止k--之后导致jk相同

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