我的PAT系列文章更新重心已移至Github痘系，歡迎來(lái)看PAT題解的小伙伴請(qǐng)到Github Pages瀏覽最新內(nèi)容(本篇文章鏈接)飒箭。此處文章目前已更新至與Github Pages同步。歡迎star我的repo锡溯。
題目
To store English words, one method is to use linked lists and store a word
letter by letter. To save some space, we may let the words share the same
sublist if they share the same suffix. For example, loading and being are
stored as showed in Figure 1.
Figure 1
You are supposed to find the starting position of the common suffix (e.g. the
position of i in Figure 1).
Input Specification:
Each input file contains one test case. For each case, the first line contains
two addresses of nodes and a positive (
), where the two
addresses are the addresses of the first nodes of the two words, and is
the total number of nodes. The address of a node is a 5-digit positive
integer, and NULL is represented by .
Then lines follow, each describes a node in the format:
Address Data Next
whereAddress is the position of the node, Data is the letter contained by
this node which is an English letter chosen from { a-z, A-Z }, and Next is
the position of the next node.
Output Specification:
For each case, simply output the 5-digit starting position of the common
suffix. If the two words have no common suffix, output -1 instead.
Sample Input 1:
11111 22222 9
67890 i 00002
00010 a 12345
00003 g -1
12345 D 67890
00002 n 00003
22222 B 23456
11111 L 00001
23456 e 67890
00001 o 00010
Sample Output 1:
67890
Sample Input 2:
00001 00002 4
00001 a 10001
10001 s -1
00002 a 10002
10002 t -1
Sample Output 2:
-1
思路
一個(gè)鏈表相關(guān)的題目。
依然暴力地（再次說(shuō)明杰刽，很不實(shí)用。不過(guò)最壞情況就需要這么多艺蝴，所以對(duì)于OJ來(lái)說(shuō)，不算浪費(fèi)）申請(qǐng)一個(gè)100000長(zhǎng)度的數(shù)組鸟废，直接用數(shù)組索引作為鏈表地址猜敢。
思路很簡(jiǎn)單：
記錄鏈表：
結(jié)構(gòu)數(shù)組[Address] => 結(jié)構(gòu)數(shù)組[Next]
遍歷第一個(gè)單詞：
標(biāo)記所有遍歷的結(jié)點(diǎn)
遍歷第二個(gè)單詞：
輸出第一個(gè)被標(biāo)記的結(jié)點(diǎn)
我定義的結(jié)構(gòu)只有下一個(gè)結(jié)點(diǎn)的地址和一個(gè)標(biāo)記，沒有記錄字符盒延，因?yàn)槟銜?huì)發(fā)現(xiàn)它沒用缩擂。。兰英。
盲點(diǎn)：?jiǎn)卧~開頭地址可能為NULL撇叁。盲生，你是否發(fā)現(xiàn)這個(gè)了華點(diǎn)畦贸？
代碼
最新代碼@github陨闹，歡迎交流
#include <stdio.h>
typedef struct Node Node;
struct Node {
int checked;
struct Node *next;
};
int main()
{
char data;
int start1, start2, address, next, N;
Node list[100000] = {0}, *p;
scanf("%d %d %d", &start1, &start2, &N);
/* record a linked list */
for(int i = 0; i < N; i++)
{
scanf("%d %c %d", &address, &data, &next);
list[address].next = next == -1 ? NULL : &list[next];
}
if(start1 == -1 || start2 == -1)
{
printf("-1");
return 0;
}
/* First traverse the first string */
for(p = list + start1; p; p = p->next)
p->checked = 1;
/* Then traverse the second looking for checked node */
for(p = list + start2; p && !p->checked; p = p->next)
;
if(p)
printf("%05ld", p - list);
else
printf("-1");
return 0;
}
