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