刷leetCode算法題+解析(二)

因為上一張墨跡了好多,加上那道題是中等難度的级解,我自己捋思路也比較墨跡,不過今天刷的都是簡單的抡爹,很容易理解啦芒划。
目前個人計劃是一天刷3——5題左右欧穴。

兩數(shù)之和

這個其實我覺得是最簡單的一個苔可,雖然我的答案也不怎么好(看了解析才覺得自己想法賊麻煩)

題目:給定一個整數(shù)數(shù)組 nums 和一個目標(biāo)值 target袋狞,請你在該數(shù)組中找出和為目標(biāo)值的那 兩個 整數(shù),并返回他們的數(shù)組下標(biāo)同蜻。你可以假設(shè)每種輸入只會對應(yīng)一個答案早处。但是,你不能重復(fù)利用這個數(shù)組中同樣的元素默责。

示例:
給定 nums = [2, 7, 11, 15], target = 9
因為 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

思路:這個題其實很好理解咸包,然后我一開始審題就定了兩個思路:一個是遍歷數(shù)組兩兩相加烂瘫,直到結(jié)果是target為止,另一個就是把target拆分成兩個數(shù)字坟比,一組組去數(shù)組判斷葛账,直到某組存在為止。
下面的是我沒有看解析的 代碼:

    public int[] twoSum(int[] nums, int target) {
        //兩種思路:首先因為nums是整數(shù)數(shù)組籍琳,target也是整數(shù)巩割,所以一種是nums中兩兩相加,當(dāng)結(jié)果為target時找到了想要的 愈犹,另一種target拆分都可以?+勋颖?勋锤,判斷這兩個數(shù)字是否在nums中都存在,如果遇到都存在的茄厘,也找到了想要的答案谈宛。
    int length = nums.length;
    int[] result = new int[2];
    //遍歷數(shù)組,兩兩相加
    for(int i = 0;i<length;i++){
        //因為i是從第一個開始循環(huán)窑滞,所以j直接從第二個開始就可以了恢筝,畢竟一個數(shù)只能用一次
        for(int j=1;j<length;j++){
            if(i==j){
                //因為一個數(shù)只能用一次,所以i==j說明是同一個數(shù)聊训,所以直接跳出恢氯、
                continue;
            }
           if(nums[i]+nums[j]==target){             
               result[0]=i;
               result[1]=j;
               //Q狻B韬颉!這個很重要啸胧,在匹配到之后直接返回幔虏,不然繼續(xù)循環(huán)肯定這兩個數(shù)會反過來
               return result;
           }
        }
    }
     return result;
    }

然后勉強(qiáng)多次踩坑完成了功能的實現(xiàn),(主要坑在了1陷谱,i和j相同的那個continue還有直接找到結(jié)果就return這兩點(diǎn))
再之后看人家的題解,感覺我寫的還是需要?dú)v練吧渣窜。很多細(xì)節(jié)的優(yōu)化我都沒想到宪躯。比如上文的第二個循環(huán)j,我是從1開始详瑞,還自以為已經(jīng)優(yōu)化了冬阳,其實還有更好的解法:就是我們只需要把i和往后的數(shù)字比較就好了肝陪,所以j的取值完全可以是i+1。這樣在數(shù)字多的時候饲常,可以省去大部分沒用的判斷狼讨。

優(yōu)化后的代碼

然后因為我一開始就說了有兩種方法,所以下面是另一種解法(直接是最優(yōu)化的版本了播聪,中間也看了題解優(yōu)化過的):

    public int[] twoSum(int[] nums, int target) {
        //兩種思路:首先因為nums是整數(shù)數(shù)組布隔,target也是整數(shù)衅檀,所以一種是nums中兩兩相加,當(dāng)結(jié)果為target時找到了想要的 沉眶,另一種target拆分都可以杉适?+?传藏,判斷這兩個數(shù)字是否在nums中都存在,如果遇到都存在的哭靖,也找到了想要的答案侈离。
    int length = nums.length;
    int[] result = new int[2];
    Map<Integer,Integer> map = new HashMap<Integer,Integer>();
    for(int i=0;i<length;i++){
        //遍歷數(shù)組,這個說起來有點(diǎn)繞铺坞,但是大概就是把每一個數(shù)字存為map 的key洲胖,下標(biāo)存為value绿映。
        //存的同時用target減去這個數(shù),如果結(jié)果在map中已經(jīng)存在了則說明這兩個數(shù)相加是target叉弦,
        //然后把這兩個數(shù)的下標(biāo)取出來存在result中返回
        //如果數(shù)據(jù)庫中有這個數(shù)的另一半則直接進(jìn)到if中
       if(map.containsKey(target-nums[i])){
           result[0] = map.get(target-nums[i]);
           result[1] = i;
          return result;
       }else{
           //map中沒有這個數(shù)的另一半,所以把這個數(shù)存起來库车。
           map.put(nums[i],i);
       }
    }
     return result;
    }

其實這個要說下題外話樱拴,這兩種方式都是我想出來的,但是U浞弧1窆禽最!看了大佬們的題解之后我反而更加懵了川无,因為什么時間復(fù)雜度,哈希碰撞什么的晾虑,我都快懷疑看了個假題了。
我目前水平有限糙捺,什么是好笙隙?代碼簡潔易懂,什么是性能好签钩?字面上看沒有大循環(huán)小循環(huán)坏快,一層又一層循環(huán)就是好。就比如這兩種方法昧旨,明顯第一種可能執(zhí)行的代碼要比第二種多得多富拗,這不就是好么啃沪。多了不說了,這道題比較簡單缰雇,繼續(xù)下一題追驴。

整數(shù)反轉(zhuǎn)

這個題真的殿雪,一下子又懷疑人生了,心態(tài)太炸了丙曙。

題目:給出一個 32 位的有符號整數(shù)亏镰,你需要將這個整數(shù)中每位上的數(shù)字進(jìn)行反轉(zhuǎn)。

示例 1:
輸入: 123
輸出: 321
示例 2:
輸入: -123
輸出: -321
示例 3:
輸入: 120
輸出: 21
注意:
假設(shè)我們的環(huán)境只能存儲得下 32 位的有符號整數(shù)钧忽,則其數(shù)值范圍為 [?231, 231 ? 1]。請根據(jù)這個假設(shè)桃煎,如果反轉(zhuǎn)后整數(shù)溢出那么就返回 0崎坊。

思路:我不知道是我真的傻還是確實是思維方式?jīng)]練出來奈揍,第一反應(yīng)這道題兩個關(guān)鍵點(diǎn):正負(fù)數(shù),溢出另患。
然後寫了一堆賊SB的代碼:

public int reverse(int x) {
        String s = x+"";
        String[]  arr = s.split("");
        int length =arr.length;
        String result = "";
        boolean flag = false;
        for(int i =0;i<length;i++){
            if("-".equals(arr[i])){
                flag = true;
            }
           //最后一個元素就是length-1蛾绎。
           result += arr[length-1-i]; 
        }
        //如果是負(fù)數(shù)則最后一個是-
        if(flag){
           result = result.replaceAll("-","");
           result = "-"+result;
        }
        //將字符串轉(zhuǎn)成int 租冠,如果溢出會報錯,則返回0
        try{
            int r = Integer.parseInt(result);
            return r;
        }catch(Exception e){
            return 0;
        }       
    }

然後看題解:人家大佬真真正正的三行邏輯代碼纤泵,再多的是符號和定義了。要說多深奧也就罷了,沒接觸到的知識不會還能安慰安慰自己,但是其實看過之后很容易懂公荧,只能覺得自己怎么就想不到循狰?H住朱灿!
貼上大佬的代碼(這段代碼):

    public int reverse(int x) {
        long rs = 0;
        while(x != 0){
            rs = rs*10+x%10;
            x /= 10;
        }
        return (rs<Integer.MIN_VALUE || rs>Integer.MAX_VALUE) ? 0:(int)rs;
    }

看看人家的邏輯D扑摹9蚶恪甸祭!重點(diǎn)是while里面的判斷褥影。x%10獲取的是參數(shù)的尾數(shù),x /= 10因為X是int型校焦,所以自動舍棄尾數(shù)统倒,不用考慮四舍五入。獲取的就是最后一位耸成。然后rs10井氢,在第一位數(shù)無效岳链,因為rs是0,0乘以十還是0,但要是別的位10以后自動把最后一位空了出來左胞。
整體總結(jié):看了能看懂举户,自己想想不出來俭嘁。
我覺得這個就是思路的重要性。
全文手打拐云,對你有幫助麻煩點(diǎn)個喜歡點(diǎn)個關(guān)注啥的,也祝大家工作順順利利近她!

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末叉瘩,一起剝皮案震驚了整個濱河市,隨后出現(xiàn)的幾起案子粘捎,更是在濱河造成了極大的恐慌薇缅,老刑警劉巖危彩,帶你破解...
    沈念sama閱讀 223,207評論 6 521
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異泳桦,居然都是意外死亡汤徽,警方通過查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,455評論 3 400
  • 文/潘曉璐 我一進(jìn)店門灸撰,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人浮毯,你說我怎么就攤上這事完疫。” “怎么了债蓝?”我有些...
    開封第一講書人閱讀 170,031評論 0 366
  • 文/不壞的土叔 我叫張陵趋惨,是天一觀的道長。 經(jīng)常有香客問我惦蚊,道長器虾,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 60,334評論 1 300
  • 正文 為了忘掉前任蹦锋,我火速辦了婚禮兆沙,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘莉掂。我一直安慰自己葛圃,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,322評論 6 398
  • 文/花漫 我一把揭開白布憎妙。 她就那樣靜靜地躺著库正,像睡著了一般。 火紅的嫁衣襯著肌膚如雪厘唾。 梳的紋絲不亂的頭發(fā)上褥符,一...
    開封第一講書人閱讀 52,895評論 1 314
  • 那天,我揣著相機(jī)與錄音抚垃,去河邊找鬼喷楣。 笑死,一個胖子當(dāng)著我的面吹牛鹤树,可吹牛的內(nèi)容都是我干的铣焊。 我是一名探鬼主播,決...
    沈念sama閱讀 41,300評論 3 424
  • 文/蒼蘭香墨 我猛地睜開眼罕伯,長吁一口氣:“原來是場噩夢啊……” “哼曲伊!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起追他,我...
    開封第一講書人閱讀 40,264評論 0 277
  • 序言:老撾萬榮一對情侶失蹤坟募,失蹤者是張志新(化名)和其女友劉穎绽榛,沒想到半個月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體婿屹,經(jīng)...
    沈念sama閱讀 46,784評論 1 321
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,870評論 3 343
  • 正文 我和宋清朗相戀三年推溃,在試婚紗的時候發(fā)現(xiàn)自己被綠了昂利。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,989評論 1 354
  • 序言:一個原本活蹦亂跳的男人離奇死亡铁坎,死狀恐怖蜂奸,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情硬萍,我是刑警寧澤扩所,帶...
    沈念sama閱讀 36,649評論 5 351
  • 正文 年R本政府宣布,位于F島的核電站朴乖,受9級特大地震影響祖屏,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜买羞,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,331評論 3 336
  • 文/蒙蒙 一袁勺、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧畜普,春花似錦期丰、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,814評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至舶衬,卻和暖如春埠通,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背逛犹。 一陣腳步聲響...
    開封第一講書人閱讀 33,940評論 1 275
  • 我被黑心中介騙來泰國打工植阴, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人圾浅。 一個月前我還...
    沈念sama閱讀 49,452評論 3 379
  • 正文 我出身青樓掠手,卻偏偏與公主長得像,于是被迫代替她去往敵國和親狸捕。 傳聞我的和親對象是個殘疾皇子喷鸽,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,995評論 2 361

推薦閱讀更多精彩內(nèi)容