【LeetCode-955】解题报告（暴力，贪心）

原始题目
题目大意
解题思路
解题代码
收获与反思

原始题目

给定由 N 个小写字母字符串组成的数组 A，其中每个字符串长度相等

选取一个删除索引序列，对于 A 中的每个字符串，删除对应每个索引处的字符。

比如，有 A = [“abcdef”, “uvwxyz”]，删除索引序列 {0, 2, 3}，删除后 A 为[“bef”, “vyz”]。

假设，我们选择了一组删除索引 D，那么在执行删除操作之后，最终得到的数组的元素是按字典序（A[0] <= A[1] <= A[2] … <= A[A.length - 1]）排列的，然后请你返回 D.length 的最小可能值。

题目大意

找出最小的删除索引的可能值

解题思路

裸枚举+贪心

解题代码

裸枚举

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<string, string> pss;
typedef vector<int> vi;
typedef vector<string> vs;

#define rep(i, a, n) for (int i = a; i < n; ++i)
#define per(i, a, n) for (int i = n - 1; i >= a; --i)
#define all(x) x.begin(), x.end()
#define mp make_pair
#define pb push_back
#define np next_permutation
#define fi first
#define se second

bool compare(vector<string>& A)
{
    rep(i, 1, A.size())
    {
        if (A[i - 1] > A[i]) {
            return false;
        }
    }
    return true;
}

class Solution {
    public:
        int minDeletionSize(vector<string>& A)
        {
            vector<string> test(A.size(), "");
            int ans = 0;
            rep(i, 0, A.front().size())
            {
                rep(j, 0, A.size())
                {
                    test[j].pb(A[j][i]);
                }
                if (!compare(test)) {
                    ans++;
                    rep(j, 0, A.size())
                    {
                        test[j].pop_back();
                    }
                }
            }
            return ans;
        }
};

贪心

class Solution {
public:
    int minDeletionSize(vector<string>& A)
    {
        int ans = 0;
        vi pos(A.size(), 0);
        rep(i, 0, A.front().size())
        {
            int flag = 0;
            rep(j, 1, A.size())
            {
                if (!pos[j] && A[j][i] < A[j - 1][i]) {
                    ans++;
                    flag = 1;
                    break;
                }
            }
            if (flag)
                continue;
            rep(j, 1, A.size())
            {
                if (A[j - 1][i] < A[j][i]) {
                    pos[j] = 1;
                }
            }
        }
        return ans;
    }
};

收获与反思

none