刷leetCode算法题+解析（六）
最大子序和
题目：给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
思路：额，这个题目很简单，但是一开始我思路差了，所以越想越复杂，最后还是直接看了大神的思路才理明白这个要怎么做。定义两个值，一个是目前子序和的最大值，另一个是子序慢慢相加的当前和。而这个当前和的特性就是如果和为负值就把之前的都舍去，从头开始加。然后当前值不断和最大值相比较，取较大的那个。这样一遍下来，最大值就是这个数组的最大子序和
反正我代码的特点就是墨迹不行的注释，自己看吧。但是我总觉得这个题不仅仅是简单的。。。哈哈
public int maxSubArray(int[] nums) {
//为什么这个res是第一个元素而不是0呢，因为万一只有一个元素，而这个元素是负数，那么结果就不对了！
int res = nums[0];
int sum = 0;
for(int i:nums){
//从头开始加
if(sum<0){
sum = i;
}else{//累加
sum += i;
}
//这样res总会是较大的那个值！
res = res>=sum?res:sum;
}
return res;
}
因为我这个是直接看了大神解题的，所以思路是一样的，就不多说了。
最后一个单词的长度
题目：给定一个仅包含大小写字母和空格 ' ' 的字符串，返回其最后一个单词的长度。如果不存在最后一个单词，请返回 0 。说明：一个单词是指由字母组成，但不包含任何空格的字符串。
示例:
输入: "Hello World"
输出: 5
思路：这个题，尤其是跟上道题一对比我都怀疑是不是有什么我不知道的限制了，反正两行代码的事。一看题就有两种思路：一种按照“ ”拆成数组，取最后一个的长度，一种是按照最后一个“ ”往后截取，取最后一个长度。
public int lengthOfLastWord(String s) {
String [] strs = s.split(" ");
return strs.length!=0?strs[strs.length-1].length():0;
}
我选了一种简单又常用的，然后接下来大神思路（我上面的代码审核通过，但是性能和执行时间并不好）：大神思路就是获取最后一个“ ”后面的，但是存在一种“a ”这样的情况，所以要先去掉末尾的“ ”。但是这个有现成的api，我也不知道这个题要考啥。反正就这样吧。
class Solution {
public int lengthOfLastWord(String s) {
//去掉首尾空格
s = s.trim();
//字符串没出现“ ”则返回-1
int last = s.lastIndexOf(" ");
//因为下标从0开始，所以这个last是下标位置，如果按实际元素位置算应该是下标+1.所以这里是s.length()-1-last
return last==-1?s.length():s.length()-1-last;
}
}
上面的是另一个思路的代码。
加一
题目：给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。你可以假设除了整数 0 之外，这个整数不会以零开头。
示例 1:
输入: [1,2,3]
输出: [1,2,4]
解释: 输入数组表示数字 123。
示例 2:
输入: [4,3,2,1]
输出: [4,3,2,2]
解释: 输入数组表示数字 4321。
思路：这个题其实也挺简单的，就是加1嘛。唯一需要注意的点应该就是进位了。其实可以把这个数组看成一整个数，我虽然还没做，但是觉得思路是没问题的，等我做完回来贴代码
好吧，这个题啪啪的打脸，他说是可以看做非负整数，结果恨不得二十多位的数组，什么整数这么长啊！然后推到重开，我换了个思路，开始正常判断，末尾不是9则正常加1，是9才需要进位，一步步往上，下面是代码（速度不错，消耗性能较高）：
public int[] plusOne(int[] digits) {
for(int n =digits.length-1;n>=0;n-- ){
//不是9正常加1
if(digits[n]!=9){
digits[n]=digits[n]+1;
return digits;
}else{
//是9进位，末尾变0，下一个循环中n减一，也就是这位数的上一位
digits[n]=0;
}
}
//for循环里都没return的话，说明要进位了,所以选择数组扩充
int[] arr=new int[digits.length+1];
System.arraycopy(digits,0,arr,1,digits.length);
//进位只可能进1，所以这里直接首位变成1
arr[0] = 1;
return arr;
}
接下来去看看大神的解析：
大神解析和我差不多，不多说这个，说一个挺好玩的事：这个数组最后的复制，其实因为int数组，默认就是0，既然整体进位了，所以肯定每一位都是0这个没话说，所以这个其实没有复制的过程结果也是对的。
但是，有意思的是，如果没这句话，反而消耗内存越多！很稳定，红色框起来的是有这句代码的，绿色框起来的是没有的。所以说让系统自动赋值还不如自己手动复制来的快！
image.png
二进制求和
题目：给定两个二进制字符串，返回他们的和（用二进制表示）。输入为非空字符串且只包含数字 1 和 0。
示例 1:
输入: a = "11", b = "1"
输出: "100"
示例 2:
输入: a = "1010", b = "1011"
输出: "10101"
思路：审完题我觉得这个题有两个思路可解：1.直接二进制计算。逢二进一嘛2.二进制转化数字，数字相加再转回二进制。
因为我还没做，但是我记得已经有线程的api可以二进制转换成十进制。但是我估计这道题应该不是想要调用现成的api。所以我这采用二进制计算吧（做的多了还是对LeetCode出题有一定的了解了，哈哈）。
其实这个题如果是二进制直接相加的话，跟上一道题有一定的相似之处。
续：不得不说这个出题人可以，刚刚没禁住诱惑打算先直接调用api完成一次再说，结果。。
image.png
错误原因，该二进制数字超出long范围，我还是老老实实的去直接加吧。就当复习复习包装类api的知识了。
继续说这个题，乍一看很简单，但是真做起来可能是我思路没理清楚，这叫一个墨迹。用了一个小时的第一版本：
image.png
先看执行用时，超过百分之5的用户，心都碎了，然后上代码：
class Solution {
public String addBinary(String a, String b) {
String[] arr = a.split("");
String[] brr = b.split("");
int[] arrs = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
arrs[i] = Integer.parseInt(arr[i]);
}
int[] brrs = new int[brr.length];
for (int i = 0; i < brr.length; i++) {
brrs[i] = Integer.parseInt(brr[i]);
}
int alen = arrs.length - 1;
int blen = brrs.length - 1;
//作为结果集的数组，因为可能会进位所以直接预留出一个位数
int[] result = new int[alen > blen?alen+2:blen+2];
int r = result.length-1;
while(alen>=0 || blen>=0) {
//判断a是否遍历完了，是则补0，不是则该是多少是多少
int aNum = alen>=0?arrs[alen]:0;
int bNum = blen>=0?brrs[blen]:0;
//大于等于2则进位，否则不进位
if(aNum+bNum>=2) {
//这个位数加上ab合并应该加的数，累加是因为可能本身有进位的1
result[r] += aNum+bNum-2;
if(alen>=1) {
arrs[alen-1] = arrs[alen-1]+1;
}else if (blen>=1) {
brrs[blen-1] = brrs[blen-1]+1;
}else {
result[r-1] = 1;
}
}else {
result[r] += aNum+bNum;
}
alen--;
blen--;
r--;
}
String res = "";
for(int i : result) {
res += i;
}
if(res.charAt(0)=='0') {
res = res.substring(1);
}
return res;
}
}
我觉得我这个性能主要消耗在字符串数组转成int数组了，或者还有一些别的，但是先实现再优化嘛！接着开始一点点优化：
class Solution {
public String addBinary(String a, String b) {
int [] arrs = new int[a.length()];
int [] brrs = new int[b.length()];
for(int i=0;i<a.length();i++){
arrs[i]= a.charAt(i)-'0';
}
for(int i=0;i<b.length();i++){
brrs[i]= b.charAt(i)-'0';
}
//这里直接减一是为了表示下标
int alen = arrs.length - 1;
int blen = brrs.length - 1;
//作为结果集的数组，因为可能会进位所以直接预留出一个位数
int[] result = new int[alen > blen?alen+2:blen+2];
int r = result.length-1;
//两个字符串有没遍历完的
while(alen>=0 || blen>=0) {
//判断a，b是否遍历完了，是则补0，不是则该是多少是多少
int aNum = alen>=0?arrs[alen]:0;
int bNum = blen>=0?brrs[blen]:0;
//大于等于2则进位，否则不进位
if(aNum+bNum>=2) {
//这个位数加上ab合并应该加的数，累加是因为可能本身有进位的1
result[r] += aNum+bNum-2;
if(alen>=1) {//判断a是否遍历完，是则这个进位加b上
arrs[alen-1] = arrs[alen-1]+1;
}else if (blen>=1) {//判断b是否遍历完，因为a在前，走到这本身说明a已经遍历完了
brrs[blen-1] = brrs[blen-1]+1;
}else {
//走到这步只能是最后一位进位了
result[0] = 1;
}
}else {
result[r] += aNum+bNum;
}
alen--;
blen--;
r--;
}
//这个之前用string来着，现在是优化版，stringBufferuffer性能较好
StringBuffer res = new StringBuffer();
for(int i : result) {
res.append(i);
}
//首位是0则说明没有进位，去掉首位就可以了，不是0则该是是多少是多少
return res.charAt(0)=='0'?res.substring(1):res.toString();
}
}
优化后鸟枪换炮了
优化后结果
其实主要优化点就两个：一个是string换成了变长字符串stringBuffer，还有一个就是我第一版本是字符串转换成字符串数组，再遍历转化成int数组的。在优化后就是字符串直接转化成int数组，少了一步转化过程，用时超过百分之98，我已经相当满意了。接下来去看大神 的思路：
额，大神思路大多也就这样，不过我是正向思维，从最后往前一个个遍历的，但是大神是从前往后，最后倒转一下的。别的大同小异，就不多说了。
用了一天半，这个帖子才算真正写完，如果稍微帮到了你记得点个喜欢点个关注！也祝大家工作顺顺利利！
