替换空格

Esay 原题连接：替换空格

请实现一个函数，把字符串 s 中的每个空格替换成”%20”。

示例：

输入：s = "We are happy."
输出："We%20are%20happy."

提示：

  • 0 <= s 的长度 <= 10000

解题思路

将字符对象转变为char[]类型对象，再遍历替换目标子字符串

最后组合成StringBuilder类型返回toString

不过，有现成方法就不用再重复造轮子了，理解万岁

// String中的replace方法
public String replace(char oldChar, char newChar) {
    // 替换前后字符串一致就不用转换了
    if (oldChar != newChar) {
        // 判断对象是否是拉丁文（就是好不好转码）调用不同编码的实现方式做转换
        String ret = isLatin1() ? StringLatin1.replace(value, oldChar, newChar)
                                : StringUTF16.replace(value, oldChar, newChar);
        if (ret != null) {
            return ret;
        }
    }
    return this;
}    

// 这里以StringLatin1的replace作为例子分析
/*  
  String.value属性:  private final byte[] value;
  The value is used for character storage.
*/
  // 参数分别是String的值，需要被替换的值和要用于替换的值
  public static String replace(byte[] value, char oldChar, char newChar) {
        // 判断能不能编码
        if (canEncode(oldChar)) {
            int len = value.length;
            int i = -1;
            // 用于后续判断是否需要进行替换，如果需要替换就找到第一个需要替换的点位
            while (++i < len) {
                if (value[i] == (byte)oldChar) {
                    break;
                }
            }
            // 如果i不小于len 就是字符中没有要被替换的子字符串
            if (i < len) {
                // 用于替换的字符可以正常编码
                if (canEncode(newChar)) {
                    byte[] buf = StringConcatHelper.newArray(len);
                    for (int j = 0; j < i; j++) {    // TBD arraycopy?
                        buf[j] = value[j];
                    }
                    // 替换实现
                    while (i < len) {
                        byte c = value[i];
                        buf[i] = (c == (byte)oldChar) ? (byte)newChar : c;
                        i++;
                    }
                    return new String(buf, LATIN1);
                } else {
                // 用于替换的字符不能正常编码
                    byte[] buf = StringUTF16.newBytesFor(len);
                    // inflate from latin1 to UTF16
                    inflate(value, 0, buf, 0, i);
                    // 替换实现
                    while (i < len) {
                        char c = (char)(value[i] & 0xff);
                        StringUTF16.putChar(buf, i, (c == oldChar) ? newChar : c);
                        i++;
                    }
                    return new String(buf, UTF16);
                }
            }
            // 没有要被替换的子字符，不用做处理
        }
        // 不能编码都是假的，做不了处理
        return null; // for string to return this;
    }

做了操作的部分就是String判断是否可编码，常数级复杂度

Latin1中是否需要替换，O(n)复杂度遍历 + 常熟复杂度判断

遍历替换：O(n)复杂度

以上操作是串行，所以总的来说时间复杂度还是O(n)

Java代码

class Solution {
    public String replaceSpace(String s) {
        return s.replace(" ","%20");
    }
}

左旋转字符串

Easy 原题： 左旋转字符串

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串”abcdefg”和数字2，该函数将返回左旋转两位得到的结果”cdefgab”。

示例：

输入: s = "abcdefg", k = 2
输出: "cdefgab"
    
输入: s = "lrloseumgh", k = 6
输出: "umghlrlose"

提示：

  1. 1 <= k < s.length <= 10000

解题思路

有轮子+1，不过还是读读原码

// String中的subStirng方法
// 殊途同归
public String substring(int beginIndex) {
    return substring(beginIndex, length());
}
public String substring(int beginIndex, int endIndex) {
    int length = length();
    checkBoundsBeginEnd(beginIndex, endIndex, length);
    int subLen = endIndex - beginIndex;
    // 从头返回到尾:不变
    if (beginIndex == 0 && endIndex == length) {
        return this;
    }
    // 符合裁剪要求，判断是否可以编码
    return isLatin1() ? StringLatin1.newString(value, beginIndex, subLen)
                      : StringUTF16.newString(value, beginIndex, subLen);
}

// 这里以StringLatin1的newString作为例子分析
// 额，拼接
public static String newString(byte[] val, int index, int len) {
    return new String(Arrays.copyOfRange(val, index, index + len),
                      LATIN1);
}

Java代码

class Solution {
    public String reverseLeftWords(String s, int n) {
        return s.substring(n)+s.substring(0, n);
    }
}