開始挑戰 Math 這個分類的題目,一樣是參考網路上已經有整理的 Leetcode 分类顺序表。
參考的頻道或部落格條列如下,提供給大家參考:
YT:花花醬 / Cspiration 官方频道 / Jacob Huang /basketwangCoding/今天比昨天厲害/来Offer – LaiOffer/小Q刷Leetcode
Blog:Grandyang/
這篇基本上就是總覽,把解題過程的思路和參考的講解視頻以及其他參考資料都整理在下面。
[2020/11/20] 這個類型花了一個月,其實大部分時間都蠻偷懶的,真正寫的時間不多,但也寫完Math 這個分類,總計30題:15E、15M。
這個類型真的比較偏數學,需要思考一些相關公式,相較於前面兩個單元比較沒有那麼有趣,不過還是可以拿來練練手感。
No. | 完成日期 | 難易度 | Leetcode Link | 網路講解視頻 | Memo |
1 | 2020/10/18 | Easy | 7. Reverse Integer | Leetcode : 7. Reverse Integer 讲解 | 將給定整數反轉 這題之前在判斷數字是否回文的時候有遇過,9. Palindrome Number,不過這次要處理負數,且需要記得處理超界的Case。 |
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 因為輸入 1 <= digits.length <= 100 ,這題需要針對字串來處理。首先先判斷是否要進位,如果要的話該位=0,繼續往前加;如果不需要進位,則直接回傳最後一個字元加一的結果。當整個字串遍歷完還沒 return,即表示需要在最前面多加一位元1。 | |
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 則繼續直到只有一個位數。 進階一點題目要求O(1)時間,那就是考樹根的定義 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 二进制数相加 | 相加兩給定字串 宣告兩個指針指向字串最後一位,每次取一個出來轉成數字,如果已經取完則等於0。另外宣告 carry 變數,初始化0。把兩個數字及 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 检验完全平方数 | 檢驗完全平方數 確認一個數是否為平方,使用二分查找或是找小於平方根的都可以,參考旁邊的連結有多種解法。 另外一個是 反平方根快速演算法,竟然可以在O(1)時間中找到。 | |
9 | Easy | 204. Count Primes | [LeetCode] 204. Count Primes 质数的个数 | 判斷有幾個質數 厄拉托西尼 快速篩選出質數:先宣告一個N大小陣列初始成T,找到T後把後面他的倍數都標成F,如此一來即可先把非質數的篩出來跳過了。 | |
10 | Easy | 1. Two Sum | [LeetCode] 1. Two Sum 两数之和 | 找出給定陣列中相加=Target 的兩個數字 用 map 紀錄&查找看是否出現過符合的值 | |
11 | Easy | 167. Two Sum II – Input array is sorted | [LeetCode] Two Sum II – Input array is sorted 两数之和之二 – 输入数组有序 | 找出給定陣列中相加=Target 的兩個數字 基本上與上一題相同,差異在要輸出的 index 是從1開始計算&index 小的排前面。 另外也可以用2ptr 來解,一個從前往後一個從後往前。 | |
12 | 2020/10/21 | Medium | 15. 3Sum | Leetcode : 15 3Sum 讲解 [Leetcode 15]3Sum | 找出給定陣列中相加=0的三個數字 先將字串排序,從第一個開始當 base & 使用2ptr 遍歷後面找出相加=0的組合。 需要注意的是指針移動時需要跳過與當前相同的,才不會重複計算。 |
13 | Medium | 16. 3Sum Closest | [LeetCode] 16. 3Sum Closest 最近三数之和 | 找出給定陣列中相加最接近Target 的三個數字和 等同於上一題,新增一個 diff 變數記錄目前的最小值,以及一個 closet 紀錄 diff 為最小值的和。 | |
14 | Medium | 18. 4Sum | Leetcode: 18 4Sum 讲解 贾考博 LeetCode 18. 4Sum [LeetCode] 18. 4Sum 四数之和 | 找出給定陣列中相加=0的四個數字 與 3Sum 類似,外面再套一層就可以解 4Sum。 | |
15 | Easy | 231. Power of Two | [LeetCode] Power of Two 判断2的次方数 | 判斷給定數字是否為2的次方 一個方式是直接/2,看是否有餘數;但這種方式較耗時,直接 bit operation:該數字−1再 or 自己會等於0。 | |
16 | Easy | 326. Power of Three | [LeetCode] Power of Three 判断3的次方数 | 判斷給定數字是否為3的次方 直接/3,看是否有餘數,如果想看其他數學方式可參考旁邊的連結。 | |
17 | Easy | 342. Power of Four | [LeetCode] Power of Four 判断4的次方数 | 判斷給定數字是否為4的次方 直接/4,看是否有餘數,如果想看其他數學方式可參考旁邊的連結。 | |
18 | Easy | 202. Happy Number | [LeetCode] Happy Number 快乐数 | 判斷給定數字是否為快樂數(把每個 bit 平方和加起來最後會得到1) 用一個Set 存出現過的數,如果有重複則表示不是,如果得到1表示是。 | |
19 | Easy | 263. Ugly Number | [LeetCode] 263. Ugly Number 丑陋数 | 判斷給定數字是否為醜陋數(只有235這三個質因數) 假設是上述的倍數就一直除,最後看剩下的是否=1 | |
20 | 2020/11/15 | Medium | 264. Ugly Number II | [LeetCode] 264. Ugly Number II 丑陋数之二 | 求給定的第幾個醜陋數 從子列表中依序乘過235,把最小的存入陣列中,最後回傳陣列最後一個值。 |
21 | Easy | 172. Factorial Trailing Zeroes | [LeetCode] 172. Factorial Trailing Zeroes 求阶乘末尾零的个数 | 求階乘後面零的個數 本來想先乘開再%10,但直接 Overflow。後來發現其實就是找有幾個5。 | |
22 | Medium | 343. Integer Break | [LeetCode] 343. Integer Break 整数拆分 | 整數拆分,給定一個整數,將它拆成至少兩個整數和,且乘積最大 觀察規律會發現從5開始以三個為一組,5/6/7分別是3*2 or 3 or 4 8/9/10分別是3*3*2 or 3 or 4 所以先把有幾個3拆出來,乘上最後剩下的2 or 3 or 4即可。 | |
23 | 2020/11/16 | Medium | 386. Lexicographical Numbers | [LeetCode] Lexicographical Numbers 字典顺序的数字 7 lines simple C++ recursive solution | 依字典順序列出數字 題目給定一個數字N,需要將[1~N]依照字母順序排列。參考討論區解法,從1開始先乘10,超過N之後若個位數非9則加一繼續這個循環。 EX 13 遍歷過程為:1 -> 10 -> (100) -> 11 -> (110) -> 12 -> (120) -> 13 -> (130) -> (14) -> 2 -> (20) … -> 9 -> (90) |
24 | Medium | 396. Rotate Function | [LeetCode] Rotate Function 旋转函数 | 旋轉函數 給定一個陣列,將陣列不斷往右移,找出i*A[i]的最大和。參考答案可以發現這個題目有以下規律: 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 整数替换 | 整數替換 給定一整數N,偶數就/2;奇數可選+1or −1,求變成1的最小步數 可用遞迴求解 如果=1回傳0;如果是偶數,回傳1+除以2的最小步數; 如果是奇數,回傳2+ min ((t+1)除以2的步數,(t−1)除以2的步數) 奇數要另外用 long long t=N來處理,t+1)除以2也是都是為了避免 N=INT_MAX 時超界。 |
26 | Medium | 368. Largest Divisible Subset | [LeetCode] Largest Divisible Subset 最大可整除的子集合 | 給一整數字串,找出彼此都可以整除的最大子集合 終於又遇到DP題了,第一層從i=n~0往前移動,第二層j=i~n往後移動,找出i~N中是否有i的倍數。 如果有,根據 dp 確認子字串長度是否較大,如果是將i的 parent 填為j 同時宣告變數存目前掃到的最大子字串長度,與當下的起始點。 最後再從起始點開始建子集合即可。 | |
27 | Medium | 357. Count Numbers with Unique Digits | [LeetCode] Count Numbers with Unique Digits 计算各位不相同的数字个数 | 給定N,計算0~N中各位數皆不同的數字有幾個 有個公式如下,可以透過這個把符合的加總起來 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 來處理,宣告一個t=除數,p用來計數 當被除數>(t<<1)t<<=1;p<<=1,這樣可以先算出有幾個除數 接著再把被除數−t也丟下去再遞迴計算,直到被除數小於除數。 需要注意的是正負號的判斷,以及如果 overflow 就直接回傳IMT_MAX |
29 | Easy | 69. Sqrt(x) | [LeetCode] 69. Sqrt(x) 求平方根 | 求平方根(取整數) 可以用BS從0~X找到t平方<X但+1就大於的點。注意 overflow,可以用 long 或是除法。 | |
30 | Medium | 50. Pow(x, n) | [LeetCode] 50. Pow(x, n) 求x的n次方 Leetcode 50:Pow(x, n)(超详细的解法!!!) | 求X的N次方 直接暴力解會超時,這題用到一個想法,是N每次/2,直到變成0 假設是奇數次方每次都乘上當下的X,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