プログラマー-最長のパリントロム-C++

3329 ワード
アルゴリズム#アルゴリズム# プログラマ テキストリンク
https://programmers.co.kr/learn/courses/30/lessons/12904

問題の説明

  • 文字列sが与えられると、最も長いパリンドロンsub-stringの長さの問題が返される.

    • 方法1

  • sub-stringおよびreverse-sub-stringの文字列を比較するために、最初に2つのfor文が使用される.

  • 制約条件がsの最大長さが2500であるため、O(n^2)は問題ないが、reverse関数がO(n)であることは無視される.

    • 答えを出す。

    #include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int solution(string s)
{
    int answer=0;
    for(int j=0;j<s.length();j++){
        string tmp;
        for(int i=j;i<s.length();i++){
            string p;
            tmp += s[i];
            p=tmp;
            reverse(p.begin(),p.end());	// p를 거꾸로 하여
            if(tmp == p && answer < tmp.length()){	// tmp와 비교
                answer = tmp.length();	// answer 보다 크면 바꿔주기
            }
         }
    }
    return answer;
}

    結果。



    方法2

  • sub-stringなので必ず一度for文を書きますが、sub-stringの各文字を比較するので、もう一度for文を書きます...reverse()を使わないことが重要らしい.

  • reverse()全体比較をしたいのですが、変えるときは順番が同じで、前後が同じでいいのではないでしょうか.だから私は急に演算を減らしたいと思っています.

  • 一番前、一番後ろの2文字を比較し、同じ場合は一番前、右、最後の左、左を繰り返します.

  • bool変数が異なる場合はfalse処理を行い、次の文字列に移動します.

  • 一番長い文字を返すので、一番長い文字から比較して、パリンドロンなら文字の長さが一番大きい!!私はこれを考えています.私はどうしてこんなに愚かですか.

    • 説明する。

    #include <iostream>
#include <string>
using namespace std;
int solution(string s)
{
    int answer=0;
    for(int i = s.length();i>0;i--){	// sub-string의 길이 i
            for(int j=0;j<=s.length()-i;j++){
                int l = j;
                int r = i-1+j;
                bool pal = true;
                while(l<r){
                    if(s[l]!=s[r]){
                        pal = false;
                        break;
                    }
                    l++;r--;	// 다음 문자 인덱스로 넘기기
                }
                if(pal){	// 팰린드롬이 맞으면 return
                    return answer = i;
                }
            } 
    }
    return answer;
}

    結果。



    に感銘を与える


  • reverse()は時間的複雑度nを有する.あらためて実感する

  • 最大長さを求めているので、最後まで探索する必要はありません...メモ...ほほほ、これで私はもっと強くなりました.
    • [BOJ]11054-最長のバイナリ部分数列
    白駿3055号:脱出(python)