写点什么

算法题

用户头像
黄敏
关注
发布于: 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
用户头像

黄敏

关注

还未添加个人签名 2019.11.30 加入

还未添加个人简介

评论

发布
暂无评论
算法题