LeetCode 807. 保持城市天际线 / 630. 课程表 III(贪心+优先队列)/ 851. 喧闹和富有(拓扑排序)
807. 保持城市天際線
2021.12.13 每日一題
題目描述
給你一座由 n x n 個街區(qū)組成的城市,每個街區(qū)都包含一座立方體建筑。給你一個下標從 0 開始的 n x n 整數矩陣 grid ,其中 grid[r][c] 表示坐落于 r 行 c 列的建筑物的 高度 。
城市的 天際線 是從遠處觀察城市時,所有建筑物形成的外部輪廓。從東、南、西、北四個主要方向觀測到的 天際線 可能不同。
我們被允許為 任意數量的建筑物 的高度增加 任意增量(不同建筑物的增量可能不同) 。 高度為 0 的建筑物的高度也可以增加。然而,增加的建筑物高度 不能影響 從任何主要方向觀察城市得到的 天際線 。
在 不改變 從任何主要方向觀測到的城市 天際線 的前提下,返回建筑物可以增加的 最大高度增量總和 。
示例 1:
輸入:grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]
輸出:35
解釋:建筑物的高度如上圖中心所示。
用紅色繪制從不同方向觀看得到的天際線。
在不影響天際線的情況下,增加建筑物的高度:
gridNew = [ [8, 4, 8, 7],
[7, 4, 7, 7],
[9, 4, 8, 7],
[3, 3, 3, 3] ]
示例 2:
輸入:grid = [[0,0,0],[0,0,0],[0,0,0]]
輸出:0
解釋:增加任何建筑物的高度都會導致天際線的變化。
提示:
n == grid.length
n == grid[r].length
2 <= n <= 50
0 <= grid[r][c] <= 100
來源:力扣(LeetCode)
鏈接:https://leetcode-cn.com/problems/max-increase-to-keep-city-skyline
著作權歸領扣網絡所有。商業(yè)轉載請聯系官方授權,非商業(yè)轉載請注明出處。
思路
class Solution {public int maxIncreaseKeepingSkyline(int[][] grid) {//每一個位置的最大高度就是橫豎兩個方向最低的高度//因為那是天際線int n = grid.length;int[] col = new int[n];int[] row = new int[n];for(int i = 0; i < n; i++){for(int j = 0; j < n; j++){col[i] = Math.max(col[i], grid[i][j]);row[j] = Math.max(row[j], grid[i][j]);}}int res = 0;for(int i = 0; i < n; i++){for(int j = 0; j < n; j++){int temp = Math.min(col[i], row[j]);res += temp - grid[i][j];}}return res;} }630. 課程表 III
2021.12.14 每日一題
題目描述
這里有 n 門不同的在線課程,按從 1 到 n 編號。給你一個數組 courses ,其中 courses[i] = [durationi, lastDayi] 表示第 i 門課將會 持續(xù) 上 durationi 天課,并且必須在不晚于 lastDayi 的時候完成。
你的學期從第 1 天開始。且不能同時修讀兩門及兩門以上的課程。
返回你最多可以修讀的課程數目。
示例 1:
輸入:courses = [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]
輸出:3
解釋:
這里一共有 4 門課程,但是你最多可以修 3 門:
首先,修第 1 門課,耗費 100 天,在第 100 天完成,在第 101 天開始下門課。
第二,修第 3 門課,耗費 1000 天,在第 1100 天完成,在第 1101 天開始下門課程。
第三,修第 2 門課,耗時 200 天,在第 1300 天完成。
第 4 門課現在不能修,因為將會在第 3300 天完成它,這已經超出了關閉日期。
示例 2:
輸入:courses = [[1,2]]
輸出:1
示例 3:
輸入:courses = [[3,2],[4,3]]
輸出:0
提示:
1 <= courses.length <= 10^4
1 <= durationi, lastDayi <= 10^4
來源:力扣(LeetCode)
鏈接:https://leetcode-cn.com/problems/course-schedule-iii
著作權歸領扣網絡所有。商業(yè)轉載請聯系官方授權,非商業(yè)轉載請注明出處。
思路
class Solution {public int scheduleCourse(int[][] courses) {//范圍是10的4次,應該是個拓撲排序我覺得//按照截止日期排序還是按照花費時間排序呢//如果按照截止日期排序的話,每次取出來是截止日期最早的,但是不是時間最短的,這樣會有問題嗎//應該是會有問題的,比如后面有幾個時間很短的,就不能被完成//首先明確第一點,兩門課程,有截止時間d1<=d2,那么先完成課程1再完成課程2肯定比反過來是更優(yōu)的//這是必然呢,因為想一下,如果能先學習后面的,再學習前面的,那么肯定可以先學習前面的,再學習后面的,而反過來就不一定了//所以將所有課程按照截止時間排序,依次選出課程//如果當前選出了一個最優(yōu)的課程序列,k1,k2..kn,判斷下一個課程是否可以加入這個序列//如果這個課程滿足截止時間的要求,那么可以加入,并且因為之前序列是最優(yōu)的,所以加入也是最優(yōu)的//如果這個課程不滿足截止時間的要求,那么就看這個課程能否替換原來序列的課程//如果原來序列中的課程時間都比這個課程短,那么不能替換;如果有一個比這個長,那么就可以進行替換int n = courses.length;//按照截止時間排序Arrays.sort(courses, (a, b) -> (a[1] - b[1]));//用一個優(yōu)先隊列記錄目前序列中的課程所需時間,替換堆頂的課程PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> (b - a));int time = 0;for(int i = 0; i < n; i++){int temptime = time + courses[i][0];//如果可以加入,那么插入最后if(temptime <= courses[i][1]){pq.offer(courses[i][0]);time = temptime;}else{//如果不可以,那么替換if(!pq.isEmpty() && pq.peek() > courses[i][0]){int t = pq.poll();pq.offer(courses[i][0]);time = time - t + courses[i][0];}}}return pq.size();} }851. 喧鬧和富有
2021.12.15 每日一題
題目描述
有一組 n 個人作為實驗對象,從 0 到 n - 1 編號,其中每個人都有不同數目的錢,以及不同程度的安靜值(quietness)。為了方便起見,我們將編號為 x 的人簡稱為 "person x "。
給你一個數組 richer ,其中 richer[i] = [ai, bi] 表示 person ai 比 person bi 更有錢。另給你一個整數數組 quiet ,其中 quiet[i] 是 person i 的安靜值。richer 中所給出的數據 邏輯自恰(也就是說,在 person x 比 person y 更有錢的同時,不會出現 person y 比 person x 更有錢的情況 )。
現在,返回一個整數數組 answer 作為答案,其中 answer[x] = y 的前提是,在所有擁有的錢肯定不少于 person x 的人中,person y 是最安靜的人(也就是安靜值 quiet[y] 最小的人)。
示例 1:
輸入:richer = [[1,0],[2,1],[3,1],[3,7],[4,3],[5,3],[6,3]], quiet = [3,2,5,4,6,1,7,0]
輸出:[5,5,2,5,4,5,6,7]
解釋:
answer[0] = 5,
person 5 比 person 3 有更多的錢,person 3 比 person 1 有更多的錢,person 1 比 person 0 有更多的錢。
唯一較為安靜(有較低的安靜值 quiet[x])的人是 person 7,
但是目前還不清楚他是否比 person 0 更有錢。
answer[7] = 7,
在所有擁有的錢肯定不少于 person 7 的人中(這可能包括 person 3,4,5,6 以及 7),
最安靜(有較低安靜值 quiet[x])的人是 person 7。
其他的答案也可以用類似的推理來解釋。
示例 2:
輸入:richer = [], quiet = [0]
輸出:[0]
提示:
n == quiet.length
1 <= n <= 500
0 <= quiet[i] < n
quiet 的所有值 互不相同
0 <= richer.length <= n * (n - 1) / 2
0 <= ai, bi < n
ai != bi
richer 中的所有數對 互不相同
對 richer 的觀察在邏輯上是一致的
來源:力扣(LeetCode)
鏈接:https://leetcode-cn.com/problems/loud-and-rich
著作權歸領扣網絡所有。商業(yè)轉載請聯系官方授權,非商業(yè)轉載請注明出處。
思路
這樣寫竟然超時了,相當于一個拓撲排序
因為是計算每個人的時候,都進行了一次圖的遍歷,其實做了很多無用功,應該是在一次遍歷的時候,如果遇到了能計算的,就直接計算出結果,后面就不用再遍歷一次這個值了
這樣應該能快很多,想想怎么寫
改成遞歸形式,做一次處理,過了
class Solution {Map<Integer, List<Integer>> map;int[] quiet;int[] res;public int[] loudAndRich(int[][] richer, int[] quiet) {//兩個比較的維度,一個是富有,一個是安靜//需要先將兩個維度進行排序,對于安靜值,比如說查一群人中安靜值最小的人,//首先得找到這群人,然后直接在quiet數組中比較這群人的安靜值就行了//那么怎么找這群人呢,就是根據richer給出的關系,可以構建一幅圖,然后根據這幅圖的關系來查找答案//怎么構造這幅圖比較方便呢,因為是單向的,所以可以構建一個二維數組//g[i][j]為true表示i比j有錢,或者就直接遍歷richer數組//比如判斷0位置,那么this.quiet = quiet;int n = quiet.length;int l = richer.length;//統計比key直接富有的人map = new HashMap<>();for(int i = 0; i < l; i++){int rich = richer[i][0];int poor = richer[i][1];List<Integer> list = map.getOrDefault(poor, new ArrayList<>());list.add(rich);map.put(poor, list);}res = new int[n];Arrays.fill(res, -1);for(int i = 0; i < n; i++){if(res[i] == -1)backtracking(i);}return res;}public int backtracking(int i){//如果沒有這個人的關系if(!map.containsKey(i)){res[i] = i;return i;}int min = quiet[i];int minp = i;List<Integer> list = map.get(i);for(int p : list){//如果這個人已經得到了結果了int temp = -1;if(res[p] != -1){temp = res[p];//否則遞歸}elsetemp = backtracking(p);if(quiet[temp] < min){min = quiet[temp];minp = temp;}}res[i] = minp;return minp;} }將圖反過來,可以用拓撲排序一次遍歷完成
class Solution {public int[] loudAndRich(int[][] richer, int[] quiet) {//寫一下一次的拓撲排序int n = quiet.length;int l = richer.length;boolean[][] g = new boolean[n][n]; //富有指向貧窮int[] inDeg = new int[n]; //入度for(int i = 0; i < l; i++){g[richer[i][0]][richer[i][1]] = true;inDeg[richer[i][1]]++;}Queue<Integer> queue = new LinkedList<>();int[] res = new int[n];for(int i = 0; i < n; i++){res[i] = i;if(inDeg[i] == 0)queue.add(i);}while(!queue.isEmpty()){int top = queue.poll();//遍歷所有比它貧窮的人for(int i = 0; i < n; i++){if(g[top][i]){//如果當前富有的這個人的安靜值比窮的人安靜值小,那么更改if(quiet[res[top]] < quiet[res[i]])res[i] = res[top];//這個人的入度減1inDeg[i]--;if(inDeg[i] == 0)queue.add(i);}}}return res;} }總結
以上是生活随笔為你收集整理的LeetCode 807. 保持城市天际线 / 630. 课程表 III(贪心+优先队列)/ 851. 喧闹和富有(拓扑排序)的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: scrapy实战之爬取简书
- 下一篇: 安全事件响应观察报告及其变种