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 1V 5X 10L 50C 100D 500M 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 1V 5X 10L 50C 100D 500M 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; };备注
十五题总结：
遇到去重的时候，如果不是在算法解决的时候就曾经思考去重了，就尽量放在循环里面，升高工夫复杂度。没有思路的时候思考排序加多指针。