-
Preface
- FAQ
-
Part I - Basics
- Basics Data Structure
- Basics Sorting
- Basics Algorithm
- Basics Misc
-
Part II - Coding
- String
-
Integer Array
-
Remove Element
-
Zero Sum Subarray
-
Subarray Sum K
-
Subarray Sum Closest
-
Recover Rotated Sorted Array
-
Product of Array Exclude Itself
-
Partition Array
-
First Missing Positive
-
2 Sum
-
3 Sum
-
3 Sum Closest
-
Remove Duplicates from Sorted Array
-
Remove Duplicates from Sorted Array II
-
Merge Sorted Array
-
Merge Sorted Array II
-
Median
-
Partition Array by Odd and Even
-
Kth Largest Element
-
Remove Element
-
Binary Search
-
First Position of Target
-
Search Insert Position
-
Search for a Range
-
First Bad Version
-
Search a 2D Matrix
-
Search a 2D Matrix II
-
Find Peak Element
-
Search in Rotated Sorted Array
-
Search in Rotated Sorted Array II
-
Find Minimum in Rotated Sorted Array
-
Find Minimum in Rotated Sorted Array II
-
Median of two Sorted Arrays
-
Sqrt x
-
Wood Cut
-
First Position of Target
-
Math and Bit Manipulation
-
Single Number
-
Single Number II
-
Single Number III
-
O1 Check Power of 2
-
Convert Integer A to Integer B
-
Factorial Trailing Zeroes
-
Unique Binary Search Trees
-
Update Bits
-
Fast Power
-
Hash Function
-
Happy Number
-
Count 1 in Binary
-
Fibonacci
-
A plus B Problem
-
Print Numbers by Recursion
-
Majority Number
-
Majority Number II
-
Majority Number III
-
Digit Counts
-
Ugly Number
-
Plus One
-
Palindrome Number
-
Task Scheduler
-
Single Number
-
Linked List
-
Remove Duplicates from Sorted List
-
Remove Duplicates from Sorted List II
-
Remove Duplicates from Unsorted List
-
Partition List
-
Add Two Numbers
-
Two Lists Sum Advanced
-
Remove Nth Node From End of List
-
Linked List Cycle
-
Linked List Cycle II
-
Reverse Linked List
-
Reverse Linked List II
-
Merge Two Sorted Lists
-
Merge k Sorted Lists
-
Reorder List
-
Copy List with Random Pointer
-
Sort List
-
Insertion Sort List
-
Palindrome Linked List
-
LRU Cache
-
Rotate List
-
Swap Nodes in Pairs
-
Remove Linked List Elements
-
Remove Duplicates from Sorted List
-
Binary Tree
-
Binary Tree Preorder Traversal
-
Binary Tree Inorder Traversal
-
Binary Tree Postorder Traversal
-
Binary Tree Level Order Traversal
-
Binary Tree Level Order Traversal II
-
Maximum Depth of Binary Tree
-
Balanced Binary Tree
-
Binary Tree Maximum Path Sum
-
Lowest Common Ancestor
-
Invert Binary Tree
-
Diameter of a Binary Tree
-
Construct Binary Tree from Preorder and Inorder Traversal
-
Construct Binary Tree from Inorder and Postorder Traversal
-
Subtree
-
Binary Tree Zigzag Level Order Traversal
-
Binary Tree Serialization
-
Binary Tree Preorder Traversal
- Binary Search Tree
- Exhaustive Search
-
Dynamic Programming
-
Triangle
-
Backpack
-
Backpack II
-
Minimum Path Sum
-
Unique Paths
-
Unique Paths II
-
Climbing Stairs
-
Jump Game
-
Word Break
-
Longest Increasing Subsequence
-
Palindrome Partitioning II
-
Longest Common Subsequence
-
Edit Distance
-
Jump Game II
-
Best Time to Buy and Sell Stock
-
Best Time to Buy and Sell Stock II
-
Best Time to Buy and Sell Stock III
-
Best Time to Buy and Sell Stock IV
-
Distinct Subsequences
-
Interleaving String
-
Maximum Subarray
-
Maximum Subarray II
-
Longest Increasing Continuous subsequence
-
Longest Increasing Continuous subsequence II
-
Maximal Square
-
Triangle
- Graph
- Data Structure
- Big Data
- Problem Misc
-
Part III - Contest
- Google APAC
- Microsoft
- Appendix I Interview and Resume
-
Tags
Space Replacement
Tags: String, Cracking The Coding Interview, Easy
Question
- lintcode: Space Replacement
Problem Statement
Write a method to replace all spaces in a string with %20
. The string is
given in a characters array, you can assume it has enough space for
replacement and you are given the true length of the string.
You code should also return the new length of the string after replacement.
Notice
If you are using Java or Python,please use characters array instead of string.
Example
Given "Mr John Smith"
, length = 13
.
The string after replacement should be "Mr%20John%20Smith"
, you need to
change the string in-place and return the new length 17
.
Challenge
Do it in-place.
题解
根据题意,给定的输入数组长度足够长,将空格替换为%20
后也不会溢出。通常的思维为从前向后遍历,遇到空格即将%20
插入到新数组中,这种方法在生成新数组时很直观,但要求原地替换时就不方便了,这时可联想到插入排序的做法——从后往前遍历,空格处标记下就好了。由于不知道新数组的长度,故首先需要遍历一次原数组,字符串类题中常用方法。
需要注意的是这个题并未说明多个空格如何处理,如果多个连续空格也当做一个空格时稍有不同。
C++
int replaceBlank(char string[], int length) {
int n = 0;
for (int i=0; i<length; i++)
if (string[i] == ' ') n++;
int new_len = length + n*2;
for (int i=length-1; i>=0; i--) {
if (string[i] != ' ') {
string[--new_len] = string[i];
} else {
string[--new_len] = '0';
string[--new_len] = '2';
string[--new_len] = '%';
}
}
return length + n*2;
}
copy
Java
public class Solution {
/**
* @param string: An array of Char
* @param length: The true length of the string
* @return: The true length of new string
*/
public int replaceBlank(char[] string, int length) {
if (string == null) return 0;
int space_cnt = 0;
for (int i = 0; i < length; i++) {
if (string[i] == ' ') {
space_cnt++;
}
}
final int new_length = 2*space_cnt + length;
int right = new_length - 1;
for (int i = length - 1; i >= 0; i--) {
if (string[i] == ' ') {
string[right--] = '0';
string[right--] = '2';
string[right--] = '%';
} else {
string[right--] = string[i];
}
}
return new_length;
}
}
copy
源码分析
先遍历一遍求得空格数,得到『新数组』的实际长度,从后往前遍历。
复杂度分析
遍历两次原数组,时间复杂度近似为 , 使用了right
作为标记,空间复杂度 .