2427. Number of Common Factors
Given two positive integers a and b, return the number of common factors of a and b.
An integer x is a common factor of a and b if x divides both a and b.
Constraints:
1 <= a, b <= 1000
給定正整數a, b
,回傳他們的公因數的數量
條件:
1 <= a, b <= 1000
想法:
x 從 1 開始到 min(a,b),如果 a 可以被 x 整除 且 b 可以被 x 整除,x 即為 (a,b) 的公因數
時間複雜度:O(n)
實作
|
|
改進:
- 呼叫 gcd 找出最大公因數,再計算他的因數個數
時間複雜度:O(n)
|
|
或使用 count
並傳入 block
|
|
附註:基礎題
2428. Maximum Sum of an Hourglass
You are given an m x n integer matrix grid.
We define an hourglass as a part of the matrix with the following form: Return the maximum sum of the elements of an hourglass.
Note that an hourglass cannot be rotated and must be entirely contained within the matrix.
Constraints:
m == grid.length
n == grid[i].length
3 <= m, n <= 150
0 <= grid[i][j] <= 106
給定一個 m x n 的二維數字陣列,定義一個圖案( hourglass, 沙漏)如圖示,找出圖案覆蓋的最大數字和
條件
- 圖案不能翻轉,且不能超出範圍
3 <= 邊長 <= 150
0 <= 數值 <= 1_000_000
想法
依照題目要求窮舉所有圖案,並計算數字和
時間複雜度 O(n^2)
實作
|
|
改進
|
|
附註:暴力解,基礎題