首先是 2427. Number of Common Factors (easy)
https://leetcode.com/problems/number-of-common-factors/
找出兩個數字的所有公因數。
就基本題,沒啥好敘述的,找到兩個數字的所有因數,再進行交集即可。
1.找出所有數字的因數(若這題有坑應該在這邊),存到set裡
2.交集
class Solution:
def commonFactors(self, a: int, b: int) -> int:
comA,comB = set(),set()
for i in range(1,int(a**(1/2)+1)): #這邊用點小技巧可以降低時間複雜度
if a % i == 0:
comA.add(i)
comA.add(a//i)
for i in range(1,int(b**(1/2)+1)):
if b % i == 0:
comB.add(i)
comB.add(b//i)
return len(comA & comB)
再來是 2428. Maximum Sum of an Hourglass (medium)
https://leetcode.com/problems/maximum-sum-of-an-hourglass/
提供一個matrix,獲取工字形裡所有數字的總和,個人覺得是基本題。
得到所有總和後獲取裡面最大值。
想法:
class Solution:
def maxSum(self, grid: List[List[int]]) -> int:
movement = [(-1,-1),(-1,0),(-1,1),(0,0),(1,-1),(1,0),(1,1)]
L,W = len(grid),len(grid[0])
ans = 0
for i in range(1,L-1):
for j in range(1,W-1):
temp = 0
for k in movement:
temp += grid[i+k[0]][j+k[1]]
ans = max(ans,temp)
return ans
再來是 2429. Minimize XOR (medium)
https://leetcode.com/problems/minimize-xor/
給予兩個數字n1,n2
當n1與n2化為二進制時會有固定個數的1跟0
若n2的1與0可以重新排列
求n1 xor n2的最小值x
我個人對於xor比較不熟,這樣的寫法就可以過了,不過應該有更好的寫法。
找機會再研究一下各路大神的寫法。
class Solution:
def minimizeXor(self, num1: int, num2: int) -> int:
b1 = bin(num1)[2:]
b2 = bin(num2)[2:]
b1L = list(b1)
b2L = list(b2)
n1 = b1.count('1')
n2 = b2.count('1')
ans = 0
print(b1,b2)
if n1>n2:
temp = n1 - n2
for i in range(len(b1)):
if b1L[-i-1] == '1':
if temp == 0:
break
b1L[-i-1] = '0'
temp -= 1
print(b1L)
for i in range(len(b1L)):
if b1L[-i-1] == '1':
ans += 2**i
elif n2>n1:
temp = n2-n1
for i in range(len(b1)):
if temp == 0:
break
if b1L[-i-1] == '0':
b1L[-i-1] = '1'
temp-=1
if temp:
b1L = ['1']*temp + b1L
print(b1L)
for i in range(len(b1L)):
if b1L[-i-1] == '1':
ans += 2**i
else:
ans = num1
return ans
以上就是今天的練習感謝大家的觀看。