算法题

黄敏

关注

发布于: 2021 年 03 月 17 日

面试题 01.03. URL 化

URL 化。编写一种方法，将字符串中的空格全部替换为 %20。假定该字符串尾部有足够的空间存放新增字符，并且知道字符串的“真实”长度。（注：用 Java 实现的话，请使用字符数组实现，以便直接在数组上操作。）

示例 1：

输入："Mr John Smith ", 13

输出："Mr%20John%20Smith"

class Solution {    public String replaceSpaces(String S, int length) {            char[] ch = new char[length * 3];        int index = 0;        for (int i = 0; i < length; i++) {            char c = S.charAt(i);            if (c == ' ') {                ch[index++] = '%';                ch[index++] = '2';                ch[index++] = '0';            } else {                ch[index] = c;                index++;            }        }        return new String(ch, 0, index);    }}

复制代码

1528. 重新排列字符串

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

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

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

示例 1：

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

输出："leetcode"

解释：如图所示，"codeleet" 重新排列后变为 "leetcode" 。

思路与算法

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

class Solution {    public String restoreString(String s, int[] indices) {        int length = s.length();        char[] result = new char[length];
        for (int i = 0; i < length; i++) {            result[indices[i]] = s.charAt(i);        }        return new String(result);    }}

复制代码

复杂度分析

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

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

发布于: 2021 年 03 月 17 日阅读数: 16

原文链接:【http://xie.infoq.cn/article/38288a2ce97243e2bfc195972】。

黄敏

关注

还未添加个人签名 2019.11.30 加入

还未添加个人简介

发布

暂无评论

创作场景

算法题

面试题 01.03. URL 化

1528. 重新排列字符串

黄敏

评论