「剣指Offer」面接問題-2 D配列での検索

6702 ワード

タイトル1384:2 D配列での検索
時間制限:1秒
メモリ制限:32メガ
特殊問題:いいえ
コミット:7318
解決:1418
タイトルの説明:
2 D配列では、各行が左から右に増加し、各列が上から下に増加した順にソートされます.関数を完了し、このような2次元配列と整数を入力して、配列にその整数が含まれているかどうかを判断してください.

入力:
入力には、各テストケースについて、複数のテストケースが含まれる場合があります.
入力される第1の動作の2つの整数mおよびn(1<=m,n<=1000):入力するマトリクスの行数および列数を表す.
入力された2行目には、検索する数値を表す整数t(1<=t<=1000000)が含まれます.
次のm行は、各行にn個の数があり、問題が与えるm行n列を表す行列(行列は、問題記述に示すように、各行が左から右に増加する順序で並べ替えられ、各列が上から下に増加する順序で並べ替えられる.

出力:
各テストケースに対応し、
出力「Yes」は、2次元配列で数値tが見つかったことを表します.
出力「No」は、2次元配列に数字tが見つからないことを表す.

サンプル入力:

サンプル出力:

Yes
No
No

コード(一):
問題:
1、所在地の行を見つけて、各行の最後の要素と比較する
2、列の要素の位置を見つける

#include
#include
int A[1010][1010];

void print(int flag){
if(flag == 2)
printf("Yes");
else printf("No");
}

int main(int argc, char const *argv[])
{
int m, n, mark, pos, i, j, x, y;
while(~scanf("%d %d", &m, &n)){
mark = 0;
scanf("%d", &pos);
for(i=1;i<=m;++i)
for(j=1;j<=n;++j)
scanf("%d", &A[i][j]);
for(x=1;x<=m;++x){
if(pos > A[x][n])
continue;
else break;
}
if(x>m) {print(mark); continue;}
for(y=1;y<=n;++y)
if(pos == A[x][y]){
mark = 2;
break;
}
print(mark);
}

return 0;
}

コード(二)、
問題:
1、二分で何行目を探すか
2、二分で何列目を探すか

#include
#include
int A[1010][1010];

void print(int flag){
if(flag == 2)
printf("Yes");
else printf("No");
}

int main(int argc, char const *argv[])
{
int m, n, mark, pos, i, j, x, y;
int mid, h, l;
while(~scanf("%d %d", &m, &n)){
mark = 0;
scanf("%d", &pos);
for(i=1;i<=m;++i)
for(j=1;j<=n;++j)
scanf("%d", &A[i][j]);

h = m;
l = 1;
while(l mid = (l+h)/2;
if(pos > A[mid][n])
l = mid+1;
else h = mid;
}
x = l;

if(x>m) {print(mark); continue;}

h = n+1;
l = 1;
while(l mid = (l+h)/2;
if(pos == A[x][mid]) {mark = 2; break;}
if(pos > A[x][mid])
l = mid+1;
else h = mid;
}

print(mark);
}

return 0;
}

コード(三)、
問題:
1、二次元配列を一次元配列に変換し、二分検索を行う
2、配列を開いてスペースが爆発しないように注意する

#include
int A[1000000];

int main(int argc, char const *argv[])
{
int i, pos, mul, m, n, flag;
int h, l, mid;
while(~scanf("%d %d %d", &m, &n, &pos)){
mul = m*n;
for(i=0;i scanf("%d", &A[i]);
h = mul;
flag = l = 0;
while(l mid = (h+l)/2;
if(A[mid] == pos){flag = 1; break;}
if(A[mid] > pos) h = mid;
else l = mid + 1;
}
if(flag == 1) printf("Yes");
else printf("No");
}
return 0;
}

コード(四)、
問題:
1、要素を入力して検索した要素かどうかを判断する

#include

int main()
{
int i, pos, mul, m, n, flag, dd;
while(~scanf("%d %d %d", &m, &n, &pos)){
flag = 0;
mul = m*n;
for(i=0;i scanf("%d", &dd);
if(dd == pos) flag = 1;
}
if(flag == 1) printf("Yes");
else printf("No");
}
return 0;
}

コード(五)、

問題:

1、文字列処理によって速度が大幅に向上するが、方法とコード(4)は同じである.

#include

char tmp[8000];
int main()
{
int i,j,n,m,t,f,s;
while(scanf("%d%d",&n,&m)!=EOF){
scanf("%d",&t);f=0;
for(i=0;i for(j=0;j scanf("%d",&s);
f|=s==t;
}
if(f){
while(i fgets(tmp,8000,stdin);i++;
}
break;
}
}
if(f)printf("Yes");
else printf("No");
}
return 0;
}

まとめ:
1、最初は入力されて騙されたが、結局このコードはAC==!
2、どうやら9度OJは自分の能力をあまり悲しませたくないので、水を入れてくれました.
3、以上のコードの考え方は実は間違っています...
4、もし問題が本当に簡単に見えるなら、面接官もこのような問題を出さないでしょう.TIMEを無駄にします.の

テストデータは次のようになります.

01,02,08,0902,04,09,1204,07,10,1306,08,11,15
この行列の最小値mは左上、最大値Mは右下である.
このような1つの行列から任意に1つのサブ行列を囲み,この法則にも合致する.
整数kは、mより小さいかMより大きい場合、必然的にこの行列内にない.

行列を上下に分割します.
01,02,08,0902,04,09,12 ------------04,07,10,1306,08,11,15

整数kが、上半分の右下隅の値(ここでは12)より大きい場合、kは必然的に上半分ではない.
整数kが、上半分の左上隅の値(ここでは04)より小さい場合、kは必ず下半分ではない.
マトリクスを左右に分割します.
01,02 | 08,0902,04 | 09,1204,07 | 10,1306,08 | 11,15

整数kが、左半分の右下隅の値(ここでは08)より大きい場合、kは必ず左半分ではない.
整数kが、右半分の左上隅の値(ここでは08)より小さい場合、kは必ず右半分ではない.

考え方:

01:一番上のエッジで、二分法でkを検索し、見つけたら終了します.そうでなければ、kより大きい最小整数を見つけ、その位置と右側の列をすべて「切り取る」.
02:一番右のエッジで、二分法でkを検索し、見つけたら終了します.そうでなければ、kより小さい最大整数を見つけ、その位置と上の行をすべて「切り落とす」.
03:以上の各ステップで、「カット」前のマトリクスサイズが0の場合、終了に失敗します.以上の2つのステップが終了した後、まだ見つからない場合は01に戻り、カットを続けます.

もっと詳しい解法は、『剣指Offer』という本ですが、読む前に、少なくとも自分が一番挫折したバージョンが必要です!

コード、自己感覚は再帰したほうが書きやすいです.

自分のまとめ:

01:後でやはり考えを整理して、まず考えがあって、それからコードを書きます.

02:远虑することができなくて、面接の时よく出すのは最も简単な问题で、试験するのは细部で、アルゴリズムがどれだけ强いかではありません.

転載先:https://www.cnblogs.com/firstrate/p/3535935.html

Opencv学習ノート(三)--画像圧縮と保存

1514:数値の整数次数@jobdu