LeetCode-貪心算法-Easy

記錄了初步解題思路 以及本地實作代碼；并不一定為最優 也希望大家能一起探讨 一起進步

目錄

• • • 122.best-time-to-buy-and-sell-stock-ii 買賣股票的最佳時機 II
    • 455.assign-cookies 分發餅幹
    • 860.lemonade-change 檸檬水找零
    • 874.walking-robot-simulation 模拟行走機器人
    • 944.delete-columns-to-make-sorted 删列造序

122.best-time-to-buy-and-sell-stock-ii 買賣股票的最佳時機 II

解題思路：如果數值變小 可以在前一天将股票賣掉

最後添加一個0 可以解決末端問題

def maxProfit(prices):
    """
    :type prices: List[int]
    :rtype: int
    """
    ret = 0
    if not prices:
        return ret
    pre = 0
    prices.append(0)
    start=prices[pre]
    for i in range(1,len(prices)):
        if prices[i]<prices[i-1]:
            if i-1>pre:
                ret += prices[i-1]-prices[pre]
            pre= i
            start=prices[pre]
    return ret
           

455.assign-cookies 分發餅幹

解題思路：個人需求，餅幹大小從小到大

周遊餅幹

找到最小的小于餅幹的人可以添加

def findContentChildren(g, s):
    """
    :type g: List[int]
    :type s: List[int] 餅幹
    :rtype: int
    """
    p=0
    ret = 0
    if not s or not g:
        return ret
    s.sort()
    g.sort()
    for i in s:
        if g[p]<=i:
            ret+=1
            p+=1
        if p==len(g):
            break
    
    return ret
           

860.lemonade-change 檸檬水找零

解題思路：

def lemonadeChange(bills):
    """
    :type bills: List[int]
    :rtype: bool
    """
    dic={}
    dic[5]=0
    dic[10]=0
    for v in bills:
        if v==5:
            dic[5]+=1
        elif v==10:
            if dic[5]>0:
                dic[5]-=1
                dic[10]+=1
            else:
                return False
        else:
            if dic[10]>0 and dic[5]>0:
                dic[10]-=1
                dic[5]-=1
            elif dic[5]>2:
                dic[5]-=3
            else:
                return False
    return True
           

874.walking-robot-simulation 模拟行走機器人

解題思路：題目是傳回途中最大的歐氏距離平方 并非終點的值

四個方向 用direc來記錄往哪邊走

commands>0時代表走的步數 需要一步步走 來判斷是否會遇到障礙物

障礙物放入set中友善判斷

def robotSim(commands, obstacles):
    """
    :type commands: List[int]
    :type obstacles: List[List[int]]
    :rtype: int
    """
    #0：N 1:E 2:S 3:W
    direc = 0
    x=0
    y=0
    s = set()
    ret=0
    def check(pos):
        if pos in s:
            return True
        return False
    for v in obstacles:
        s.add((v[0],v[1]))
    for c in commands:
        if c==-1:
            direc+=1
            if direc>3:
                direc=0
        elif c==-2:
            direc-=1
            if direc<0:
                direc=3
        else:
            for i in range(c):
                if direc==0:
                    y+=1
                    if check((x,y)):
                        y-=1
                        break
                elif direc==1:
                    x+=1
                    if check((x,y)):
                        x-=1
                        break
                elif direc==2:
                    y-=1
                    if check((x,y)):
                        y+=1
                        break
                elif direc==3:
                    x-=1
                    if check((x,y)):
                        x+=1
                        break
            ret = max(ret,x*x+y*y)
    return ret
           

944.delete-columns-to-make-sorted 删列造序

解題思路：1:正常方法 一列列尋找是否符合

2:使用zip(*A)将A解壓

def minDeletionSize1(A):
    """
    :type A: List[str]
    :rtype: int
    """
    ret = 0
    if not A:
        return ret
    slen = len(A[0])
    for i in range(slen):
        pre = 'a'
        for j in range(len(A)):
            if A[j][i]<pre:
                ret+=1
                break
            else:
                pre= A[j][i]
    return ret

def minDeletionSize2(A):
    """
    :type A: List[str]
    :rtype: int
    """
    ret = 0
    for i in zip(*A):
        if list(i)!=sorted(i):
            ret+=1
    return ret