テンセント2017夏休み実習生のプログラミング問題の問題解

タイトルリンク:https://www.nowcoder.com/test/1725829/summary
1.構造回文
文字列sを指定すると、残りの列がエコー列になるように、いくつかの文字を削除できます.どのように削除して文字列を最も長くすることができますか?削除する文字数を出力します.
问题の考え方の分析:问题の意味は私达に少なくともいくつかの文字を削除してこの文字を1つの回文列に変えることができることを闻くことを闻いて、ここで回文列の性质を使う必要があります.回文列は前后対称なので、私达は文字列とその反列の最も长い共通のサブ列の长さを要求するだけでいいです.最長共通サブシーケンス長を解く方法は動的に計画すればよく、dp[i][j]は、1番目の文字列iの位置の前のサブ列と2番目の文字列jの前のサブ列の最長共通サブシーケンス長を一致させると、s 1[i]==s 2[j]であれば、dp[i][j]=dp[i-1][j-1]+1となり、そうでなければdp[i][j]=max(dp[i-1][j],dp[i][j-1])となる.
コード;

#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 1000+5;
char s1[maxn], s2[maxn];
int dp[maxn][maxn];
int main() {
    while(cin >> s1) {
        int len = strlen(s1);
        for(int i=0; i

2.アルゴリズムの基礎
小Qは最近、文字列の大文字を文字列の後ろに置くと、各文字の相対的な位置が変わらず、余分な空間を申請できないという難題に直面した.Qさんを手伝ってもらえますか.
問題を解く構想の分析:余分な空間を開くことができなくて、それでは私達は直接この文字列の上で交換することができて、この問題は私達は後ろから前へ行って、1つの大文字に出会うだけで、それをずっと後ろに最後あるいは別の大文字に交換します.
コード:

#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 1000 + 5;
char str[maxn];
int main() {
    while(cin >> str) {
        int len = strlen(str);
        int pos = len - 1;
        for(int i=len-1; i>=0; i--) {
            if(str[i] <= 'Z' && str[i] >= 'A') {
                for(int j=i+1; j<=pos; j++) {
                    swap(str[j-1], str[j]);
                }
                pos--;
            }
        }
        cout << str << endl;
    }
}

3.面白い数字
Qさんは今日トイレに行くとき、この問題を思い出しました.n個の数があり、2つの2つが2元グループを構成しています.差が一番小さいのはどのくらいですか.差が一番大きいのは?
問題を解く構想の分析:問題の意味は私たちに差の最小と最大の二元グループがどれだけ正しいかを聞くことです.
まず、すべての数をソートしてから、すべての数の重複要素を削除し、その出現回数を記録します.明らかに、差の最大値は最大の数から最小の数を減算するに違いありません.したがって、差の最大対数は最大の数の個数に最小の数を乗算する個数です.繰り返し要素が現れた場合、最小の差はもちろん0であり、繰り返し要素が現れなければ、この順序付けされたシーケンスの隣接要素の差から最小を探すだけです.最小の差は隣接要素の差に違いないので、2回目の遍歴で見つけることができます.
コード:

#include