問題 ２つの文字列str1, str2が与えられた時に、str2がstr1を回転させたものであるか調べる。 例えば str1 = "apple" str2 = "pplea" ならtrue である。 考え方 回転させたものなら str2 + str2としたものの中にstr1が含まれるはずである。 ただし、str1.len…

問題 M*N の行列において、(i, j)が0なら、その行iと列jを全て０にする。 考え方 (0, 0)から０の成分を見つけて、変換していくと全て０に変わってしまうので、まずは０の成分のある位置を格納する。 何個あるかわからないので、可変長配列(C++ではvector型)…

問題 N*Nの行列を90度回転させる 考え方 あまりたくさんのメモリを使いたくないので、１つの値だけを保持して回転させたい。 回転させると(i, j) -> (j, N-i)に移る。移った先を考えると、 (j, N-i)-> (N-i, N-j) (N-i, N-j) -> (N-j, i) (N-j, i) -> (i, j)…

問題 文字列を圧縮する。同じ文字が続いた数を使って表現する。 例：abbccccddd -> a1b2c4d3 とする。ただし、圧縮した方が、文字数が増えている場合は元の文字列を変えす。 考え方 元の文字列を１つずつ進んでいく。sに文字を入れて、s == str[i]である時に…

問題 ２つの文字列が与えられた際に、１回の変換(文字の追加、削除、置き換え）で等しくなるか 考え方 文字列の長さが等しい時は１文字だけ違ったら、置き換えで対応できます。 str1[i] != str2[i]となる数を判定して、これが１以下ならture。 文字列の長さ…

問題 文字列から回文が作れるか判定する 考え方 文字の数を数えて、文字の種類Mに対して、M-1個の文字が偶数回出れば良い。 アクセスを早くするためにhashを利用する。 計算量 文字列の長さをN、文字の種類をMとする。N >= M である。 hashに記録する際にはO…