剣指OFFERのチェーンテーブルの最後からk番目のノード(九度OJ 1517)
11380 ワード
タイトルの説明:
チェーンテーブルを入力し、チェーンテーブルの最後からk番目のノードを出力します.(hint:チェーンテーブルは必ず使用してください.)
入力:
入力には複数のテストサンプルが含まれ、入力はEOFで終了します.各テストケースについて、入力される第1の動作の2つの整数nおよびk(0<=n<=1000、0<=k<=1000):nは、入力するチェーンテーブル要素の個数を表し、kは、クエリの最後から数番目の要素を表す.入力された2行目は、チェーンテーブルの要素を表すn個の数t(1<=t<=100000,000)を含む.
出力:
各テストケースに対応し、結果があれば、対応する検索結果を出力します.そうでなければNULLを出力します.
サンプル入力:
5 2
1 2 3 4 5
1 0
5サンプル出力:
4
NULL問題解決の考え方：
まず,一般的な考え方でチェーンテーブルの長さを取得し,次にlength−k番目の要素の値を出力することが,最後からk番目の要素の値であることを考慮した.しかし、面接のテクニックを考えると、この方法はだめですが、問題を作るときはACができます.コードは以下の通り、すべてのチェーンテーブルに関連するものを削除してもACが可能です.
#include <stdio.h>
#include <stdlib.h>
typedef struct node{
int number;
struct node * next;
}Node;
int main(){
int n,k,i,temp;
int flag = 0;
Node *link = (Node *)malloc(sizeof(Node));
link->next = NULL;
while(scanf("%d %d",&n,&k)!=EOF && n>=0 && n<=1000 && k>=0 && k<=1000 ){
flag = 0;
for(i=0;i<n;i++){
scanf("%d",&temp);
if(i == n-k){
flag = 1;
printf("%d
",temp);
}
Node *n = (Node *)malloc(sizeof(Node));
n->next = link->next;
link->next = n;
n->number = temp;
}
if(!flag)
printf("NULL
");
}
return 0;
}
/**************************************************************
Problem: 1517
User: xhalo
Language: C
Result: Accepted
Time:100 ms
Memory:2496 kb
****************************************************************/しかし,考慮した複雑点は,時間複雑度がO(n)であれば,1回のスキャンでは長さを取得したり出力したりすることは不可能である.
そこでチェーンテーブルのループを判断する考え方を採用し,2つのポインタを採用し,1つ目のポインタはk−1ステップ前に下へ,2つ目のポインタはさらに1つ目のポインタに従ってまっすぐ行く.最初のポインタが末尾を指し、2番目のポインタの要素の値が、私たちが要求した値であることを知っています.
p1 = link->next;
for(i=1;i<k;i++){
p1 = p1->next;
}
p2 = link->next;
while(p1->next!=NULL){
p1 = p1->next;
p2 = p2->next;
}
return p2->number;しかし、特別な状況を考慮すると、
1入力したkが0であれば,すなわち不正な値である.解決策
2チェーンテーブルが空の場合、検索する値が見つかりません.解決策
if(link->next == NULL || k == 0)
return -1;3 p 1がチェーンテーブルの末尾に達し、p 2がまだ始まっていない場合、つまりチェーンテーブルの長さがk個足りない場合、どうすればいいのでしょうか.解決策
p1 = link->next;
for(i=1;i<k;i++){
if(p1->next == NULL)
return -1;
p1 = p1->next;
}すべてのコード:
#include <stdio.h>
#include <stdlib.h>
typedef struct node{
int number;
struct node * next;
}Node;
int getK(Node *link,int k);
int main(){
int n,k,i,temp;
int flag;
while(scanf("%d %d",&n,&k)!=EOF && n>=0 && n<=1000 && k>=0 && k<=1000 ){
Node *link = (Node *)malloc(sizeof(Node));
link->next = NULL;
flag = 0;
Node *tail;
tail = link;
for(i=0;i<n;i++){
scanf("%d",&temp);
Node *n = (Node *)malloc(sizeof(Node));
n->next = tail->next;
tail->next = n;
tail = tail->next;
n->number = temp;
}
int numberK = getK(link,k);
numberK ==-1?printf("NULL
"):printf("%d
",numberK);
}
return 0;
}
int getK(Node *link,int k){
Node *p1,*p2;
int i;
if(link->next == NULL || k == 0)
return -1;
p1 = link->next;
for(i=1;i<k;i++){
if(p1->next == NULL)
return -1;
p1 = p1->next;
}
p2 = link->next;
while(p1->next!=NULL){
p1 = p1->next;
p2 = p2->next;
}
return p2->number;
}
/**************************************************************
Problem: 1517
User: xhalo
Language: C
Result: Accepted
Time:100 ms
Memory:2496 kb
****************************************************************/