百度的
华子的笔试记录
华子第二道
可以把提供的前置后置，转成课程表的二维数组，
0 编号为0的服务没有前置服务
1,0 编号为1的服务有1个前置，服务编号为0
1,1 编号为2的服务有1个前置，服务编号为1
2,0,1 编号为3的服务有1个前置，服务编号为0,1
转化成:[1,0][2,1][3,1]
第二题 拓扑排序
leetcode的课程表：
思路：建立一个入度表
入度表 队列 中间存储
1.统计课程安排图中每个节点的入度，生成 入度表 indegrees。
2.用一个·List<List<Integer>>存储两者的依赖关系，第几个list是节点，存储它的前置节点
- 借助一个队列 queue，将所有入度为 0 的节点入队。当 queue 非空时，依次将队首节点出队，在课程安排图中删除此节点 pre：
并不是真正从邻接表中删除此节点 pre，而是将此节点对应所有邻接节点 cur 的入度 变成−1，即 indegrees [cur] -= 1。
// 当入度 -1后邻接节点 cur 的入度为 0，说明 cur 所有的前驱节点已经被 “删除”，此时将 cur 入队。
在每次 pre 出队时，执行 numCourses--；
若整个课程安排图是有向无环图（即可以安排），则所有节点一定都入队并出队过，即完成拓扑排序。换个角度说，若课程安排图中存在环，一定有节点的入度始终不为 0。
因此，拓扑排序出队次数等于课程个数，返回 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 商店买东西的规划。N个商品，第i个商品开业有个初始价格Ai，以后每天涨价Bi，也就是说第d天的价格为Ai + Bi * d。购买从第0天开始，奇数天做活动可以买一送一。问买到所有商品最少需要花费多少？
输入
3
6 8
2 9
4 7
输出
13
第0天 买了 2
第1天买了 4+7的商品 11 送了 6+8的商品
首先可以考虑，当要购买的商品集合确定的时候，A[i]的大小是不影响结果的，结果只和Bi大小有关，越大的越要先买，所以先按Bi排序，接下来就是确定哪些商品是要购买的，可以算出来要购买的件数是m，dp[i][j]表示前i件物品选了j件的最小代价，每次有选和不选两种选项，最后dp[n][m]就是结果
