この章について

配列と文字列の基本操作に関する章です。今後の章でも問題を解いていくことしかしません(多分)。

やるぞ

何問か解くごとに投稿していけたらと思っています。C++で書きます。飽きないよう頑張ります。
引用元は全てこの本の第3刷です。原著(英語)はこちらです。
ど素人なのでどんな事でもコメントいただけると喜びます...
長期に渡って書くので口調がバラバラかもしれません。ひと段落ついたら統一します..........

Question 1.1

ある文字列が、すべて固有である(重複する文字列がない)かどうかを判定するアルゴリズムを実装してください。

例 : "qiita" → iが2回出てくるのでFalse, "question" → どの文字も一度しか出現しないのでTrue

1-1.cpp

#include<iostream>
using namespace std;

bool f[256];
//文字コードが(拡張)ASCIIの場合
bool UniqueExtendedAscii(string s){
    for(int i = 0;i < s.length();i++){
        int v = (int)(s[i]);
        if(f[v]){return false;}
        f[v] = true;
    }
    return true;
}

//英小文字26文字の場合
bool UniqueOrNot(string s){
    int v = 0, a;
    for(int i = 0;i < s.length();i++){
        a=(int)(s[i]-'a');
        if((v&(1<<a)) > 0){return false;}
        v|=(1<<a);
    }
    return true;
}

~~Unicodeなんてない。~~
(拡張)ASCIIに対しては文字ごとにフラグ管理、英小文字に限定するなら(int)(s[i]-'a')が0から25までの整数を返してくれるので32bit整数のビットを立てることで管理できる。

1-1example.cpp

#include<iostream>
#include<bitset>
using namespace std;
int main(){
    string s="question";//簡単のためにsを適当に定めた
    int n = 0;
    for(int i = 0;i < s.length();i++){
        int a = (int)(s[i]-'a');
        n|=(1<<a);
    }
    cout<<bitset<32>(n)<<endl;
}

出力結果

00000000000111010110000100010000

ちゃんと"question"の各文字に対応する場所にビットが立っているのが分かる。

Question 1.2

2つの文字列が与えられたとき、片方がもう片方の並び替えになっているかどうかを決定するメソッドを書いてください。

例 : "dog"と"god" → True , "question"と"answer" → False
大文字と小文字を区別してます。

1-2.cpp

#include<iostream>
#include<algorithm>
using namespace std;

bool perm1(string s, string t){
    sort(s.begin(),s.end());
    sort(t.begin(),t.end());
    return s==t;
}

int let[256];
bool perm2(string s,string t){
    for(int i = 0;i < s.length();i++){
        let[s[i]]++;
    }
    for(int i = 0;i < s.length();i++){
        let[t[i]]--;
        if(let[t[i]] < 0){return false;}
    }
    return true;
}

perm1 : sortして比較、ズル。
perm2 : 先にsの各文字の登場回数をカウントして、tの各文字の登場回数を引いている。sとtが互いの順列なら各文字に対して登場回数の差は0になるはずなのでlet[t[i]]の値が負になった瞬間にfalseを返す。

Question 1.3

文字列内に出現するすべての空白文字を"%20"で置き換えるメソッドを書いてください。

例 : "This is a pen" → "This%20is%20a%20pen"
なんやこれ...と思っていたらURLのエンコードでスペースを%20に置き換えるみたいなのがあるらしい(?)

1-3.cpp

#include<iostream>
using namespace std;
string SubstitutePer20ForSpace(string s){
    string t="";
    for(int i = 0;i < s.length();i++){
        if(s[i]!=' '){t.insert(t.end(),s[i]);}
        else{t+="%20";}
    }
    return t;
}
int main(){
    string s;
    getline(cin,s);//入力が空白区切りで困ったのでこうした
    cout<<SubstitutePer20ForSpace(s)<<endl;
}

分岐をしただけになった。

Question 1.4

文字列が与えられたとき、その文字列が回文の順列であるかを調べる関数を書いてください。

例 : "lelev" → "level"の順列なのでTrue , "aakkaaa" → "kaaaaak"の順列なのでこれもTrue(英単語として意味をなす必要はない)

1-4.cpp

#include<iostream>
using namespace std;

//英小文字26文字の場合
bool palindrome1(string s){
    int n = 0;
    for(int i = 0;i < s.length();i++){
        if(s[i]==' '){continue;}//空白は無視
        else{
            int a = 1<<(int)(s[i]-'a');
            n^=a;//排他的論理和を取ると立ってたビットが倒れ、倒れてたビットが立つ
            }
    }
    return (n&(n-1))==0;
}

//(拡張)ASCIIの場合
int charcount[256];
bool palindrome2(string s){
    int OddCount = 0;
    for(int i = 0;i < s.length();i++){
        charcount[s[i]]++;
        if(charcount[s[i]]%2==1){OddCount++;}
        else{OddCount--;}
    }
    return (OddCount<=1);
}

回文を左右から見ると、ほとんどの文字が偶数回出ている。与えられた文字列の長さが奇数なら、回文の中央にはある文字が奇数個並ぶことになるので、奇数個登場する文字は高々一種類。

やってることはQuestion1.1とそんなに変わらない。
palindrome1 : 入力が英小文字だけなら32ビット整数で管理できる。文字の登場回数の偶奇にしか興味がないのでビットを立てたり倒したりすれば良い。
もし入力が回文の順列となっていれば奇数回登場する文字は高々1つなので、立っているビットも1本か0本である。関数中では変数nに格納しているのでこれが0又は1000...00の形をしていればよい。
桁数が少ないので2で割り続けるのもまあいいが、nが上の形をしているかどうかは(n&(n-1))==0で一発で判別できる(これ普通に感動した)。

palindrome2 : (拡張)ASCII想定なのでサイズが256の配列にそれぞれの登場回数を格納する。
登場回数のカウントが奇数になるごとにOddCountの値をインクリメント、偶数になるごとにデクリメントすることで、全ての文字に対する登場回数を調べなくて済む。

Question 1.5

文字列に対して行うことができる3種類の編集:文字の挿入、文字の削除、文字の置き換えがあります。2つの文字列が与えられたとき、一方の文字列に対して1操作(もしくは操作なし)でもう一方の文字列にできるかどうかを判定してください。

例 : "apple"と"aple" → "apple"から'p'を削除すると等しくなる, "orange"と"apple" → 一回の操作では不可能
考察しやすいように2つの文字列をsとtとすると、s.length()<=t.length()としておく。sをtに埋め込みたい

1-5.cpp

#include<iostream>
using namespace std;
bool Edit(string s,string t){
    if(abs((int)(s.length()-t.length())) > 1){return false;}//2文字以上違えば論外
    if(s.length() > t.length()){swap(s,t);}//文字数の大小関係を固定しておく
    bool diff = false;//異なる文字を見つけたらtrueにする
    int i1 = 0;
    int i2 = 0;
    while((i1 < s.length())&&(i2 < t.length())){
        if(s[i1]!=t[i2]){
            if(diff){return false;}//diffがtrueならこの時点で2文字違ったことになるのでfalseが返る
            diff = true;//1文字違ったのでtrueにしておく
            if(s.length()==t.length()){
                i1++;//手前から走査しているので進めるだけ
                }
            }
        else{
            i1++;//等しいなら等しいで進める
        }
        i2++;//s.length()<=t.length()なのでtのindexは常に進める
    }
    return true;
}

これなら一度sとtを見るだけで済むので早そう。

#Question 1.6

文字の連続する数を使って基本的な文字列圧縮を行うメソッドを実装してください。

例 : "aaabbcccc" → "a3b2c4", "sssssttttu" → "s5t4u1"

1-6.cpp

#include<iostream>
using namespace std;
string compression(string s){
    string t = "";
    int count = 1;
    for(int i = 0;i < s.length()-1;i++){
        if(s[i]==s[i+1]){count++;}//連続しているうちはcountを増やすだけ
        else{
            t.insert(t.end(),s[i]);//そうでなければtに文字と連続した個数をjoinする
            t+=to_string(count);
            count = 1;//countの値を戻す
            }
    }
    t.insert(t.end(),s[s.length()-1]);
    t+=(count!=1 ? to_string(count) : "");//最後の文字だけ処理が行われていないのでループ出た後に書かないといけなくなった
    return t;
}

これも素直な実装だと思っている、sを一度見るだけでいいので効率良さそう。

Question 1.7

N×Nの行列に描かれた、1つのピクセルが4バイト四方の画像があります。その画像を90度回転させるメソッドを書いてください。

「4バイトの四方の画像〜」というのがよく分からなかったので普通にN×Nの行列を右に90度回転させた。

1-7.cpp

#include<iostream>
using namespace std;
const int N = 3000;//もちろんサイズはなんでも良い。書き方の都合で今回は定めた。
int mat[N][N];
void Rotate90(){
    for(int i = 0;i < N/2;i++){
        for(int j = 0;j < (N+1)/2;j++){
            int from = mat[i][j];
            mat[i][j] = mat[N-1-j][i];
            mat[N-1-j][i] = mat[N-1-i][N-1-j];
            mat[N-1-i][N-1-j] = mat[j][N-1-i];
            mat[j][N-1-i] = from;
        }
    }
}

これはNの偶奇によって回転の様子が少し違うので、7行目でj<(N+1)/2とすることでまとめて処理できるようにした。
図解↓ 左がNが奇数、右がNが偶数の場合。

左上の領域にある値を持って、左下→左上、右下→左下、右上→右下、持っておいた左上の値→右上という風に代入している。

Question 1.8

M×Nの行列について、要素が0であれば、その行と列すべてを0にするようなアルゴリズムを書いてください。

1-8.cpp

#include<iostream>
using namespace std;
const int M = 3000;
const int N = 3000;//今回もとりあえずサイズを決めた
int mat[M][N];

//解法1。愚直。メモリを食う
void fillzero1(){
    bool row[M],col[N];
    for(int i=0;i<M;i++){
        for(int j=0;j<N;j++){
            if(mat[i][j]==0){
                row[i]=true;
                col[j]=true;
            }
        }
    }
    for(int i = 0;i < M;i++){
        for(int j = 0;j < N;j++){
            if(row[i]||col[j]){
                mat[i][j] = 0;
            }
        }
    }
}

//解法2。行・列共にサイズが小さければ32ビット整数に格納するのもアリ
void fillzero2(){
    int ROW = 0, COL = 0;
    for(int i = 0;i < M;i++){
        for(int j = 0;j < N;j++){
            if(mat[i][j]==0){
                //それぞれのビットを立てる
                ROW |= 1<<i;
                COL |= 1<<j;
            }
        }
    }
    for(int i = 0;i < M;i++){
        for(int j = 0;j < N;j++){
            if((ROW>>i)||(COL>>j)){
                //どちらかのビットが立っていればその要素は0
                mat[i][j] = 0;
            }
        }
    }
}

//解法3。これが一番メモリを食わないしM,Nが実装に影響しない(はず)
void fillzero3(){
    for(int i = 0;i < M;i++){
        for(int j = 0;j < N;j++){
            if(mat[i][j]==0){
                //要素が0かどうかの情報を各行・各列の0番目に保存しておく
                mat[i][0] = 0;
                mat[0][j] = 0;
            }
        }
    }

    for(int i = 0;i < M;i++){
        for(int j = 0;j < N;j++){
            if((mat[i][0]==0)||(mat[0][j]==0)){
                mat[i][j] = 0;
            }
        }
    }
}

解法1 : 多分これが真っ先に思いつく(?) 0がある行(列)の情報をそれぞれサイズM,Nの配列に保存して最後にいっぺんに更新。
解法2 : (行(列)のサイズが共に小さくないと使えないが...) 0がある行(列)の桁のビットを立てる。あとは一緒。
解法3 : 解法1,2と比べて空間計算量が少ない。どうせ0にするんだから最初から全部0行目と0列目に保存しておこうという発想。

Question 1.9

片方の文字列が、もう片方の文字列の一部分になっているかどうかを調べるメソッド「isSubstring」が使えるものと仮定します。2つの文字列s1とs2が与えられたとき、isSubstringメソッドを一度だけ使ってs2がs1を回転させたものであるかどうかを判定するコードを書いてください。

(isSubstringなんて実装したっけ...)
解答を見たところ、"文字列Sを回転する" 　の意味するものが
"文字列Sを「どちらも空でなく共通部分を持たない」かつ「T,Uの順に結合するとSと等しくなる」2つの文字列T,Uに分け、U,Tの順に結合し直すこと"
っぽく書かれている。s1を逆から読むとs2になるか判別する問題だと思っていた...

まあ練習と思ってisSubstringから実装していく。

1-9.cpp

#include<iostream>
using namespace std;

//sがtの部分文字列かを調べる
bool isSubstring(string s,string t){
    int sindex = 0, tindex = 0;
    while((sindex < s.length())&&(tindex < t.length())){
        if(s[sindex]==t[tindex]){sindex++; tindex++;}
        else{tindex++;}
    }
    return sindex==s.length();
}

//問題文の意味が解答の通りだとこうなる
bool isRotate(string s1, string s2){
    string s3 = s1 + s1;
    return isSubstring(s2,s3);
}

//"回転"がreverseを意味しているならs1+s2に対してこれを実行すればいい
bool isPalindrome(string s){
    int first = 0, last = s.length()-1;
    while(first < last){
        if(s[first]!=s[last]){return false;}
        first++;
        last--;
    }
    return true;
}