2022-04-12 华百笔试记录

百度的
华子的笔试记录
华子第二道
可以把提供的前置后置，转成课程表的二维数组，
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是节点，存储它的前置节点

3. 借助一个队列 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]就是结果