思考與發呆的過程

695. Max Area of Island (medium)
     https://leetcode.com/problems/max-area-of-island/
     Submission：https://leetcode.com/submissions/detail/852479153/

You are given an m x n binary matrix grid. An island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.
The area of an island is the number of cells with a value 1 in the island.
Return the maximum area of an island in grid. If there is no island, return 0.

0是水1是島，找出有多少座島。幹，這是我一開始沒看清楚字所想的。
真實是要找到最大島的面積是多少。就dfs或bfs查找就好，查完之後記得紀錄查過的部分。

class Solution:
    #找出所有的島
    #0是水,1是島,2代表找過的島
    #1<=m,n<=50，範圍不大
    #可能用for從(0,0)~(49,49)，找到1就dfs或bfs，結束繼續找
    
    #幹，是找最大的島啦，白癡
    #題目要看清楚==
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        length,width = len(grid),len(grid[0])
        movement = [(1,0),(0,1),(-1,0),(0,-1)]
        def dfs(x,y):
            total = 0
            stack = [(x,y)]
            while stack:
                x,y = stack.pop()
                if grid[x][y] == 2:
                    continue
                total += 1
                grid[x][y] = 2
                for i in movement:
                    newX,newY = x+i[0],y+i[1]
                    if 0 <= newX < length and 0 <= newY < width and grid[newX][newY] == 1:
                        stack.append((newX,newY))
            return total
        ans = 0
        for x in range(length):
            for y in range(width):
                if grid[x][y] == 1:
                    temp = dfs(x,y)
                    ans = max(temp,ans)
        return ans

1085. Sum of Digits in the Minimum Number (easy)
      https://leetcode.com/problems/sum-of-digits-in-the-minimum-number/
      Submission：https://leetcode.com/submissions/detail/852481166/
      Given an integer array nums, return 0 if the sum of the digits of the minimum integer in nums is odd, or 1 otherwise.
      誒都，解釋在程式碼裡

class Solution:
    #找出nums裡最小的數字
    #把所有位數都加起來，若odd則0,even則1
    def sumOfDigits(self, nums: List[int]) -> int:
        return 0 if sum([int(i) for i in str(min(nums))])%2 else 1
        

1086. High Five (easy)
      https://leetcode.com/problems/high-five/
      Submission：https://leetcode.com/submissions/detail/852484138/

Given a list of the scores of different students, items, where items[i] = [IDi, scorei] represents one score from a student with IDi, calculate each student's top five average.

Return the answer as an array of pairs result, where result[j] = [IDj, topFiveAveragej] represents the student with IDj and their top five average. Sort result by IDj in increasing order.

A student's top five average is calculated by taking the sum of their top five scores and dividing it by 5 using integer division.
這題題目落落長，但就是很簡單的找出前五筆最高的成績，然後算平均。

from collections import defaultdict
class Solution:
    #串列items
    #items[0]為座號
    #items[1]為成績
    #算出每個人最高五筆成績的平均值
    #Sort result by IDj in increasing order.
    def highFive(self, items: List[List[int]]) -> List[List[int]]:
        rec = defaultdict(list)
        ans = []
        for i in items:
            rec[i[0]].append(i[1])
        for i,v in rec.items():
            v.sort(reverse = True)
            ans.append([i,sum(v[:5])//5])
        return sorted(ans)
        

1570. Dot Product of Two Sparse Vectors (medium)
      https://leetcode.com/problems/dot-product-of-two-sparse-vectors/
      Submission：https://leetcode.com/submissions/detail/852495504/

Given two sparse vectors, compute their dot product.

Implement class SparseVector:

SparseVector(nums) Initializes the object with the vector nums
dotProduct(vec) Compute the dot product between the instance of SparseVector and vec
A sparse vector is a vector that has mostly zero values, you should store the sparse vector efficiently and compute the dot product between two SparseVector.

Follow up: What if only one of the vectors is sparse?

這題基本上來講就是要處理SparseVector，也就是多數0的問題。
但題目是以計算兩個串列同索引值的乘積來包裝，我一開始還想說到底要幹嘛想很久

#不會錯但不會是最好的寫法
class SparseVector:
    def __init__(self, nums: List[int]):
        self.v = nums

    # Return the dotProduct of two sparse vectors
    def dotProduct(self, vec: 'SparseVector') -> int:
        total = 0
        for index,value in enumerate(self.v):
            total += vec.v[index]*value
        return total

#sparse vector的定義是具有大量0的vector，所以我應該想辦法用更有效率的方法找出計算方式。
#hash map的方法比較快
#dictionary
class SparseVector:
    def __init__(self, nums: List[int]):
        self.rec = {k:v for k,v in enumerate(nums) if v != 0}
    
    def dotProduct(self, vec: 'SparseVector') -> int:
        ans = 0
        for k,v in self.rec.items():
            if k in vec.rec:
                ans +=v*vec.rec[k]
        return ans

#概念跟dict很像，就是要忽略掉0
#Bsearch
class SparseVector:
    def __init__(self, nums: List[int]):
        self.rec = [(i,v) for i,v in enumerate(nums) if v != 0]
        
    def dotProduct(self, vec: 'SparseVector') -> int:
        def bSearch(nums,L,R,target):
            while L <= R:
                M = (L+R)//2
                if nums[M][0] == target:
                    return nums[M][1]
                elif nums[M][0] < target:
                    L = M + 1
                else:
                    R = M - 1
            return -1#沒找到該索引值
        ans = 0
        for i,v in self.rec:
            # print(i,v)
            temp = bSearch(vec.rec,0,len(vec.rec)-1,i)
            if temp != -1:
                ans += temp*v
        return ans

以上為今天的練習