iT邦幫忙

2022 iThome 鐵人賽

DAY 18
0
自我挑戰組

leetcode 30天 不中斷解題挑戰系列 第 18

Day18 leetcode Weekly Contest 313

  • 分享至 

  • xImage
  •  

首先是 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,獲取工字形裡所有數字的總和,個人覺得是基本題。
得到所有總和後獲取裡面最大值。

想法:

  1. 建立一個串列movement專門走工字形
  2. 由於走的範圍不可以超過邊界,故直接限縮範圍
  3. 雙重迴圈,每個地方都走過並比較大小找最大值
  4. 輸出
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
                    

以上就是今天的練習感謝大家的觀看。


上一篇
Day17 leetcode隨機挑題(Biweekly Contest 88)
下一篇
Day19 leetcode隨機挑題 (Greedy、Sliding Window)
系列文
leetcode 30天 不中斷解題挑戰30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言