当前位置 博文首页 > 程序员吴师兄的博客:一道简简单单的字节跳动算法面试题
点击上方“图解面试算法”,选择“星标”公众号
重磅干货,第一时间送达
今天分享的题目来源于 LeetCode 上的剑指 Offer 系列 面试题05. 替换空格,据官方统计,近半年在字节跳动算法面试中出现过 5 次。
题目链接:https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof/
请实现一个函数,把字符串 s 中的每个空格替换成"%20"。
示例 1:
输入:s?=?"We?are?happy."
输出:"We%20are%20happy."
限制:
0 <= s 的长度 <= 10000
这题还是挺简单的。
遍历字符串中的每个字符,如果不是空格,直接赋值过去数组中;否则,赋值 %20 过去数组中。
最后,从数组中的前 size
个字符创建新字符串,并返回新字符串。
//来源:https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof/solution/mian-shi-ti-05-ti-huan-kong-ge-by-leetcode-solutio/
class?Solution?{
????public?String?replaceSpace(String?s)?{
????????//获取字符串?s?的长度?length
????????int?length?=?s.length();
????????//创建字符数组?array,其长度为?length?*?3
????????char[]?array?=?new?char[length?*?3];
????????//初始化?size?为?0,size?表示替换后的字符串的长度
????????int?size?=?0;
????????//从左到右遍历字符串?s
????????for?(int?i?=?0;?i?<?length;?i++)?{
????????????//获得?s?的当前字符?c
????????????char?c?=?s.charAt(i);
????????????//如果字符?c?是空格,则令?array[size]?=?'%',array[size?+?1]?=?'2',array[size?+?2]?=?'0',并将?size?的值加?3
????????????if?(c?==?'?')?{
????????????????array[size++]?=?'%';
????????????????array[size++]?=?'2';
????????????????array[size++]?=?'0';
????????????}?else?{
????????????????array[size++]?=?c;
????????????}
????????}
????????//遍历结束之后,size?的值等于替换后的字符串的长度,从?array?的前?size?个字符创建新字符串,并返回新字符串
????????String?newStr?=?new?String(array,?0,?size);
????????return?newStr;
????}
}
时间复杂度为 O(n),遍历字符串 s
一遍。
空间复杂度:O(n),额外创建字符数组,长度为 s
的长度的 3 倍。
字符串
数组
---
由 五分钟学算法 原班人马打造的公众号:图解面试算法,现已正式上线!
接下来我们将会在该公众号上,为大家分享优质的算法解题思路,坚持每天一篇原创文章的输出,感兴趣的小伙伴可以关注一下哈!
cs