60-Day LeetCoding Challenge (Math)

開始挑戰Ｍath 這個分類的題目，一樣是參考網路上已經有整理的 Leetcode 分类顺序表。

參考的頻道或部落格條列如下，提供給大家參考：
ＹＴ：花花醬 / Cspiration 官方频道 / Jacob Huang ／basketwangCoding／今天比昨天厲害／来Offer – LaiOffer／小Q刷Leetcode
Ｂlog：Grandyang／

這篇基本上就是總覽，把解題過程的思路和參考的講解視頻以及其他參考資料都整理在下面。

[2020/11/20] 這個類型花了一個月，其實大部分時間都蠻偷懶的，真正寫的時間不多，但也寫完Ｍath 這個分類，總計３０題：１５Ｅ、１５Ｍ。
這個類型真的比較偏數學，需要思考一些相關公式，相較於前面兩個單元比較沒有那麼有趣，不過還是可以拿來練練手感。

No.	完成日期	難易度	Leetcode Link	網路講解視頻	Ｍｅｍｏ
1	2020/10/18	Easy	7. Reverse Integer	Leetcode : 7. Reverse Integer 讲解	將給定整數反轉這題之前在判斷數字是否回文的時候有遇過，9. Palindrome Number，不過這次要處理負數，且需要記得處理超界的Ｃａｓｅ。
2		Medium	165. Compare Version Numbers	贾考博 LeetCode 165. Compare Version Numbers 如果版本都搞错了，还开发个啥 [LeetCode] Compare Version Numbers 版本比较	比較版本號碼先用點把數字一段一段切開，轉成整數後一個一個開始比較。
3		Easy	66. Plus One	贾考博 LeetCode 66. Plus One [LeetCode] Plus One 加一运算	將給定整數字串＋１因為輸入 `1 <= digits.length <= 100`，這題需要針對字串來處理。首先先判斷是否要進位，如果要的話該位＝０，繼續往前加；如果不需要進位，則直接回傳最後一個字元加一的結果。當整個字串遍歷完還沒 return，即表示需要在最前面多加一位元１。
4		Medium	8. String to Integer (atoi)	[LeetCode] 8. String to Integer (atoi) 字符串转为整数	把字符串轉成整數這題跟 65. Valid Number 判斷是否為有效數字相同，但相較下更單純只要判斷正負／找出數字區間／避免 overflow 即可。
5		Easy	258. Add Digits	[LeetCode] Add Digits 加数字	求數根：將每一位數相加，直到剩下個位數直接計算就是把每個位數相加，如果還是大於 10 則繼續直到只有一個位數。進階一點題目要求Ｏ(１)時間，那就是考樹根的定義 dr(n)=0, if n=0 dr(n)=9, if n=9k dr(n) = n mod 9, if n != 9k 直接 num == 0 ? 0 : (num – 1) % 9 + 1; 一行解決
6	2020/10/20	Easy	67. Add Binary	贾考博 LeetCode 67. Add Binary [LeetCode] Add Binary 二进制数相加	相加兩給定字串宣告兩個指針指向字串最後一位，每次取一個出來轉成數字，如果已經取完則等於０。另外宣告 carry 變數，初始化０。把兩個數字及 carry 加起來，取餘數等於當前位值，取商等於是否進位，最後在判斷是否有 carry 另外加上。
7		Medium	43. Multiply Strings	[Leetcode 43] Multiply Strings [LeetCode] 43. Multiply Strings 字符串相乘	相乘兩給定字串兩字串相乘，最大長度就是兩個的長度和。根據乘法計算原理，從最後的位數開始往前乘，並加上目前位元的值（上一 run 的進位）訂一個 lo 存餘數，hi 存進位。最後再遍歷結果把 leading zero 去掉即可。
8		Easy	367. Valid Perfect Square	[LeetCode] 367. Valid Perfect Square 检验完全平方数	檢驗完全平方數確認一個數是否為平方，使用二分查找或是找小於平方根的都可以，參考旁邊的連結有多種解法。另外一個是反平方根快速演算法，竟然可以在Ｏ(１)時間中找到。
9		Easy	204. Count Primes	[LeetCode] 204. Count Primes 质数的个数	判斷有幾個質數厄拉托西尼快速篩選出質數：先宣告一個Ｎ大小陣列初始成Ｔ，找到Ｔ後把後面他的倍數都標成Ｆ，如此一來即可先把非質數的篩出來跳過了。
10		Easy	1. Two Sum	[LeetCode] 1. Two Sum 两数之和	找出給定陣列中相加＝Ｔarget 的兩個數字用 map 紀錄＆查找看是否出現過符合的值
11		Easy	167. Two Sum II – Input array is sorted	[LeetCode] Two Sum II – Input array is sorted 两数之和之二 – 输入数组有序	找出給定陣列中相加＝Ｔarget 的兩個數字基本上與上一題相同，差異在要輸出的 index 是從１開始計算＆index 小的排前面。另外也可以用２ptr 來解，一個從前往後一個從後往前。
12	2020/10/21	Medium	15. 3Sum	Leetcode : 15 3Sum 讲解 [Leetcode 15]3Sum	找出給定陣列中相加＝０的三個數字先將字串排序，從第一個開始當 base ＆使用２ptr 遍歷後面找出相加＝０的組合。需要注意的是指針移動時需要跳過與當前相同的，才不會重複計算。
13		Medium	16. 3Sum Closest	[LeetCode] 16. 3Sum Closest 最近三数之和	找出給定陣列中相加最接近Ｔarget 的三個數字和等同於上一題，新增一個 diff 變數記錄目前的最小值，以及一個 closet 紀錄 diff 為最小值的和。
14		Medium	18. 4Sum	Leetcode： 18 4Sum 讲解贾考博 LeetCode 18. 4Sum [LeetCode] 18. 4Sum 四数之和	找出給定陣列中相加＝０的四個數字與 3Sum 類似，外面再套一層就可以解 4Sum。
15		Easy	231. Power of Two	[LeetCode] Power of Two 判断2的次方数	判斷給定數字是否為２的次方一個方式是直接／２，看是否有餘數；但這種方式較耗時，直接 bit operation：該數字−１再 or 自己會等於０。
16		Easy	326. Power of Three	[LeetCode] Power of Three 判断3的次方数	判斷給定數字是否為３的次方直接／３，看是否有餘數，如果想看其他數學方式可參考旁邊的連結。
17		Easy	342. Power of Four	[LeetCode] Power of Four 判断4的次方数	判斷給定數字是否為４的次方直接／４，看是否有餘數，如果想看其他數學方式可參考旁邊的連結。
18		Easy	202. Happy Number	[LeetCode] Happy Number 快乐数	判斷給定數字是否為快樂數（把每個 bit 平方和加起來最後會得到１）用一個Ｓet 存出現過的數，如果有重複則表示不是，如果得到１表示是。
19		Easy	263. Ugly Number	[LeetCode] 263. Ugly Number 丑陋数	判斷給定數字是否為醜陋數（只有２３５這三個質因數）假設是上述的倍數就一直除，最後看剩下的是否＝１
20	2020/11/15	Medium	264. Ugly Number II	[LeetCode] 264. Ugly Number II 丑陋数之二	求給定的第幾個醜陋數從子列表中依序乘過２３５，把最小的存入陣列中，最後回傳陣列最後一個值。
21		Easy	172. Factorial Trailing Zeroes	[LeetCode] 172. Factorial Trailing Zeroes 求阶乘末尾零的个数	求階乘後面零的個數本來想先乘開再％１０，但直接 Overflow。後來發現其實就是找有幾個５。
22		Medium	343. Integer Break	[LeetCode] 343. Integer Break 整数拆分	整數拆分，給定一個整數，將它拆成至少兩個整數和，且乘積最大觀察規律會發現從５開始以三個為一組，５／６／７分別是３＊２ or ３ or ４８／９／１０分別是３＊３＊２ or ３ or ４所以先把有幾個３拆出來，乘上最後剩下的２ or ３ or ４即可。
23	2020/11/16	Medium	386. Lexicographical Numbers	[LeetCode] Lexicographical Numbers 字典顺序的数字 7 lines simple C++ recursive solution	依字典順序列出數字題目給定一個數字Ｎ，需要將［１～Ｎ］依照字母順序排列。參考討論區解法，從１開始先乘１０，超過Ｎ之後若個位數非９則加一繼續這個循環。 EX 13 遍歷過程為：1 -> 10 -> (100) -> 11 -> (110) -> 12 -> (120) -> 13 -> (130) -> (14) -> 2 -> (20) … -> 9 -> (90)
24		Medium	396. Rotate Function	[LeetCode] Rotate Function 旋转函数	旋轉函數給定一個陣列，將陣列不斷往右移，找出ｉ＊Ａ［ｉ］的最大和。參考答案可以發現這個題目有以下規律： F(0) = 0A + 1B + 2C +3D F(1) = 0D + 1A + 2B +3C F(2) = 0C + 1D + 2A +3B F(3) = 0B + 1C + 2D +3A sum = 1A + 1B + 1C + 1D F(1) = F(0) + sum – 4D F(2) = F(1) + sum – 4C F(3) = F(2) + sum – 4B F(i) = F(i-1) + sum – n*A[n-i]
25	2020/11/17	Medium	397. Integer Replacement	[LeetCode] Integer Replacement 整数替换	整數替換給定一整數Ｎ，偶數就／２；奇數可選＋１or −１，求變成１的最小步數可用遞迴求解如果＝１回傳０；如果是偶數，回傳１＋除以２的最小步數；如果是奇數，回傳２＋ min (（ｔ＋１）除以２的步數,（ｔ−１）除以２的步數）奇數要另外用 long long ｔ＝Ｎ來處理，ｔ＋１）除以２也是都是為了避免Ｎ＝INT_MAX 時超界。
26		Medium	368. Largest Divisible Subset	[LeetCode] Largest Divisible Subset 最大可整除的子集合	給一整數字串，找出彼此都可以整除的最大子集合終於又遇到ＤＰ題了，第一層從ｉ＝ｎ～０往前移動，第二層ｊ＝ｉ～ｎ往後移動，找出ｉ～Ｎ中是否有ｉ的倍數。如果有，根據 dp 確認子字串長度是否較大，如果是將ｉ的 parent 填為ｊ同時宣告變數存目前掃到的最大子字串長度，與當下的起始點。最後再從起始點開始建子集合即可。
27		Medium	357. Count Numbers with Unique Digits	[LeetCode] Count Numbers with Unique Digits 计算各位不相同的数字个数	給定Ｎ，計算０～Ｎ中各位數皆不同的數字有幾個有個公式如下，可以透過這個把符合的加總起來 f(1) = 10, …, f(k) = 9 * 9 * 8 * … (9 – k + 2)
28	2020/11/19	Medium	29. Divide Two Integers	[LeetCode] 29. Divide Two Integers 两数相除	求兩數相除的商（取整數），但不能用到減法除法與％這題可以用 bit operation 來處理，宣告一個ｔ＝除數，ｐ用來計數當被除數＞（ｔ＜＜１）ｔ＜＜＝１；ｐ＜＜＝１，這樣可以先算出有幾個除數接著再把被除數−ｔ也丟下去再遞迴計算，直到被除數小於除數。需要注意的是正負號的判斷，以及如果 overflow 就直接回傳ＩＭＴ＿ＭＡＸ
29		Easy	69. Sqrt(x)	[LeetCode] 69. Sqrt(x) 求平方根	求平方根（取整數）可以用ＢＳ從０～Ｘ找到ｔ平方＜Ｘ但＋１就大於的點。注意 overflow，可以用 long 或是除法。
30		Medium	50. Pow(x, n)	[LeetCode] 50. Pow(x, n) 求x的n次方 Leetcode 50：Pow(x, n)（超详细的解法！！！）	求Ｘ的Ｎ次方直接暴力解會超時，這題用到一個想法，是Ｎ每次／２，直到變成０假設是奇數次方每次都乘上當下的Ｘ，Ｘ在自乘變平方。最後判斷Ｎ正負選擇直接回傳或是倒數。

倒讚＞讚，之後再考慮回來刷：

390. Elimination Game
365. Water and Jug Problem
372. Super Pow
233. Number of Digit One
319. Bulb Switcher
292. Nim Game
400. Nth Digit
306. Additive Number

發佈留言 取消回覆

發佈留言取消回覆