iT邦幫忙

2022 iThome 鐵人賽

DAY 23
0
自我挑戰組

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

Day23 leetcode隨機挑題 (Matrix、Math)沒錯周五就是要偷懶

  • 分享至 

  • xImage
  •  

首先 860. Lemonade Change (easy)
https://leetcode.com/problems/lemonade-change/

找零錢遊戲,善良題,每次只找一杯,看所有流程中零錢夠不夠

想法:

  1. 兩個變數統計5,10元硬幣
  2. 每買一次檢查一次有沒有負數
class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        five,ten =0,0
        for i in bills:
            if i ==5:
                five+=1
            elif i == 10:
                five-=1
                ten+=1
            else:
                if ten>0:
                    ten-=1
                    five-=1
                else:
                    five-=3
            if five<0 or ten<0:
                return 0
        return 1

再來是 867. Transpose Matrix (easy)
https://leetcode.com/problems/transpose-matrix/

matrix基本題,行列互調

做法1
一行解

class Solution:
    def transpose(self, matrix: List[List[int]]) -> List[List[int]]:
        return zip(*matrix)

做法2
乖乖跑for迴圈進行調換

class Solution:
    
    #行列對調
    def transpose(self, matrix: List[List[int]]) -> List[List[int]]:
        L,W = len(matrix),len(matrix[0])
        ans = [[0 for i in range(L)] for j in range(W)]
        for i in range(L):
            for j in range(W):
                ans[j][i] = matrix[i][j]
        return ans
    
    #感覺比較快
    def transpose(self, matrix: List[List[int]]) -> List[List[int]]:
        ans = []
        for i in range(len(matrix[0])):
            temp = []
            for j in range(len(matrix)):
                temp.append(matrix[j][i])
            ans.append(temp)
        return ans

再來是 812. Largest Triangle Area (easy)
https://leetcode.com/problems/largest-triangle-area/

提供很多座標,找出最大的三角形面積

我稱之為懷念高中數學題,直接拉出行列式法來解

class Solution:
    #三角形面積公式
    #a向量(a1,a2)
    #b向量(b1,b2)
    #面積行列式法 (a1*b2 - b1*a2)取絕對值除以2 
    def largestTriangleArea(self, points: List[List[int]]) -> float:
        ans = 0
        pL = len(points)
        for i in range(pL):
            for j in range(i+1,pL):
                for k in range(j+1,pL):
                    a,b,c = points[i],points[j],points[k]
                    a1,a2 = points[j][0] - points[i][0],points[j][1] - points[i][1]
                    b1,b2 = points[k][0] - points[i][0],points[k][1] - points[i][1]
                    temp = abs(a1*b2-b1*a2)/2
                    ans = max(temp,ans)
        return ans
    
    #三角形面積公式2
    #三點座標
    def largestTriangleArea(self, points: List[List[int]]) -> float:
        ans = 0
        pL = len(points)
        for i in range(pL):
            for j in range(i+1,pL):
                for k in range(j+1,pL):
                    a,b,c = points[i],points[j],points[k]
                    temp = abs(a[0]*b[1] + b[0]*c[1] + a[1]*c[0] - c[0]*b[1] - b[0]*a[1]- a[0]*c[1])/2
                    ans = max(temp,ans)
        return ans
    
    #三角形面積公式2
    #三點座標(化簡)
    def largestTriangleArea(self, points: List[List[int]]) -> float:
        ans = 0
        n = len(points)
        for i in range(n):
            x1,y1 = points[i]
            for j in range(i+1,n):
                x2,y2 = points[j]
                for k in range(j+1,n):
                    x3,y3 = points[k]
                    temp = abs(0.5*(x1*(y2-y3)+x2*(y3-y1)+x3*(y1-y2)))
                    if tmep>ans:
                        ans = temp
        return ans

以上就是今天的練習,感謝大家


上一篇
Day22 leetcode隨機挑題 (Design、Matrix、Search)
下一篇
Day24 leetcode隨機挑題(Slide、Prefix sum)
系列文
leetcode 30天 不中斷解題挑戰30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言