[TOC]

局部最優(yōu)解->全局最優(yōu)

455. 分發(fā)餅干（簡單/貪心）

假設(shè)你是一位很棒的家長常熙，想要給你的孩子們一些小餅干湿颅。但是叨襟，每個(gè)孩子最多只能給一塊餅干敬扛。對每個(gè)孩子 i晰洒，都有一個(gè)胃口值 g[i]，這是能讓孩子們滿足胃口的餅干的最小尺寸啥箭；并且每塊餅干 j谍珊，都有一個(gè)尺寸 s[j] 。如果 s[j] >= g[i]急侥，我們可以將這個(gè)餅干 j 分配給孩子 i 砌滞，這個(gè)孩子會(huì)得到滿足侮邀。你的目標(biāo)是盡可能滿足越多數(shù)量的孩子，并輸出這個(gè)最大數(shù)值贝润。
 
輸入: g = [1,2,3], s = [1,1]
輸出: 1
解釋: 
你有三個(gè)孩子和兩塊小餅干绊茧，3個(gè)孩子的胃口值分別是：1,2,3。
雖然你有兩塊小餅干打掘，由于他們的尺寸都是1华畏，你只能讓胃口值是1的孩子滿足。
所以你應(yīng)該輸出1尊蚁。
 
輸入: g = [1,2], s = [1,2,3]
輸出: 2
解釋: 
你有兩個(gè)孩子和三塊小餅干亡笑，2個(gè)孩子的胃口值分別是1,2。
你擁有的餅干數(shù)量和尺寸都足以讓所有孩子滿足横朋。
所以你應(yīng)該輸出2.
 

// g是胃口仑乌，s是餅干
// 用大餅干優(yōu)先滿足胃口大的，并統(tǒng)計(jì)滿足小孩數(shù)量琴锭。 https://leetcode.cn/problems/assign-cookies/solution/455-fen-fa-bing-gan-tan-xin-jing-dian-ti-o6k6/
func findContentChildren(g []int, s []int) int {
    sort.Ints(g)
    sort.Ints(s)

    gLen := len(g)
    sLen := len(s)

    index := sLen - 1
    count := 0
    for i := gLen - 1; i > 0; i-- {
        if index >= 0 && s[index] >= g[i] {
            count++
            index--
        }
    }
    return count
}

392. 判斷子序列（簡單/貪心）

452. 用最少數(shù)量的箭引爆氣球（中等/貪心）

有一些球形氣球貼在一堵用 XY 平面表示的墻面上晰甚。墻面上的氣球記錄在整數(shù)數(shù)組 points ，其中points[i] = [xstart, xend] 表示水平直徑在 xstart 和 xend之間的氣球决帖。你不知道氣球的確切 y 坐標(biāo)厕九。一支弓箭可以沿著 x 軸從不同點(diǎn) 完全垂直 地射出。在坐標(biāo) x 處射出一支箭古瓤，若有一個(gè)氣球的直徑的開始和結(jié)束坐標(biāo)為 xstart止剖，xend腺阳， 且滿足  xstart ≤ x ≤ xend落君，則該氣球會(huì)被 引爆 ⊥ひ可以射出的弓箭的數(shù)量 沒有限制 绎速。 弓箭一旦被射出之后，可以無限地前進(jìn)焙蚓。給你一個(gè)數(shù)組 points 纹冤，返回引爆所有氣球所必須射出的 最小 弓箭數(shù) 。
 
輸入：points = [[10,16],[2,8],[1,6],[7,12]]
輸出：2
解釋：氣球可以用2支箭來爆破:
-在x = 6處射出箭购公，擊破氣球[2,8]和[1,6]萌京。
-在x = 11處發(fā)射箭，擊破氣球[10,16]和[7,12]宏浩。

輸入：points = [[1,2],[3,4],[5,6],[7,8]]
輸出：4
解釋：每個(gè)氣球需要射出一支箭知残，總共需要4支箭。

// https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/solution/yong-zui-shao-shu-liang-de-jian-yin-bao-qi-qiu-1-2/
// 一定存在一種最優(yōu)（射出的箭數(shù)最斜茸）的方法求妹，使得每一支箭的射出位置都恰好對應(yīng)著某一個(gè)氣球的右邊界乏盐。
func findMinArrowShots(points [][]int) int {
    // 按照右邊界進(jìn)行排序
    sort.Slice(points, func(i, j int) bool {
        return points[i][1] < points[j][1]
    })

    fmt.Println(points)
    count := 1 // 必定有一只箭
    end := points[0][1] 
    for i := 1; i < len(points); i++ {
        if points[i][0] > end { //前一個(gè)氣球重點(diǎn) < 當(dāng)前氣球起點(diǎn)，則數(shù)量+1,這里注意是point[i][0],注意是 > 
            count++
            end = points[i][1] //  這里注意是point[i][1]
        }
    }
    return count
}

435. 無重疊區(qū)間（中等/貪心）

給定一個(gè)區(qū)間的集合 intervals 制恍，其中 intervals[i] = [starti, endi] 父能。返回 需要移除區(qū)間的最小數(shù)量，使剩余區(qū)間互不重疊 净神。

輸入: intervals = [[1,2],[2,3],[3,4],[1,3]]
輸出: 1
解釋: 移除 [1,3] 后何吝，剩下的區(qū)間沒有重疊。

輸入: intervals = [ [1,2], [1,2], [1,2] ]
輸出: 2
解釋: 你需要移除兩個(gè) [1,2] 來使剩下的區(qū)間沒有重疊鹃唯。

輸入: intervals = [ [1,2], [2,3] ]
輸出: 0
解釋: 你不需要移除任何區(qū)間岔霸，因?yàn)樗鼈円呀?jīng)是無重疊的了。

func eraseOverlapIntervals(intervals [][]int) int {
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][1] < intervals[j][1]
    })
    fmt.Println(intervals)
    count := 1
    end := intervals[0][1]
    for i := 1; i < len(intervals); i++ {
        if intervals[i][0] >= end { // /當(dāng)區(qū)間的左邊界大于上一個(gè)區(qū)間的右邊界的時(shí)候 說明是一對不重合區(qū)間,注意是 >=
            count++
            end = intervals[i][1]
        }

    }
    return len(intervals) - count // //intervals的長度減去最多的不重復(fù)的區(qū)間 就是最少刪除區(qū)間的個(gè)數(shù)
}

1167. 連接棒材的最低費(fèi)用(貪心/小頂堆)

你有一些長度為正整數(shù)的棍子俯渤。這些長度以數(shù)組 sticks 的形式給出呆细， sticks[i] 是 第i個(gè) 木棍的長度。你可以通過支付 x + y 的成本將任意兩個(gè)長度為 x 和 y 的棍子連接成一個(gè)棍子八匠。你必須連接所有的棍子絮爷，直到剩下一個(gè)棍子。返回以這種方式將所有給定的棍子連接成一個(gè)棍子的 最小成本 梨树。

輸入：sticks = [2,4,3]
輸出：14
解釋：從 sticks = [2,4,3] 開始坑夯。
1. 連接 2 和 3 ，費(fèi)用為 2 + 3 = 5 ÷账模現(xiàn)在 sticks = [5,4]
2. 連接 5 和 4 柜蜈，費(fèi)用為 5 + 4 = 9 。現(xiàn)在 sticks = [9]
所有木棍已經(jīng)連成一根指巡，總費(fèi)用 5 + 9 = 14

輸入：sticks = [1,8,3,5]
輸出：30
解釋：從 sticks = [1,8,3,5] 開始淑履。
1. 連接 1 和 3 ，費(fèi)用為 1 + 3 = 4 ≡逖現(xiàn)在 sticks = [4,8,5]
2. 連接 4 和 5 秘噪，費(fèi)用為 4 + 5 = 9 。現(xiàn)在 sticks = [9,8]
3. 連接 9 和 8 勉耀，費(fèi)用為 9 + 8 = 17 ≈讣澹現(xiàn)在 sticks = [17]
所有木棍已經(jīng)連成一根，總費(fèi)用 4 + 9 + 17 = 30

輸入：sticks = [5]
輸出：0
解釋：只有一根木棍便斥，不必再連接至壤。總費(fèi)用 0

枢纠、像街、http://www.reibang.com/p/80a3d7add522

type intHeap []int

func (key intHeap) Len() int {
    return len(key)
}

func (key intHeap) Less(i int, j int) bool {
    return key[i] < key[j]
}

func (key intHeap) Swap(i int, j int) {
    key[i], key[j] = key[j], key[i]
}

func (h *intHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}

func (h *intHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

func (h *intHeap) push(x int) {
    heap.Push(h, x)
}

func (h *intHeap) pop() int {
    return heap.Pop(h).(int)
}

func connectSticks(sticks []int) int {
    res := 0
    sticksHeap := intHeap{}
    sticksHeap = sticks
    heap.Init(&sticksHeap)
    for sticksHeap.Len() > 1 {
        first, second := sticksHeap.pop(), sticksHeap.pop()
        sticksHeap.push(first+second)
        res += first+second
    }   
    return res
}

860. 檸檬水找零(簡單/其實(shí)感覺沒用到貪心)

在檸檬水?dāng)偵希恳槐瓩幟仕氖蹆r(jià)為 5 美元。顧客排隊(duì)購買你的產(chǎn)品宅广，（按賬單 bills 支付的順序）一次購買一杯葫掉。每位顧客只買一杯檸檬水，然后向你付 5 美元跟狱、10 美元或 20 美元俭厚。你必須給每個(gè)顧客正確找零，也就是說凈交易是每位顧客向你支付 5 美元驶臊。注意挪挤，一開始你手頭沒有任何零錢。給你一個(gè)整數(shù)數(shù)組 bills 关翎，其中 bills[i] 是第 i 位顧客付的賬扛门。如果你能給每位顧客正確找零，返回 true 纵寝，否則返回 false 论寨。

輸入：bills = [5,5,5,10,20]
輸出：true
解釋：
前 3 位顧客那里，我們按順序收取 3 張 5 美元的鈔票爽茴。
第 4 位顧客那里葬凳，我們收取一張 10 美元的鈔票，并返還 5 美元室奏。
第 5 位顧客那里火焰，我們找還一張 10 美元的鈔票和一張 5 美元的鈔票。
由于所有客戶都得到了正確的找零胧沫，所以我們輸出 true昌简。
 
輸入：bills = [5,5,10,10,20]
輸出：false
解釋：
前 2 位顧客那里，我們按順序收取 2 張 5 美元的鈔票绒怨。
對于接下來的 2 位顧客纯赎，我們收取一張 10 美元的鈔票，然后返還 5 美元窖逗。
對于最后一位顧客址否，我們無法退回 15 美元餐蔬，因?yàn)槲覀儸F(xiàn)在只有兩張 10 美元的鈔票碎紊。
由于不是每位顧客都得到了正確的找零，所以答案是 false樊诺。

// 一開始我還想著利用map來存仗考，我真是傻逼
func lemonadeChange(bills []int) bool {
    five, ten := 0, 0
    for _, bill := range bills {
        if bill == 5 {
            five++
        } else if bill == 10 {
            if five == 0 {
                return false
            }
            five--
            ten++
        } else {
            if five > 0 && ten > 0 {
                five--
                ten--
            } else if five >= 3 {
                five -= 3
            } else {
                return false
            }
        }
    }
    return true
}

56. 合并區(qū)間 （中等/感覺和貪心也沒啥關(guān)系）

以數(shù)組 intervals 表示若干個(gè)區(qū)間的集合，其中單個(gè)區(qū)間為 intervals[i] = [starti, endi] 词爬。請你合并所有重疊的區(qū)間秃嗜，并返回 一個(gè)不重疊的區(qū)間數(shù)組，該數(shù)組需恰好覆蓋輸入中的所有區(qū)間 。

輸入：intervals = [[1,3],[2,6],[8,10],[15,18]]
輸出：[[1,6],[8,10],[15,18]]
解釋：區(qū)間 [1,3] 和 [2,6] 重疊, 將它們合并為 [1,6].

輸入：intervals = [[1,4],[4,5]]
輸出：[[1,5]]
解釋：區(qū)間 [1,4] 和 [4,5] 可被視為重疊區(qū)間锅锨。

// ================ 解法一 ====================================
func merge(intervals [][]int) [][]int {
    //先從小到大排序
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })
    //再弄重復(fù)的
    for i := 0; i < len(intervals)-1; i++ {
        // 當(dāng)前右邊界intervals[i][1]和下一區(qū)間左邊界intervals[i+1][0]比較
        if intervals[i][1] >= intervals[i+1][0] {
            // 更新區(qū)間右邊界最大值
            intervals[i][1] = max(intervals[i][1], intervals[i+1][1]) //賦值最大值
            // 刪除下一個(gè)區(qū)間元素叽赊，因?yàn)榇藭r(shí)當(dāng)前區(qū)間右邊界已經(jīng)變了
            intervals = append(intervals[:i+1], intervals[i+2:]...) // 很重要，刪除i+1這一行
            i--
        }
    }
    return intervals
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

//  ====================  解法二(其實(shí)就是硬寫必搞，挺好理解的)  ============================
func merge(intervals [][]int) [][]int {
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })
    var res [][]int
    start, end := intervals[0][0], intervals[0][1]
    for i := 1; i < len(intervals); i++ {
        if intervals[i][0] <= end {
            if intervals[i][1] > end {
                end = intervals[i][1]
            }
        } else {
            res = append(res, []int{start, end})
            start, end = intervals[i][0], intervals[i][1]
        }
    }
    return append(res, []int{start, end})
}

55. 跳躍游戲（中等）

給定一個(gè)非負(fù)整數(shù)數(shù)組 nums 必指，你最初位于數(shù)組的 第一個(gè)下標(biāo) 。數(shù)組中的每個(gè)元素代表你在該位置可以跳躍的最大長度恕洲。判斷你是否能夠到達(dá)最后一個(gè)下標(biāo)塔橡。

輸入：nums = [2,3,1,1,4]
輸出：true
解釋：可以先跳 1 步，從下標(biāo) 0 到達(dá)下標(biāo) 1, 然后再從下標(biāo) 1 跳 3 步到達(dá)最后一個(gè)下標(biāo)霜第。

輸入：nums = [3,2,1,0,4]
輸出：false
解釋：無論怎樣葛家，總會(huì)到達(dá)下標(biāo)為 3 的位置。但該下標(biāo)的最大跳躍長度是 0 泌类， 所以永遠(yuǎn)不可能到達(dá)最后一個(gè)下標(biāo)癞谒。

45. 跳躍游戲 II（中等）

給你一個(gè)非負(fù)整數(shù)數(shù)組 nums ，你最初位于數(shù)組的第一個(gè)位置刃榨。數(shù)組中的每個(gè)元素代表你在該位置可以跳躍的最大長度扯俱。你的目標(biāo)是使用最少的跳躍次數(shù)到達(dá)數(shù)組的最后一個(gè)位置。假設(shè)你總是可以到達(dá)數(shù)組的最后一個(gè)位置喇澡。

輸入: nums = [2,3,1,1,4]
輸出: 2
解釋: 跳到最后一個(gè)位置的最小跳躍數(shù)是 2迅栅。
     從下標(biāo)為 0 跳到下標(biāo)為 1 的位置，跳 1 步晴玖，然后跳 3 步到達(dá)數(shù)組的最后一個(gè)位置读存。

輸入: nums = [2,3,0,1,4]
輸出: 2

1306. 跳躍游戲 III（中等）

這里有一個(gè)非負(fù)整數(shù)數(shù)組 arr，你最開始位于該數(shù)組的起始下標(biāo) start 處呕屎。當(dāng)你位于下標(biāo) i 處時(shí)让簿，你可以跳到 i + arr[i] 或者 i - arr[i]。請你判斷自己是否能夠跳到對應(yīng)元素值為 0 的 任一 下標(biāo)處秀睛。注意尔当，不管是什么情況下，你都無法跳到數(shù)組之外蹂安。

輸入：arr = [4,2,3,0,3,1,2], start = 5
輸出：true
解釋：
到達(dá)值為 0 的下標(biāo) 3 有以下可能方案： 
下標(biāo) 5 -> 下標(biāo) 4 -> 下標(biāo) 1 -> 下標(biāo) 3 
下標(biāo) 5 -> 下標(biāo) 6 -> 下標(biāo) 4 -> 下標(biāo) 1 -> 下標(biāo) 3 

輸入：arr = [4,2,3,0,3,1,2], start = 0
輸出：true 
解釋：
到達(dá)值為 0 的下標(biāo) 3 有以下可能方案： 
下標(biāo) 0 -> 下標(biāo) 4 -> 下標(biāo) 1 -> 下標(biāo) 3

122. 買賣股票的最佳時(shí)機(jī) II（中等/貪心）

給你一個(gè)整數(shù)數(shù)組 prices 椭迎，其中 prices[i] 表示某支股票第 i 天的價(jià)格。在每一天田盈，你可以決定是否購買和/或出售股票畜号。你在任何時(shí)候 最多 只能持有 一股 股票。你也可以先購買允瞧，然后在 同一天 出售简软。返回 你能獲得的 最大 利潤 蛮拔。

輸入：prices = [7,1,5,3,6,4]
輸出：7
解釋：在第 2 天（股票價(jià)格 = 1）的時(shí)候買入，在第 3 天（股票價(jià)格 = 5）的時(shí)候賣出, 這筆交易所能獲得利潤 = 5 - 1 = 4 痹升。
     隨后建炫，在第 4 天（股票價(jià)格 = 3）的時(shí)候買入，在第 5 天（股票價(jià)格 = 6）的時(shí)候賣出, 這筆交易所能獲得利潤 = 6 - 3 = 3 疼蛾。
     總利潤為 4 + 3 = 7 踱卵。

輸入：prices = [1,2,3,4,5]
輸出：4
解釋：在第 1 天（股票價(jià)格 = 1）的時(shí)候買入，在第 5 天 （股票價(jià)格 = 5）的時(shí)候賣出, 這筆交易所能獲得利潤 = 5 - 1 = 4 据过。
     總利潤為 4 惋砂。

/*
res =  (prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])
    =  prices[3] - prices[0]
按照貪心算法，在下標(biāo)為 1绳锅、2西饵、3 的這三天，我們做的操作應(yīng)該是買進(jìn)昨天的鳞芙，賣出今天的眷柔。
等價(jià)于：在下標(biāo)為 0 的那一天買入，在下標(biāo)為 3 的那一天賣出原朝。
貪心算法的直覺：由于不限制交易次數(shù)驯嘱，只要今天股價(jià)比昨天高，就交易喳坠。
*/

func maxProfit(prices []int) (ans int) {
    for i := 1; i < len(prices); i++ {
        ans += max(0, prices[i]-prices[i-1])
    }
    return
}

561. 數(shù)組拆分（簡單）

給定長度為 2n 的整數(shù)數(shù)組 nums 鞠评，你的任務(wù)是將這些數(shù)分成 n 對, 例如 (a1, b1), (a2, b2), ..., (an, bn) ，使得從 1 到 n 的 min(ai, bi) 總和最大壕鹉。返回該 最大總和 剃幌。

輸入：nums = [1,4,3,2]
輸出：4
解釋：所有可能的分法（忽略元素順序）為：
1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
所以最大總和為 4

輸入：nums = [6,2,6,5,1,2]
輸出：9
解釋：最優(yōu)的分法為 (2, 1), (2, 5), (6, 6). min(2, 1) + min(2, 5) + min(6, 6) = 1 + 2 + 6 = 9

1710. 卡車上的最大單元數(shù)（簡單/貪心）

請你將一些箱子裝在 一輛卡車 上。給你一個(gè)二維數(shù)組 boxTypes 晾浴，其中 boxTypes[i] = [numberOfBoxesi, numberOfUnitsPerBoxi] ：numberOfBoxesi 是類型 i 的箱子的數(shù)量负乡。numberOfUnitsPerBoxi 是類型 i 每個(gè)箱子可以裝載的單元數(shù)量。整數(shù) truckSize 表示卡車上可以裝載 箱子 的 最大數(shù)量 脊凰。只要箱子數(shù)量不超過 truckSize 抖棘，你就可以選擇任意箱子裝到卡車上。返回卡車可以裝載 單元 的 最大 總數(shù)狸涌。

輸入：boxTypes = [[1,3],[2,2],[3,1]], truckSize = 4
輸出：8
解釋：箱子的情況如下：
- 1 個(gè)第一類的箱子切省，里面含 3 個(gè)單元。
- 2 個(gè)第二類的箱子杈抢，每個(gè)里面含 2 個(gè)單元数尿。
- 3 個(gè)第三類的箱子，每個(gè)里面含 1 個(gè)單元惶楼。
可以選擇第一類和第二類的所有箱子，以及第三類的一個(gè)箱子。
單元總數(shù) = (1 * 3) + (2 * 2) + (1 * 1) = 8

輸入：boxTypes = [[5,10],[2,5],[4,7],[3,9]], truckSize = 10
輸出：91

func maximumUnits(boxTypes [][]int, truckSize int) int {
    sort.Slice(boxTypes, func(i, j int) bool {
        return boxTypes[i][1] > boxTypes[j][1]
    })
    res := 0
    for _, v := range boxTypes {
        size := min(truckSize, v[0])
        res += size * v[1]
        truckSize -= size
    }
    return res
}

1217. 玩籌碼(簡單/貪心)

有 n 個(gè)籌碼歼捐。第 i 個(gè)籌碼的位置是 position[i] 何陆。我們需要把所有籌碼移到同一個(gè)位置。在一步中豹储，我們可以將第 i 個(gè)籌碼的位置從 position[i] 改變?yōu)?
position[i] + 2 或 position[i] - 2 贷盲，此時(shí) cost = 0
position[i] + 1 或 position[i] - 1 ，此時(shí) cost = 1
返回將所有籌碼移動(dòng)到同一位置上所需要的 最小代價(jià) 剥扣。

輸入：position = [1,2,3]
輸出：1
解釋：第一步:將位置3的籌碼移動(dòng)到位置1巩剖，成本為0。
第二步:將位置2的籌碼移動(dòng)到位置1钠怯，成本= 1佳魔。
總成本是1。

輸入：position = [2,2,2,3,3]
輸出：2
解釋：我們可以把位置3的兩個(gè)籌碼移到位置2晦炊。每一步的成本為1鞠鲜。總成本= 2断国。

輸入：position = [1,1000000000]
輸出：1

1247. 交換字符使得字符串相同（中等）

有兩個(gè)長度相同的字符串 s1 和 s2贤姆，且它們其中 只含有 字符 "x" 和 "y"，你需要通過「交換字符」的方式使這兩個(gè)字符串相同稳衬。每次「交換字符」的時(shí)候霞捡，你都可以在兩個(gè)字符串中各選一個(gè)字符進(jìn)行交換。交換只能發(fā)生在兩個(gè)不同的字符串之間薄疚，絕對不能發(fā)生在同一個(gè)字符串內(nèi)部弄砍。也就是說，我們可以交換 s1[i] 和 s2[j]输涕，但不能交換 s1[i] 和 s1[j]音婶。最后，請你返回使 s1 和 s2 相同的最小交換次數(shù)莱坎，如果沒有方法能夠使得這兩個(gè)字符串相同铜跑，則返回 -1 。

輸入：s1 = "xx", s2 = "yy"
輸出：1
解釋：
交換 s1[0] 和 s2[1]慕趴，得到 s1 = "yx"深夯，s2 = "yx"。

輸入：s1 = "xy", s2 = "yx"
輸出：2
解釋：
交換 s1[0] 和 s2[0]乃正，得到 s1 = "yy"住册，s2 = "xx" 。
交換 s1[0] 和 s2[1]瓮具，得到 s1 = "xy"荧飞，s2 = "xy" 凡人。
注意，你不能交換 s1[0] 和 s1[1] 使得 s1 變成 "yx"叹阔，因?yàn)槲覀冎荒芙粨Q屬于兩個(gè)不同字符串的字符挠轴。

輸入：s1 = "xx", s2 = "xy"
輸出：-1

輸入：s1 = "xxyyxyxyxx", s2 = "xyyxyxxxyx"
輸出：4

1400. 構(gòu)造 K 個(gè)回文字符串（中等/貪心）

給你一個(gè)字符串 s 和一個(gè)整數(shù) k 。請你用 s 字符串中 所有字符 構(gòu)造 k 個(gè)非空 回文串 耳幢。如果你可以用 s 中所有字符構(gòu)造 k 個(gè)回文字符串岸晦，那么請你返回 True ，否則返回 False 睛藻。

輸入：s = "annabelle", k = 2
輸出：true
解釋：可以用 s 中所有字符構(gòu)造 2 個(gè)回文字符串启上。
一些可行的構(gòu)造方案包括："anna" + "elble"，"anbna" + "elle"店印，"anellena" + "b"

輸入：s = "leetcode", k = 3
輸出：false
解釋：無法用 s 中所有字符構(gòu)造 3 個(gè)回文串冈在。

輸入：s = "true", k = 4
輸出：true
解釋：唯一可行的方案是讓 s 中每個(gè)字符單獨(dú)構(gòu)成一個(gè)字符串。

輸入：s = "yzyzyzyzyzyzyzy", k = 2
輸出：true
解釋：你只需要將所有的 z 放在一個(gè)字符串中吱窝，所有的 y 放在另一個(gè)字符串中讥邻。那么兩個(gè)字符串都是回文串。

輸入：s = "cr", k = 7
輸出：false
解釋：我們沒有足夠的字符去構(gòu)造 7 個(gè)回文串院峡。

921. 使括號有效的最少添加（中等/貪心）

只有滿足下面幾點(diǎn)之一兴使，括號字符串才是有效的：
它是一個(gè)空字符串，或者
它可以被寫成 AB （A 與 B 連接）, 其中 A 和 B 都是有效字符串照激，或者
它可以被寫作 (A)发魄，其中 A 是有效字符串。
給定一個(gè)括號字符串 s 俩垃，在每一次操作中励幼，你都可以在字符串的任何位置插入一個(gè)括號

例如，如果 s = "()))" 口柳，你可以插入一個(gè)開始括號為 "(()))" 或結(jié)束括號為 "())))" 苹粟。
返回 為使結(jié)果字符串 s 有效而必須添加的最少括號數(shù)。

輸入：s = "())"
輸出：1

輸入：s = "((("
輸出：3

func minAddToMakeValid(S string) int {
    //left, right 分別表示左右未配對的括號
    left, right := 0, 0
    for _, s := range S {
        if s == '(' {
            left++
        } else if left > 0 && s == ')' {
            left--
        } else {
            right++
        }
    }
    return left + right
}

1029. 兩地調(diào)度（中等/貪心）

公司計(jì)劃面試 2n 人跃闹。給你一個(gè)數(shù)組 costs 嵌削，其中 costs[i] = [aCosti, bCosti] 。第 i 人飛往 a 市的費(fèi)用為 aCosti 望艺，飛往 b 市的費(fèi)用為 bCosti 苛秕。返回將每個(gè)人都飛到 a 、b 中某座城市的最低費(fèi)用找默，要求每個(gè)城市都有 n 人抵達(dá)艇劫。

輸入：costs = [[10,20],[30,200],[400,50],[30,20]]
輸出：110
解釋：
第一個(gè)人去 a 市，費(fèi)用為 10惩激。
第二個(gè)人去 a 市店煞，費(fèi)用為 30蟹演。
第三個(gè)人去 b 市，費(fèi)用為 50浅缸。
第四個(gè)人去 b 市轨帜，費(fèi)用為 20魄咕。

最低總費(fèi)用為 10 + 30 + 50 + 20 = 110衩椒，每個(gè)城市都有一半的人在面試。

輸入：costs = [[259,770],[448,54],[926,667],[184,139],[840,118],[577,469]]
輸出：1859

// 思路很重要：
我們這樣來看這個(gè)問題哮兰，公司首先將這 2N 個(gè)人全都安排飛往 B 市毛萌，
再選出 N 個(gè)人改變它們的行程，讓他們飛往 A 市喝滞。
如果選擇改變一個(gè)人的行程阁将，那么公司將會(huì)額外付出 price_A - price_B 的費(fèi)用，這個(gè)費(fèi)用可正可負(fù)右遭。
因此最優(yōu)的方案是做盅，選出 price_A - price_B 最小的 N 個(gè)人，讓他們飛往 A 市窘哈，其余人飛往 B 市吹榴。
func twoCitySchedCost(costs [][]int) int {
    sort.Slice(costs, func(i, j int) bool {
        return (costs[i][0] - costs[i][1]) > (costs[j][0] - costs[j][1])
    })

    cost := 0
    for i := 0; i < len(costs)/2; i++ { // 去B城市的
        cost += costs[i][1]
    }

    for i := len(costs) / 2; i < len(costs); i++ { // 去A城市的
        cost += costs[i][0]
    }

    return cost
}

1605. 給定行和列的和求可行矩陣 (中等/貪心)

給你兩個(gè)非負(fù)整數(shù)數(shù)組 rowSum 和 colSum ，其中 rowSum[i] 是二維矩陣中第 i 行元素的和滚婉， colSum[j] 是第 j 列元素的和图筹。換言之你不知道矩陣?yán)锏拿總€(gè)元素，但是你知道每一行和每一列的和让腹。請找到大小為 rowSum.length x colSum.length 的任意 非負(fù)整數(shù) 矩陣远剩，且該矩陣滿足 rowSum 和 colSum 的要求。請你返回任意一個(gè)滿足題目要求的二維矩陣骇窍，題目保證存在 至少一個(gè) 可行矩陣瓜晤。

輸入：rowSum = [3,8], colSum = [4,7]
輸出：[[3,0],
      [1,7]]
解釋：
第 0 行：3 + 0 = 3 == rowSum[0]
第 1 行：1 + 7 = 8 == rowSum[1]
第 0 列：3 + 1 = 4 == colSum[0]
第 1 列：0 + 7 = 7 == colSum[1]
行和列的和都滿足題目要求，且所有矩陣元素都是非負(fù)的腹纳。
另一個(gè)可行的矩陣為：[[1,2],
                  [3,5]]

輸入：rowSum = [5,7,10], colSum = [8,6,8]
輸出：[[0,5,0],
      [6,1,0],
      [2,0,8]]

輸入：rowSum = [14,9], colSum = [6,9,8]
輸出：[[0,9,5],
      [6,0,3]]

135. 分發(fā)糖果 (困難/貪心)

n 個(gè)孩子站成一排痢掠。給你一個(gè)整數(shù)數(shù)組 ratings 表示每個(gè)孩子的評分。你需要按照以下要求只估，給這些孩子分發(fā)糖果：
每個(gè)孩子至少分配到 1 個(gè)糖果志群。
相鄰兩個(gè)孩子評分更高的孩子會(huì)獲得更多的糖果。
請你給每個(gè)孩子分發(fā)糖果蛔钙，計(jì)算并返回需要準(zhǔn)備的 最少糖果數(shù)目 锌云。

輸入：ratings = [1,0,2]
輸出：5
解釋：你可以分別給第一個(gè)、第二個(gè)吁脱、第三個(gè)孩子分發(fā) 2桑涎、1彬向、2 顆糖果。

輸入：ratings = [1,2,2]
輸出：4
解釋：你可以分別給第一個(gè)攻冷、第二個(gè)娃胆、第三個(gè)孩子分發(fā) 1、2等曼、1 顆糖果里烦。
     第三個(gè)孩子只得到 1 顆糖果，這滿足題面中的兩個(gè)條件禁谦。

53. 最大子數(shù)組和（中等/貪心）

給你一個(gè)整數(shù)數(shù)組 nums 胁黑，請你找出一個(gè)具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個(gè)元素），返回其最大和州泊。子數(shù)組 是數(shù)組中的一個(gè)連續(xù)部分丧蘸。

輸入：nums = [-2,1,-3,4,-1,2,1,-5,4]
輸出：6
解釋：連續(xù)子數(shù)組 [4,-1,2,1] 的和最大，為 6 遥皂。

輸入：nums = [5,4,-1,7,8]
輸出：23

280. 擺動(dòng)排序 (會(huì)員/中等/貪心)

給你一個(gè)的整數(shù)數(shù)組 nums, 將該數(shù)組重新排序后使 nums[0] <= nums[1] >= nums[2] <= nums[3]... 
輸入數(shù)組總是有一個(gè)有效的答案力喷。

輸入：nums = [3,5,2,1,6,4]
輸出：[3,5,1,6,2,4]
解釋：[1,6,2,5,3,4]也是有效的答案

輸入：nums = [6,6,5,6,3,8]
輸出：[6,6,5,6,3,8]

738. 單調(diào)遞增的數(shù)字(中等/貪心)

當(dāng)且僅當(dāng)每個(gè)相鄰位數(shù)上的數(shù)字 x 和 y 滿足 x <= y 時(shí)，我們稱這個(gè)整數(shù)是單調(diào)遞增的演训。給定一個(gè)整數(shù) n 弟孟，返回 小于或等于 n 的最大數(shù)字，且數(shù)字呈 單調(diào)遞增 仇祭。

輸入: n = 10
輸出: 9

輸入: n = 1234
輸出: 1234

輸入: n = 332
輸出: 299

402. 移掉 K 位數(shù)字(中等/貪心)

給你一個(gè)以字符串表示的非負(fù)整數(shù) num 和一個(gè)整數(shù) k 披蕉，移除這個(gè)數(shù)中的 k 位數(shù)字，使得剩下的數(shù)字最小乌奇。請你以字符串形式返回這個(gè)最小的數(shù)字没讲。

輸入：num = "1432219", k = 3
輸出："1219"
解釋：移除掉三個(gè)數(shù)字 4, 3, 和 2 形成一個(gè)新的最小的數(shù)字 1219 。

輸入：num = "10200", k = 1
輸出："200"
解釋：移掉首位的 1 剩下的數(shù)字為 200. 注意輸出不能有任何前導(dǎo)零礁苗。

輸入：num = "10", k = 2
輸出："0"
解釋：從原數(shù)字移除所有的數(shù)字爬凑，剩余為空就是 0 。

861. 翻轉(zhuǎn)矩陣后的得分(中等/貪心)

有一個(gè)二維矩陣 A 其中每個(gè)元素的值為 0 或 1 试伙。移動(dòng)是指選擇任一行或列嘁信，并轉(zhuǎn)換該行或列中的每一個(gè)值：將所有 0 都更改為 1，將所有 1 都更改為 0疏叨。在做出任意次數(shù)的移動(dòng)后潘靖，將該矩陣的每一行都按照二進(jìn)制數(shù)來解釋，矩陣的得分就是這些數(shù)字的總和蚤蔓。返回盡可能高的分?jǐn)?shù)卦溢。

輸入：[[0,0,1,1],[1,0,1,0],[1,1,0,0]]
輸出：39
解釋：
轉(zhuǎn)換為 [[1,1,1,1],[1,0,0,1],[1,1,1,1]]
0b1111 + 0b1001 + 0b1111 = 15 + 9 + 15 = 39

555. 分割連接字符串（會(huì)員/中等/貪心）

給定一個(gè)字符串列表 strs，你可以將這些字符串連接成一個(gè)循環(huán)字符串，對于每個(gè)字符串单寂，你可以選擇是否翻轉(zhuǎn)它贬芥。在所有可能的循環(huán)字符串中，你需要分割循環(huán)字符串（這將使循環(huán)字符串變成一個(gè)常規(guī)的字符串）宣决，然后找到字典序最大的字符串蘸劈。具體來說，要找到字典序最大的字符串尊沸，你需要經(jīng)歷兩個(gè)階段：

將所有字符串連接成一個(gè)循環(huán)字符串威沫，你可以選擇是否翻轉(zhuǎn)某些字符串，并按照給定的順序連接它們椒丧。
在循環(huán)字符串的某個(gè)位置分割它壹甥，這將使循環(huán)字符串從分割點(diǎn)變成一個(gè)常規(guī)的字符串救巷。
你的工作是在所有可能的常規(guī)字符串中找到字典序最大的一個(gè)壶熏。

輸入: strs = ["abc","xyz"]
輸出: "zyxcba"
解釋: 你可以得到循環(huán)字符串 "-abcxyz-", "-abczyx-", "-cbaxyz-", "-cbazyx-"，其中 '-' 代表循環(huán)狀態(tài)浦译。 
答案字符串來自第四個(gè)循環(huán)字符串棒假， 你可以從中間字符 'a' 分割開然后得到 "zyxcba"。

輸入: strs = ["abc"]
輸出: "cba"

2144. 打折購買糖果的最小開銷（簡單/貪心）

一家商店正在打折銷售糖果精盅。每購買 兩個(gè) 糖果帽哑，商店會(huì) 免費(fèi) 送一個(gè)糖果。免費(fèi)送的糖果唯一的限制是：它的價(jià)格需要小于等于購買的兩個(gè)糖果價(jià)格的 較小值 叹俏。比方說妻枕，總共有 4 個(gè)糖果，價(jià)格分別為 1 粘驰，2 屡谐，3 和 4 ，一位顧客買了價(jià)格為 2 和 3 的糖果蝌数，那么他可以免費(fèi)獲得價(jià)格為 1 的糖果愕掏，但不能獲得價(jià)格為 4 的糖果。
給你一個(gè)下標(biāo)從 0 開始的整數(shù)數(shù)組 cost 顶伞，其中 cost[i] 表示第 i 個(gè)糖果的價(jià)格饵撑，請你返回獲得 所有 糖果的 最小 總開銷。

輸入：cost = [1,2,3]
輸出：5
解釋：我們購買價(jià)格為 2 和 3 的糖果唆貌，然后免費(fèi)獲得價(jià)格為 1 的糖果滑潘。
總開銷為 2 + 3 = 5 。這是開銷最小的 唯一 方案锨咙。
注意语卤，我們不能購買價(jià)格為 1 和 3 的糖果，并免費(fèi)獲得價(jià)格為 2 的糖果。
這是因?yàn)槊赓M(fèi)糖果的價(jià)格必須小于等于購買的 2 個(gè)糖果價(jià)格的較小值粱侣。

輸入：cost = [6,5,7,9,2,2]
輸出：23
解釋：最小總開銷購買糖果方案為：
- 購買價(jià)格為 9 和 7 的糖果
- 免費(fèi)獲得價(jià)格為 6 的糖果
- 購買價(jià)格為 5 和 2 的糖果
- 免費(fèi)獲得價(jià)格為 2 的最后一個(gè)糖果
因此羊壹，最小總開銷為 9 + 7 + 5 + 2 = 23 。

輸入：cost = [5,5]
輸出：10
解釋：由于只有 2 個(gè)糖果齐婴，我們需要將它們都購買油猫，而且沒有免費(fèi)糖果。
所以總最小開銷為 5 + 5 = 10 柠偶。

func minimumCost(cost []int) int {
    sort.Sort(sort.Reverse(sort.IntSlice(cost)))
    res := 0
    for i := range cost {
        if i%3 != 2 {
            res += cost[i]
        }
    }
    return res
}

2098. 長度為 K 的最大偶數(shù)和子序列（會(huì)員/中等/貪心）

給你一個(gè)整數(shù)數(shù)組 nums 和一個(gè)整數(shù) k 情妖。找出 nums 長度為 k 的所有子序列中的 最大偶數(shù)和 。
返回此總和诱担，如果此總和不存在毡证，則返回 -1。
子序列 是一個(gè)數(shù)組蔫仙，可以通過刪除一些元素或不刪除任何元素而從另一個(gè)數(shù)組派生料睛，而不改變其余元素的順序。

輸入: nums = [4,1,5,3,1], k = 3
輸出: 12
解釋:
具有最大可能偶數(shù)和的子序列是[4,5,3]摇邦。它的和為 4 + 5 + 3 = 12

/*
思路：
1恤煞、先降序排序，計(jì)算前K個(gè)數(shù)的和施籍，如果是偶數(shù)居扒，直接返回結(jié)果。如果是奇數(shù)丑慎，往下喜喂。
2、求前k個(gè)數(shù)中竿裂， 最小的奇數(shù)和偶數(shù)
3玉吁、求后n-k個(gè)數(shù)中最大的奇數(shù)和偶數(shù)
4、前k個(gè)數(shù)和為奇數(shù)铛绰，故減去其中最小的奇/偶數(shù)诈茧，加上后n-k個(gè)數(shù)中最大的偶/奇數(shù)，兩個(gè)值返回最大
*/
func largestEvenSum(nums []int, k int) int64 {

    sort.Sort(sort.Reverse(sort.IntSlice(nums)))

    tempSum := 0
    for i := 0; i < k; i++ {
        tempSum += nums[i]
    }

    if tempSum%2 == 0 {
        return int64(tempSum)
    }

    minOdd := math.MaxInt32
    minEven := math.MaxInt32

    for i := 0; i < k; i++ {
        if nums[i]%2 != 0 && nums[i] < minOdd { //奇數(shù)
            minOdd = nums[i]
        }

        if nums[i]%2 == 0 && nums[i] < minEven {
            minEven = nums[i]
        }
    }

    maxOdd := math.MinInt32
    maxEven := math.MinInt32

    for i := k; i < len(nums); i++ {
        if nums[i]%2 != 0 && nums[i] > maxOdd { //奇數(shù)
            maxOdd = nums[i]
        }

        if nums[i]%2 == 0 && nums[i] > maxEven {
            maxEven = nums[i]
        }
    }

    // 前k個(gè)數(shù)和為奇數(shù)捂掰，故減去其中最小的奇/偶數(shù)敢会，加上后n-k個(gè)數(shù)中最大的偶/奇數(shù)，兩個(gè)值返回最大这嚣，這兩個(gè)值也可能不存在
    ans1 := -1
    ans0 := -1
    if minOdd != math.MaxInt32 && maxEven != math.MinInt32 {
        ans1 = tempSum + maxEven - minOdd
    }
    if minEven != math.MaxInt32 && maxOdd != math.MinInt32 {
        ans0 = tempSum + maxOdd - minEven
    }
    return max(ans0, ans1)  // 不存在就返回-1
}

624. 數(shù)組列表中的最大距離(會(huì)員/中等/貪心)

給定 m 個(gè)數(shù)組鸥昏，每個(gè)數(shù)組都已經(jīng)按照升序排好序了。現(xiàn)在你需要從兩個(gè)不同的數(shù)組中選擇兩個(gè)整數(shù)（每個(gè)數(shù)組選一個(gè)）并且計(jì)算它們的距離姐帚。兩個(gè)整數(shù) a 和 b 之間的距離定義為它們差的絕對值 |a-b| 吏垮。你的任務(wù)就是去找到最大距離

輸入： 
[[1,2,3],
 [4,5],
 [1,2,3]]
輸出： 4
解釋：
一種得到答案 4 的方法是從第一個(gè)數(shù)組或者第三個(gè)數(shù)組中選擇 1，同時(shí)從第二個(gè)數(shù)組中選擇 5 。
 

1686. 石子游戲 VI（中等）

484. 尋找排列（會(huì)員/中等）

由范圍 [1,n] 內(nèi)所有整數(shù)組成的 n 個(gè)整數(shù)的排列 perm 可以表示為長度為 n - 1 的字符串 s 膳汪，其中:

如果 perm[i] < perm[i + 1] 唯蝶，那么 s[i] == ' i '
如果 perm[i] > perm[i + 1] ，那么 s[i] == 'D' 遗嗽。
給定一個(gè)字符串 s 粘我，重構(gòu)字典序上最小的排列 perm 并返回它。

輸入： s = "I"
輸出： [1,2]
解釋： [1,2] 是唯一合法的可以生成秘密簽名 "I" 的特定串痹换，數(shù)字 1 和 2 構(gòu)成遞增關(guān)系征字。

輸入： s = "DI"
輸出： [2,1,3]
解釋： [2,1,3] 和 [3,1,2] 可以生成秘密簽名 "DI"，
但是由于我們要找字典序最小的排列娇豫，因此你需要輸出 [2,1,3]匙姜。