Leetcode質問セット：インタビュー質問01.06。文字列圧縮

Leetcode Question Set

Leetcode Chineseは最近、毎日1つの質問アクティビティ、短い回答の質問を公開しましたが、私はそれを数回提出し、多くの間違いを犯しました。だから記録する

トピック分析 ：文字列圧縮、特別なことは何もありません。数字に文字を追加する方法は非常に一般的です。圧縮された文字列が元の文字列よりも小さい場合の要件 短縮しませんでした 、次に元の文字列を返します。それ以外の場合は、圧縮された文字列を返します。

トピックの意味は非常に明確で、非常に明確です。コーディングを開始するだけで、すぐに書き出すことができます。

class Solution { public: string compressString(string S) { if(S.size()<=1) return S // When S length<=1, return the original string string res(1, S[0]) // initial first character int cnt = 1 for(int i=1i=S.size()?S:res // length judgment, return result } }

その結果、31番目のサンプルでメモリ制限が報告されました。今少し混乱していますが、追加の文字列を使用できないようにする必要がありますか？

考えてみると、元の文字列だけを変更すると、文字列を変更して再カウントする必要があるため、達成できないようです。 前がすべて異なる単一文字である場合、圧縮後のインデックスが文字トラバーサルインデックスよりも大きい状況が発生します 、トラバーサルエラーが発生します。ストレージ用に追加の文字列を開くためですが、なぜメモリ制限を超えるのでしょうか。

それを考えた後、それはこの文字列の追加に問題があるためにのみ可能です。そこで、一般的に使われているベクトル最適化の方法でもある別の考え方を考えました。 事前に長さを指定することです 。では、どのくらいの長さが適切ですか？元の文字列より長くないので、文字列と同じ長さに設定してください。したがって、次のバージョンのコードがあります。

class Solution { public: string compressString(string S) { int len = S.size() if(len<=2) return S // In fact, the original string is returned directly if the string is <=2, because the compressed string is at least 2 string res(len+2, S[0]) // Initialize to len+2 length, to prevent res index overflow, reserve two more positions // cur records the index of the current compressed string int cnt = 1, cur = 0 for(int i=1i=len-1) return S //exit when cur>=len-1 is set here, because the length of the next round must be at least 1 } res[++cur] = cnt+'0' // --- return cur+1>=len?S:res.substr(0, cur+1) } }

問題ないようですが、非常に低レベルのエラーがあります。つまり、cntカウントはすべて1桁ではありません。 。 。 jio jioを選ぶ必要があり、提出数は+1です。

つまり、ループ内の各ビットを追加する必要があり、私はそれを心の中で拒否しますが、それでも次のコードを記述しました。

class Solution { public: void stringAddInt(string &res, int &cur, const int &cnt){ string tem = to_string(cnt) // converted to string for(auto item:tem) // cyclically fill in the index position of the letter string res[++cur] = item } string compressString(string S) { int len = S.size() if(len<=2) return S string res(len+2, S[0]) // reserve the length of +2 len int cnt = 1, cur = 0 // cur represents the current index for(int i=1i=len-1) return S // if cur index is greater than len-1, exit } stringAddInt(res, cur, cnt) return cur+1>=len?S:res.substr(0, cur+1) } }

コードは最終的に渡されます。次に戻って、最初のタイプがメモリ超過のエラーを報告する理由を考えてみてください。問題は文字列の追加です。次の何が問題になっていますか？

res = res + to_string(cnt)

よく見ると本当に問題です！この文章の分析は、 2つの文字列オブジェクトを追加してから、再度割り当てます 。途中で、新しいオブジェクトが作成され、新しいオブジェクトはメモリを占有している必要があります。このように、消費量は確かに大きいです。したがって、予約された長さに変更し、インデックスを介して値を割り当てます。余分なオブジェクトは生成されないため、メモリ超過の問題は発生しません。 その場合、+ =を直接使用することは可能ですか？たとえば、+ =は、新しい追加の変数を生成せずに変数を直接操作することです。 。だから私はそれを試しました：

class Solution { public: string compressString(string S) { if(S.size()<=1) return S string res(1, S[0]) int cnt = 1 for(int i=1i=S.size()?S:res } }

結果は合格です。自閉症

問題は単純ですが、多くの問題が発生しています。実際、最後の問題にはまだ問題があります。つまり、res [res.size（）-1]をS [i-1]に置き換える方が実際には優れています。