LeetCode解题记录(11~15)
11. 盛最多水的容器
给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器，且 n 的值至少为 2。
image
图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
示例:
输入: [1,8,6,2,5,4,8,3,7]
输出: 49
分析：根据图示，其实就是要求我们求两个下标之间的距离与下标对应的数值中较小一个的乘积的最大值。首先，我们可以用暴力法求解，从i=0开始，每一次计算i+1..n与i=0之间的乘积，保存最大值。
int maxArea(vector<int>& height) {
int area = 0;
int startIndex = 0;
while (startIndex < height.size() -1) {
for (int i = 1; i < height.size(); ++i) {
int cur = (i - startIndex) * (height[startIndex] < height[i] ? height[startIndex] : height[i]);
if (cur > area) {
area = cur;
}
}
startIndex++;
}
return area;
}
进阶：首先，我们假设有一个最优解，就是a[n]中以0为起点，n为终点，取baseArea = min[a[0],a[n]]*(n-0)。然后如果a[0]<a[n],则取a[1..n]，否则取a[0..n-1]，继续计算容器最大值area，与baseArea比较，令baseArea = max(area, baseArea)。
int maxArea(vector<int> & height) {
int l = 0;
int r = height.size() - 1;
int baseArea = (r-l) * min(height[l], height[r]);
while(l < r) {
if(height[l] < height[r]) {
l++;
} else {
r--;
}
baseArea = max(baseArea, (r-l)* min(height[l], height[r]));
}
return baseArea;
}
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 的范围内。
示例 1:
输入: 3
输出: "III"
示例 2:
输入: 4
输出: "IV"
示例 3:
输入: 9
输出: "IX"
示例 4:
输入: 58
输出: "LVIII"
解释: C = 100, L = 50, XXX = 30, III = 3.
示例 5:
输入: 1994
输出: "MCMXCIV"
解释: M = 1000, CM = 900, XC = 90, IV = 4.
分析：首先我们需要得到每一位数上的值，这里我们可以用num%10以及num/10来循环得到。然后判断该位属于个，十，百，千上的哪一位，这里我们使用一个基数m=1在循环时不断乘以10来计算位数。然后排除特殊情况下数字对应的字符串，同时要注意一个情况 数字<5和>5的时候的不同表示。
string intToRoman(int num) {
stack<string> S; // 栈LOFI的规则与我们循环的时候获取到的字符串匹配
int m = 1; // 数位
while (num > 0) {
int n = num % 10; // 当前数位上的数
n = n * m; // 与数位相乘得到具体的数字
m = m * 10; // 数位增加一位
num = num / 10; // 原数字减去一位
if (n == 0) continue; //如果得到的数为0 直接继续循环
switch (n) { // 开关选择
// 特殊情况 4，9，40，90，400，900的处理
case 4:
S.push("IV");
break;
case 9:
S.push("IX");
break;
case 40:
S.push("XL");
break;
case 90:
S.push("XC");
break;
case 400:
S.push("CD");
break;
case 900:
S.push("CM");
break;
default:
//一般情况下各个位置上数字的处理
if (n < 10) {
//分为<5 和 >5的情况
if (n < 5) {
for (int i = 0; i < n; ++i) {
S.push("I");
}
}else {
S.push("V");
for (int i = 0; i < n - 5; ++i) {
S.push("I");
}
}
}else if (n < 100) {
if (n < 50) {
for (int i = 0; i < n/10; ++i) {
S.push("X");
}
}else {
S.push("L");
for (int i = 0; i < n/10 - 5; ++i) {
S.push("X");
}
}
}else if (n < 1000) {
if (n < 500) {
for (int i = 0; i < n/100; ++i) {
S.push("C");
}
}else {
S.push("D");
for (int i = 0; i < n/100 - 5; ++i) {
S.push("C");
}
}
}else {
for (int i = 0; i < n/1000; ++i) {
S.push("M");
}
}
break;
}
}
string romanStr = "";
while(!S.empty()) {
romanStr += S.pop();
}
return romanStr;
}
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 的范围内。
示例 1:
输入: "III"
输出: 3
示例 2:
输入: "IV"
输出: 4
示例 3:
输入: "IX"
输出: 9
示例 4:
输入: "LVIII"
输出: 58
解释: C = 100, L = 50, XXX = 30, III = 3.
示例 5:
输入: "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.
分析：这个题正好和上一道题相反，在处理的时候，我们也需要对特殊情况进行处理，在特殊情况下，低位或者小的数字出现在高位或者大数的右边，这是需要用(高位-低位)或(大-小)，其他情况下我们只需要遍历字符串不断对字符串对应的数字相加即可。
int romanToInt(string s) {
int res = 0; //设置数据为0
for (int i = 0; i < s.size(); ++i) { // 遍历处理字符串
char c = s[i];
int n = getNumWithChar(c); // 获取字符对应的数值
//特殊情况的处理 当下一个字符代表的为高位或大于当前字符代表的数时，取负即可。
if (c == 'I' && (s[i+1] == 'V' || s[i+1] == 'X')) {
n = -n;
}
if (c == 'X' && (s[i+1] == 'L' || s[i+1] == 'C')) {
n = -n;
}
if (c == 'C' && (s[i+1] == 'M' || s[i+1] == 'D')) {
n = -n;
}
res += n;
}
return res;
}
int getNumWithChar(char c) {
switch(c) {
case 'I':
return 1;
case 'V':
return 5;
case 'X':
return 10;
case 'L':
return 50;
case 'C':
return 100;
case 'D':
return 500;
case 'M':
return 1000;
default:
return 0;
}
}
14. 最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1:
输入: ["flower","flow","flight"]
输出: "fl"
示例 2:
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
说明:
所有输入只包含小写字母 a-z 。
分析：首先，我们排除2中特殊情况数组位空时，直接返回“”，数组只有一个元素时返回这个元素即可。一般情况下，由于最长公共子串不可能超过数组中最短的元素，所以我们先找到最短的元素的长度，然后在这个长度之内取查找字符串相同的最小长度即为最长公共前缀
string longestCommonPrefix(vector<string>& strs) {
if(strs.empty()) return "";
if(strs.size() == 1) return strs[0];
string commonPrefix = ""; //初始化一个字符串保存前缀
int minLength = INT_MAX; //初始化最小长度为INT_MAX
for(int i = 0; i < strs.size(); ++i) { //获取最想长度
if (strs[i].length() < minLength) {
minLength = strs[i].length();
}
}
int n = 0; // 从第0号元素开始匹配
while(n < minLength) {
char c = strs[0][n];
if(isCommonChar(strs, c, n)) { //匹配是否成功
commonPrefix.push_back(c);
}else {
break;
}
++n;
}
return commonPrefix;
}
//判断当前元素是否是公共元素
bool isCommonChar(vector<string> strs, char c, int index) {
for(int i = 0; i < strs.size(); ++i) {
string s = strs[i];
if (s[index] != c) return false;
}
return true;
}
15. 三数之和
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
分析：根据题意，集合中不能出现重复的三元组，所以我们可以将数组先排序，这样方便我们排除掉相同的元素。然后取元素都后一个位置与数组最后一个元素为起始位置分别判断相加结果是否为0，根据结果与0比较从两头像中间逼急，取得所有结果为0的组合。
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res;
if (nums.size() < 3) return res; //数组元素不足3个，返回空。
sort(nums.begin(), nums.end()); // 排序数组
//遍历元素
for (int i = 0; i < nums.size() - 2; ++i) {
if(nums[i] > 0) break; //如果取得的元素大于0，难么元素右边的所有数都大于0，即不可能存在3元素和为0的情况，此时结束循环。
if (i == 0 || nums[i] > nums[i-1]) { //只有当i==0 或当前元素大于上一个元素是进入，排出重复的情况。
int j = i+1; // 左
int k = (int)nums.size() - 1; //右
while (j < k) {
if (nums[i] + nums[j] + nums[k] == 0) { // 和为0时满足，存入结果
vector<int> a = {nums[i], nums[j], nums[k]};
res.push_back(a);
//左右向中间逼近
++j;
--k;
//排除掉重复的元素
while (j < k && nums[j] == nums[j-1]) {
++j;
}
while (j < k && nums[k] == nums[k+1]) {
++k;
}
}else if (nums[i] + nums[j] + nums[k] < 0) { // 小于0时，说明左边的元素太小，向右靠近
++j;
}else { // 右边元素太大，向左靠近
--k;
}
}
}
}
return res;
