打廣告：Java技術(shù)交流群：130031711，歡迎各位踴躍加入竟稳。
刷題繼續(xù)：

完全平方數(shù)

題目：給定正整數(shù) n宜咒，找到若干個(gè)完全平方數(shù)（比如 1, 4, 9, 16, ...）使得它們的和等于 n裹粤。你需要讓組成和的完全平方數(shù)的個(gè)數(shù)最少邑贴。

示例 1:
輸入: n = 12
輸出: 3
解釋: 12 = 4 + 4 + 4.
示例 2:
輸入: n = 13
輸出: 2
解釋: 13 = 4 + 9.

思路：(剛剛做了個(gè)測(cè)試，16本身就是完全平方數(shù)铃在，而不是4+4+4+4阵具。其實(shí)也能理解碍遍，不然都是1相加還不用算了呢。)以上都是廢話阳液，因?yàn)槲矣锌吹搅耸雇耆椒綌?shù)的個(gè)數(shù)最少怕敬，是我審題不清，哈哈帘皿，咱們繼續(xù)說(shuō)：首先我思路是從最大的完全平方數(shù)開(kāi)始算东跪。比如12，最大的完全平方數(shù)是3鹰溜，然后9剩下3虽填，只能是三個(gè)1，這樣就是4曹动。 然后其次大的是2,4剩下8又分了兩個(gè)四斋日，結(jié)果就是3.3比4小所以選擇3。同理墓陈，13最大完全平方數(shù)3的平方9恶守。拋出了9繼續(xù)算。除了本身是完全平方外贡必，剩下如果有兩個(gè)組成了就直接返回兔港。不然就再往下判斷下。判斷到高位出現(xiàn)這個(gè)數(shù)就不用繼續(xù)往下了仔拟。我感覺(jué)我說(shuō)的很亂押框，因?yàn)槎际橇闵⒌乃悸罚胰?xiě)寫(xiě)代碼整合一下思路理逊。
好了，做完回來(lái)了了盒揉，思路可以用晋被，然后性能也還好，我直接貼代碼：

class Solution {
    int min = Integer.MAX_VALUE;
    public int numSquares(int n) {
        countN(n,0);
        return min;
    }
    public void countN(int n , int count){
        if(min == 2) return;
        count++;
        if(count== min) return; 
        int sq = (int)Math.sqrt(n);
        if(sq*sq == n) {
            min = Math.min(min,count);
            return;
        }
        for(int i = sq;i>0;i--){
           countN(n-i*i,count);
        }
    }
}

上面有一句代碼刚盈，如果min==2直接返回羡洛。其實(shí)這個(gè)是因?yàn)槭紫热绻@個(gè)數(shù)本身是完全平方數(shù)，那么根本不會(huì)走到for循環(huán)中的遞歸藕漱，所以其實(shí)不可能出現(xiàn)min=1的情況欲侮。其次如果這個(gè)數(shù)不是完全平方數(shù)，那么最少也就是拆成兩個(gè)肋联，所以如果出現(xiàn)了min是2威蕉，就沒(méi)必要遞歸了。不過(guò)現(xiàn)在越想越覺(jué)得這句話其實(shí)作用也沒(méi)多大橄仍，有點(diǎn)雞肋韧涨，不過(guò)寫(xiě)了就寫(xiě)了吧牍戚。
性能超過(guò)百分之九十六，所以我自我感覺(jué)挺好虑粥，我去看一眼性能排行第一的代碼如孝，問(wèn)題不大就直接過(guò)了。
問(wèn)題有點(diǎn)大娩贷，因?yàn)槲覜](méi)太看懂：

class Solution {

  protected boolean isSquare(int n) {
    int sq = (int) Math.sqrt(n);
    return n == sq * sq;
  }

  public int numSquares(int n) {
    while (n % 4 == 0)
      n /= 4;
    if (n % 8 == 7)
      return 4;

    if (this.isSquare(n))
      return 1;
    for (int i = 1; i * i <= n; ++i) {
      if (this.isSquare(n - i * i))
        return 2;
    }
    return 3;
  }
}

除了這個(gè)for循環(huán)第晰，剩下的，我都沒(méi)太看懂彬祖。代碼我是明白了茁瘦，這里只會(huì)返回1,2,3,4.如果第二次循環(huán)還不是0就返回3，第二次循環(huán)就沒(méi)了返回2涧至，本身是完全平方數(shù)返回1.重點(diǎn)是這個(gè)4.腹躁。。除8余7就是4南蓬？我決定去評(píng)論看一看了纺非，我是不是錯(cuò)過(guò)了什么？

四平方定理

笑而不語(yǔ)赘方，我感覺(jué)我可能是沒(méi)學(xué)過(guò)數(shù)學(xué)烧颖。。好的吧窄陡，看了這個(gè)配上代碼算是明白了炕淮，我也盡量記住這個(gè)定理。下一題吧跳夭。

頂端迭代器

題目：給定一個(gè)迭代器類(lèi)的接口涂圆，接口包含兩個(gè)方法： next() 和 hasNext()。設(shè)計(jì)并實(shí)現(xiàn)一個(gè)支持 peek() 操作的頂端迭代器 -- 其本質(zhì)就是把原本應(yīng)由 next() 方法返回的元素 peek() 出來(lái)币叹。

示例:
假設(shè)迭代器被初始化為列表 [1,2,3]润歉。
調(diào)用 next() 返回 1，得到列表中的第一個(gè)元素颈抚。
現(xiàn)在調(diào)用 peek() 返回 2踩衩，下一個(gè)元素。在此之后調(diào)用 next() 仍然返回 2贩汉。
最后一次調(diào)用 next() 返回 3驱富，末尾元素。在此之后調(diào)用 hasNext() 應(yīng)該返回 false匹舞。
進(jìn)階：你將如何拓展你的設(shè)計(jì)褐鸥？使之變得通用化，從而適應(yīng)所有的類(lèi)型策菜，而不只是整數(shù)型晶疼？

思路：這個(gè)題我看了幾遍題目酒贬，大概的理解是next相當(dāng)于一個(gè)取出第一個(gè)元素并返回這個(gè)值。peek相當(dāng)于一個(gè)返回第一個(gè)元素的值但是不取出翠霍。hasNext是判斷下面還有沒(méi)有元素了锭吨。至于進(jìn)階條件我覺(jué)得是泛型解決的。其實(shí)這類(lèi)題我最懵的是不知道能用什么不能用什么寒匙。單純的實(shí)現(xiàn)的話零如，我覺(jué)得集合鏈表都能實(shí)現(xiàn)。next就是獲取第一個(gè)然后刪除锄弱。peek就是獲取第一個(gè)不做任何操作考蕾。hasNext就是判斷當(dāng)前集合或者鏈表中還有沒(méi)有元素。甚至用隊(duì)列的話這三個(gè)方法都是現(xiàn)成的会宪。肖卧。哎，我都不知道這個(gè)題目是想要啥掸鹅。我去嘗試寫(xiě)寫(xiě)吧塞帐，先實(shí)現(xiàn)了，再去看評(píng)論好知道題目到底啥意思巍沙。
好了葵姥，我實(shí)現(xiàn)了，先貼代碼：

// Java Iterator interface reference:
// https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html
class PeekingIterator implements Iterator<Integer> {
    Iterator<Integer> iterator;
    Integer temp;
    public PeekingIterator(Iterator<Integer> iterator) {
        // initialize any member here.
        this.iterator = iterator;
        
    }

    // Returns the next element in the iteration without advancing the iterator.
    public Integer peek() {
        if(temp==null){
            temp = iterator.next();
        }
        return temp;
    }

    // hasNext() and next() should behave the same as in the Iterator interface.
    // Override them if needed.
    @Override
    public Integer next() {
        if(temp==null){
            return iterator.next();
        }else{
            int res = temp;
            temp = null;
            return res;
        }
    }

    @Override
    public boolean hasNext() {
        return temp == null?iterator.hasNext():true;
    }
}

因?yàn)槲沂情_(kāi)始寫(xiě)代碼了才發(fā)現(xiàn)這個(gè)題目構(gòu)造器穿的參數(shù)就是Iterator句携，所以直接用了現(xiàn)有的api榔幸。不過(guò)有一個(gè)問(wèn)題就是這個(gè)peek，迭代器是不支持取出值不移動(dòng)元素的矮嫉，所以我這里做了個(gè)小處理削咆，就是把用temp緩存起來(lái)。每次移除節(jié)點(diǎn)也會(huì)先判斷一下蠢笋。
性能一般态辛，只超過(guò)百分之七十多的人，但是主要是這個(gè)題我連題意都不知道挺尿，所以我直接去看評(píng)論了，回來(lái)再分享題目是什么意思炊邦。
回來(lái)了编矾，性能排行第一的代碼和我思路一樣一樣的，就是細(xì)節(jié)處理有點(diǎn)點(diǎn)區(qū)別馁害。窄俏。評(píng)論中也沒(méi)有別的說(shuō)法，所以這道題好像就是這么簡(jiǎn)單碘菜，哈哈凹蜈。這道題就這么過(guò)了限寞，下一題了。

尋找重復(fù)數(shù)

題目：給定一個(gè)包含 n + 1 個(gè)整數(shù)的數(shù)組 nums仰坦，其數(shù)字都在 1 到 n 之間（包括 1 和 n）履植，可知至少存在一個(gè)重復(fù)的整數(shù)。假設(shè)只有一個(gè)重復(fù)的整數(shù)悄晃，找出這個(gè)重復(fù)的數(shù)玫霎。

示例 1:
輸入: [1,3,4,2,2]
輸出: 2
示例 2:
輸入: [3,1,3,4,2]
輸出: 3
說(shuō)明：
不能更改原數(shù)組（假設(shè)數(shù)組是只讀的）。
只能使用額外的 O(1) 的空間妈橄。
時(shí)間復(fù)雜度小于 O(n2) 庶近。
數(shù)組中只有一個(gè)重復(fù)的數(shù)字，但它可能不止重復(fù)出現(xiàn)一次眷蚓。

思路：額鼻种，怎么說(shuō)呢，在我沒(méi)有看最后一句話的時(shí)候我甚至覺(jué)得題目還比較簡(jiǎn)單沙热，畢竟從1加到n叉钥，然后再把結(jié)果去數(shù)組挨個(gè)減，最后負(fù)幾校读，重復(fù)的數(shù)就是這個(gè)數(shù)的相反數(shù)沼侣。。但是歉秫！我還是太年輕了蛾洛，只有一個(gè)重復(fù)數(shù)字，但是可能不止重復(fù)一次雁芙，我簡(jiǎn)直笑了轧膘！ 時(shí)間復(fù)雜度小于O(n方)，我感覺(jué)這個(gè)題應(yīng)該比較復(fù)雜的兔甘，不然題目要求不會(huì)這么簡(jiǎn)單谎碍。不考慮時(shí)間復(fù)雜度的方法就是每一個(gè)數(shù)和其余的異或，有等于0的就是這個(gè)數(shù)重復(fù)了洞焙。但是現(xiàn)在我說(shuō)這么多都被pass了蟆淀，我再好好想想怎么實(shí)現(xiàn)吧。
emmm..暫時(shí)沒(méi)思路澡匪，我用雙層循環(huán)試了下熔任，雖然性能不能看，但是居然沒(méi)超時(shí)通過(guò)了唁情，也挺有意思疑苔。

class Solution {
    public int findDuplicate(int[] nums) {
        for(int i = 0;i<nums.length-1;i++){
            for(int j = i+1;j<nums.length;j++){
                if(nums[i]==nums[j]) return nums[i];
            }
        }
        return -1;
    }
}

不過(guò)其實(shí)我覺(jué)得這個(gè)標(biāo)準(zhǔn)上不會(huì)到O(n方)，但是性能差成這樣甸鸟，我覺(jué)得正確答案可能是O(n)左右惦费，O（n）的實(shí)現(xiàn)方式兵迅。。我想想薪贫。其實(shí)目前還有個(gè)想法恍箭，就是二進(jìn)制的每一個(gè)的個(gè)數(shù)。正常如果是順序來(lái)的后雷，二進(jìn)制的數(shù)應(yīng)該是一定的季惯。比如1,10,11連著的數(shù)每一位都是2個(gè)1.如果變成10，10臀突，11就變成了第二位3個(gè)1勉抓，第一位1個(gè)。這樣很明顯就是第二位的1多了一個(gè)候学，第一位少了一個(gè)1.所以重復(fù)的數(shù)是10.藕筋。。但是這個(gè)是我粗略的想法梳码， 而且我二進(jìn)制運(yùn)算是真的渣隐圾。。我先進(jìn)來(lái)去考慮下這個(gè)思路的可性能吧掰茶。
好吧暇藏，簡(jiǎn)單百度了下，這個(gè)方法最大的問(wèn)題需要存儲(chǔ)每一個(gè)二進(jìn)制位的1的個(gè)數(shù)濒蒋。盐碱。用到了數(shù)組，題目不讓用額外空間沪伙，所以這個(gè)思路就這么pass了瓮顽。我再繼續(xù)想想吧。
我看了題解围橡，真的大把大把掉頭發(fā)也沒(méi)想出來(lái)暖混。。然后看了題解還要理解好久翁授。拣播。真的是覺(jué)得自己越來(lái)越菜了。
哎收擦，簡(jiǎn)單說(shuō)下對(duì)題解的理解吧诫尽。主要分兩部分：

鏈表成環(huán)

明明題目是數(shù)組，為什么說(shuō)到鏈表了呢炬守？其實(shí)數(shù)組的下標(biāo)和數(shù)值可以組成一個(gè)鏈表的。數(shù)值是下一個(gè)鏈表的指針剂跟。下標(biāo)作為當(dāng)前鏈表的值就可以了啊减途。
我先畫(huà)個(gè)圖大概理解下怎么把數(shù)組理解成鏈表

數(shù)組抽象成鏈表

如上圖酣藻，其實(shí)我一開(kāi)始看的時(shí)候也不太理解，但是畫(huà)了幾個(gè)圖才發(fā)現(xiàn)鳍置，鏈表一定是有環(huán)的辽剧，因?yàn)橄聵?biāo)是從0開(kāi)始，而數(shù)值是從1開(kāi)始税产。所以第一步一定是能走出去的怕轿！
這個(gè)時(shí)候指針已經(jīng)指向下一個(gè)了，像8這種自循環(huán)的不會(huì)被指到辟拷，所以也不會(huì)是重復(fù)的值撞羽。我們只要順著指針往下指，哪怕指到自循環(huán)了那么更好了衫冻，直接說(shuō)明這個(gè)數(shù)重復(fù)出現(xiàn)了（別的下標(biāo)有這個(gè)值诀紊，這個(gè)下標(biāo)還是這個(gè)值，直接就是出現(xiàn)了兩次嘛Ｓ绶）
所以放心邻奠，只要有重復(fù)的值，肯定是有環(huán)的为居。我們現(xiàn)在要做的是從起點(diǎn)開(kāi)始碌宴，快慢指針找到環(huán)的交點(diǎn)！

環(huán)的起點(diǎn)

其實(shí)這個(gè)題我們做過(guò)的蒙畴，當(dāng)時(shí)我也是理解起來(lái)比較慢還手動(dòng)畫(huà)了個(gè)圖贰镣，就是怎么根據(jù)環(huán)的交點(diǎn)判斷起點(diǎn)的，這里也貼一下：

快慢指針從交點(diǎn)找環(huán)起點(diǎn)

如圖忍抽，紅色是慢指針八孝，紅+綠是快指針。因?yàn)榭熘羔樢淮蝺蓚€(gè)鸠项，慢指針一次一個(gè)干跛。所以紅色和綠色是相等的。
然后因?yàn)榄h(huán)的起點(diǎn)到交點(diǎn)是一一段共同路徑（慢指針走一遍祟绊，快指針走了兩遍）楼入，所以紅色實(shí)線和綠色實(shí)線也是相等的。
此時(shí)如果快指針從b開(kāi)始牧抽，再來(lái)一個(gè)指針從起點(diǎn)開(kāi)始相同速度走嘉熊，最終實(shí)線會(huì)同時(shí)走完，并且兩個(gè)指針肯定相交在環(huán)的入口處扬舒。

所以這道題就分兩步：找到環(huán)形交點(diǎn)阐肤，找到環(huán)的起點(diǎn)。
環(huán)的起點(diǎn)就是這個(gè)重復(fù)元素。
我去寫(xiě)代碼了：

class Solution {
    public int findDuplicate(int[] nums) {
        int slow = 0;
        int fast = 0;
        while(true){
            slow = nums[slow];
            //這個(gè)下標(biāo)的下標(biāo)就相當(dāng)于走了兩步
            fast = nums[nums[fast]];
            if(slow == fast){//相交了
                fast = 0;//從頭開(kāi)始走
                while(slow != fast){//slow == fast 說(shuō)明相交于環(huán)的起點(diǎn)了
                    fast = nums[fast];
                    slow = nums[slow];
                }
                return slow;
            }

        }
    }
}

思路清晰了代碼其實(shí)不難孕惜，不過(guò)我還是調(diào)試了很多次愧薛，關(guān)于slow值和nums[slow]這類(lèi)的，while條件是帶nums[slow]這類(lèi)的衫画，返回也要這要的毫炉，比較的是直接量，返回的也要是削罩，只要統(tǒng)一了就行了瞄勾。
這個(gè)題乍一看簡(jiǎn)單，所有的約束條件都用上了的話真的有點(diǎn)燒腦啊弥激，其實(shí)環(huán)找入口不用額外空間是做過(guò)的进陡，但是沒(méi)和這個(gè)題聯(lián)系起來(lái)。還是做題少秆撮，見(jiàn)得少四濒。這個(gè)題就這樣了，繼續(xù)往下刷題职辨。

生命游戲

題目：根據(jù)百度百科盗蟆，生命游戲，簡(jiǎn)稱(chēng)為生命舒裤，是英國(guó)數(shù)學(xué)家約翰·何頓·康威在1970年發(fā)明的細(xì)胞自動(dòng)機(jī)喳资。

給定一個(gè)包含 m × n 個(gè)格子的面板，每一個(gè)格子都可以看成是一個(gè)細(xì)胞腾供。每個(gè)細(xì)胞具有一個(gè)初始狀態(tài) live（1）即為活細(xì)胞仆邓， 或 dead（0）即為死細(xì)胞。每個(gè)細(xì)胞與其八個(gè)相鄰位置（水平伴鳖，垂直节值，對(duì)角線）的細(xì)胞都遵循以下四條生存定律：

如果活細(xì)胞周?chē)藗€(gè)位置的活細(xì)胞數(shù)少于兩個(gè)，則該位置活細(xì)胞死亡榜聂；

如果活細(xì)胞周?chē)藗€(gè)位置有兩個(gè)或三個(gè)活細(xì)胞搞疗，則該位置活細(xì)胞仍然存活；

如果活細(xì)胞周?chē)藗€(gè)位置有超過(guò)三個(gè)活細(xì)胞须肆，則該位置活細(xì)胞死亡匿乃；

如果死細(xì)胞周?chē)糜腥齻€(gè)活細(xì)胞，則該位置死細(xì)胞復(fù)活豌汇；

根據(jù)當(dāng)前狀態(tài)幢炸，寫(xiě)一個(gè)函數(shù)來(lái)計(jì)算面板上細(xì)胞的下一個(gè)（一次更新后的）狀態(tài)。下一個(gè)狀態(tài)是通過(guò)將上述規(guī)則同時(shí)應(yīng)用于當(dāng)前狀態(tài)下的每個(gè)細(xì)胞所形成的拒贱，其中細(xì)胞的出生和死亡是同時(shí)發(fā)生的宛徊。

示例:
輸入:
[
[0,1,0],
[0,0,1],
[1,1,1],
[0,0,0]
]
輸出:
[
[0,0,0],
[1,0,1],
[0,1,1],
[0,1,0]
]
進(jìn)階:
你可以使用原地算法解決本題嗎佛嬉？請(qǐng)注意，面板上所有格子需要同時(shí)被更新：你不能先更新某些格子闸天，然后使用它們的更新后的值再更新其他格子巷燥。
本題中，我們使用二維數(shù)組來(lái)表示面板号枕。原則上，面板是無(wú)限的陨享，但當(dāng)活細(xì)胞侵占了面板邊界時(shí)會(huì)造成問(wèn)題葱淳。你將如何解決這些問(wèn)題？

思路：首先沒(méi)有時(shí)間復(fù)雜度的要求抛姑，我覺(jué)得題目難度少了一半赞厕。至于進(jìn)階的第一個(gè)所謂的同時(shí)，我打算用狀態(tài)來(lái)區(qū)分定硝。比如之前是1.要變成0.我就給變成-1.這樣他周?chē)奈揖椭肋@個(gè)數(shù)是1了皿桑，之前是0要變成1，我就先變?yōu)?2.這樣周?chē)簿瓦@道這個(gè)數(shù)是0了蔬啡。最后都走完了我再遍歷一次诲侮，是-1的改成0.是-2的改成1.嘖嘖，我覺(jué)得這個(gè)想法一點(diǎn)問(wèn)題沒(méi)有箱蟆。至于第二個(gè)邊界問(wèn)題沟绪，，空猜，說(shuō)實(shí)話我沒(méi)太看懂绽慈，所以這里就先不想了，我去代碼實(shí)現(xiàn)下試試辈毯。
思路完全沒(méi)問(wèn)題坝疼，代碼性能超過(guò)百分百，有點(diǎn)小興奮谆沃，雖然寫(xiě)著確實(shí)有點(diǎn)麻煩钝凶，哈哈。我直接貼代碼了：

class Solution {
    public void gameOfLife(int[][] board) {
        if(board.length==0 || board[0].length==0) return;
        //0變1先變成-1   1變0先變成 -2
        for(int i = 0;i<board.length;i++){
            for(int j = 0;j<board[0].length;j++){
                int n = isLive(board,i,j);
                if(board[i][j]==0){
                    //死變活現(xiàn)先變-1
                    if(n==3) board[i][j] = -1;
                }
                if(board[i][j]==1){
                    //活變死
                    if(n<2 || n>3) board[i][j] = -2;
                }               
            }
        }
        for(int i = 0;i<board.length;i++){
            for(int j = 0;j<board[0].length;j++){
                if(board[i][j]==-1) board[i][j] = 1;
                else if(board[i][j]==-2) board[i][j] = 0;
            }
        }

    }
    public int isLive(int[][] board,int i,int j){
        //判斷周?chē)罴?xì)胞的個(gè)數(shù)
        int n = 0;
        for(int k = i-1;k<=i+1;k++ ){
            for(int r = j-1;r<=j+1;r++){
                if(k==i && r==j) continue;
                if(k>=0 && k<board.length && r>=0 && r<board[0].length &&
                (board[k][r]==1 || board[k][r]==-2)) n++;
            }
        }
        return n;
    }
}

因?yàn)橐郧白龆S數(shù)組的擴(kuò)散管毙，像素啥的用過(guò)這樣的辦法腿椎，所以這里直接封裝了個(gè)判斷上下左右對(duì)角線活著的細(xì)胞數(shù)量的方法（其實(shí)拆開(kāi)是四層循環(huán)）。
然后細(xì)心耐心就好了夭咬，這個(gè)題不難啃炸，但是很可能一個(gè)字母錯(cuò)了就調(diào)試好久，比如我一開(kāi)始isLive中第二層循環(huán)是r=j-i卓舵。真的是看瞎眼了南用，調(diào)試兩邊才抓到這個(gè)錯(cuò)的，哈哈
今天的筆記就記到這里，如果稍微幫到你了記得點(diǎn)個(gè)喜歡點(diǎn)個(gè)關(guān)注裹虫。也祝大家工作順順利利Ｖ壮啊（ps：打個(gè)廣告：Java技術(shù)交流群：130031711，歡迎各位踴躍加入筑公。）