剣指offer題3:2 D配列の
3091 ワード
タイトルの説明:二次元配列では、各行は左から右に増加し、各列は上から下に増加した順にソートされます.関数を完了し、このような2次元配列と整数を入力して、配列にその整数が含まれているかどうかを判断してください.
入力:入力は、各テストケースについて、複数のテストケースを含むことができる.
入力される第1の動作の2つの整数mおよびn(1<=m,n<=1000):入力するマトリクスの行数および列数を表す.
入力された2行目には、検索する数値を表す整数t(1<=t<=1000000)が含まれます.
次のm行は、各行にn個の数があり、問題が与えるm行n列を表す行列(行列は、問題記述に示すように、各行が左から右に増加する順序で並べ替えられ、各列が上から下に増加する順序で並べ替えられる.
出力:は各テストケースに対応し、
出力「Yes」は、2次元配列で数値tが見つかったことを表します.
出力「No」は、2次元配列に数字tが見つからないことを表す.
分析:
右上から比較し、ちょうど等しい場合はtrueに戻ります.
検索する数が右上隅より大きい場合は、その行が比較されていないことを示します.行数に1を加えて次の行の右上隅を比較します.
検索する数が右上隅より小さい場合は、所在する列を呼ばなくてもいいことを示します.列数を1減らして、前の伊一列の右上隅に比較します.
最初は9度OJでやったので、そのまま彼のフォーマットで来ました.
方法1つは、動的に2次元配列を割り当てる方法であり、直接的であるが割り当てられた配列は同じ行のみがメモリに連続しているが、同業者がメモリに連続していないことを保証することはできない.例えば、2行目のアドレスが必ずしも1行目の後ろにあるとは限らない.
方法2は,1次元配列を用いて2次元配列を格納し,関数パラメータにおいてもエラーが発生しにくい折衷方式を用いた.
もちろん配列を使うことも多いですが、初期値としてdefineのMAXを使うだけですが、なんだか堅苦しいです
方法1: #include
#include
#define MAX 10
bool ifIncluded(int **data,int m,int n,int num) //
{
int i=0,j=n-1,temp;
while(i=0)
{
temp= *(*(data+i)+j); //
if(num ==temp )
return true;
if(num > temp)
i++;
else j--;
}
return false;
}
int main(void)
{
int m,n,num;
int **data;
int i,j,count=-1;
bool result[MAX]={false};
while(scanf("%d%d%d",&m,&n,&num)!=EOF)
{
count++;
data=(int**)malloc(sizeof(int*)*m);
for(i=0;i
方法2: #include
#include
#define MAX
#define false 0 // OJ false,true undeclared
#define true 1
int ifIncluded(int *data,int m,int n,int num) //
{
int i=0,j=n-1,temp;
if(!data || m <=0 || n<=0) return false;
if(data[0]>num || data[m*n-1]=0)
{
temp=*(data+i*n+j); //
if(temp==num) return true;
if(temp>num) j--;
else i++;
}
return false;
}
int main(void)
{
int m,n,num;
int *data;
int i,j,count=-1;
int result[MAX]={false};
int len=0;
while(scanf("%d%d%d",&m,&n,&num)!=EOF)
{
printf("input matrix
");
count++;
len=m*n;
data=(int*)malloc(sizeof(int)*m*n);
for(i=0;i
テスト例：
1 positive:探した要素はマトリクスの中で、最小の要素に等しく、最大の要素に等しく、最大と最小の中間にある.
2 negative:探した要素はマトリクスになく、最小要素より小さく、最大要素より大きく、最大と最小の中間にあるが存在しない.
4 invalid:入力した配列は空です.
知識点:
1二次元配列の割り当て方法(静的,動的)の使用と,二次元配列パラメータへの伝達方法.詳細については、http://www.cnblogs.com/wuyuegb2312/archive/2013/06/14/3135277.html
2私自身はいつもscanfの时に忘れました&!!!像&data[i][j]
入力される第1の動作の2つの整数mおよびn(1<=m,n<=1000):入力するマトリクスの行数および列数を表す.
入力された2行目には、検索する数値を表す整数t(1<=t<=1000000)が含まれます.
次のm行は、各行にn個の数があり、問題が与えるm行n列を表す行列(行列は、問題記述に示すように、各行が左から右に増加する順序で並べ替えられ、各列が上から下に増加する順序で並べ替えられる.
出力:は各テストケースに対応し、
出力「Yes」は、2次元配列で数値tが見つかったことを表します.
出力「No」は、2次元配列に数字tが見つからないことを表す.
分析:
右上から比較し、ちょうど等しい場合はtrueに戻ります.
検索する数が右上隅より大きい場合は、その行が比較されていないことを示します.行数に1を加えて次の行の右上隅を比較します.
検索する数が右上隅より小さい場合は、所在する列を呼ばなくてもいいことを示します.列数を1減らして、前の伊一列の右上隅に比較します.
最初は9度OJでやったので、そのまま彼のフォーマットで来ました.
方法1つは、動的に2次元配列を割り当てる方法であり、直接的であるが割り当てられた配列は同じ行のみがメモリに連続しているが、同業者がメモリに連続していないことを保証することはできない.例えば、2行目のアドレスが必ずしも1行目の後ろにあるとは限らない.
方法2は,1次元配列を用いて2次元配列を格納し,関数パラメータにおいてもエラーが発生しにくい折衷方式を用いた.
もちろん配列を使うことも多いですが、初期値としてdefineのMAXを使うだけですが、なんだか堅苦しいです
方法1: #include
#include
#define MAX 10
bool ifIncluded(int **data,int m,int n,int num) //
{
int i=0,j=n-1,temp;
while(i=0)
{
temp= *(*(data+i)+j); //
if(num ==temp )
return true;
if(num > temp)
i++;
else j--;
}
return false;
}
int main(void)
{
int m,n,num;
int **data;
int i,j,count=-1;
bool result[MAX]={false};
while(scanf("%d%d%d",&m,&n,&num)!=EOF)
{
count++;
data=(int**)malloc(sizeof(int*)*m);
for(i=0;i
方法2: #include
#include
#define MAX
#define false 0 // OJ false,true undeclared
#define true 1
int ifIncluded(int *data,int m,int n,int num) //
{
int i=0,j=n-1,temp;
if(!data || m <=0 || n<=0) return false;
if(data[0]>num || data[m*n-1]=0)
{
temp=*(data+i*n+j); //
if(temp==num) return true;
if(temp>num) j--;
else i++;
}
return false;
}
int main(void)
{
int m,n,num;
int *data;
int i,j,count=-1;
int result[MAX]={false};
int len=0;
while(scanf("%d%d%d",&m,&n,&num)!=EOF)
{
printf("input matrix
");
count++;
len=m*n;
data=(int*)malloc(sizeof(int)*m*n);
for(i=0;i
テスト例：
1 positive:探した要素はマトリクスの中で、最小の要素に等しく、最大の要素に等しく、最大と最小の中間にある.
2 negative:探した要素はマトリクスになく、最小要素より小さく、最大要素より大きく、最大と最小の中間にあるが存在しない.
4 invalid:入力した配列は空です.
知識点:
1二次元配列の割り当て方法(静的,動的)の使用と,二次元配列パラメータへの伝達方法.詳細については、http://www.cnblogs.com/wuyuegb2312/archive/2013/06/14/3135277.html
2私自身はいつもscanfの时に忘れました&!!!像&data[i][j]
右上から比較し、ちょうど等しい場合はtrueに戻ります.
検索する数が右上隅より大きい場合は、その行が比較されていないことを示します.行数に1を加えて次の行の右上隅を比較します.
検索する数が右上隅より小さい場合は、所在する列を呼ばなくてもいいことを示します.列数を1減らして、前の伊一列の右上隅に比較します.
最初は9度OJでやったので、そのまま彼のフォーマットで来ました.
方法1つは、動的に2次元配列を割り当てる方法であり、直接的であるが割り当てられた配列は同じ行のみがメモリに連続しているが、同業者がメモリに連続していないことを保証することはできない.例えば、2行目のアドレスが必ずしも1行目の後ろにあるとは限らない.
方法2は,1次元配列を用いて2次元配列を格納し,関数パラメータにおいてもエラーが発生しにくい折衷方式を用いた.
もちろん配列を使うことも多いですが、初期値としてdefineのMAXを使うだけですが、なんだか堅苦しいです
方法1: #include
#include
#define MAX 10
bool ifIncluded(int **data,int m,int n,int num) //
{
int i=0,j=n-1,temp;
while(i=0)
{
temp= *(*(data+i)+j); //
if(num ==temp )
return true;
if(num > temp)
i++;
else j--;
}
return false;
}
int main(void)
{
int m,n,num;
int **data;
int i,j,count=-1;
bool result[MAX]={false};
while(scanf("%d%d%d",&m,&n,&num)!=EOF)
{
count++;
data=(int**)malloc(sizeof(int*)*m);
for(i=0;i
方法2: #include
#include
#define MAX
#define false 0 // OJ false,true undeclared
#define true 1
int ifIncluded(int *data,int m,int n,int num) //
{
int i=0,j=n-1,temp;
if(!data || m <=0 || n<=0) return false;
if(data[0]>num || data[m*n-1]=0)
{
temp=*(data+i*n+j); //
if(temp==num) return true;
if(temp>num) j--;
else i++;
}
return false;
}
int main(void)
{
int m,n,num;
int *data;
int i,j,count=-1;
int result[MAX]={false};
int len=0;
while(scanf("%d%d%d",&m,&n,&num)!=EOF)
{
printf("input matrix
");
count++;
len=m*n;
data=(int*)malloc(sizeof(int)*m*n);
for(i=0;i
テスト例：
1 positive:探した要素はマトリクスの中で、最小の要素に等しく、最大の要素に等しく、最大と最小の中間にある.
2 negative:探した要素はマトリクスになく、最小要素より小さく、最大要素より大きく、最大と最小の中間にあるが存在しない.
4 invalid:入力した配列は空です.
知識点:
1二次元配列の割り当て方法(静的,動的)の使用と,二次元配列パラメータへの伝達方法.詳細については、http://www.cnblogs.com/wuyuegb2312/archive/2013/06/14/3135277.html
2私自身はいつもscanfの时に忘れました&!!!像&data[i][j]
#include
#include
#define MAX 10
bool ifIncluded(int **data,int m,int n,int num) //
{
int i=0,j=n-1,temp;
while(i=0)
{
temp= *(*(data+i)+j); //
if(num ==temp )
return true;
if(num > temp)
i++;
else j--;
}
return false;
}
int main(void)
{
int m,n,num;
int **data;
int i,j,count=-1;
bool result[MAX]={false};
while(scanf("%d%d%d",&m,&n,&num)!=EOF)
{
count++;
data=(int**)malloc(sizeof(int*)*m);
for(i=0;i #include
#include
#define MAX
#define false 0 // OJ false,true undeclared
#define true 1
int ifIncluded(int *data,int m,int n,int num) //
{
int i=0,j=n-1,temp;
if(!data || m <=0 || n<=0) return false;
if(data[0]>num || data[m*n-1]=0)
{
temp=*(data+i*n+j); //
if(temp==num) return true;
if(temp>num) j--;
else i++;
}
return false;
}
int main(void)
{
int m,n,num;
int *data;
int i,j,count=-1;
int result[MAX]={false};
int len=0;
while(scanf("%d%d%d",&m,&n,&num)!=EOF)
{
printf("input matrix
");
count++;
len=m*n;
data=(int*)malloc(sizeof(int)*m*n);
for(i=0;i テスト例：
1 positive:探した要素はマトリクスの中で、最小の要素に等しく、最大の要素に等しく、最大と最小の中間にある.
2 negative:探した要素はマトリクスになく、最小要素より小さく、最大要素より大きく、最大と最小の中間にあるが存在しない.
4 invalid:入力した配列は空です.
知識点:
1二次元配列の割り当て方法(静的,動的)の使用と,二次元配列パラメータへの伝達方法.詳細については、http://www.cnblogs.com/wuyuegb2312/archive/2013/06/14/3135277.html
2私自身はいつもscanfの时に忘れました&!!!像&data[i][j]
1二次元配列の割り当て方法(静的,動的)の使用と,二次元配列パラメータへの伝達方法.詳細については、http://www.cnblogs.com/wuyuegb2312/archive/2013/06/14/3135277.html
2私自身はいつもscanfの时に忘れました&!!!像&data[i][j]