貪心問題

分發餅幹 lc 455
無重疊區間 lc 435
合并重疊區域 lc 56
求兩個電話同時說話的時間
投飛镖刺破氣球 lc 452
根據身高重建隊列 lc 406
判斷是否為子序列 lc 392
買賣股票的最佳時機 lc 121
買賣股票的最大收益 II lc 122
種花問題 lc 605
非遞減數列 lc 665
劃分字母區間 lc 763

while的使用：

while list，直到list為空
i=0 while 内部循環i自增，對于list來說pop或者remove之後直接往前頂，是以每次操作的都是i。不删除才往上增加。
上述的就是變長度的list還要跟蹤是否到底。

分發餅幹 lc 455

對每個孩子 i，都有一個胃口值 g[i]，這是能讓孩子們滿足胃口的餅幹的最小尺寸；并且每塊餅幹 j，都有一個尺寸 s[j] 。如果 s[j] >= g[i]，我們可以将這個餅幹 j 配置設定給孩子 i ，這個孩子會得到滿足。你的目标是盡可能滿足越多數量的孩子，并輸出這個最大數值。

輸入: g = [1,2,3], s = [1,1]

輸出: 1

解釋:

你有三個孩子和兩塊小餅幹，3個孩子的胃口值分别是：1,2,3。

雖然你有兩塊小餅幹，由于他們的尺寸都是1，你隻能讓胃口值是1的孩子滿足。

是以你應該輸出1。

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g.sort()
        s.sort()
        count = 0

        i,j=0,0
        while i < len(g) and j < len(s):
            if g[i]<=s[j]:
                count+=1
                i+=1
            #因為排序好了，每人隻能得到一個，是以目前要是不滿足後面也不會滿足要跳過
            j+=1

        return count

# 解法2，和字元串之變化一個思路一緻，兩個變量都要滿足，隻需要移動一個保持另一個
class Solution(object):
    def findContentChildren(self, g, s):
        """
        :type g: List[int]
        :type s: List[int]
        :rtype: int
        """
        g.sort()
        s.sort()
        length_g = len(g)

        start = 0
        count = 0
        for i in range(len(s)):
            if start<length_g and s[i]>=g[start]  :
                count+=1
                start+=1
        return count

貪心法典型問題，排好序，目前不滿足直接往後調
兩個數組都要往下滾動，一般是有一個必須要往下滾動，另一個滿足條件才往下滾動，是以一個for另一個是計數方式。

無重疊區間 lc 435

給定一個區間的集合，找到需要移除區間的最小數量，使剩餘區間互不重疊。

輸入: [ [1,2], [2,3], [3,4], [1,3] ]

輸出: 1

解釋: 移除 [1,3] 後，剩下的區間沒有重疊。

class Solution:
    def eraseOverlapIntervals(self, intervals):
        intervals = sorted(intervals,key=lambda x:x[-1])
        count = 0
        i = 1
        while 1<=i<len(intervals):
            if intervals[i-1][-1] > intervals[i][0]:
                count+=1
                #注意remove的用法，就是直接删除了，如果是for就不行了
                intervals.remove(intervals[i])
            else:
                i+=1
        return count

挺有現實意義的，思路是如果有重疊是前一個的第二位大于後一個的第一位。
按照第二位排序好之後直接去删除後面的那個位置的内容即可，因為排好序了。
注意這是while，remove之後是删除該内容，但是序号沒跟着變。
remove産出指定的内容，删除之後後面的元素自動往前移動，for的特性是每次疊代自動往後挪，是以如果使用for的話用remove删除應該從後往前删除。否則用while，因為自增和周遊是分離的，如本題目所示。

合并重疊區域 lc 56

leetcode 貪心分發餅幹 lc 455無重疊區間 lc 435合并重疊區域 lc 56求兩個電話同時說話的時間投飛镖刺破氣球 lc 452根據身高重建隊列 lc 406判斷是否為子序列 lc 392買賣股票的最佳時機 lc 121買賣股票的最大收益 II lc 122種花問題 lc 605非遞減數列 lc 665劃分字母區間 lc 763

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda x:x[0])
        i = 0
        while i!=len(intervals)-1:
            if intervals[i][1]>=intervals[i+1][0]:
                tmp = [intervals[i][0],max(intervals[i][1],intervals[i+1][1])]
                intervals.pop(i)
                intervals.pop(i)
                intervals.insert(i,tmp)
            else:
                i+=1
        return intervals

l = [[1,3],[4,5],[10,15],[2,6]]
# l = [[1,3],[2,6]]
print(merge(l))

這個問題是對list的pop和insert的了解。
pop和remove一樣，出去了下标都會往前挪。

求兩個電話同時說話的時間

在資料存儲時，我們将時間軸上的區間資料存儲為清單格式，清單中的每個元素代表對應時間軸的一段時間區間，如：(1,1.5)代表從第1秒開始到第1.5秒結束。現有兩個時間軸A、B及其各自包含的時間區間資訊，求兩個時間軸上時間區間的交集部分：
A = [(1,1.5), (3,8)]
B = [(2,4), (5,6), (7,9)]
O = overlap(A,B)
O = [(3,4), (5,6), (7,8)]


def inner(l1,l2):
    lst = [l1,l2]
    lst.sort(key=lambda x:x[0])
    if lst[0][1]>lst[1][0]:
        inner = (max(lst[0][0],lst[1][0]),min(lst[0][1],lst[1][1]))
        return inner

def overlap(A,B):
    res = []
    for i in A:
        for j in B:
            res.append(inner(i,j))
    return [i for i in res if i!=None]

#優化一下，目前如果沒有交集，則後面都沒有交集。
def overlap(A,B):
    res = []
    flag = 0
    for i in A:
        for j in B:
            if inner(i,j) is None:
                flag = 1
                break
            res.append(inner(i,j))
        if flag:
            flag = 0
            continue
    return res

注意不能直接合并，因為合并，因為可能後面還會有過長，不是貪心問題，隻有求交集才是。

投飛镖刺破氣球 lc 452

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        if not points:
            return 0
        points.sort(key=lambda x:x[1])
        res = 1
        curr_pos = points[0][1]
        for i in range(len(points)):
            if curr_pos>=points[i][0]:
                continue
            curr_pos = points[i][1]
            res+=1
        return res

有重疊的問題就很容易想到貪心，就逐漸的去戳。
用的箭最少需要從邊上開始，因為從中間開始就去掉更多的連結了，想象成一個圖。
因為已經按照右邊排好序，是以每次隻看左邊有沒有超過上一次的右邊就可以了，不用管箭的位置，如果不是的話再+1并且移動新的框。

根據身高重建隊列 lc 406

假設有打亂順序的一群人站成一個隊列，數組 people 表示隊列中一些人的屬性（不一定按順序）。每個 people[i] = [hi, ki] 表示第 i 個人的身高為 hi ，前面正好有 ki 個身高大于或等于 hi 的人。

請你重新構造并傳回輸入數組 people 所表示的隊列。傳回的隊列應該格式化為數組 queue ，其中 queue[j] = [hj, kj] 是隊列中第 j 個人的屬性（queue[0] 是排在隊列前面的人）

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        people.sort(key = lambda x:(-x[0],x[1]))
        res = []
        for p in people:
        #注意insert的用法，位置，值
            res.insert(p[1],p)
        return res

比較特殊的排序，先按照身高後按照前面有幾個人拍好，身高是降序排列，前面的人是升序。
而後就可以按照前面有幾個人依次插入，因為插入的身高都是對的。

判斷是否為子序列 lc 392

示例 1：

輸入：s = “abc”, t = “ahbgdc”

輸出：true

示例 2：

輸入：s = “axc”, t = “ahbgdc”

輸出：false

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        if s == '':
            return True
        start = 0
        for i in range(len(t)):
            if s[start] == t[i]:
                start+=1
            if start == len(s):
                return True
        return False

一看就是常見的兩個字元串的問題，一個使勁往下滑動，另一個找到了計數+1.
以長的為标準來。

買賣股票的最佳時機 lc 121

給定一個數組 prices ，它的第 i 個元素 prices[i] 表示一支給定股票第 i 天的價格。

你隻能選擇某一天買入這隻股票，并選擇在未來的某一個不同的日子賣出該股票。設計一個算法來計算你所能擷取的最大利潤。

傳回你可以從這筆交易中擷取的最大利潤。如果你不能擷取任何利潤，傳回 0 。

輸入：[7,1,5,3,6,4]

輸出：5

解釋：在第 2 天（股票價格 = 1）的時候買入，在第 5 天（股票價格 = 6）的時候賣出，最大利潤 = 6-1 = 5 。

注意利潤不能是 7-1 = 6, 因為賣出價格需要大于買入價格；同時，你不能在買入前賣出股票。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        result, buy = 0, float('inf')
        for price in prices:
            buy = min(buy,price)
            result = max(result,price-buy)
            
            # if buy > price:
            #     buy = price
            #
            # if result < price - buy:
            #     result = price - buy

        return result

隻周遊一遍，選出目前的最小值，和未來的內插補點的最大值，上面和下面的注釋是兩種實作。
上面是一定先選出最小，後面是目前值減去目前的最小得到的值。關鍵就是未必更新，吸引我的地方是說，周遊一遍找到。
這個的前提條件是之前先買之後才能賣，是以可以這樣周遊

買賣股票的最大收益 II lc 122

可以進行多次買賣，但是一個時間隻能進行一次，即第一次買賣結束才能進行第二次。

輸入: [7,1,5,3,6,4]

輸出: 7

解釋: 在第 2 天（股票價格 = 1）的時候買入，在第 3 天（股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。

随後，在第 4 天（股票價格 = 3）的時候買入，在第 5 天（股票價格 = 6）的時候賣出, 這筆交易所能獲得利潤 = 6-3 = 3 。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        result = 0
        #解決數組越界問題，循環處減1，具體循環下标+1。這個題目神奇的地方告訴我們，要是有先知先覺短線操作一定比長線好
        for i in range(len(prices)-1):
            if prices[i] < prices[i+1]:
                result += prices[i+1] - prices[i]

        return result

這就是模組化啊，先知了為啥多次好，多次會把每次的賺錢機會平均化，多貪心那？
貪心到兩兩作比較，[a,b,c,d,e,f]單調上升，b-a+c-b+d-c+e-d+f-e=f-a,其他正好能把峰值都買到。

種花問題 lc 605

假設有一個很長的花壇，一部分地塊種植了花，另一部分卻沒有。可是，花不能種植在相鄰的地塊上，它們會争奪水源，兩者都會死去。

給你一個整數數組 flowerbed 表示花壇，由若幹 0 和 1 組成，其中 0 表示沒種植花，1 表示種植了花。另有一個數 n ，能否在不打破種植規則的情況下種入 n 朵花？能則傳回 true ，不能則傳回 false。

輸入：flowerbed = [1,0,0,0,1], n = 1

輸出：true

class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        res=0
        flowerbed = [0] + flowerbed + [0]
        for i in range(1,len(flowerbed)-1):
            if flowerbed[i]==0 and flowerbed[i-1]==0 and flowerbed[i+1]==0:
                flowerbed[i]=1
                res +=1
        if res>=n:
            return True
        else:
            return False

連續三個好想，但是初始化那不好，看了報錯，正好這樣解就一緻了

非遞減數列 lc 665

給你一個長度為 n 的整數數組，請你判斷在最多改變 1 個元素的情況下，該數組能否變成一個非遞減數列。

class Solution:
    def checkPossibility(self, nums: List[int]) -> bool:
        count = 0 
        for i in range(1,len(nums)):
            if nums[i]>=nums[i-1]:
                continue
            if i-2>=0 and nums[i-2]>nums[i]:
                nums[i] = nums[i-1]
            else:
                nums[i-1] = nums[i]
            count+=1
            if count == 2:
                return False
        return True

本質希望的是圖一的情況，直接把前一位拉下來，但是問題是如果是圖二，太低了，拉下來隻會讓後面的都沒法進行，是以要考慮圖二，即每一個要和前兩個做對比。
這個關鍵是盡量改動前面，改前面改動量小，改後面非常容易讓下一個失效。

劃分字母區間 lc 763

字元串 S 由小寫字母組成。我們要把這個字元串劃分為盡可能多的片段，同一字母最多出現在一個片段中。傳回一個表示每個字元串片段的長度的清單。

class Solution:
    def partitionLabels(self, S: str) -> List[int]:
        adict = {}
        for i,s in enumerate(S):
            adict[s] = i
        last = 0
        start = 0
        res = []
        for i,s in enumerate(S):
            last = max(last,adict[s])
            if last == i:
                res.append(last-start+1)
                start=last+1
        return res

首先一定是周遊一遍把每個元素最後出現儲存住。
這個題特點是讓字母隻出現在一坨中，是以是周遊當下去看它出現的最後一次有多大。直到序号和最大相等說明找好了，全部收進來。

貪心問題

分發餅幹 lc 455

無重疊區間 lc 435

合并重疊區域 lc 56

求兩個電話同時說話的時間

投飛镖刺破氣球 lc 452

根據身高重建隊列 lc 406

判斷是否為子序列 lc 392

買賣股票的最佳時機 lc 121

買賣股票的最大收益 II lc 122

種花問題 lc 605

非遞減數列 lc 665

劃分字母區間 lc 763

繼續閱讀

Zeppelin 配置通路 REST APIApache Zeppelin Configuration REST API

【Torch】最簡潔logging使用指南

筆試面試題目：滑動視窗(二)

27. Remove Element(清單)題目代碼

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Cloud Studio初體驗

使用 ctypes 進行 Python 和 C 的混合程式設計

【python】【資料處理】畫多元資料分布圖

LeetCode OJ Binary Tree Right Side View

leetcode809

【python】netconf協定對接管理裝置

「Python 網絡自動化」NETCONF —— Python 使用 NETCONF 管理配置 H3C 網絡裝置

Linux裝置模型（中）之上層容器

在python中建立excel并寫入