Cracking Coding Interview - 1.3 URLify

2019-08-07 2 分钟阅读 ARTS-A

URLify: Write a method to replace all spaces in a string with ‘%20’. You may assume that the string has sufficient space at the end to hold the additional characters,and that you are given the “true” length of the string. (Note: If implementing in Java,please use a character array so that you can perform this operation in place.)

例子：

1
2

Input:  "Mr John Smith    ", 13
Output: "Mr%20John%20Smith"

基本判断

题目里说了，给的char[]有足够的空间容纳增加的%20，并且还会给出字符串的true length，那么也就是说如果true length == char[]的length，那么就说明没有空格，直接返回就是了。

弄个新数组

弄个新数组，都是空的，遍历旧数组，遇到空格就追加%20，其他的字符就直接追加。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

public char[] urlify(char[] url, int trueLength) {
  if (url.length == trueLength) {
    return url;
  }
  char[] res = new char[url.length];
  int j = 0;
  for(int i = 0; i < trueLength; i++) {
    if (url[i] != ' ') {
      res[j++] = url[i];
    } else {
      res[j++] = '%';
      res[j++] = '2';
      res[j++] = '0';
    }
  }
  return res;
}

时间复杂度：O(n)，n=true length

空间复杂度：O(n)

In place操作

题目里说了，给的char[]有足够的空间容纳增加的%20，如果这个足够的空间不多不少正正好好，那么我们可以利用这一点直接在char[]里操作，我们从字符串true length的末尾开始，把字符都丢到屁股后面去，遇到空格就丢%20。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

public void urlify(char[] url, int trueLength) {
  if (url.length == trueLength) {
    return url;
  }
  int j = url.length - 1;
  for(int i = trueLength - 1; i >= 0; i--) {
    char c = url[i];
    if (c != ' ') {
      url[j--] = c;
    } else {
      url[j--] = '0';
      url[j--] = '2';
      url[j--] = '%';
    }
  }
  return url;
}

时间复杂度：O(n)，n=true length

空间复杂度：O(1)

Cracking Coding Interview - 1.2 Check Permutation
Cracking Coding Interview - 1.4 Palindrome Permutation

版权

CC BY-NC-ND 4.0

相关文章

评论