1005、K 次取反后最大化的數(shù)組和

給你一個整數(shù)數(shù)組 nums 和一個整數(shù) k ，按以下方法修改該數(shù)組：

• 選擇某個下標 i 并將 nums[i] 替換為 -nums[i] 。

重復這個過程恰好 k 次?？梢远啻芜x擇同一個下標 i 。

以這種方式修改數(shù)組后，返回數(shù)組 可能的最大和 。

示例 1：

輸入：nums = [4,2,3], k = 1
輸出：5
解釋：選擇下標 1 ，nums 變?yōu)?[4,-2,3] 。

示例 2：

輸入：nums = [3,-1,0,2], k = 3
輸出：6
解釋：選擇下標 (1, 2, 2) ，nums 變?yōu)?[3,1,0,2] 。

class Solution {public int largestSumAfterKNegations(int[] nums, int k) {// 排序，把可能有的負數(shù)排到前面Arrays.sort(nums);int sum = 0;for (int i = 0; i < nums.length; i++) {// 貪心：如果是負數(shù)，而k還有盈余，就把負數(shù)反過來if (nums[i] < 0 && k > 0) {nums[i] = -1 * nums[i];k--;}sum += nums[i];}Arrays.sort(nums);// 如果k沒剩，那說明能轉的負數(shù)都轉正了，已經(jīng)是最大和，返回sum，此時k等于0// 如果k有剩，說明負數(shù)已經(jīng)全部轉正，所以如果k還剩偶數(shù)個就自己抵消掉，不用刪減，如果k還剩奇數(shù)個就減掉2倍最小正數(shù)。return sum - (k % 2 == 0 ? 0 : 2 * nums[0]); }
}

134、加油站

在一條環(huán)路上有 n 個加油站，其中第 i 個加油站有汽油 gas[i] 升。

你有一輛油箱容量無限的的汽車，從第 i 個加油站開往第 i+1 個加油站需要消耗汽油 cost[i] 升。你從其中的一個加油站出發(fā)，開始時油箱為空。

給定兩個整數(shù)數(shù)組 gas 和 cost ，如果你可以按順序繞環(huán)路行駛一周，則返回出發(fā)時加油站的編號，否則返回 -1 。如果存在解，則 保證 它是 唯一 的。

示例 1:

輸入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
輸出: 3
解釋:
從 3 號加油站(索引為 3 處)出發(fā)，可獲得 4 升汽油。此時油箱有 = 0 + 4 = 4 升汽油
開往 4 號加油站，此時油箱有 4 - 1 + 5 = 8 升汽油
開往 0 號加油站，此時油箱有 8 - 2 + 1 = 7 升汽油
開往 1 號加油站，此時油箱有 7 - 3 + 2 = 6 升汽油
開往 2 號加油站，此時油箱有 6 - 4 + 3 = 5 升汽油
開往 3 號加油站，你需要消耗 5 升汽油，正好足夠你返回到 3 號加油站。
因此，3 可為起始索引。

示例 2:

輸入: gas = [2,3,4], cost = [3,4,3]
輸出: -1
解釋:
你不能從 0 號或 1 號加油站出發(fā)，因為沒有足夠的汽油可以讓你行駛到下一個加油站。
我們從 2 號加油站出發(fā)，可以獲得 4 升汽油。 此時油箱有 = 0 + 4 = 4 升汽油
開往 0 號加油站，此時油箱有 4 - 3 + 2 = 3 升汽油
開往 1 號加油站，此時油箱有 3 - 3 + 3 = 3 升汽油
你無法返回 2 號加油站，因為返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。
因此，無論怎樣，你都不可能繞環(huán)路行駛一周。

首先如果總油量減去總消耗大于等于零那么一定可以跑完一圈，說明 各個站點的加油站 剩油量rest[i]相加一定是大于等于零的。

i從0開始累加rest[i]，和記為curSum，一旦curSum小于零，說明[0, i]區(qū)間都不能作為起始位置，因為這個區(qū)間選擇任何一個位置作為起點，到i這里都會斷油，那么起始位置從i+1算起，再從0計算curSum。

有沒有可能從[0, i]區(qū)間的某一位置開始，也可以有起始位置？，即curSum大于0

如圖：

如果 curSum<0 說明 區(qū)間和1 + 區(qū)間和2 < 0， 那么 假設從上圖中的位置開始計數(shù)curSum不會小于0的話，就是 區(qū)間和2>0。

區(qū)間和1 + 區(qū)間和2 < 0 同時 區(qū)間和2>0，只能說明區(qū)間和1 < 0， 那么就會從假設的箭頭初就開始從新選擇其實位置了。即如果可以作為起始位置，我們在i之前就會把它作為起始位置了

那么局部最優(yōu)：當前累加rest[i]的和curSum一旦小于0，起始位置至少要是i+1，因為從i之前開始一定不行。全局最優(yōu)：找到可以跑一圈的起始位置

class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {int curSum=0;int totalSum=0;int start=0;for(int i=0;i<gas.length;i++)totalSum+=gas[i]-cost[i];if(totalSum<0)return -1;for(int i=0;i<gas.length;i++){curSum+=gas[i]-cost[i];if(curSum<0){start=i+1;curSum=0;}}return start;}
}

135、分發(fā)糖果

n 個孩子站成一排。給你一個整數(shù)數(shù)組 ratings 表示每個孩子的評分。

你需要按照以下要求，給這些孩子分發(fā)糖果：

• 每個孩子至少分配到 1 個糖果。
• 相鄰兩個孩子評分更高的孩子會獲得更多的糖果。

請你給每個孩子分發(fā)糖果，計算并返回需要準備的 最少糖果數(shù)目 。

示例 1：

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

示例 2：

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

先確定右邊評分大于左邊的情況（也就是從前向后遍歷）

此時局部最優(yōu)：只要右邊評分比左邊大，右邊的孩子就多一個糖果，全局最優(yōu)：相鄰的孩子中，評分高的右孩子獲得比左邊孩子更多的糖果

再確定左孩子大于右孩子的情況（從后向前遍歷）

如果 ratings[i] > ratings[i + 1]，此時candyVec[i]（第i個小孩的糖果數(shù)量）就有兩個選擇了，一個是candyVec[i + 1] + 1（從右邊這個加1得到的糖果數(shù)量），一個是candyVec[i]（之前比較右孩子大于左孩子得到的糖果數(shù)量）。

class Solution {public int candy(int[] ratings) {int len =ratings.length;int[] candynum =new int[len];candynum[0]=1;//從左向右比較for(int i=1;i<len;i++){if(ratings[i]>ratings[i-1]){candynum[i]=candynum[i-1]+1;}else{candynum[i]=1;}}//從右向左比較：for(int i=len-2;i>=0;i--){if(ratings[i]>ratings[i+1]){candynum[i]=Math.max(candynum[i],candynum[i+1]+1);}}//統(tǒng)計：int sum=0;for(int i=0;i<candynum.length;i++){sum+=candynum[i];}return sum;}
}

860、檸檬水找零

在檸檬水攤上，每一杯檸檬水的售價為 5 美元。顧客排隊購買你的產(chǎn)品，（按賬單 bills 支付的順序）一次購買一杯。

每位顧客只買一杯檸檬水，然后向你付 5 美元、10 美元或 20 美元。你必須給每個顧客正確找零，也就是說凈交易是每位顧客向你支付 5 美元。

注意，一開始你手頭沒有任何零錢。

給你一個整數(shù)數(shù)組 bills ，其中 bills[i] 是第 i 位顧客付的賬。如果你能給每位顧客正確找零，返回 true ，否則返回 false 。

示例 1：

輸入：bills = [5,5,5,10,20]
輸出：true
解釋：
前 3 位顧客那里，我們按順序收取 3 張 5 美元的鈔票。
第 4 位顧客那里，我們收取一張 10 美元的鈔票，并返還 5 美元。
第 5 位顧客那里，我們找還一張 10 美元的鈔票和一張 5 美元的鈔票。
由于所有客戶都得到了正確的找零，所以我們輸出 true。

邏輯是非常固定的，唯一貪心的點就是盡可能的多留下五元的。

class Solution {public boolean lemonadeChange(int[] bills) {int[] money=new int[2]; //存儲剩余的5塊和10塊的數(shù)量for(int i=0;i<bills.length;i++){if(bills[i]==5){money[0]++;}else if(bills[i]==10){if(money[0]>0){money[0]--;money[1]++;} else return false;}else if(bills[i]==20){if(money[0]>0 && money[1]>0){money[0]--;money[1]--;}else if(money[0]>=3){money[0]=money[0]-3;}else{return false;}}}return true;}
}

406、根據(jù)身高重建隊列

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

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

示例 1：

輸入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
輸出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
解釋：
編號為 0 的人身高為 5 ，沒有身高更高或者相同的人排在他前面。
編號為 1 的人身高為 7 ，沒有身高更高或者相同的人排在他前面。
編號為 2 的人身高為 5 ，有 2 個身高更高或者相同的人排在他前面，即編號為 0 和 1 的人。
編號為 3 的人身高為 6 ，有 1 個身高更高或者相同的人排在他前面，即編號為 1 的人。
編號為 4 的人身高為 4 ，有 4 個身高更高或者相同的人排在他前面，即編號為 0、1、2、3 的人。
編號為 5 的人身高為 7 ，有 1 個身高更高或者相同的人排在他前面，即編號為 1 的人。
因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新構造后的隊列

本題好人分發(fā)糖果一樣，都是有兩個維度！所以要一個一個的來確定！

如果按照k來從小到大排序，排完之后，會發(fā)現(xiàn)k的排列并不符合條件，身高也不符合條件，兩個維度哪一個都沒確定下來。

那么按照身高h來排序呢，身高一定是從大到小排（身高相同的話則k小的站前面），讓高個子在前面。

此時我們可以確定一個維度了，就是身高，前面的節(jié)點一定都比本節(jié)點高！

那么只需要按照k為下標重新插入隊列就可以了

例如：

局部最優(yōu)：優(yōu)先按身高高的people的k來插入。插入操作過后的people滿足隊列屬性

全局最優(yōu)：最后都做完插入操作，整個隊列滿足題目隊列屬性

people[i] = [hi, ki]表示前面 正好 有 ki 個身高大于或等于 hi 的人。

所以，先按照身高進行排序，然后k來進行插入。

class Solution {public int[][] reconstructQueue(int[][] people) {int[][] result =new int[people.length][];Arrays.sort(people,(a,b)->{if(a[0]==b[0]) return a[1]-b[1]; //身高相同的，讓k小的在前面return b[0]-a[0];  //身高不同，按身高降序});LinkedList<int []> list =new LinkedList<>();for(int[] p:people){list.add(p[1],p);  //使用LinkedList 來根據(jù)位置進行插入}return list.toArray(result);}
}

452、用最少數(shù)量的箭引爆氣球

有一些球形氣球貼在一堵用 XY 平面表示的墻面上。墻面上的氣球記錄在整數(shù)數(shù)組 points ，其中points[i] = [xstart, xend] 表示水平直徑在 xstart 和 xend之間的氣球。你不知道氣球的確切 y 坐標。

一支弓箭可以沿著 x 軸從不同點 完全垂直 地射出。在坐標 x 處射出一支箭，若有一個氣球的直徑的開始和結束坐標為 xstart</font><font style="color:rgb(51, 51, 51);">，</font><font style="color:rgb(51, 51, 51);background-color:rgb(243, 244, 244);">xend， 且滿足 xstart ≤ x ≤ x``end，則該氣球會被 引爆 ?？梢陨涑龅墓臄?shù)量 沒有限制 。 弓箭一旦被射出之后，可以無限地前進。

給你一個數(shù)組 points ，返回引爆所有氣球所必須射出的 最小 弓箭數(shù) 。

示例 1：

輸入：points = [[10,16],[2,8],[1,6],[7,12]]
輸出：2
解釋：氣球可以用2支箭來爆破:
-在x = 6處射出箭，擊破氣球[2,8]和[1,6]。
-在x = 11處發(fā)射箭，擊破氣球[10,16]和[7,12]。

示例 2：

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

局部最優(yōu)：當氣球出現(xiàn)重疊，一起射，所用弓箭最少。全局最優(yōu)：把所有氣球射爆所用弓箭最少。

為了讓氣球盡可能的重疊，需要對數(shù)組進行排序。

使用重疊氣球最小右邊界來 判斷是否重疊，只要后面的氣球的左邊界小于前面重疊氣球的最小右邊界，就可以使用同一只箭來引爆，另外要注意要收縮后面氣球的右邊界。

如果氣球重疊了，重疊氣球中右邊邊界的最小值 之前的區(qū)間一定需要一個弓箭

可以看出首先第一組重疊氣球，一定是需要一個箭，氣球3，的左邊界大于了 第一組重疊氣球的最小右邊界，所以再需要一支箭來射氣球3了。

class Solution {public int findMinArrowShots(int[][] points) {// 根據(jù)氣球直徑的開始坐標從小到大排序// 使用Integer內(nèi)置比較方法，不會溢出Arrays.sort(points,(a,b)->Integer.compare(a[0],b[0]));//Arrays.sort(points,(a,b)->{ return a[0]-b[0];});   會超時溢出int count=1; //不為空 至少需要一個for(int i=1;i<points.length;i++){if(points[i][0]>points[i-1][1])  //和前面的沒有重疊{count++;}else   //有重疊，把當前的右邊界收縮到最短,這樣才能使用同一個箭，弓箭數(shù)不需要加{points[i][1]=Math.min(points[i-1][1],points[i][1]);}}return count;}
}

超時： 即最小的int減去最大的int，結果溢出。

435、無重疊區(qū)間

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

示例 1:

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

示例 2:

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

本題和前一題思路相同，先排序然后看是否重疊，如果重疊的話count++，并且把intervals[i]的右邊界取最小，相當于把右邊界大的給移除了

class Solution {public int eraseOverlapIntervals(int[][] intervals) {Arrays.sort(intervals,(a,b)->{return Integer.compare(a[0],b[0]);});int count=0; //用來計算需要移除的區(qū)間for(int i=1;i<intervals.length;i++){if(intervals[i][0]>=intervals[i-1][1]) //不重疊{continue;}else{  //重疊count++;//移除,并且右邊界取最小的,即右邊界大的會被移除intervals[i][1]=Math.min(intervals[i-1][1],intervals[i][1]);}}return count;}
}

763、劃分字母區(qū)間

給你一個字符串 s 。我們要把這個字符串劃分為盡可能多的片段，同一字母最多出現(xiàn)在一個片段中。

注意，劃分結果需要滿足：將所有劃分結果按順序連接，得到的字符串仍然是 s 。

返回一個表示每個字符串片段的長度的列表。

示例 1：

輸入：s = "ababcbacadefegdehijhklij"
輸出：[9,7,8]
解釋：
劃分結果為 "ababcbaca"、"defegde"、"hijhklij" 。
每個字母最多出現(xiàn)在一個片段中。
像 "ababcbacadefegde", "hijhklij" 這樣的劃分是錯誤的，因為劃分的片段數(shù)較少。

在遍歷的過程中相當于是要找每一個字母的邊界，如果找到之前遍歷過的所有字母的最遠邊界，說明這個邊界就是分割點了。此時前面出現(xiàn)過所有字母，最遠也就到這個邊界了。

可以分為如下兩步：

• 統(tǒng)計每一個字符最后出現(xiàn)的位置
• 從頭遍歷字符，并更新字符的最遠出現(xiàn)下標，如果找到字符最遠出現(xiàn)位置下標和當前下標相等了，則找到了分割點

如圖：

即找到最大的那個字符邊界，就是這一段的分割點

class Solution {public List<Integer> partitionLabels(String s) {List<Integer> result =new LinkedList<>();int [] edge =new int [26];   //記錄每個字母最后出現(xiàn)的位置char[] chars =s.toCharArray();for(int i=0;i<chars.length;i++){edge[chars[i]-'a']=i;   //記錄每個字母最后出現(xiàn)的位置}int index=0;int last=0;for(int i=0;i<chars.length;i++){//找到最后出現(xiàn)的最大值，以防止字母在后面還會出現(xiàn)index=Math.max(index,edge[chars[i]-'a']);  if(i==index)   //如果i就等于最后出現(xiàn)的位置，就可以是分界點了{result.add(index-last+1);last=index+1;}}return result;}
}

56、合并區(qū)間

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

示例 1：

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

示例 2：

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

class Solution {public int[][] merge(int[][] intervals) {List<int[]> result =new LinkedList<>();Arrays.sort(intervals,(a,b)->{return a[0]-b[0];});result.add(intervals[0]);for(int i=1;i<intervals.length;i++){if(intervals[i][0]>intervals[i-1][1])  //沒有重疊{result.add(intervals[i]);}else //有重疊的話,要移除前一個{intervals[i][1]=Math.max(intervals[i][1],intervals[i-1][1]);intervals[i][0]=intervals[i-1][0];result.removeLast();result.add(intervals[i]);}}return result.toArray(new int[result.size()][]);}
}

738、單調(diào)遞增的數(shù)字

當且僅當每個相鄰位數(shù)上的數(shù)字 x 和 y 滿足 x <= y 時，我們稱這個整數(shù)是單調(diào)遞增的。

給定一個整數(shù) n ，返回 小于或等于 n 的最大數(shù)字，且數(shù)字呈 __單調(diào)遞增 。

示例 1:

輸入: n = 10
輸出: 9

示例 2:

輸入: n = 1234
輸出: 1234

示例 3:

輸入: n = 332
輸出: 299

例如：98，一旦出現(xiàn)strNum[i - 1] > strNum[i]的情況（非單調(diào)遞增），首先想讓strNum[i - 1]–，然后strNum[i]給為9，這樣這個整數(shù)就是89，即小于98的最大的單調(diào)遞增整數(shù)。

從前向后遍歷的話，遇到strNum[i - 1] > strNum[i]的情況，讓strNum[i - 1]減一，但此時如果strNum[i - 1]減一了，可能又小于strNum[i - 2]。

所以要從后向前遍歷，就可以重復利用上次比較得出的結果了

class Solution {public int monotoneIncreasingDigits(int n) {String s=String.valueOf(n);char[] chars=s.toCharArray();int start=chars.length;for(int i=chars.length-2;i>=0;i--)   //從后向前判斷{if(chars[i]>chars[i+1]){chars[i]--;start=i+1;    //從最后一個減1的數(shù)之后開始都要變?yōu)?}}for(int i=start;i<chars.length;i++){chars[i]='9';}//先把chars變?yōu)镾tring，在轉為Integerreturn Integer.parseInt(String.valueOf(chars));}
}

968、監(jiān)控二叉樹

給定一個二叉樹，我們在樹的節(jié)點上安裝攝像頭。

節(jié)點上的每個攝影頭都可以監(jiān)視其父對象、自身及其直接子對象。

計算監(jiān)控樹的所有節(jié)點所需的最小攝像頭數(shù)量。

示例 1：

輸入：[0,0,null,0,0]
輸出：1
解釋：如圖所示，一臺攝像頭足以監(jiān)控所有節(jié)點。

示例 2：

輸入：[0,0,null,0,null,0,null,null,0]
輸出：2

貪心思想：為了充分利用攝像頭的覆蓋，要讓葉子結點的父節(jié)點安裝攝像頭。

所以我們要從下往上看，局部最優(yōu)：讓葉子節(jié)點的父節(jié)點安攝像頭，所用攝像頭最少，整體最優(yōu)：全部攝像頭數(shù)量所用最少！

從下到上，所以是后序遍歷。

jclass Solution {int  res=0;public int minCameraCover(TreeNode root) {// 對根節(jié)點的狀態(tài)做檢驗,防止根節(jié)點是無覆蓋狀態(tài) .if(minCame(root)==0){res++;}return res;
}
/**節(jié)點的狀態(tài)值：0 表示無覆蓋1 表示 有攝像頭2 表示有覆蓋后序遍歷，根據(jù)左右節(jié)點的情況,來判讀 自己的狀態(tài)*/
public int minCame(TreeNode root){
if(root==null){// 空節(jié)點默認為 有覆蓋狀態(tài)，避免在葉子節(jié)點上放攝像頭return 2;
}
int left=minCame(root.left);
int  right=minCame(root.right);// 如果左右節(jié)點都覆蓋了的話, 那么本節(jié)點的狀態(tài)就應該是無覆蓋,沒有攝像頭
if(left==2&&right==2){//(2,2)return 0;
}else if(left==0||right==0){// 左右節(jié)點都是無覆蓋狀態(tài),那根節(jié)點此時應該放一個攝像頭// (0,0) (0,1) (0,2) (1,0) (2,0)// 狀態(tài)值為 1 攝像頭數(shù) ++;res++;return 1;
}else{// 左右節(jié)點的 狀態(tài)為 (1,1) (1,2) (2,1) 也就是左右節(jié)點至少存在 1個攝像頭// 那么本節(jié)點就是處于被覆蓋狀態(tài)return 2;
}
}
}