首页 > 代码库 > PAT 1032 （未完成）
PAT 1032 （未完成）
斗智斗勇系列，这个时间限制太变态了，10^5的数据读进去100ms就完蛋，buffer又不能太多开，但是8M buffer开出来其实也没啥用，还是超时
除去超时数据点，还有一个数据点没有过，不知道是什么边界条件，不管了
判断两条链表是否相交，首先两条链表都走到最后一个节点，如果节点相同，则说明这两条链表是相交的。算出两条链表的长度，len1，len2，max(len1, len2) - min(len1, len2)，长的链表先走diff step，再和短的链表一起走，相遇的节点即为共同节点的起始节点。
另外学到了，PAT中的JAVA如果是返回非零，则说明存在着异常。前面有数据点返回非零是因为没有判断null。
1 import java.util.*; 2 import java.io.*; 3 4 class FastReader{ 5 BufferedReader reader; 6 StringTokenizer tokenizer; 7 8 public FastReader(InputStream stream){ 9 reader = new BufferedReader(new InputStreamReader(stream), 1 << 22); 10 tokenizer = null; 11 } 12 13 public String next(){ 14 while (tokenizer == null || !tokenizer.hasMoreTokens()){ 15 try { 16 tokenizer = new StringTokenizer(reader.readLine()); 17 } catch (Exception e){ 18 //System.out.println(-1); 19 throw new RuntimeException(e); 20 } 21 } 22 23 return tokenizer.nextToken(); 24 } 25 26 public int next_int(){ 27 return Integer.parseInt(next()); 28 } 29 } 30 31 class Node{ 32 int address; 33 int next_address; 34 Node next; 35 36 public Node(){ 37 next = null; 38 } 39 } 40 41 public class Main { 42 public static void main(String[] args){ 43 FastReader reader = new FastReader(System.in); 44 int first_start, second_start; 45 int N; 46 47 first_start = reader.next_int(); 48 second_start = reader.next_int(); 49 N = reader.next_int(); 50 51 Node[] nodes = new Node[N]; 52 53 for (int i = 0; i < N; i++){ 54 int cur_address = reader.next_int(); 55 reader.next(); 56 int next_address = reader.next_int(); 57 58 Node node = new Node(); 59 node.address = cur_address; 60 node.next_address = next_address; 61 nodes[i] = node; 62 } 63 64 Node first_word = null, second_word = null; 65 for (int i = 0; i < N; i++){ 66 Node cur_node = nodes[i]; 67 if (cur_node.address == first_start) 68 first_word = cur_node; 69 else if (cur_node.address == second_start) 70 second_word = cur_node; 71 for (int j = 0; j < N; j++){ 72 Node candidate_node = nodes[j]; 73 74 if (cur_node.next_address == candidate_node.address){ 75 cur_node.next = candidate_node; 76 break; 77 } 78 } 79 } 80 81 int len1 = 0, len2 = 0; 82 Node first_ptr = first_word, second_ptr = second_word; 83 84 if (first_ptr == null || second_ptr == null){ 85 System.out.println(-1); 86 return; 87 } 88 89 while (first_ptr.next != null){ 90 first_ptr = first_ptr.next; 91 len1++; 92 } 93 while (second_ptr.next != null){ 94 second_ptr = second_ptr.next; 95 len2++; 96 } 97 98 if (first_ptr != second_ptr){ 99 System.out.println(-1);100 return;101 }102 103 int diff_step = Math.max(len1, len2) - Math.min(len1, len2);104 if (len1 < len2){105 first_ptr = second_word;106 second_ptr = first_word;107 } else {108 first_ptr = first_word;109 second_ptr = second_word;110 }111 112 for (int i = 0; i < diff_step; i++)113 first_ptr = first_ptr.next;114 while (first_ptr != second_ptr){115 first_ptr = first_ptr.next;116 second_ptr = second_ptr.next;117 }118 119 System.out.println(first_ptr.address);120 }121 }
PAT 1032 （未完成）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。