CTF of Z2BNS
0%

增减字符串匹配

发表于 分类于 ，
| 阅读次数： |
Valine：
本文字数： 1.3k 阅读时长 ≈ 1 分钟

题目地址

难度：⭐

题目描述：

给定只含 "I"（增大）或 "D"（减小）的字符串 S ，令 N = S.length。

返回 [0, 1, ..., N] 的任意排列 A 使得对于所有 i = 0, ..., N-1，都有：

  • 如果 S[i] == "I"，那么 A[i] < A[i+1]
  • 如果 S[i] == "D"，那么 A[i] > A[i+1]

示例1：

1
2
输入："IDID"
输出：[0,4,1,3,2]

示例2：

1
2
输入："III"
输出：[0,1,2,3]

示例3：

1
2
输入："DDI"
输出：[3,2,0,1]

提示：

  • 1 <= S.length <= 10000
  • S 只包含字符 "I" 或 "D"。
🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️解题过程🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️
解题过程：

思路：

根据题目分析，字符串中第一个‘D’位置对应的A中的元素值最大为N，第二‘D’对应元素值为N-1，以此顺序依次减小。第一个‘I’位置对应的A中元素值最小为0，第二个‘I’对应元素值加1，以此顺序依次增大，A中最后一个元素在字符串S中没有对应，其值为最后一个‘I’对应元素值加1或最后一个‘D’对应元素值减1。遍历字符串，对字符的不同值‘I’或‘D’进行相应处理。

c++代码：(执行用时12ms，击败40.65%，内存消耗9.2M，击败16.95%）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> diStringMatch(string S) {
        vector<int> result;
        int N=S.length();
        int little=0,big=S.length();
        for(char c:S){
            if(c=='I'){
                result.emplace_back(little);
                ++little;
            }else{
                result.emplace_back(big);
                --big;
            }
           
        }
        result.emplace_back(little);
        return result;
    }
};
💎💎💎💎💎💎💎💎💎💎💎💎💎💎💎官 方 题 解💎💎💎💎💎💎💎💎💎💎💎💎💎💎💎
官方题解:

分析

我们首先考虑字符串中的第一个字母。如果 S[0] == 'I'，那么我们只要令 A[0] = 0，就一定能满足 A[0] < A[1]。如果 S[0] == 'D'，同样我们只要令 A[0] = N，就一定能满足 A[0] > A[1]。

接下来，当我们考虑 S 中剩下的 N - 1 个字母时，还剩下 N 个数可以使用，这 N 个数为 [0 .. N - 1] 或 [1 .. N]。可以发现，由于 S[0] 的值已经确定，那么剩下 S 中的 N - 1 个字母和 N 个可用的数变成了一个和原问题相同，但规模为 N - 1 的问题。即如果 S[1] == 'I'，我们就令 A[1] 为剩下数中最小的那个数；如果 S[1] == 'D'，我们就令 A[1] 为剩下数中最大的那个数。

我们每次会把可以使用的数的集合中的最小值或最大值取出，并放到当前的位置，因此可以使用的数的集合总是连续的，就可以非常方便的进行维护。

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int[] diStringMatch(String S) {
        int N = S.length();
        int lo = 0, hi = N;
        int[] ans = new int[N + 1];
        for (int i = 0; i < N; ++i) {
            if (S.charAt(i) == 'I')
                ans[i] = lo++;
            else
                ans[i] = hi--;
        }

        ans[N] = lo;
        return ans;
    }
}

复杂度分析

  • 时间复杂度：$O(N)$，其中 $N$ 是字符串 S 的长度。
  • 空间复杂度：$O(N)$。
⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳总 结⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳
总结：

官方题解虽然分析过程和我描述的有些差别，但思路是一致的，代码也基本相同，不过官方题解是Java实现的，题目也还好，比较容易想到👦。

------------- THE END! THANKS! -------------