算法题1

最近心情很不好，写了几道算法题缓和一下。。。

1.有 n 个同学围成一圈，其 id 依次为 1，2，3...n(n 号挨着 1 号)。现在从 1 号开始报数，第一回合报到 m 的人就出局，第二回合从出局的下一个开始报数，报到 m^2 的同学出局。以此类推直到最后一个回合报到 m^(n-1)的人出局，直到剩下最后一个同学。输出这个同学的编号。n<=15,m<=5

输入:

每一行第一个数字代表n，第二个数字代表m

输出：输出最后剩下同学的编号

示例输入：

5 2

示例输出：

 1 import java.util.ArrayList;
 2 import java.util.Scanner;
 3 
 4 public class Q1 {
 5 
 6     public static void main(String[] args) {
 7         // TODO Auto-generated method stub
 8         Scanner sc = new Scanner(System.in);
 9         while(sc.hasNext()) {
10             String str = sc.nextLine();
11             String[] strArr=str.split(" ");
12             int n=Integer.parseInt(strArr[0]);
13             int m=Integer.parseInt(strArr[1]);
14             ArrayList<Integer> nlist=new ArrayList<Integer>();
15             for(int i=0;i<n;i++) {
16                 nlist.add(i+1);
17             }
18             ArrayList<Integer> res=solution(nlist,m,1);
19             System.out.println(res.get(0));
20         }
21     }
22     
23     //µÝ¹é
24     public static ArrayList<Integer> solution(ArrayList<Integer> nlist,int m,int t) {
25         int size=nlist.size();
26         while (size>1) {
27             t=(m+t)%size-1;
28             nlist.remove(t);
29             m=m*m;
30             return solution(nlist, m, t);
31         }
32         return nlist;
33     }
34 
35 }

2. 弹幕是现今网络视频常见的评论方式，能够反映一个视频的火爆程度。假设某个时间一共有 N 条弹幕，每条弹幕 i 的持续时间为两个整数表示的时间区间(a[i],b[i])，我们定义弹幕数量最多的一个时间段为最精彩时段，求一个视频的最精彩时段。

输入：

第一行整数 N,代表弹幕的条数，其中 90%的 N < 1000000, 60%的 N < 10000 第二行到第 N+1 行，是两个整数(a[i],b[i]),代表每条弹幕的开始时间和结束时间, 请注意(a[i],b[i])是全开区间, 并且 a[i], b[i] < 100

输出：

M 行，每行两个整数(c,d)，M 是答案个数，(c,d)代表视频最精彩时段的开始时间和结束时间，并且 M 个答案区间互不重叠。答案请按照开始时间从小到大输出。请注意每行结尾应包含换行符，包括最后一行。

示例输入1：

0 4

1 4

2 3

示例输出1：

2 3

示例输入2：

1 2

3 4

2 3

4 5

示例输出2：

1 2

2 3

3 4

4 5

示例输入3：

0 2

2 4

1 3

示例输出3：

1 2

2 3

  1 import java.util.*;
  2 
  3 import static java.lang.Math.max;
  4 import static java.lang.Math.min;
  5 
  6 class Danmaku{
  7     int c;
  8     int d;
  9 }
 10 
 11 public class Q2 {
 12     public static void main(String[] args) {
 13         // TODO Auto-generated method stub
 14         Scanner sc = new Scanner(System.in);
 15         while(sc.hasNext()) {
 16             int N=sc.nextInt();
 17             sc.nextLine();
 18             ArrayList<Danmaku> list = new ArrayList<>();
 19             for(int i=0;i<N;i++) {
 20                 Danmaku danmaku=new Danmaku();
 21                 String str = sc.nextLine();
 22                 String[] strArr=str.split(" ");
 23                 danmaku.c=Integer.parseInt(strArr[0]);
 24                 danmaku.d=Integer.parseInt(strArr[1]);
 25                 list.add(danmaku);
 26             }
 27 //            for(int i=0;i<list.size();i++){
 28 //                System.out.println(list.get(i).c+" "+list.get(i).d);
 29 //            }
 30             solution(list);
 31         }
 32     }
 33 
 34     public static void solution(ArrayList<Danmaku> list) {
 35         //ArrayList<Res> reses = new ArrayList<>();
 36         HashMap<String,Integer> reses = new HashMap<>();
 37         for(int i=0;i<list.size();i++){
 38             String danmaku = list.get(i).c+" "+list.get(i).d;
 39             reses.put(danmaku,1);
 40         }
 41         for(int i=0;i<list.size()-1;i++){
 42             //判断两个区间是否有交集，若有交集，则记录交集，若无交集，则记录i本身
 43             for (int j=i+1;j<list.size();j++){
 44                 reses=intersaction(list.get(i),list.get(j),reses);
 45                 //System.out.println(i+" "+j);
 46             }
 47         }
 48 
 49         //处理结果
 50         ArrayList<String> alres = new ArrayList<>();
 51         int max=0;
 52         Iterator iter = reses.entrySet().iterator();
 53         while(iter.hasNext()){
 54             Map.Entry entry = (Map.Entry) iter.next();
 55             String key = (String)entry.getKey();
 56             int val = (Integer)entry.getValue();
 57             if(val>max){
 58                 alres.clear();
 59                 alres.add(key);
 60                 max=val;
 61             }else if(val==max){
 62                 alres.add(key);
 63             }
 64         }
 65 
 66         //System.out.println(alres);
 67         for(int i=0;i<alres.size()-1;i++){
 68             for(int j=i+1;j<alres.size();j++){
 69                 String tmp="";
 70                 String string1=alres.get(i);
 71                 String string2=alres.get(j);
 72                 String[] strings1=string1.split(" ");
 73                 String[] strings2=string2.split(" ");
 74                 int s1=Integer.parseInt(strings1[0]);
 75                 int s2=Integer.parseInt(strings2[0]);
 76                 if(s1>s2){
 77                     tmp=alres.get(i);
 78                     alres.set(i,alres.get(j));
 79                     alres.set(j,tmp);
 80                 }
 81             }
 82         }
 83 
 84         for(int i=0;i<alres.size();i++){
 85             System.out.println(alres.get(i));
 86         }
 87 
 88 //        int[] arr=new int[reses.size()];
 89 //        int count=0;
 90 //        Iterator iter1 = reses.entrySet().iterator();
 91 //        while(iter.hasNext()){
 92 //            Map.Entry entry = (Map.Entry) iter.next();
 93 //            String key = (String)entry.getKey();
 94 //            int val = (Integer)entry.getValue();
 95 //            arr[count]=val;
 96 //            count++;
 97 //            System.out.println(key+" "+val);
 98 //        }
 99 //        int max = max(arr);
100     }
101 
102     //取交集
103     public static HashMap<String,Integer> intersaction(Danmaku d1,Danmaku d2,HashMap<String,Integer> reses){
104         String danmaku="";
105         int c=max(d1.c,d2.c);
106         int d=min(d1.d,d2.d);
107         if(c<d){
108             danmaku=c+" "+d;
109             if(reses.containsKey(danmaku)){
110                 int count=reses.get(danmaku)+1;
111                 reses.put(danmaku,count);
112             }else {
113                 reses.put(danmaku,2);
114             }
115         }
116         return reses;
117     }
118 }

3. 根据输入生成一棵树，并打印该树。输入为 N 行数字对序列（例如：N = 2，数字对序列为（1，2），（ 2，3）），其中数字代表该树的节点，左边数字代表的节点是右边数字代表的节点的父节点，请根据输入的数字对序列生成一棵树，并按照广度优先的顺序打印该树。注意，存在输入无法生成树的情况，比如（1，2）（ 1，3）（ 2，4）（ 3，4），根据该序列生成的 Graph 中，2 节点和 3 节点同时为 4 节点的父节点，所以根据定义该 Graph 不是树。如遇无法生成树的情况，请输出字符串：“Not a tree” （引号不包括，大小写敏感）。广度优先遍历树并打印输出时，同一层级的节点根据输入时节点出现顺序打印输出。

输入：

输入第一行 N 表示数字对序列行树。之后的 2～N+1 行表示数字序列对，1<= N <= 10000。其中，每一行有两个不相同的数字，用英文逗号分隔，例如：1,2。所有数字都是正整数，并且小于 2 的 31 次方。没有默认的输入顺序，第一行可能不是根节点。最后一行可能不是叶子节点。可能有完全重复的行。

输出：

输出为一行，如果可以生成树，请根据广度优先顺序，输出每个节点对应的数字，并且用英文逗号隔开，同一层级的节点根据输入顺序输出。如果无法生成树，请输出字符串：”Not a tree” （引号不包括，大小写敏感）。生成树中同一层级的节点，按照节点数字在输入时出现的顺序输出。

示例输入1：

1,2

1,3

2,4

2,5

3,6

示例输出1：

1,2,3,4,5,6

示例输入2：

1,2

1,3

2,4

3,4

示例输出2：

Not a tree

示例输入3：

3,6

2,4

1,3

2,5

1,2

示例输出3：

1,3,2,6,4,5

 1 import java.util.*;
 2 
 3 class Branch{
 4     int left;
 5     int right;
 6     boolean isVisited=false;
 7 
 8     @Override
 9     public String toString() {
10         return "("+left+","+right+","+isVisited+")";
11     }
12 }
13 
14 public class Q3 {
15     public static void main(String[] args){
16         Scanner sc=new Scanner(System.in);
17         while(sc.hasNext()){
18             int N=sc.nextInt();
19             sc.nextLine();
20             ArrayList<Branch> branches=new ArrayList<>();
21             for(int i=0;i<N;i++){
22                 String str=sc.nextLine();
23                 String []strs=str.split(",");
24                 Branch branch=new Branch();
25                 branch.left=Integer.parseInt(strs[0]);
26                 branch.right=Integer.parseInt(strs[1]);
27                 branches.add(branch);
28             }
29             //System.out.println(branches);
30             solution(branches);
31         }
32     }
33     public static void solution(ArrayList<Branch> branches){
34         //广度优先遍历
35         Queue<Integer> vQueue=new LinkedList<>();
36         //找到头节点
37         int head=0;
38 
39         ArrayList<Integer> lefts=new ArrayList<>();
40         ArrayList<Integer> rights=new ArrayList<>();
41         Set<Integer> all=new TreeSet<>();
42         for(Branch branch:branches){
43             lefts.add(branch.left);
44             rights.add(branch.right);
45             all.add(branch.left);
46             all.add(branch.right);
47         }
48 
49         Set<Integer> set=new TreeSet<>();
50         for(int i=0;i<lefts.size();i++){
51             if(!rights.contains(lefts.get(i))){
52                 set.add(lefts.get(i));
53             }
54         }
55         if(set.size()>1){
56             System.out.println("Not a tree");
57         }else{
58             head=set.iterator().next();
59             vQueue.add(head);
60 //            int count=0;
61             ArrayList<Integer> res=BFS(vQueue,branches);
62 //            System.out.println(res.size());
63 //            System.out.println(res);
64             //System.out.println(branches);
65 
66             if(res.size()!=all.size()){
67                 System.out.println("Not a tree");
68             }else {
69                 String resS="";
70                 for(int i=0;i<res.size();i++){
71                     if(i==res.size()-1){
72                         resS+=res.get(i).toString();
73                     }else {
74                         resS+=res.get(i).toString()+",";
75                     }
76                 }
77                 System.out.println(resS);
78             }
79         }
80     }
81 
82     public static ArrayList<Integer> BFS(Queue<Integer> vQueue,ArrayList<Branch> branches){
83         ArrayList<Integer> res = new ArrayList<>();
84         while(!vQueue.isEmpty()){
85             int head = vQueue.remove();
86             res.add(head);
87             for(Branch branch:branches){
88                 //遍历边集合
89                 if(branch.isVisited==false&&branch.left==head){
90                     vQueue.add(branch.right);
91                     branch.isVisited=true;
92                     //System.out.println("plus:"+branch.right);
93                 }
94             }
95         }
96         return res;
97     }
98 }