狗家阳谷昂赛特

我奋斗我无悔 发表于 2019-8-20 02:29
请问，第一题，对方经过的已经占领的点，我还可以经过吗 或者我只能经过那些未被占领的点？

对的，已经占领的点不能经过。

dengzeyu147 发表于 2019-8-19 14:14
请问第二题是那个投票面经题？如果不是，能请楼主解释一下？已加米

不知道面经投票题长啥样。。
比如有N=4个Candidates，分别为0，1，2，3
input array如下，每一行从左往右分别为每一份投票in order of perference of candidates.
0 1 2 3 4
0 1 2 3 4
0 1 2 3 4
0 1 2 3 4
0 1 2 3 4
1 0 2 3 4
1 0 2 3 4
2 1 0 3 4
2 3 1 0 4
3 1 0 2 4
第一轮计算去掉第一列投票数最少的candidate 3.
0 1 2 3 4
0 1 2 3 4
0 1 2 3 4
0 1 2 3 4
0 1 2 3 4
1 0 2 3 4
1 0 2 3 4
1 0 2 3 4
2 1 0 3 4
2 3 1 0 4
3 1 0 2 4
第二轮计算去掉第一列投票数最少的candidate 2.
以此类推求出最后谁是winner。可以上网上查一下澳洲选举制度的规则。

两个人玩占领二叉树的游戏，二叉树的node可以往parent，left child，right child走，问如果你是后者开始占领的人，选哪个点获胜的可能性最大。
Follow up：如果你是先走的人，应该选哪一个点开始。  可以说详细一点吗？ 看谁占领的点最多 就赢吗？ 是不停的往二叉树棋盘上放棋子吗？ 谢谢 已加大米。

请问第一题楼主的思路是什么？

第一个问题是 Leetcode 1145 新题
https://leetcode.com/problems/binary-tree-coloring-game/

jobsjobs 发表于 2019-8-20 14:03
第一个问题是 Leetcode 1145 新题
https://leetcode.com/problems/binary-tree-coloring-game/

666666666Leetcode的新题很多都是狗家的

谢谢LZ分享

tianjiayou 发表于 2019-8-20 11:15
我其实没get到。。因为每个课程的indegree和outdegree不一定是1，这样的话，怎么算呢？

是我考虑不周，那这个方法好像有问题

tianjiayou 发表于 2019-8-20 11:15
我其实没get到。。因为每个课程的indegree和outdegree不一定是1，这样的话，怎么算呢？

感觉还是可以做，和indegree，outdegree并没有太大关系

1. class Solution {
   
2.     public int minSemester(int numCourses, int[][] prerequisites,int k) {
   
3.         int completedCourses = 0;
   
4.         List<Integer>[] nextCourses = new List[numCourses];
   
5.         int[] height = new int[numCourses];
   
6.         for(int i =0; i<numCourses; i++){
   
7.             nextCourses[i] = new ArrayList<>();
   
8.         }
   
9.         int[] incomingEdgesCount = new int[numCourses];
   
10.         for(int[] i:prerequisites){
    
11.             incomingEdgesCount[i[0]]++;
    
12.             nextCourses[i[1]].add(i[0]);               
    
13.         }
    
14.         // for(int i : incomingEdgesCount){
    
15.         //     System.out.print(i+" ");
    
16.         // }
    
17.         for(int i = 0; i < height.length; i++){
    
18.             if(height[i] == 0)
    
19.                height[i] = getHeight(height,nextCourses,i);
    
20.         }
    
21.         
    
22.         PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>(){
    
23.             public int compare(int[] a, int [] b){
    
24.                 return b[1] - a[1];
    
25.             }
    
26.         });
    
27.         // Add all nodes that have indegree zero to the BFS queue
    
28.         for(int i = 0; i<incomingEdgesCount.length; i++){
    
29.             if(incomingEdgesCount[i] == 0){
    
30.                 pq.offer(new int[]{i,height[i]});
    
31.             }
    
32.         }
    
33.         // Bfs starting with indegree 0  
    
34.         int semester = 0;
    
35.         while(!pq.isEmpty()){
    
36.             semester++;
    
37.             int num = pq.size();
    
38.             for(int g = 0; g < k && !pq.isEmpty() && g < num; g++){
    
39.             int[] course = pq.poll();
    
40.             completedCourses++;
    
41.             for(int i : nextCourses[course[0]]){
    
42.                 incomingEdgesCount[i]--;
    
43.                 if(incomingEdgesCount[i] == 0){
    
44.                     pq.offer(new int[]{i,height[i]});
    
45.                 }
    
46.             }
    
47.             }
    
48.         }
    
49.         //System.out.println(completedCourses);
    
50.         return semester;   
    
51.     }
    
52.     private int getHeight(int[] height,List<Integer>[] nexts,int idx){
    
53.         List<Integer> next = nexts[idx];
    
54.         if(next.size() == 0){
    
55.             return 1;
    
56.         }
    
57.         if(height[idx] != 0){
    
58.             return height[idx];
    
59.         }
    
60.         int max = 0;
    
61.         for(int n : next){
    
62.             max = Math.max(max,getHeight(height,nexts,n));
    
63.         }
    
64.         return max + 1;
    
65.     }
    
66. }

复制代码

zzwzzw435 发表于 2019-8-21 02:41
感觉还是可以做，和indegree，outdegree并没有太大关系
[mw_shl_code=java,true]class Solution {
     ...

我觉得还是有问题，这种做法我想过;
看下我这个例子；这里2是7的parent（实在是不好画 lol）1是2,3,4,5的parent，3,4,5都是6的parent，6是7的parent， 现在k = 3；
实际上先选1，再选345，再选2,6，再选7只需要4次；
如果先选1，再选234，接下来只能先选完5.才能再选6，再选7。这样需要5次；
            1
         /  |  \ \
      2   3  4  5
            \   |  /
                6
                |
                7