[LeetCode] 709. To Lower Case

发表于 Disqus：

LeetCode 709. To Lower Case (转换成小写字母) Diffculty: Eazy

Question

Implement function ToLowerCase() that has a string parameter str, and returns the same string in lowercase.

实现函数 ToLowerCase()，该函数接收一个字符串参数 str，并将该字符串中的大写字母转换成小写字母，之后返回新的字符串。

Example

Example 1

1
2
Input: "Hello"
Output: "hello"

Example 2

1
2
Input: "here"
Output: "here"

Example 3

1
2
Input: "LOVELY"
Output: "lovely"

Solution

Java

My Solution 1

解题思路

已知 String 实际是 char 类型的字符序列，即可将 String 转换为 char[]。题目在于将大写字母转换为小写字母，已知 char 这个字符类型，实际是存的 int，只是通过 ASCII 编码，映射了数字和字符的关系。使用 char 类型，可以数字与字符相互转换，只要找到大写字母与小写字母对应数字之间的关系即可解决该问题。转大写时，同理。

获取大小写字母映射数字的关系，可以通过查询 ASCII 编码表或以下代码：

1
2
3
4
5
6
7
8
9
10
char A = 'A';
System.out.println((int) A); // or "A - 0" = 65
char Z = 'Z';
System.out.println((int) Z); // or "Z - 0" = 90
char a = 'a';
System.out.println((int) a); // or "a - 0" = 97
char z = 'z';
System.out.println((int) z); // or "z - 0" = 122
System.out.println(a - A);   // = 32
System.out.println(z - Z);   // = 32

即：

  • A - Z 的范围： [65, 90]
  • a - z 的范围： [97, 122]
  • A 与 a 之间相差了 32
  • Z 与 z 之间相差了 32
解题步骤
  1. 定义输出变量（StringBuilder） -> result
  2. 字符串 str 转字符数组，循环字符数组 -> s
    1. 定义临时变量 char a, a = s
    2. 判断 a 是否是大写字母，即 a > 64 && a < 91，如是，则 a += 32，如否，则不变
    3. 将 a 加到 result 中
  3. 循环结束后，返回结果变量 -> result.toString()
Code
初版
1
2
3
4
5
6
7
8
9
10
11
public String toLowerCase(String str) {
    StringBuilder result = new StringBuilder();
    for (char s : str.toCharArray()) {
        char a = s;
        if (a > 64 && a < 91) {
            a += 32;
        }
        result.append(a);
    }
    return result.toString();
}
优化版

参考 LeetCode Discuss Solution 1 后：

1
2
3
4
5
6
7
public String toLowerCase(String str) {
    char[] s = str.toCharArray();
    for (int i = 0; i < s.length; i++) {
        s[i] = (char) (str.charAt(i) | (char) (32));
    }
    return new String(s);
}
Complexity Analysis
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(n)$

LeetCode Discuss Solution 1

Code
Code 1 @climberig
1
2
3
4
5
6
7
public String toLowerCase(String str) {
    char[] a = str.toCharArray();
    for (int i = 0; i < a.length; i++)
        if ('A' <= a[i] && a[i] <= 'Z')
            a[i] = (char) (a[i] - 'A' + 'a');
    return new String(a);
}
Code 2 @kevlar_ksb
1
2
3
4
5
6
7
8
public String toLowerCase(String str) {
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < str.length(); i++) {
        char c = (char) (str.charAt(i) | (char) (32));
        sb.append(c);
    }
    return sb.toString();
}
Complexity Analysis
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(n)$
解题思路

与我的解决思路差不多。

需要特别说明的是 Code 2 中，char c = (char) (str.charAt(i) | (char) (32));。

| 是按位或运算符，其功能是参与运算的两数各对应的二进位相或。只要对应的二个二进位有一个为 1 时，结果位就为 1。

可以通过以下代码看出计算过程：

1
2
3
4
5
6
7
8
9
System.out.println(Integer.toBinaryString('A'));       // 65 = 01000001
System.out.println(Integer.toBinaryString(32));        // 32 = 00100000
System.out.println(Integer.toBinaryString('A' | 32));  // 97 = 01100001
System.out.println(Integer.toBinaryString('a'));       // 97 = 01100001

System.out.println(Integer.toBinaryString('B'));       // 66 = 01000010
System.out.println(Integer.toBinaryString(32));        // 32 = 00100000
System.out.println(Integer.toBinaryString('B' | 32));  // 98 = 01100010
System.out.println(Integer.toBinaryString('b'));       // 98 = 01100010

这样一看 32 就显的很特别，这个 A 和 a 之间相差 32 是有原因的：

1
2
3
4
5
6
7
8
9
10
11
A = 65  = 01000001
a = 97  = 01100001

B = 66  = 01000010
b = 98  = 01100010
...
Y = 89  = 01011001
y = 121 = 01111001

Z = 90  = 01011010
z = 122 = 01111010

从上面的等式可以看出，大写与小写之间只有第 6 位是不同的（大写是 0，小写是 1）

而 32 = $2^5$ = 00100000

这时再回来看，'A' | 32，就很明显了，因为大小写之间的二进制位只有第 6 位是不同的。

通过按位或操作，原来位上是 1 的，按位或后还是 1，原来位上是 0 的，按位或后还是 0。

只有第 6 位，原来位上是 0，按位或后变为 1。就相当于 +32。

顺便一提，虽然 'A' | 32 相当于 'A' + 32，但实际上 | 和 + 还是有区别的。
再顺便一提，64 = $2^6$ = 01000000，因为大小写字母都大于 64，所以第 7 位都是 1。

Summary

我看到 LeetCode 上有逗比，在写 return str.toLowerCase() 之类的，直接调用提供的 API，确实是一行就写完了。但是这个算法题就没有意义了。

倒是提醒了我，顺便去看了看 Java 的 java.lang.String#toLowerCase() 的实现。

是通过 Unicode 去转换的，而且还涉及到不同的区域设置的大小写转换规则，

大致逻辑如下：

  1. 先获取字符串中的第一个需要转小写的字符的索引（firstUpper），如果没有，当然就不会继续再执行了，直接 return this;
  2. 然后将第一个需要转小写的字符索引之前的部分复制到 char[] result 中
  3. 再从 firstUpper 开始循环检查，并按转换规则，将大写字母转换为小写字母，最后赋值到对应的 result 的索引中

中间涉及的转换规则，边界检查那一大堆又是另外一回事了。

最近做的这几道题都涉及到位运算。平时用的很少，脑子转不过弯来，不是看别人的代码都想不起来还可以这么玩。抽空还是深入学习一下，写写关于位运算的好了。

References