百度的
華子的筆試記錄
華子第二道
可以把提供的前置后置，轉(zhuǎn)成課程表的二維數(shù)組，
0 編號為0的服務(wù)沒有前置服務(wù)
1,0 編號為1的服務(wù)有1個前置张漂，服務(wù)編號為0
1,1 編號為2的服務(wù)有1個前置冕杠，服務(wù)編號為1
2,0,1 編號為3的服務(wù)有1個前置，服務(wù)編號為0,1
轉(zhuǎn)化成:[1,0][2,1][3,1]
第二題 拓撲排序
leetcode的課程表：
思路：建立一個入度表
入度表 隊列 中間存儲
1.統(tǒng)計課程安排圖中每個節(jié)點的入度洼哎，生成 入度表 indegrees烫映。
2.用一個·List<List<Integer>>存儲兩者的依賴關(guān)系，第幾個list是節(jié)點噩峦，存儲它的前置節(jié)點
- 借助一個隊列 queue锭沟，將所有入度為 0 的節(jié)點入隊。當 queue 非空時识补，依次將隊首節(jié)點出隊族淮，在課程安排圖中刪除此節(jié)點 pre：
并不是真正從鄰接表中刪除此節(jié)點 pre，而是將此節(jié)點對應(yīng)所有鄰接節(jié)點 cur 的入度 變成?1凭涂，即 indegrees [cur] -= 1瞧筛。
// 當入度 -1后鄰接節(jié)點 cur 的入度為 0，說明 cur 所有的前驅(qū)節(jié)點已經(jīng)被 “刪除”导盅，此時將 cur 入隊较幌。
在每次 pre 出隊時，執(zhí)行 numCourses--白翻；
若整個課程安排圖是有向無環(huán)圖（即可以安排）乍炉，則所有節(jié)點一定都入隊并出隊過，即完成拓撲排序滤馍。換個角度說岛琼，若課程安排圖中存在環(huán)，一定有節(jié)點的入度始終不為 0巢株。
因此槐瑞，拓撲排序出隊次數(shù)等于課程個數(shù)，返回 numCourses == 0 判斷課程是否可以成功安排阁苞。
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
int[] indegrees=new int[numCourses];
List<List<Integer>> list=new ArrayList<>();
Queue<Integer> queue=new LinkedList<Integer>();
int n=numCourses;
for(int i=0;i<n;i++){
list.add(new ArrayList<Integer>());
}
for(int[] cp:prerequisites){
indegrees[cp[0]]++;
list.get(cp[1]).add(cp[0]);
}
for(int i=0;i<n;i++){
if(indegrees[i]==0){
queue.add(i);
}
}
while(!queue.isEmpty()){
int pre=queue.poll();
numCourses--;
for(int cur:list.get(pre)){
if(--indegrees[cur]==0){
queue.add(cur);
}
}
}
// System.out.println(numCourses);
return numCourses==0;
}
}
2 商店買東西的規(guī)劃困檩。N個商品，第i個商品開業(yè)有個初始價格Ai那槽，以后每天漲價Bi悼沿，也就是說第d天的價格為Ai + Bi * d。購買從第0天開始骚灸，奇數(shù)天做活動可以買一送一糟趾。問買到所有商品最少需要花費多少？
輸入
3
6 8
2 9
4 7
輸出
13
第0天 買了 2
第1天買了 4+7的商品 11 送了 6+8的商品
首先可以考慮，當要購買的商品集合確定的時候义郑，A[i]的大小是不影響結(jié)果的蝶柿，結(jié)果只和Bi大小有關(guān)，越大的越要先買非驮，所以先按Bi排序只锭，接下來就是確定哪些商品是要購買的，可以算出來要購買的件數(shù)是m院尔，dp[i][j]表示前i件物品選了j件的最小代價蜻展，每次有選和不選兩種選項，最后dp[n][m]就是結(jié)果
