p/npra3y

沐茗@蛸達

@blue61

Sun, Mar 1, 2020 4:01 AM

1

[Leetcode 讀書會][week 5][2/22 ~ 2/28]
37, 39 ~ 42
medium: 39, 40
hard: 37, 41, 42

資訊展

@kevingyc

Sun, Mar 1, 2020 4:05 AM

公司辦的嗎？

沐茗@蛸達

@blue61

Sun, Mar 1, 2020 4:06 AM

資訊展 : 不是诶，網友揪的

沐茗@蛸達

@blue61

Sun, Mar 1, 2020 4:41 AM

problem 37. Sudoku Solver
my soultion
[Hard]
解數獨
用36題的檢查方式暴力遞回解

沐茗@蛸達

@blue61

Sun, Mar 1, 2020 4:49 AM

problem 39. Combination Sum
my soultion
[Medium]
給定經過排序的數列與一個目標，找出所有加起來等於目標的可能組合
例如給2,3,6,7，就有可能是7或2+2+3兩種，都要找出來

沐茗@蛸達

@blue61

Sun, Mar 1, 2020 4:49 AM

解：還是用遞回
Step 1. 記錄"還差多少達標"，以下用"餘"來表示(上例是7
Step 2. 從最大的數字開始往回找，用遞回同時2.a跟2.b兩條路
Step 2.a. 如果"餘"砍掉一次目前的數字，
Step 2.a.i. 如果發現"餘"是0，表示找到解，記錄並終止這條路線
Step 2.a.ii. 如果發現"餘"大於0，回到2
Step 2.b. 跳過現在的數字，檢查更小的一個數字，回到2

沐茗@蛸達

@blue61

Sun, Mar 1, 2020 4:51 AM

problem 40. Combination Sum II
my soultion
[Medium]
跟39差不多的題目，但是這次給的數字沒有排序而且每個數字只能用一次，但可能會出現重複的數字
解：跟39相同，排序，燃後2不管走哪條都要跳到下一個數字，且要記得檢查重複的解

沐茗@蛸達

@blue61

Sun, Mar 1, 2020 4:54 AM

problem 41. First Missing Positive
my soultion
[Hard]
......Hard?
從一堆數字中找出最小的未出現的正整數。
排序 → 從最小的開始檢查是不是1，如果是，往下檢查2，如果不是，找下一個數字
......Hard!?!?

沐茗@蛸達

@blue61

Sun, Mar 1, 2020 4:58 AM

problem 42. Trapping Rain Water
my soultion
[Hard]
好玩的題目!!

給一排不同高度的牆壁，檢查把中間填滿水需要多少水

https://imgs.plurk.com/Qy7/UeT/WsF4BfSzx3o68y3Ha07UR5ZsX8N_lg.png

解：用一個table來記錄目前最高的牆壁高度，以及之後遞減的牆壁高度
> 當新出現的牆壁比目前最大的牆壁大的時後，從上一個最大的牆壁往後填水，並更新table
> 當新出現的牆壁比目前最小的牆壁小的時後，加在後面記錄下來
> 當新出現的牆壁比目前最小的牆壁大的時後，從最新的牆壁往回填水，並更新table

沐茗@蛸達

@blue61

Sun, Mar 1, 2020 4:58 AM

===