共计 4657 个字符，预计需要花费 12 分钟才能阅读完成。
11. 盛最多水的容器
给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai)。在坐标内画 n 条垂直线，垂直线 i 的两个端点别离为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴独特形成的容器能够包容最多的水。
阐明：你不能歪斜容器。
示例 1：
输出：[1,8,6,2,5,4,8,3,7]
输入：49
解释：图中垂直线代表输出数组 [1,8,6,2,5,4,8,3,7]。在此状况下，容器可能包容水（示意为蓝色局部）的最大值为 49。提醒：
n = height.length
2 <= n <= 3 * 104
0 <= height[i] <= 3 * 104
My Answer:
/**
* @param {number[]} height
* @return {number}
*/
/**
最大值不仅与高无关，还与宽有关系（即横坐标差），因而在找值最大的两个点时，还应思考让横坐标差最大。用两个指针 left 和 right 别离记录两个端点的坐标，left 从左向右挪动，right 从右向左挪动，当 left 所指向的点的高 小于 right 所指向的点的高 时：left 向右挪动，否则，right 向右挪动。*/
var maxArea = function(height) {
let left=0;
let right=height.length-1;
let maxValue=0;
while(left<right){if(((right-left)*(height[left]>height[right]?height[right]:height[left]))>maxValue){maxValue=(right-left)*(height[left]>height[right]?height[right]:height[left])
}
if(height[left]<height[right]){left++;}
else{right--;}
}
return maxValue;
};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:
输出: num = 1994
输入: “MCMXCIV”
解释: M = 1000, CM = 900, XC = 90, IV = 4.提醒：
1 <= num <= 3999
My Answer:
/**
* @param {number} num
* @return {string}
*/
/**
依据数字和罗马字符转换规则转化为罗马字符，对非凡数字进行替换
*/
var intToRoman = function(num) {
let res='';
// 转换为罗马字符
while(num>=1000){
res+='M';
num-=1000;
}
while(num>=500){
res+='D';
num-=500;
}
while(num>=100){
res+='C';
num-=100;
}
while(num>=50){
res+='L';
num-=50;
}
while(num>=10){
res+='X';
num-=10;
}
while(num>=5){
res+='V';
num-=5;
}
while(num>=1){
res+='I';
num-=1;
}
// 对非凡数字进行替换
res=res.replace(/DCCCC/g,'CM');
res=res.replace(/CCCC/g,'CD');
res=res.replace(/LXXXX/g,'XC');
res=res.replace(/XXXX/g,'XL');
res=res.replace(/VIIII/g,'IX');
res=res.replace(/IIII/g,'IV');
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 的范畴内。
示例 1:
输出: “MCMXCIV”
输入: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.提醒：
1 <= s.length <= 15
s 仅含字符 (‘I’, ‘V’, ‘X’, ‘L’, ‘C’, ‘D’, ‘M’)
题目数据保障 s 是一个无效的罗马数字，且示意整数在范畴 [1, 3999] 内
题目所给测试用例皆合乎罗马数字书写规定，不会呈现跨位等状况。
IL 和 IM 这样的例子并不合乎题目要求，49 应该写作 XLIX，999 应该写作 CMXCIX。
对于罗马数字的详尽书写规定，能够参考 罗马数字 – Mathematics。
My Answer:
/**
* @param {string} s
* @return {number}
*/
/**
对非凡数字进行替换，依据罗马字符转和数字换规定转化为数字，*/
var romanToInt = function(s) {
let res=0;
// 对非凡数字进行替换
s=s.replace(/CM/g,'DCCCC');
s=s.replace(/CD/g,'CCCC');
s=s.replace(/XC/g,'LXXXX');
s=s.replace(/XL/g,'XXXX');
s=s.replace(/IX/g,'VIIII');
s=s.replace(/IV/g,'IIII');
let arr=s.split('');
// 转换为数字
while(arr[0]==='M'){
res+=1000;
arr.shift();}
while(arr[0]==='D'){
res+=500;
arr.shift();}
while(arr[0]==='C'){
res+=100;
arr.shift();}
while(arr[0]==='L'){
res+=50;
arr.shift();}
while(arr[0]==='X'){
res+=10;
arr.shift();}
while(arr[0]==='V'){
res+=5;
arr.shift();}
while(arr[0]==='I'){
res+=1;
arr.shift();}
return res;
};14. 最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 “”。
示例 1：
输出：strs = [“flower”,”flow”,”flight”]
输入：”fl”
示例 2：
输出：strs = [“dog”,”racecar”,”car”]
输入：””
解释：输出不存在公共前缀。提醒：
0 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] 仅由小写英文字母组成
My Answer:
/**
* @param {string[]} strs
* @return {string}
*/
/**
顺次判断数组每个元素的第 0，1，2... 个字母是否雷同，不同则从 0 截取到不同字母的下标。*/
var longestCommonPrefix = function(strs) {
// 判断数组长度
if(strs.length<1){return '';}
let prefix=strs[0];
if(prefix===''){return '';}
// 找出最长公共前缀
for(let i=1;i<strs.length;i++){
let k=0;
while(prefix[k]===strs[i][k]&& k<prefix.length){k++;}
prefix=prefix.slice(0,k);
if(k===0){break;}
}
return prefix;
};15. 三数之和
给你一个蕴含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c，使得 a + b + c = 0？请你找出所有和为 0 且不反复的三元组。
留神：答案中不能够蕴含反复的三元组。
示例 1：
输出：nums = [-1,0,1,2,-1,-4]
输入：[[-1,-1,2],[-1,0,1]]
示例 2：输出：nums = []
输入：[]示例 3：
输出：nums = [0]
输入：[]提醒：
0 <= nums.length <= 3000
-105 <= nums[i] <= 105
My Answer:
/**
* @param {number[]} nums
* @return {number[][]}
*/
/**
暴力解法会超时！！思路：1. 将 nums 数组先升序排序，2. 三个数的挪动办法：第一个数从数组 0 开始移到最初一个，如果大大于 0 则完结
第二个数从（第一个数的下标 +1）开始向右挪动
第三个数从最初一个地位开始向左挪动
判断三个数相加是否等于 0，等于则退出
3. 去重办法：为防止反复的三元组呈现，当三个数相加等于 0 之后，须要判断第一个数前面的数字，第二个数前面的数字，第三个数后面是否等于自身，是的话则跳过
*/
var threeSum = function(nums) {let res = [];
// 判断输出是否非法
if (nums.length < 3) {return res;}
// 排序
nums.sort((a, b) => (a - b));
for (let i = 0; i < nums.length; i++) {
// 去重
if (nums[i] === nums[i - 1]) {continue;}
// 不满足条件
if (nums[i] > 0) {break;}
let left = i + 1;
let right = nums.length - 1;
while (left < right) {if (nums[i] + nums[left] + nums[right] === 0) {let t = [];
t.push(nums[i], nums[left], nums[right]);
res.push(t);
// 去重
while (nums[left] === nums[left + 1]) {left++;}
while (nums[right] === nums[right - 1]) {right--;}
left++;
}
else if (nums[i] + nums[left] + nums[right] > 0) {right--;}
else {left++;}
}
}
return res;
};备注
十五题总结：
遇到去重的时候，如果不是在算法解决的时候就曾经思考去重了，就尽量放在循环里面，升高工夫复杂度。没有思路的时候思考排序加多指针。
