CTF of Z2BNS
0%

重新排列字符串

发表于 更新于 分类于 ，
| 阅读次数： |
Valine：
本文字数： 1.8k 阅读时长 ≈ 2 分钟

题目地址

难度：⭐

题目描述：

给你一个字符串 s 和一个 长度相同 的整数数组 indices 。

请你重新排列字符串 s ，其中第 i 个字符需要移动到 indices[i] 指示的位置。

返回重新排列后的字符串。

示例1：

img

1
2
3
输入：s = "codeleet", indices = [4,5,6,7,0,2,1,3]
输出："leetcode"
解释：如图所示，"codeleet" 重新排列后变为 "leetcode" 。

示例2：

1
2
3
输入：s = "abc", indices = [0,1,2]
输出："abc"
解释：重新排列后，每个字符都还留在原来的位置上。

示例3：

1
2
输入：s = "aiohn", indices = [3,1,4,2,0]
输出："nihao"

示例4：

1
2
输入：s = "aaiougrt", indices = [4,0,2,6,7,3,1,5]
输出："arigatou"

示例5：

1
2
输入：s = "art", indices = [1,0,2]
输出："rat"

提示：

  • s.length == indices.length == n

  • 1 <= n <= 100

  • s 仅包含小写英文字母。

  • 0 <= indices[i] < n

  • indices 的所有的值都是唯一的（也就是说，indices 是整数 0 到 n - 1 形成的一组排列）。

🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️解题过程🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️
解题过程：

思路：

使用map容器，map容器存储键值对，会根据各键值对的键的大小升序排序。用indices数组中的值作为键，对应的字符作为值存到map容器中，最后用map中的值组成字符串返回。

c++代码：(执行用时36ms，击败5.57%，内存消耗16.8M，击败5.04%）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    string restoreString(string s, vector<int>& indices) {
        map<int,char> myMap;
        //初始化map容器，会按照键值从小到大排序
        for(int i=0;i<s.length();++i){
            myMap[indices[i]]=s[i];
        }
        for(int i=0;i<myMap.size();++i){
            s[i]=myMap[i];
        }
        return s;
    }
};
💎💎💎💎💎💎💎💎💎💎💎💎💎💎💎官 方 题 解💎💎💎💎💎💎💎💎💎💎💎💎💎💎💎
官方题解:

方法一：模拟
思路与算法

创建一个新字符串 $\textit{result}$ 来存储答案。对于 $s$ 每个下标 $i$，将 $\textit{result}[\textit{indices}$[i]]处的字符设成 $s[i]$即可。

代码：（执行8ms，击败98.89%，内存15.2M，击败15.39%）

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    string restoreString(string s, vector<int>& indices) {
        int length = s.length();
        string result(length, 0);

        for(int i = 0; i < length; i++) {
            result[indices[i]] = s[i];
        }
        return result;
    }
};

复杂度分析

  • 时间复杂度：$O(N)$，其中 $N$为字符串 $s$ 的长度。我们只需对字符串 $s$ 执行一次线性扫描即可。

  • 空间复杂度：$O(1)$或 $O(N)$。除开辟的存储答案的字符串外，我们只需要常数空间存放若干变量。如果使用的语言不允许对字符串进行修改，我们还需要 $O(N)$的空间临时存储答案。

方法二：原地修改
思路与算法

本题也可以通过原地修改输入数据的方式来求解。

直观的想法是：对于下标 $i$，需要把字符 $s[i]$ 移动到 $\textit{indices}[i]$ 的位置上；然后，我们前进到位置 ，并将字符 $s[\textit{indices}[i]]$移动到 $\textit{indices}[\textit{indices}[i]]$的位置上。类似的过程以此类推，直到最终回到起点 $i$。此时，封闭路径 $i \to \textit{indices}[i] \to \textit{indices}[\textit{indices}[i]] \to … \to i$上的所有字符，都已经被设置成正确的值。

我们只要找到 $\textit{indices}[i]$中所有这样的封闭路径，并进行对应的移动操作，就能够得到最终的答案。

这样做有一个小小的问题：当在第二步试图把字符 $s[\textit{indices}[i]]$移动到 $\textit{indices}[\textit{indices}[i]]$ 的位置上时，会发现字符 已经在第一步被覆写了。因此，在每一步移动前，需要先额外记录目标位置处字符的原有值。

另一个隐含的问题是如何避免处理重复的封闭路径。为了解决此问题，我们每处理一个封闭路径，就将该路径上的 $\textit{indices}$数组的值设置成下标自身。这样，当某个封闭路径被处理完毕后，扫描到该路径的另一个下标时，就不会处理该封闭路径了。

由于许多语言中的字符串类型都是不可更改的，实现原地修改较为麻烦，因此下面只给出 C++ 的参考代码。

代码：（执行16ms，击败77.65%，内存15.3M，击败13.37%）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    string restoreString(string s, vector<int>& indices) {
        int length = s.length();
        for (int i = 0; i < length; i++) {
            if (indices[i] != i) {
                char ch = s[i]; // 当前需要被移动的字符
                int idx = indices[i]; // 该字符需要被移动的目标位置
                while (idx != i) {
                    swap(s[idx], ch); // 使用 swap 函数，在覆写 s[idx] 之前，先将其原始值赋给变量 ch
                    swap(indices[idx], idx); // 将封闭路径中的 indices 数组的值设置成下标自身
                }
                // 退出循环后，还要再覆写起点处的字符
                s[i] = ch;
                indices[i] = i;
            }
        }
        return s;
    }
};

复杂度分析

  • 时间复杂度：$O(N)$，其中 $N$ 为字符串 $s$ 的长度。尽管代码看上去有两层循环，但因为不会处理相同的封闭路径，每个下标实际上只被处理了一次，故时间复杂度是线性的。

  • 空间复杂度：$O(1)$。我们只需开辟常量大小的额外空间。

⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳总 结⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳
总结：

这道题其实直接模拟是效率比较高的，其他的方法反而可能效率不是那么高，我还用到了map集合想着高端一点🤣，结果官方题解都没用map

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