最大子序和

題目：給定一個(gè)整數(shù)數(shù)組 nums 乔外，找到一個(gè)具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個(gè)元素）拧揽，返回其最大和。

示例:
輸入: [-2,1,-3,4,-1,2,1,-5,4],
輸出: 6
解釋: 連續(xù)子數(shù)組 [4,-1,2,1] 的和最大憋沿，為 6逛揩。

思路：額，這個(gè)題目很簡(jiǎn)單馋嗜，但是一開(kāi)始我思路差了齐板，所以越想越復(fù)雜，最后還是直接看了大神的思路才理明白這個(gè)要怎么做。定義兩個(gè)值甘磨，一個(gè)是目前子序和的最大值橡羞，另一個(gè)是子序慢慢相加的當(dāng)前和。而這個(gè)當(dāng)前和的特性就是如果和為負(fù)值就把之前的都舍去济舆，從頭開(kāi)始加卿泽。然后當(dāng)前值不斷和最大值相比較，取較大的那個(gè)滋觉。這樣一遍下來(lái)签夭，最大值就是這個(gè)數(shù)組的最大子序和

反正我代碼的特點(diǎn)就是墨跡不行的注釋?zhuān)约嚎窗伞５俏铱傆X(jué)得這個(gè)題不僅僅是簡(jiǎn)單的椎侠。第租。。哈哈

    public int maxSubArray(int[] nums) {
        //為什么這個(gè)res是第一個(gè)元素而不是0呢我纪，因?yàn)槿f(wàn)一只有一個(gè)元素慎宾，而這個(gè)元素是負(fù)數(shù)，那么結(jié)果就不對(duì)了浅悉！
        int res = nums[0];
        int sum = 0;
        for(int i:nums){
           //從頭開(kāi)始加
           if(sum<0){
               sum = i;              
           }else{//累加
              sum += i; 
           }
           //這樣res總會(huì)是較大的那個(gè)值趟据！
           res = res>=sum?res:sum;
        }
        return res;

    }

因?yàn)槲疫@個(gè)是直接看了大神解題的，所以思路是一樣的术健，就不多說(shuō)了汹碱。

最后一個(gè)單詞的長(zhǎng)度

題目：給定一個(gè)僅包含大小寫(xiě)字母和空格 ' ' 的字符串，返回其最后一個(gè)單詞的長(zhǎng)度苛坚。如果不存在最后一個(gè)單詞比被，請(qǐng)返回 0 。說(shuō)明：一個(gè)單詞是指由字母組成泼舱，但不包含任何空格的字符串等缀。

示例:
輸入: "Hello World"
輸出: 5

思路：這個(gè)題，尤其是跟上道題一對(duì)比我都懷疑是不是有什么我不知道的限制了娇昙，反正兩行代碼的事尺迂。一看題就有兩種思路：一種按照“ ”拆成數(shù)組，取最后一個(gè)的長(zhǎng)度冒掌，一種是按照最后一個(gè)“ ”往后截取噪裕，取最后一個(gè)長(zhǎng)度。

 public int lengthOfLastWord(String s) {
        String [] strs = s.split(" ");
        return strs.length!=0?strs[strs.length-1].length():0;       
    }

我選了一種簡(jiǎn)單又常用的股毫，然后接下來(lái)大神思路（我上面的代碼審核通過(guò)膳音，但是性能和執(zhí)行時(shí)間并不好）：大神思路就是獲取最后一個(gè)“ ”后面的，但是存在一種“a ”這樣的情況铃诬，所以要先去掉末尾的“ ”祭陷。但是這個(gè)有現(xiàn)成的api苍凛，我也不知道這個(gè)題要考啥。反正就這樣吧兵志。

class Solution {
    public int lengthOfLastWord(String s) {
        //去掉首尾空格    
        s = s.trim();
        //字符串沒(méi)出現(xiàn)“ ”則返回-1
        int last = s.lastIndexOf(" ");
        //因?yàn)橄聵?biāo)從0開(kāi)始醇蝴，所以這個(gè)last是下標(biāo)位置，如果按實(shí)際元素位置算應(yīng)該是下標(biāo)+1.所以這里是s.length()-1-last
        return last==-1?s.length():s.length()-1-last;
    }
}

上面的是另一個(gè)思路的代碼想罕。

加一

題目：給定一個(gè)由整數(shù)組成的非空數(shù)組所表示的非負(fù)整數(shù)悠栓，在該數(shù)的基礎(chǔ)上加一。最高位數(shù)字存放在數(shù)組的首位按价， 數(shù)組中每個(gè)元素只存儲(chǔ)單個(gè)數(shù)字惭适。你可以假設(shè)除了整數(shù) 0 之外，這個(gè)整數(shù)不會(huì)以零開(kāi)頭俘枫。

示例 1:
輸入: [1,2,3]
輸出: [1,2,4]
解釋: 輸入數(shù)組表示數(shù)字 123腥沽。
示例 2:
輸入: [4,3,2,1]
輸出: [4,3,2,2]
解釋: 輸入數(shù)組表示數(shù)字 4321。

思路：這個(gè)題其實(shí)也挺簡(jiǎn)單的鸠蚪，就是加1嘛。唯一需要注意的點(diǎn)應(yīng)該就是進(jìn)位了师溅。其實(shí)可以把這個(gè)數(shù)組看成一整個(gè)數(shù)茅信，我雖然還沒(méi)做，但是覺(jué)得思路是沒(méi)問(wèn)題的墓臭，等我做完回來(lái)貼代碼
好吧蘸鲸，這個(gè)題啪啪的打臉，他說(shuō)是可以看做非負(fù)整數(shù)酌摇，結(jié)果恨不得二十多位的數(shù)組，什么整數(shù)這么長(zhǎng)拔嗽亍窑多！然后推到重開(kāi)，我換了個(gè)思路，開(kāi)始正常判斷，末尾不是9則正常加1颠毙，是9才需要進(jìn)位，一步步往上增蹭，下面是代碼（速度不錯(cuò)滴某，消耗性能較高）：

    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進(jìn)位，末尾變0滋迈，下一個(gè)循環(huán)中n減一霎奢，也就是這位數(shù)的上一位
                digits[n]=0;
            }
        }
        //for循環(huán)里都沒(méi)return的話(huà)，說(shuō)明要進(jìn)位了,所以選擇數(shù)組擴(kuò)充
        int[] arr=new int[digits.length+1];
        System.arraycopy(digits,0,arr,1,digits.length);
        //進(jìn)位只可能進(jìn)1饼灿，所以這里直接首位變成1
        arr[0] = 1;
        return arr;      
    }

接下來(lái)去看看大神的解析：
大神解析和我差不多幕侠，不多說(shuō)這個(gè)，說(shuō)一個(gè)挺好玩的事：這個(gè)數(shù)組最后的復(fù)制碍彭，其實(shí)因?yàn)閕nt數(shù)組晤硕，默認(rèn)就是0，既然整體進(jìn)位了庇忌，所以肯定每一位都是0這個(gè)沒(méi)話(huà)說(shuō)舞箍，所以這個(gè)其實(shí)沒(méi)有復(fù)制的過(guò)程結(jié)果也是對(duì)的。

但是皆疹，有意思的是疏橄，如果沒(méi)這句話(huà)，反而消耗內(nèi)存越多略就！很穩(wěn)定捎迫，紅色框起來(lái)的是有這句代碼的，綠色框起來(lái)的是沒(méi)有的表牢。所以說(shuō)讓系統(tǒng)自動(dòng)賦值還不如自己手動(dòng)復(fù)制來(lái)的快窄绒！

image.png

二進(jìn)制求和

題目：給定兩個(gè)二進(jìn)制字符串，返回他們的和（用二進(jìn)制表示）初茶。輸入為非空字符串且只包含數(shù)字 1 和 0颗祝。

示例 1:
輸入: a = "11", b = "1"
輸出: "100"
示例 2:
輸入: a = "1010", b = "1011"
輸出: "10101"

思路：審?fù)觐}我覺(jué)得這個(gè)題有兩個(gè)思路可解：1.直接二進(jìn)制計(jì)算。逢二進(jìn)一嘛2.二進(jìn)制轉(zhuǎn)化數(shù)字恼布，數(shù)字相加再轉(zhuǎn)回二進(jìn)制螺戳。
因?yàn)槲疫€沒(méi)做，但是我記得已經(jīng)有線(xiàn)程的api可以二進(jìn)制轉(zhuǎn)換成十進(jìn)制折汞。但是我估計(jì)這道題應(yīng)該不是想要調(diào)用現(xiàn)成的api倔幼。所以我這采用二進(jìn)制計(jì)算吧（做的多了還是對(duì)LeetCode出題有一定的了解了，哈哈）爽待。
其實(shí)這個(gè)題如果是二進(jìn)制直接相加的話(huà)损同，跟上一道題有一定的相似之處翩腐。
續(xù)：不得不說(shuō)這個(gè)出題人可以，剛剛沒(méi)禁住誘惑打算先直接調(diào)用api完成一次再說(shuō)膏燃，結(jié)果茂卦。。

image.png

image.png

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;
        //作為結(jié)果集的數(shù)組，因?yàn)榭赡軙?huì)進(jìn)位所以直接預(yù)留出一個(gè)位數(shù)
        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則進(jìn)位，否則不進(jìn)位
            if(aNum+bNum>=2) {
                //這個(gè)位數(shù)加上ab合并應(yīng)該加的數(shù)辩尊，累加是因?yàn)榭赡鼙旧碛羞M(jìn)位的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; 
    }
}

我覺(jué)得我這個(gè)性能主要消耗在字符串?dāng)?shù)組轉(zhuǎn)成int數(shù)組了，或者還有一些別的康辑，但是先實(shí)現(xiàn)再優(yōu)化嘛摄欲！接著開(kāi)始一點(diǎn)點(diǎn)優(yōu)化：

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';
        }
        //這里直接減一是為了表示下標(biāo)
        int alen = arrs.length - 1;
        int blen = brrs.length - 1; 
        //作為結(jié)果集的數(shù)組，因?yàn)榭赡軙?huì)進(jìn)位所以直接預(yù)留出一個(gè)位數(shù)
        int[] result = new int[alen > blen?alen+2:blen+2];
        int r = result.length-1;
        //兩個(gè)字符串有沒(méi)遍歷完的
        while(alen>=0 || blen>=0) {
            //判斷a疮薇，b是否遍歷完了胸墙，是則補(bǔ)0，不是則該是多少是多少
            int aNum = alen>=0?arrs[alen]:0;
            int bNum = blen>=0?brrs[blen]:0;
            //大于等于2則進(jìn)位按咒，否則不進(jìn)位
            if(aNum+bNum>=2) {
                //這個(gè)位數(shù)加上ab合并應(yīng)該加的數(shù)迟隅，累加是因?yàn)榭赡鼙旧碛羞M(jìn)位的1
                result[r] += aNum+bNum-2;
                if(alen>=1) {//判斷a是否遍歷完，是則這個(gè)進(jìn)位加b上
                    arrs[alen-1] = arrs[alen-1]+1;
                }else if (blen>=1) {//判斷b是否遍歷完励七，因?yàn)閍在前智袭，走到這本身說(shuō)明a已經(jīng)遍歷完了
                    brrs[blen-1] = brrs[blen-1]+1;
                }else {
                    //走到這步只能是最后一位進(jìn)位了
                    result[0] = 1;
                }               
            }else {
                result[r] += aNum+bNum;
            }
            alen--;
            blen--;
            r--;
        }
        //這個(gè)之前用string來(lái)著，現(xiàn)在是優(yōu)化版掠抬，stringBufferuffer性能較好
        StringBuffer res = new StringBuffer();
        for(int i : result) {
            res.append(i);
        }
        //首位是0則說(shuō)明沒(méi)有進(jìn)位吼野，去掉首位就可以了，不是0則該是是多少是多少
        return res.charAt(0)=='0'?res.substring(1):res.toString(); 
    }
}

優(yōu)化后鳥(niǎo)槍換炮了

優(yōu)化后結(jié)果