程序员面试金典 <Cracking the Coding Interview> 面试题 01.03. URL化 配图
标签:ima com div ems nbsp lse 算法 ace 试题
地址 https://leetcode-cn.com/problems/string-to-url-lcci/solution/
URL化。编写一种方法,将字符串中的空格全部替换为%, , , ] 范围内。
解答
算法1
(逆序枚举) O(n)
看题意 题目似乎有个隐藏条件
不需要额外的空间 只在输入的字符串中进行计算
因为字符串的长度实际比输入的字符要大
那么我们可以倒序计算
两个指针分别指向字母和字符串的最末尾,
如果是其他字母则照样复制 两指针分别向前移动
如果是空格则在字符串末尾添加%20三个字符,向前移动三位,字母的指针则向前移动一位
class Solution {public: string replaceSpaces(string S, int length) { int fillIdx = S.size()-1; int i = 0; for ( i = length-1; i >= 0; i--) { if (S[i] == ‘ ‘) { S[fillIdx] = ‘0‘; S[fillIdx - 1] = ‘2‘; S[fillIdx - 2] = ‘%‘; fillIdx -= 3; } else { S[fillIdx] = S[i]; fillIdx--; } } S = S.substr(fillIdx+1); return S; } };
程序员面试金典 <Cracking the Coding Interview> 面试题 01.03. URL化 配图
标签:ima com div ems nbsp lse 算法 ace 试题
原文地址:https://www.cnblogs.com/itdef/p/14459484.html