KaiChun Yang

題目連結:492. Construct the Rectangle
難度:easy

題目大意:
測資給予一個長方形面積,需計算出其差異最小的長寬。
(長減寬最小,長放前方,寬放後方)

解題過程:
【version 1】
1. 對 area 開根號,找出最接近平方根的數,開始找能整除的值
2. 由於是從接近平方根開始找,因此找到的第一個必為長寬差異最小的答案
【version 2】
1. 從 1 開始找能整除 area 的數,並以 vector 紀錄
2. 當遇到其他能整除 area 的數,比較其寬高差異,取較小者存入 vector

使用語言:C++

實作程式如下:

version 1

時間複雜度:O(N ^ 0.5),N = area
空間複雜度:O(1)

Runtime: 70 ms, faster than 20.67% of C++ online submissions for Construct the Rectangle.
Memory Usage: 6 MB, less than 92.50% of C++ online submissions for Construct the Rectangle.

version 2

時間複雜度:O(N^0.5)
空間複雜度:O(1)

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Construct the Rectangle.
Memory Usage: 6.2 MB, less than 32.63% of C++ online submissions for Construct the Rectangle.

--

--

題目連結:485. Max Consecutive Ones
難度:easy

題目大意:
測資提供一組陣列,需要找到最大的連續 1 數量為何。

解題過程:
【version 1】
1. 遍歷整個 vector,同時紀錄目前連續數量及最大連續數量
2. 當遇到 1 時,更新目前連續數量
【version 2】
1. 遍歷整個 vector,當目前值為 1 時,與前一個數加總
2. 找出 vector 中最大的值
【version 3】
slide window

使用語言:C++

實作程式如下:

version 1

時間複雜度:O(N),N 為 nums.size()
空間複雜度:O(1)

Runtime: 52 ms, faster than 52.35% of C++ online submissions for Max Consecutive Ones.
Memory Usage: 36.2 MB, less than 21.11% of C++ online submissions for Max Consecutive Ones.

version 2

時間複雜度:O(N),N 為 nums.size()
空間複雜度:O(1)

Runtime: 61 ms, faster than 31.98% of C++ online submissions for Max Consecutive Ones.
Memory Usage: 36.2 MB, less than 20.98% of C++ online submissions for Max Consecutive Ones.

--

--

題目連結:476. Number Complement
難度:easy

題目大意:
求測資所給數字之補數為何。

解題過程:
1. 利用 log2 計算出 num 的二進位有幾位數
2. 再透過 pow() 得出全部由1組成的該位數數字
3. 最後使用 XOR 計算出補數

舉例,測資為 5,其二進位為 101,補數為 010log2(5) + 1 = 3
pow(2,3) - 1 = 7(二進位為 111)
101 XOR 111 = 010

使用語言:C++

實作程式如下:

時間複雜度:O(1)
空間複雜度:O(1)

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Number Complement.
Memory Usage: 6.1 MB, less than 9.21% of C++ online submissions for Number Complement.

--

--

題目連結:463. Island Perimeter
難度:easy

題目大意:
測資會給予一組二維陣列,為 Grid Cells 組成的一塊範圍,需回傳這塊範圍的邊長為何(這塊範圍不會有空心區域,也不會有 >1 塊範圍)。

解題過程:
遍歷整個 Grid,遇到陸地(grid[i][j]=1)時,加上 4 個邊;若此陸地的左方及上方有陸地,則分別減 2 個邊(扣除陸地相接所重複計算的邊)。

使用語言:C++

實作程式如下:

時間複雜度:O(M*N),M, N 分別為 grid 的長寬
空間複雜度:O(1)

Runtime: 185 ms, faster than 29.90% of C++ online submissions for Island Perimeter.
Memory Usage: 96.1 MB, less than 84.87% of C++ online submissions for Island Perimeter.

--

--

題目連結:461. Hamming Distance
難度:easy

題目大意:
計算測資所給的兩個二進位數字之漢明距離。

Hamming Distance: 兩個相同長度的字串,在相同位置上有多少個數值不同。對於二進位字串來說,就是 1 的個數。

解題過程:
1. 將測資數字轉為二進位
2. 將兩數字做 XOR 運算
3. 使用 bitset 中 count() 函式計算 1 的個數。

使用語言:C++

實作程式如下:

時間複雜度:O(N),N 為 x 的二進位長度
空間複雜度:O(N)

Runtime: 3 ms, faster than 35.84% of C++ online submissions for Hamming Distance.
Memory Usage: 5.8 MB, less than 73.51% of C++ online submissions for Hamming Distance.

--

--

題目連結:459. Repeated Substring Pattern
難度:easy

題目大意:
檢查測資所給的字串是否能由自己內部的 substring 組成。

解題過程:
1. 從長度為 1 的 substring 開始搜尋
2. 當 s.length() 能夠被 substring.length() 整除時,才比對子字串
3. 透過 substr() 函式取得 s 的子字串

使用語言:C++

實作程式如下:

時間複雜度:O(N²),N 為 s.length()
空間複雜度:O(1)

Runtime: 22 ms, faster than 71.49% of C++ online submissions for Repeated Substring Pattern.
Memory Usage: 16.6 MB, less than 30.24% of C++ online submissions for Repeated Substring Pattern.

--

--

題目連結:455. Assign Cookies
難度:easy

題目大意:
測資提供兩個 vector,分別為孩子的需求及餅乾,當餅乾大於需求時,才能滿足孩子,要計算總共能滿足多少孩子。

解題過程:
1. 排序兩個 vector
2. 從後往前看是否有符合的情況,並做加總

使用語言:C++

實作程式如下:

時間複雜度:O(N*logN),N 為 s.size()
空間複雜度:O(1)

Runtime: 54 ms, faster than 15.24% of C++ online submissions for Assign Cookies.
Memory Usage: 17.5 MB, less than 79.02% of C++ online submissions for Assign Cookies.

--

--

題目連結:448. Find All Numbers Disappeared in an Array
難度:easy

題目大意:
將測資所給的 vector nums 中缺少的數字回傳。
(vector 中正確的數字應為 1~nums.size() )

解題過程:
1. 以 nums 的數字作為 index,將 nums 中出現過的數字之位置都改為負數
2. 檢查 nums 中有哪些位置的值 >0,即可判斷此位置的值沒有出現過,再將位置 push 到 answer vector 中

使用語言:C++

實作程式如下:

時間複雜度:O(N),N 為 nums.size()
空間複雜度:O(N)

Runtime: 53 ms, faster than 91.20% of C++ online submissions for Find All Numbers Disappeared in an Array.
Memory Usage: 33.6 MB, less than 84.10% of C++ online submissions for Find All Numbers Disappeared in an Array.

--

--

題目連結:441. Arranging Coins
難度:easy

題目大意:
計算測資所給金幣數量,可以疊成幾個完整的 row。
(一列數量從 1 開始,之後每一列會多一個金幣)

解題過程:
【version 1】
用迴圈將 n 從 1 開始扣除,直到無法排成完整的 row(>0)。
【version 2】
用梯形公式計算 n ≤ 1+2+…+x 為 n ≤ (1+x) * x / 2
2n ≤ x²+x2n ≤ (x²+x+1/4)-1/42n ≤ (x+1/2)²-1/4
x ≥ √(2n+1/4)-1/2
(為避免程式將 1/4 視為0,需寫為小數 0.25;且要注意 n*2 可能會超出 int 大小)

使用語言:C++

實作程式如下:

version 1

時間複雜度:O(N)
空間複雜度:O(1)

Runtime: 7 ms, faster than 49.08% of C++ online submissions for Arranging Coins.
Memory Usage: 6 MB, less than 28.25% of C++ online submissions for Arranging Coins.

version 2

時間複雜度:O(1)
空間複雜度:O(1)

Runtime: 3 ms, faster than 78.58% of C++ online submissions for Arranging Coins.
Memory Usage: 5.8 MB, less than 71.63% of C++ online submissions for Arranging Coins.

--

--