Fizz Buzz

題目：寫(xiě)一個(gè)程序，輸出從 1 到 n 數(shù)字的字符串表示。1. 如果 n 是3的倍數(shù)，輸出“Fizz”；2. 如果 n 是5的倍數(shù)，輸出“Buzz”；3.如果 n 同時(shí)是3和5的倍數(shù)，輸出 “FizzBuzz”。

示例：
n = 15,
返回:
[
"1",
"2",
"Fizz",
"4",
"Buzz",
"Fizz",
"7",
"8",
"Fizz",
"Buzz",
"11",
"Fizz",
"13",
"14",
"FizzBuzz"
]

思路:這個(gè)題怎么說(shuō)呢。應(yīng)該是很簡(jiǎn)單的啊，沒(méi)坑的話一個(gè)循環(huán)搞定，是3,5的倍數(shù)輸出FizzBuzz，是3倍數(shù)輸出Fizz是5倍數(shù)輸出Buzz，不是輸出字符串本身。我去做做看坑在哪里

class Solution {
    public List<String> fizzBuzz(int n) {
        List<String> res = new ArrayList<String>();
        for(int i=1;i<=n;i++){
            if(i%3==0 && i%5==0){
                res.add("FizzBuzz");
            }else if(i%3==0){
                res.add("Fizz");
            }else if(i%5==0){
                res.add("Buzz");
            }else{
                res.add(i+"");
            }
        }
        return res;       
    }
}

額，有點(diǎn)尷尬，一次做完，都沒(méi)發(fā)現(xiàn)有坑，我可能是讓LeetCode坑的有了被害妄想癥了。因?yàn)檫@個(gè)性能也不錯(cuò)，所以直接這樣了，下一題。

第三大的數(shù)

題目：給定一個(gè)非空數(shù)組，返回此數(shù)組中第三大的數(shù)。如果不存在，則返回?cái)?shù)組中最大的數(shù)。要求算法時(shí)間復(fù)雜度必須是O(n)。

示例 1:
輸入: [3, 2, 1]
輸出: 1
解釋: 第三大的數(shù)是 1.
示例 2:
輸入: [1, 2]
輸出: 2
解釋: 第三大的數(shù)不存在, 所以返回最大的數(shù) 2 .
示例 3:
輸入: [2, 2, 3, 1]
輸出: 1
解釋: 注意，要求返回第三大的數(shù)，是指第三大且唯一出現(xiàn)的數(shù)。
存在兩個(gè)值為2的數(shù)，它們都排第二。

思路：這道題第一反應(yīng)排序，估計(jì)直接sort之類(lèi)的有點(diǎn)問(wèn)題，我先理理思路：大體上分兩種情況，有第三大的返回第三大的。沒(méi)第三大的返回最大的。其實(shí)又有那個(gè)想法了：不考慮性能的話怎么都能做出來(lái)！不管是list，map，還是數(shù)組都可以做到。就是里面三個(gè)不同元素，遍歷數(shù)組每一個(gè)比較大小，小于已有的三個(gè)則繼續(xù)往下，大于已有的三個(gè)依次比較，保證存儲(chǔ)的元素是最大的三個(gè)就行了。我覺(jué)得這個(gè)思路可以實(shí)現(xiàn)，就是不知道性能怎么樣，我去試試。
事實(shí)證明剛剛的想法是可行的，就是性能確實(shí)不怎么地，先上代碼：

class Solution {
    public int thirdMax(int[] nums) {
        Map<Integer,Long> map = new HashMap<Integer,Long>();
        map.put(1,-3000000000l);
        map.put(2,-3000000000l);
        map.put(3,-3000000000l);
        for(int i = 0 ;i<nums.length;i++){
            if(nums[i]>map.get(3)){
                if(map.get(1)<nums[i]){
                    map.put(3,map.get(2));
                    map.put(2,map.get(1));
                    map.put(1,(long)nums[i]);
                }else if(map.get(2)<nums[i] && nums[i]!=map.get(1)){
                    map.put(3,map.get(2));
                    map.put(2,(long)nums[i]);
                }else if(map.get(3)<nums[i] && nums[i]!=map.get(2) && nums[i]!=map.get(1)){
                    map.put(3,(long)nums[i]);
                }
            }
        }
        return map.get(3)==-3000000000l?map.get(1).intValue():(int)map.get(3).intValue();
    }
}

啰里啰嗦的，事實(shí)證明我還年輕，所以沒(méi)想到測(cè)試案例第三的值會(huì)是int的最小值，卡了好久。
然后我這用的map，但是我估計(jì)數(shù)組，list 都可以，具體哪個(gè)性能好也不知道，但是我覺(jué)得應(yīng)該是數(shù)組比較好，我去試試：

class Solution {
    public int thirdMax(int[] nums) {
        long[] res = new long[3];
        res[0] = -3000000000l;
        res[1] = -3000000000l;
        res[2] = -3000000000l;
        for(int i = 0 ;i<nums.length;i++){
            if(nums[i]>res[2]){
                if(res[0]<nums[i]){
                    res[2] = res[1];
                    res[1] = res[0];
                    res[0] = nums[i];
                }else if(res[1]<nums[i] && nums[i]!=res[0]){
                    res[2] = res[1];
                    res[1] = nums[i];
                }else if(res[2]<nums[i] && nums[i]!=res[1] && nums[i]!=res[0]){
                    res[2] = nums[i];
                }
            }
        }
        return res[2]==-3000000000l?(int)res[0]:(int)res[2];
    }
}

嗯，換了數(shù)組確實(shí)性能一下子上來(lái)了，超過(guò)百分之九十九的用戶，所以這道題就這樣，下一題吧。

字符串相加

題目:給定兩個(gè)字符串形式的非負(fù)整數(shù) num1 和num2 ，計(jì)算它們的和。

num1 和num2 的長(zhǎng)度都小于 5100.
num1 和num2 都只包含數(shù)字 0-9.
num1 和num2 都不包含任何前導(dǎo)零。
你不能使用任何內(nèi)建 BigInteger 庫(kù)， 也不能直接將輸入的字符串轉(zhuǎn)換為整數(shù)形式。

思路：很好，又沒(méi)看懂題目，這個(gè)不能使用BigInteger可以理解，還不能轉(zhuǎn)化整數(shù)是什么意思？for循環(huán)每一個(gè)字符相加不行么？有點(diǎn)費(fèi)解，我去用測(cè)試案例試試什么意思

image.png

class Solution {
    public String addStrings(String num1, String num2) {
        StringBuilder sb = new StringBuilder();
        int carry = 0;
        int i = num1.length()-1; 
        int j = num2.length()-1;
        while(i >= 0 || j >= 0 || carry != 0){
            if(i>=0) carry += num1.charAt(i--)-'0';
            if(j>=0) carry += num2.charAt(j--)-'0';
            sb.append(carry%10);
            carry /= 10;
        }
        return sb.reverse().toString();
    }
}

在多次循環(huán)并且越寫(xiě)越墨跡以后，我選擇了直接嫖大神代碼：對(duì)，就是如圖所示，簡(jiǎn)單易懂，我就很納悶同樣的大腦為啥思路差這么多呢（手動(dòng)滑稽）。
反正如圖，做的很好，如果進(jìn)位了，carry/10還會(huì)是1，這樣自動(dòng)進(jìn)位了，不然不足10會(huì)是0，相當(dāng)于重置計(jì)算下一位數(shù)字。
而且大神說(shuō)了，適用于十進(jìn)制，二進(jìn)制，任何進(jìn)制（只不過(guò)參數(shù)要改，但是思路不變。前提是不考慮負(fù)數(shù)）。
反正方法就是這么個(gè)方法，代碼也就是這么幾行代碼。我是存在u盤(pán)里了，覺(jué)得真的挺經(jīng)典的，除了膜拜沒(méi)啥說(shuō)的。繼續(xù)往下吧，現(xiàn)在一篇目標(biāo)5+題。

字符串中的單詞數(shù)

題目：統(tǒng)計(jì)字符串中的單詞個(gè)數(shù)，這里的單詞指的是連續(xù)的不是空格的字符。請(qǐng)注意，你可以假定字符串里不包括任何不可打印的字符。

示例:
輸入: "Hello, my name is John"
輸出: 5

思路:這個(gè)題說(shuō)真的，類(lèi)似的做了好多好多遍了，好像是不能直接用split？我忘了有啥潛含的要求了，反正我現(xiàn)在賊煩這種題目上看不出來(lái)的限制。我就按照我自己的想法做一遍，通過(guò)了的話剩下題解見(jiàn)吧。對(duì)了這個(gè)題好像也可以是所有莫名其妙的符號(hào)轉(zhuǎn)換成空格。比如什么逗號(hào)句號(hào)問(wèn)號(hào)啥的，我先去做做再說(shuō)

空格和空字符串

然后繼續(xù)往下，這個(gè), , ,這算是三個(gè)單詞，出題人腦回路6666.然后一開(kāi)始split不行，換了個(gè)思路，我直接上代碼:

class Solution {
    public int countSegments(String s) {
        char [] ch = s.toCharArray();
        int res = 0;
        int temp = 0;
        for(int i=0;i<s.length();i++ ){
            if(!Character.isSpace(ch[i])){
                temp++;
            }else{
                if(temp!=0) {
                    res += 1;
                }
                temp=0;
            }
        }
        return temp==0?res:res+1;
    }
}

說(shuō)實(shí)話判斷邏輯挺無(wú)腦的，就是有不是空格的就計(jì)數(shù)，遇到空格說(shuō)明總數(shù)+1.如果遇到空格發(fā)現(xiàn)計(jì)數(shù)為0說(shuō)明多個(gè)空格在一起了，不算是單詞。一直遍歷到最后，判斷最后計(jì)數(shù)上是不是0，是0說(shuō)明空格結(jié)尾，之前有多少單詞返回多少，不是0說(shuō)明最后的單詞還沒(méi)算，所以要+1.
整體邏輯就這樣，因?yàn)橹苯有阅馨俜职?，所以直接下一題。

路徑總和三

題目：給定一個(gè)二叉樹(shù)，它的每個(gè)結(jié)點(diǎn)都存放著一個(gè)整數(shù)值。找出路徑和等于給定數(shù)值的路徑總數(shù)。路徑不需要從根節(jié)點(diǎn)開(kāi)始，也不需要在葉子節(jié)點(diǎn)結(jié)束，但是路徑方向必須是向下的（只能從父節(jié)點(diǎn)到子節(jié)點(diǎn)）。二叉樹(shù)不超過(guò)1000個(gè)節(jié)點(diǎn)，且節(jié)點(diǎn)數(shù)值范圍是 [-1000000,1000000] 的整數(shù)。

image.png

思路：二叉樹(shù)的題，主思路遞歸/迭代。我習(xí)慣性遞歸。首先判斷例子可以看出幾點(diǎn)1.樹(shù)節(jié)點(diǎn)不唯一。2.樹(shù)節(jié)點(diǎn)沒(méi)有規(guī)律，什么左小右大都沒(méi)有，正負(fù)也是。 3.本來(lái)我預(yù)計(jì)的是某條線到了給定數(shù)字就清0從來(lái)，但是現(xiàn)在看不行，很有可能到了給定數(shù)字然后往下加個(gè)正數(shù)減個(gè)負(fù)數(shù)啥的又變成了這個(gè)數(shù)字。這就有點(diǎn)問(wèn)題了，暫時(shí)沒(méi)有啥思路，我去理理
好吧，沒(méi)理出來(lái)，雖然知道是遞歸但是具體怎么做一點(diǎn)思路沒(méi)有，所以直接看了官方的題解,不得不說(shuō)看了題解豁然開(kāi)朗,然后我先把題解大概說(shuō)一下：

• 路徑的開(kāi)頭可以不是根節(jié)點(diǎn)，結(jié)束也可以不是葉子節(jié)點(diǎn)，是不是有點(diǎn)復(fù)雜？
  如果問(wèn)題是這樣：找出以根節(jié)點(diǎn)為開(kāi)始，任意節(jié)點(diǎn)可作為結(jié)束，且路徑上的節(jié)點(diǎn)和為 sum 的路徑的個(gè)數(shù)；
• 是不是前序遍歷一遍二叉樹(shù)就可以得到所有這樣的路徑？是的；
  如果這個(gè)問(wèn)題解決了，那么原問(wèn)題可以分解成多個(gè)這個(gè)問(wèn)題；
• 是不是和數(shù)線段是同一個(gè)問(wèn)題，只不過(guò)線段變成了二叉樹(shù)；
  在解決了以根節(jié)點(diǎn)開(kāi)始的所有路徑后，就要找以根節(jié)點(diǎn)的左孩子和右孩子開(kāi)始的所有路徑，三個(gè)節(jié)點(diǎn)構(gòu)成了一個(gè)遞歸結(jié)構(gòu)；
• 遞歸真的好簡(jiǎn)單又好難；

然后看了這個(gè)題的解釋豁然開(kāi)朗，我去試著寫(xiě)寫(xiě)代碼：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int pathSum(TreeNode root, int sum) {
        if(root==null) return 0;
        return pathNode(root,sum)+pathSum(root.right,sum)+pathSum(root.left,sum);

    }
    public int pathNode(TreeNode root,int sum){
        if(root==null) return 0;
        int res = 0;
        if(root.val==sum) res += 1;
        return res+pathNode(root.right,sum-root.val)+pathNode(root.left,sum-root.val); 
    }

如圖所示，兩個(gè)遞歸。要調(diào)試瘋了，反正沒(méi)技術(shù)，沒(méi)技巧，我就一點(diǎn)點(diǎn)打印調(diào)試。等做出來(lái)了才發(fā)現(xiàn)其實(shí)也沒(méi)那么簡(jiǎn)單。就是每一個(gè)節(jié)點(diǎn)的符合條件的路徑數(shù)，然后再遞歸把所有的加在一起。但是我這么寫(xiě)性能不咋地，我去看看性能好的寫(xiě)法：
算了看了性能好的寫(xiě)法有點(diǎn)看不懂，而且剛剛不斷調(diào)試那個(gè)雙遞歸也頭暈，換下一道題換個(gè)心情吧。能自己做出來(lái)我就挺滿意了，不追求完美了。

排列硬幣

題目：你總共有 n 枚硬幣，你需要將它們擺成一個(gè)階梯形狀，第 k 行就必須正好有 k 枚硬幣。給定一個(gè)數(shù)字 n，找出可形成完整階梯行的總行數(shù)。n 是一個(gè)非負(fù)整數(shù)，并且在32位有符號(hào)整型的范圍內(nèi)。

示例 1:
n = 5
硬幣可排列成以下幾行:
¤
¤ ¤
¤ ¤
因?yàn)榈谌胁煌暾?，所以返?.
示例 2:
n = 8
硬幣可排列成以下幾行:
¤
¤ ¤
¤ ¤ ¤
¤ ¤
因?yàn)榈谒男胁煌暾?，所以返?.

思路：很喜歡這種一個(gè)簡(jiǎn)單一個(gè)難的題目啊，這道題又是送分題，不就是判斷一個(gè)數(shù)字拆成1，2，3，。。最多能拆到幾么。我去寫(xiě)代碼了

class Solution {
    public int arrangeCoins(int n) {
        int i = 1;
        while(n>=i){
            n=n-i;
            i++;
        }
        return i-1;
    }
}

一次搞定，雖然性能不行。不過(guò)在寫(xiě)的時(shí)候就有了隱隱約約的貌似有什么規(guī)律的感覺(jué)。第一行+倒數(shù)第二行是倒數(shù)第一行（這里忽略了不滿的最后一行）第二行加倒數(shù)第三行也是最后一行，第三行加倒數(shù)第四行。。以此類(lèi)推，肯定是有規(guī)律的，我去“看”規(guī)律了！
算了，手頭沒(méi)筆和紙，還是在這里打字吧：第n行，前面有n-1除2的n，如果是偶數(shù)還會(huì)有個(gè)中間的二分之n的數(shù)，再加上本身的 第n行，嗯嗯，有道理，我還是直接看題解吧。哈哈，覺(jué)得沒(méi)啥必要非要手算，知道有規(guī)律就行了我覺(jué)得。

image.png