leetCode进阶算法题+解析（二）
字符串转换整数
题目：请你来实现一个 atoi 函数，使其能将字符串转换成整数。首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。在任何情况下，若函数不能进行有效的转换时，请返回 0。说明：假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。
示例 1:
输入: "42"
输出: 42
示例 2:
输入: " -42"
输出: -42
解释: 第一个非空白字符为 '-', 它是一个负号。
我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。
示例 3:
输入: "4193 with words"
输出: 4193
解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。
示例 4:
输入: "words and 987"
输出: 0
解释: 第一个非空字符是 'w', 但它不是数字或正、负号。
因此无法执行有效的转换。
示例 5:
输入: "-91283472332"
输出: -2147483648
解释: 数字 "-91283472332" 超过 32 位有符号整数范围。
因此返回 INT_MIN (−231) 。
思路：这个题的叙述文字很多啊，多的我都觉得是不是我看漏什么了。单纯的说这道题感觉应该不难，首先第一个字符是字母则返回0.第一个字符是+-则用一个boolean判断这个数是正是负。然后接下来的数字超过整数最大值则返回int最小值。差不多就是这个逻辑，我去实现看看。
面向测试案例编程。。。一次次尝试补漏，一点点改动终于是改完了，性能超过了百分之九十九。我直接贴代码：
class Solution {
public int myAtoi(String str) {
long res = 0;
boolean flag = true;
int f = -1;
char[] c = str.toCharArray();
for(int i = 0; i<c.length;i++) {
if(f==-1 && (c[i]=='-' || c[i]=='+') ) {
flag = c[i]=='-'?false:true;
f = 1;
}else if(Character.isDigit(c[i])) {
res = res*10 + (c[i]-'0');
if(res>Integer.MAX_VALUE){
if(!flag) return Integer.MIN_VALUE;
return Integer.MAX_VALUE;
}
f = 1;
}else if(c[i]>30 ){
if(f==-1 && c[i]==' ') continue;
break;
}
}
return flag == true?(int)res:(int)-res;
}
}
首先这个一开始我想到可能溢出所以直接用long保存的，但是万万没想到long也能溢出，所以改成了每次追加都要判断，int溢出了直接返回。
其次测试案例+-1这种，一开始我也没想到，所以在没数字之前的+-正常判断的，所以添加了f表示第一个正负号已经搞定。反正都是小问题，一点点补漏就行了。感觉这道题对不起中等难度，下一题了。
盛最多水的容器
题目：给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。说明：你不能倾斜容器，且 n 的值至少为 2。
题目截图
思路：暂时没啥思路啊，就是生算呗。。。我打算先暴力法试试水。就是第一个跟后面每一个试试，第二个跟后面每一个试试，，以此类推，不超时肯定是稳了，，超时再说超时的。我去撸代码了。
咳咳，喜大普奔，暴力法通过了， 但是遗憾的是将将通过，性能排行二十多。。我先贴上代码，再想想不暴力要怎么做：
class Solution {
public int maxArea(int[] height) {
int res = 0;
for(int i = 0;i<height.length-1;i++){
for(int j = i+1;j<height.length;j++){
int l = Math.min(height[i],height[j]);
res = Math.max(l*(j-i),res);
}
}
return res;
}
}
其实换个思路，不用全遍历，因为在给定值后面的，最高值前面的那些都不用计算，毕竟没最高值长，也没最高值高，不可能比最高值大，但是要怎么写呢？还有当前值*最后值的长度也没当前面积大的页不用考虑了。其实优化点还很多，我一点点看看怎么写。
改了一点点，但是还没到达想要的目标。 尽我所能一点点调试才到百分之三十八。估计不换思路也就这样了，附上改良版代码：
class Solution {
public int maxArea(int[] height) {
int res = 0;
int max = height[0];
int len = height.length;
for(int i = 0;i<len-1;i++){
if(height[i]*(len-i)<res || height[i]<max) continue;
max = height[i];
for(int j = i+1;j<len;j++){
int l = Math.min(height[i],height[j]);
res = Math.max(l*(j-i),res);
}
}
return res;
}
}
性能改良过程
我还是直接看性能排行第一的代码吧。
好了，看完了并且分析完了，而且自己用自己的方式写完了，先说一下大概思路：双指针，首先第一步第一个和最后一个的面积。然后两个指针一点点往中间走，如果遇到比边上的还要短的直接继续往下，因为长度已经在缩短了，如果长度还要短就没啥可比性了，接下来贴代码：
class Solution {
public int maxArea(int[] height) {
int res = 0;
int l = 0;
int r = height.length-1;
while(l<r){
int left = height[l];
int right = height[r];
int n = Math.min(left,right);
res = Math.max(res,n*(r-l));
//前面的短挪前面的
if(left<=right){
l++;
while(left>height[l] && l<height.length){
l++;
}
}else{//后面的短挪后面的
r--;
while(right>height[r] && r>=0){
r--;
}
}
}
return res;
}
}
其实这个厉害的是思路，我在做的时候就若有若无的有点小思路，但是没有坚持完善成代码。急功近利的锅，虽然有可能坚持也想不到这样。反正又学到了一招。
感觉现在刷题每道题都能学到东西，挺好的。下一题吧。
整数转罗马数字
题目：罗马数字包含以下七种字符： 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"
解释: L = 50, V = 5, III = 3.
示例 5:
输入: 1994
输出: "MCMXCIV"
解释: M = 1000, CM = 900, XC = 90, IV = 4.
思路：这个题做过类似的，我记得当时是罗马数字转整数，是个简单的题目。这个就是反过来，我记得麻烦是很麻烦，但是并不难。因为题目范围是1-3999之间，我完全可以钻空子，（顺便说一下，前几天做的两个非0数和的那个也是钻了这个空子，其实我自己感觉也不太好，毕竟取值范围扩大了就逻辑啥的都要重新写，但是不得不说好用啊~）直接判断数的大小然后去写。我去实现啦。
好的，今天的第一道一次及格的题目。就是生生写了好几十行判断的，我直接贴出来：
class Solution {
public String intToRoman(int num) {
StringBuffer sb = new StringBuffer();
while(num>=1000){
sb.append("M");
num -= 1000;
}
if(num>=900){
sb.append("CM");
num -= 900;
}
if(num>=500){
sb.append("D");
num -= 500;
}
if(num>=400){
sb.append("CD");
num -= 400;
}
while(num>=100){
sb.append("C");
num -= 100;
}
if(num>=90){
sb.append("XC");
num -= 90;
}
if(num>=50){
sb.append("L");
num -= 50;
}
if(num>=40){
sb.append("XL");
num -= 40;
}
while(num>=10){
sb.append("X");
num -= 10;
}
if(num>=9){
sb.append("IX");
num -= 9;
}
if(num>=5){
sb.append("V");
num -= 5;
}
if(num>=4){
sb.append("IV");
num -= 4;
}
while(num>=1){
sb.append("I");
num -= 1;
}
return sb.toString();
}
}
然后挺开心的，而且我看了下，已经给定的罗马字也没啥数组扩大的情况。比如超过5千题目上也没有啊。而且改动只要在最开始添加几个判断就行了，反正对自己挺满意。
接下来去看看排行第一的代码：
看了排行第一的代码，其实就是把我这个整合到一个循环里，而且用了两个数组来让数字和值对应上，不难，挺简单的，我贴出来分享下然后下一题了：
class Solution {
public String intToRoman(int num) {
int[] nums = {1,4,5,9,10,40,50,90,100,400,500,900,1000};
String[] roma = {"I","IV","V","IX","X","XL","L","XC","C","CD","D","CM","M"};
StringBuilder sb = new StringBuilder();
int i = nums.length-1;
while(i>=0) {
if (num >=nums[i]) {
sb.append(roma[i]);
num = num-nums[i];
}
else i--;
}
return sb.toString();
}
}
三数之和
题目：给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。注意：答案中不可以包含重复的三元组。
示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
思路：目前刚刚审完题，思路是三次循环，第一层i=0开始，第二层j=i+1开始，第三层k=j+1开始，如果i+j+k等于0就add进结果集。暂时就这个想法，不知道超时不，我去实现了。
感觉三重循环这个死在了不能有重复的三元组，所以换个思路，还是别暴力法了，想想什么技巧可言解决这个问题。
额， 我又想到了数组下标代替数字。因为这个是有正有负的，所以目前打算是两个数组，一个正一个负。然后负的两个相加如果正的这个值是有的，则是一对。反之没有继续往下。毕竟abc相加等于0除了三个000必然有正有负。就是不知道这个题abc的范围是多少。但是我觉得思路是没问题的，我去试试。
很好，又超时了！！！最后的数字大于数百万。。313个测试案例过了311个，最后两个卡主了。我也很无奈啊。。继续想怎么处理吧。
或者放在set中，判断是否有这个值？然后重复的元素单独处理、我再去试试。
好的吧，这个题我绝望了，做了一下午两个多小时，超时两次，剩下各种bug，直接看了题解的思路，居然回归到一开始的循环，只不过处理的优雅了点，变成了两层循环，并且用sort排序处理重复的三元组。。我去试着根据理解写代码了。
写是写出来了，然后性能依旧可怜，我不知道是不是因为我自己写list的原因，一会再调整，我先贴代码:
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
Arrays.sort(nums);
//当第i个元素大于0说明已经不可能凑成三元组了
//所以这里一定是主动break，无所谓i的范围
for(int i = 0;i<nums.length;i++) {
if(nums[i]>0) break;
//第一个正常算，第二个开始直接continue
if(i>0 && nums[i]==nums[i-1]) continue;
int l = i+1;//第二个元素
int r = nums.length-1;//第三个元素
//这里用了双指针，不断往中间计算，省去了两次循环
while(l<r) {
int sum = nums[i] + nums[l] + nums[r];
if(sum==0) {//正好是结果，存入结果集
res.add(getList(nums[i], nums[l], nums[r]));
while(l<r && nums[l]==nums[l+1]) l++;
while(r>l && nums[r]==nums[r-1]) r--;
//注意这里是除了while还要加加减减，因为不相等的时候都不进while
l++;
r--;
}else if (sum>0) {//大于0说明右边的大了，往左移指针
r--;
}else {//小于0说明左边的小了，往右移指针
l++;
}
}
}
return res;
}
public List<Integer> getList(int i,int j,int k){
List<Integer> list = new ArrayList<Integer>();
list.add(i);
list.add(j);
list.add(k);
return list;
}
}
因为这个题我思路也不是很清楚，所以都是一点点写代码的。感觉写的挺全了。接下来我去试着优化下了。
把这个新添加list改成数组转list的形式，时间超过百分之九十二的人了。而且可能这种时间长的速度不稳定。提交几次几次不同的结果，但是因为最好的成绩超过百分之九十二，所以我这道题就这样了，贴上最后版的代码：
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
Arrays.sort(nums);
//当第i个元素大于0说明已经不可能凑成三元组了
//所以这里一定是主动break，无所谓i的范围
for(int i = 0;i<nums.length;i++) {
if(nums[i]>0) break;
//第一个正常算，第二个开始直接continue
if(i>0 && nums[i]==nums[i-1]) continue;
int l = i+1;//第二个元素
int r = nums.length-1;//第三个元素
//这里用了双指针，不断往中间计算，省去了两次循环
while(l<r) {
int sum = nums[i] + nums[l] + nums[r];
if(sum==0) {//正好是结果，存入结果集
res.add(Arrays.asList(nums[i],nums[l],nums[r]));
while(l<r && nums[l]==nums[l+1]) l++;
while(r>l && nums[r]==nums[r-1]) r--;
//注意这里是除了while还要加加减减，因为不相等的时候都不进while
l++;
r--;
}else if (sum>0) {//大于0说明右边的大了，往左移指针
r--;
}else {//小于0说明左边的小了，往右移指针
l++;
}
}
}
return res;
}
}
最接近的三数之和
题目：给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).
思路：这个题目如此简洁。。。啧啧啧。其次上道题是三数之和，这道题是最接近的三数之和。有区别，但是又好像是有联系。我不知道能不能用上道题的思路来解，但是起码要试试。我去试试。
我不知道要怎么说，结果这道题很稳，借鉴上一道题的思路。一次过了，但是性能就不是那么好，只超过了百分之八十五的人！算了，我先贴出第一版代码：
clclass Solution {
public int threeSumClosest(int[] nums, int target) {
int res = Integer.MAX_VALUE;
boolean flag = true;
Arrays.sort(nums);
for(int i = 0;i<nums.length-2;i++){
int l = i+1;
int r = nums.length-1;
while(l<r){
int sum = nums[i]+nums[l]+nums[r];
//结果大了，右指针往左
if(sum>target){
if(sum-target<res){
flag = true;
res = sum - target;
}
r--;
} else {//结果小了左指针往右
if(target-sum<res){
flag = false;
res = target - sum;
}
l++;
}
}
}
return flag==true?target+res:target-res;
}
}
自己优化了半天也没进步，最好结果也就是百分之八十五，我直接去看排行第一的代码吧。
class Solution {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int result = Integer.MAX_VALUE,left,right,min = Integer.MAX_VALUE;
for (int i = 0; i < nums.length - 2; i++) {
left = i + 1;
right = nums.length - 1;
int rangemax = nums[i] + nums[right] + nums[right - 1];
int rangemin = nums[i] + nums[left] + nums[left + 1];
if (rangemin > target) {
if (rangemin - target < min) {
min = rangemin -target;
result = rangemin;
}
} else if (rangemax < target) {
if (rangemax - target < min) {
min = target - rangemax;
result = rangemax;
}
} else {
while (left < right) {
int sum = nums[left] + nums[i] + nums[right];
if (sum > target) {
right--;
} else if (sum < target) {
left++;
} else {
return sum;
}
if (Math.abs(sum - target) < min) {
min = Math.abs(sum - target);
result = sum;
}
}
}
}
return result;
}
}
感觉百分之九十的相似度。就是差不多的。只不过人家在我代码的基础上多了两个判断。就是这个双端取值。也就是多了这一步直接性能上来了，这个真的是想的不够多，不是疏忽，是真的没想到。学到了。
今天的笔记就记到这里。昨天刷了四道题，今天五道。是在进步的，加油！另外本篇文章如果稍微帮到你了记得点个喜欢点个关注，也祝大家工作顺顺利利！
