算法标签：贪心、数组、双指针
假设有一个二维的平面，这个二维平面的每一个整点坐标上有一根竖线，从中挑两条竖线，两条竖线会形成一个凹槽，往凹槽里面倒水，题目要求选择哪两条竖线可以使得倒水的总面积最大
输入的是一个数组，下标是横坐标，数组的值就是它的高度，题目给出了很多柱子的位置和高度，问怎么选可以使得总面积最大？
两个指针分别指向开头和结尾两侧，每次比较这两个指针指向的柱子的高度，如果第二个指针指向的高度比较低的话，就把第二个指针往前移动一位，如果第一个指针指向的高度比较低的话，就把第一个指针往后移动一位
样例中，发现第一个指针指向的高度比较低，就把 1 往中间移动一格
每移动一次，求当前两个指针指向的高度所组成的面积是多少(两个指针高度比较低的那个 × 它们之间的距离)，然后更新一下最大值就可以了
证明如下：
假设最优解是下面两个柱子，最一开始两个指针在最优解的两侧，每次把一个指针往中间靠拢，这两个指针必然会有一个指针先到最优解的某一边，要么是左边先到、要么是右边先到
假设左边先到，左边到达最优解的柱子的时候，此时右边还没有到最优解的位置，还在离最优解比较远的位置上，如果左边先到达最优解的边界的话，证明右边一定会向左边不断靠拢(右边指向的竖线高度每次一定严格小于左边的最优解的竖线)，移动到最优解的位置
这样就可以证明这个做法一定可以找到最优解，两个指针的最大值就是最优解（对于任意一个最优解，只要有一边到达边界，另外一边一定会向这个边界不断靠拢）
反证法
假设左边先到达最优解的边界，假设右边高度 ≥ 左边最优解的高度，那么它们能够倒水的区域就是下面这个红色的矩形
实际最优解是蓝色部分区域，右边高度 ≥ 左边最优解的高度，面积一定是大于最优解的面积的，就与 最优解是蓝色部分区域 产生矛盾
所以得出结论：只要左边先到达最优解的位置，右边的高度必然是严格小于左边界的，意味着右边的指针一定会往左边走，直到走到最优解的位置为止
时间复杂度为 O( n )
class Solution {
public:
int maxArea(vector& 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]) j--;
//否则把左边往右移动一格
else i++;
}
return res;
}
};
整数转罗马数字
算法标签：哈希表、数学、字符串
给出了罗马数字的表示方式，给出一个整数，返回一个字符串形式的罗马数字表示
一般是左边大，右边小，如果左边小，右边大的话表示减法
IV 表示 5 - 1 = 4
模拟过程，罗马数字是一位一位表示的，从千位开始看，先表示千位再表示百位、十位、个位，罗马数字的每一位可能不止一个字母，阿拉伯数字每一位就只有一个数字
当我们想表示某一个数字的时候，查表，找对应的字符串是什么，从高位到低位开始拼接，先拼接高位再拼接次高位. . .
技巧：
千位
只要大于等于一千，就一直减，每减一个一千，就把它换成 M
百位
规律：100 - 300，有几个 100 就减几个 C，600 - 800，除了 D 之外，有几个 100 就加几个 C
其余没有规律需要单独记录下来：900、500、400、100
怎么实现比较方便？同时可以让我们把它对应起来？
输入 100 返回 C，输入 200 返回 CC，输入 600 返回 DC，输入 900 返回 CM
从大到小去考虑这些项（900、500、400、100）
只要大于等于 900 就把它对应成 CM，只要大于等于 500 就把它对应成 D，然后减去 500，只要大于等于400，就减去 400，再加一个 C，只要大于等于 100，就减去 100，再加上一个 C
对于十位和个位也是类似的
模拟样例
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;
//一共13个数
for(int i = 0;i < 13;i++ ) {
//当前数值更大
while(num >= values[i]) {
num -= values[i];
res += reps[i];
}
}
return res;
}
};
罗马数字转整数
算法标签：哈希表、数学、字符串
给出一个罗马数字，把它转换成阿拉伯数字
看一下每一个字母在阿拉伯数字中表示的数值是多少，可以发现，除了绿色框起来的数之外，对于其他的数，把它的每一个字符转换成对应的数字，相加就是表示的总数
如果前一个字母的数值比后一个字母的数值小的话，应该要减去前面的字母的数值
特判当前字母的值是不是比后面字母的值要小，如果比后面字母要小的话，就减去它的值，反之，就加上它的值
开一个哈希表把一个字母映射成一个数字
class Solution {
public:
int romanToInt(string s) {
//从个位开始
unordered_map 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;
}
};
最长公共前缀
算法标签：字符串、枚举
编写一个函数来查找字符串数组（所有字符串）中的最长公共前缀
前缀：前面若干个连续的字符
a 是前缀，ab 是前缀，abc 也是前缀
公共前缀：这个前缀是所有字符串的前缀
abc 是第一个字符串的前缀，也是第二个字符串的前缀
最长公共前缀：所有公共前缀里面最长的一个
由于会输入所有的字符串，时间复杂度至少是所有字符串的长度之和
先看每一个字符串的第一个字符是不是一样，如果第一个字符不一样，那么它们的公共前缀是空的，如果第一个字符一样，说明最长公共前缀最少长度是 1，再看每一个字符串的第二个字符是不是一样，不断试探. . .试探到第四个字符的时候，发现不全一样，说明最大公共前缀就是 3，最坏情况下会把所有字符串的每一个字符枚举一遍，时间复杂度小于等于所有字符串长度之和
前缀 / 子串不是子序列，下标一定要连续
两重循环，第一重循环枚举当前枚举的是第几个字符，第二重循环枚举所有字符串，看一下所有字符串的这个字符是不是一样的
class Solution {
public:
string longestCommonPrefix(vector& strs) {
//定义答案
string res;
//输入为空 直接返回
if(strs.empty()) return res;
//从前往后枚举最长公共前缀的长度
for(int i = 0;;i ++ ) {
//如果 i 大于等于第一个字符串的长度 说明第一个字符串中不存在第 i 个字母 直接返回
if(i >= strs[0].size()) return res;
//把第一个字符串的第 i 个字母拿出来
char c = strs[0][i];
//依次判断所有字符串的第 i 个字符是否和这个字符相同 必须加& 否则每次会复制一遍整个数组 时间复杂度变成平方级别
for(auto& str : strs)
//如果某个字符串长度小于第一个字符串的长度或者第 i 个字符不同
if(str.size() <= i || str[i] != c)
return res;
//第 i 个字符相同 前缀里面加上第 i 个字符
res += c;
}
return res;
}
};
三数之和
算法标签：数组、双指针、排序
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a、b、c 使得它们的和为 0，注意是三个元素，a、b、c 不能是同一个元素，但是它们的数值可以一样
找出所有和为 0 且不重复的三元组，注意 1、2、3 和 3、2、1 算同一个三元组
最优做法：双指针
次优做法：哈希表，时间复杂度和双指针一样，但是哈希表会额外用到一些空间
首先不考虑可能有重复的问题
双指针做法一定要有序，先将整个数组排序，排序后，先去枚举第一个数的位置，为了避免重复，要求第一个指针指向的数是最小的，三个指针 i < j < k，这样就会减少一些重复的情况，当 i 固定之后，j 和 k 就可以用双指针了
暴力做法：假设 j 的位置如下，要找到一个最小的 k，使得 nums[ j ] + nums[ k ] + nuns[ i ] ≥ 0（不能用 = 作为单调性，要保证 k 一直存在）
对于每一个 j 都会找到一个对应的 k，两重循环枚举 j、k 找最小值，时间复杂度 O( n^2 )
如果用双指针，时间复杂度为 O( n )
由于整个序列是有序的，i 是固定的，当 j 往后移动的时候，意味着 nums[ j ] 是变大的，要求 nums[ j ] + nums[ k ] + nums[ i ] ≥ 0，而且要找到一个最小的 k，nums[ k ] 一定是变小的，j 越大，k 越小
如果 j 从当前位置走到 j '，那么 k 一定 k 的基础上往左走，走到 k '，k 右边的值就不用枚举了
基于以上的思想，虽然两个指针还是两个独立的变量，但是 j 只会递增，k 只会递减，所以 j 最多只会枚举 n 个数，k 最多只会枚举 n 个数，一共会枚举 2n 个数，把 O( n^2 ) 的时间复杂度优化成 O( 2n )
证明：当 k 变大的时候，k 一定是变小的
反证法，当 j 变大之后，k 有没有可能也变得比较大呢？
由于 j ' 在 j 右边，nums[ j ' ] > nums[ j ]，假设 nums[ j ' ] 对应最小的 k ' 在 k 右边， nums[ j ' ] + nums[ k ] + nums[ i ] ≥ 0，nums[ j ' ] + nums[ k ' ] + nums[ i ] ≥ 0，就与 要找到一个最小的 k 产生矛盾，所以 j ' 对应的 k 只能在 k 左边，不能比 k 更大，最终整个算法的时间复杂度是 O( n^2 )
双指针算法、位运算、离散化、区间合并_小雪菜本菜的博客-CSDN博客
要求不能有重复的
下面这个例子在枚举的时候会枚举很多重复的，需要把重复的元素去掉
在枚举 i 的时候，当前 i 在第一个位置，当 i 移动到下一个位置的时候，发现下一个位置的值和上一个位置的值一样，实际上这个值在上一个位置已经被枚举过了，所以下一个位置的情况不能考虑
只要判断当前这个数是不是和上一个数一样，如果一样就跳过，就可以避免重复的方案
注意：j 和 k 也需要判重，k 完全由 j 和 k 决定，不需要考虑重复
while( j < k - 1 && nums[ i ] + nums[ j ] + nums[ k - 1 ] >= 0)
检查 k 下一个要去的点是否满足nums[ i ] + nums[ j ] + nums[k - 1] ≥ 目标值，如果满足，说明此时的 k 还可以更小。如果不满足了，此时的 k 跳出 while 循环，这时候的 k 就一定是使得nums[ i ] + nums[ j ] + nums[ k - 1 ] ≥ 目标值情况下，能取到的最左边的 k。
class Solution {
public:
vector> threeSum(vector& nums) {
//定义答案数组
vector> res;
//排序
sort(nums.begin(),nums.end());
//枚举三个指针 i < j < k
for(int i = 0;i < nums.size();i++ ) {
//如果 i 大于 0 并且 nums[i] 等于上一个数 去除重复方案
if(i && nums[i] == nums[i - 1]) continue;
for(int j = i + 1,k = nums.size() - 1;j < k;j++ ) {
//j 不是第 1 个数 并且 nums[j] 等于上一个数 跳过
if(j > i + 1 && nums[j] == nums[j - 1]) continue;
//找三个数相加大于等于 0 的最小的 k
//下一个数 k - 1 和 j 不能重叠 每次试探下一个数是否满足 如果满足就用下一个数
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;
}
}; 
