回答日:2021年05月19日

質問する

質問リンク:リンクテキスト

アクセスと解析

以下のすべての条件を満たす数列xは、スター数列として定義される.
1.xの長さが2より大きい偶数.(空の列は許可されていません.)
2.x長が2 nの場合、n個の集合{x[0]、x[1]、{x[2]、{x[3]}、...、{x[2 n−2],x[2 n−1]}の交差における要素数は1より大きい.
3. x[0] != x[1], x[2] != x[3], ..., x[2n-2] != x[2n-1].
以上提案したスター数列となる条件から,2次条件で問題を解決すべきであると直感的に考えられる.
交差する要素は1つ以上存在しなければならず、これらの要素をどのように設定すれば最終的にはスター数列の長さも異なるので、単純な方法は、与えられた数列に現れる数字の周波数を利用してスター数列の条件をチェックすればよい.
これを実現するために,数列に存在する数の個数を計算し,存在する数を交差する要素に設定して,スター数列の条件が満たされているかどうかを調べた.
このとき、トリミング可能なハウジングが存在する.
例えば、与えられた数列[1,2,1,3,4,1,3]において、交差要素が1の場合、[1,2,1,3,4,1,3]には長さ8の星数列が生成され、交差要素が3であると考えると、どんなにうまくやっても最大長4の星数列しか生成されない.そのため、このような状況ではスターの数列条件をチェックする必要はありません.

コード#コード#

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(std::vector<int> a) {
    int answer = -1;
    vector<int> counter(a.size() + 1, 0); // a에 있는 수를 저장하기 위해 초기화
    
    for (int i = 0; i < a.size(); i++) {
        counter[a[i]]++; // a에 있는 수들의 갯수 저장
    }
    
    for (int i = 0; i < counter.size(); i++) {
        if (!counter[i]) continue; // 수열에 존재하지 않는 숫자
        if (counter[i] <= answer) continue; // 체크안해봐도 되는 케이스
        
        int cnt = 0;
        
        for (int j = 0; j < a.size() - 1; ) {
            if ((a[j] == i || a[j + 1] == i) && (a[j] != a[j + 1])) { // 스타수열 조건을 만족하는 경우
                cnt++; // 스타수열 길이 계산
                j += 2;
            } else {
                j += 1;
            }
        }
        answer = max(answer, cnt);
    }
    
    return answer * 2; // 길이는 2배해서 return
}

結果

フィードバック

問題を見るときは簡単そうに見えるので、簡単に解決したいです.どうして毎回クイズの时に初めて思ったのはGRADYですか...
しかし、サイトを参考にしてみると、思った以上に考えなければならないこともあれば、よく考えなければならないこともある.本当に頭のいい人がたくさんいます
問題を解くときは、与えられたテストケースをより深く考え、例外ケースをすばやく思い出すために、より多くの練習が必要になる可能性があります.

リファレンスサイト

リンクテキスト