算法通过村第十二关-字符串|青铜笔记|隐形的王者

---

前言

---

提示：为别人而活着，其实是最简单的一种活法。 --蔡崇达《命运》

字符串本身并不是一种数据结构，但是由于其本身的特殊性，额可以产生很多特殊的算法问题。另外，字符串在工程里也有非常广泛的应用。因此字符串在学习算法中是不可忽视的，属于是隐形的王者，一直以来也都是算法考察的重点问题之一，当然也是我们研究对象的重点。

字符串本身并不是一种数据结构，但是由于其本身的特殊性，可以产生一些特定的算法题目，而C、C++和Java等语言创建和管理字符串的方式也有差异，因此针对语言特征又会产生很多问题，这些问题也是算法中需要注意的，避坑。（这些也是常考的，技术面也长存在）在链表、数组等结构中，元素之间没有语义的关联的，但是字符串则不同，前后几个字母组合在一起就是一个单词，这个时候，我们就可以从一个单词，字母的角度等组合出很多花样，这也是为什么字符串问题之多的原因之一。

字符串里存放的可以是字母，也可以是数组，甚至是一些特殊符号，字母又可以分为大写和小写。这就会导致字符串的一类常见问题：转换问题。这些题目无非就是这几种类型之间相互转换。但是在转换的过程中需要处理几种特殊的情况：例如首先就是转之前判断当前元素能不能转。如果是字符串转数字，则要考虑当前元素是不是数字。转完之后会不会溢出等。问题本身并不复杂，但是需要考虑周全，如果考虑不周全的话，面试的时候的会被扣分。我们先看看下面的一些题目热手：

转换成小写字母

参考题目介绍：709. 转换成小写字母 - 力扣（LeetCode）

我们直到每个字母都是有确定的ASCII的，因此我们可以根据ASCII码表操作字符串即可：

找来了一张图片：ASCII码对应表，ASCII码值的大小顺序 (zhihu.com)

这里主要记住常用的字母和数字：

• 0-9 48-57
• A-Z 65-90
• a-z 97-122

也就是常说的486597(597-486 = 111)

这个题目就是先遍历整个字符串，然后对每一位字符串作判断，如果str[i]在A-Z之间的后，则需要在原先的基础上ASCII加上32 即可转换成对应的小写啦：

	 /**
         * 大写字母转小写字母
         * @param s
         * @return
         */
    public static String toLowerCase(String s) {
        int n = s.length();
        // 获取chars数组操作
        char[] chars = s.toCharArray();
        for (int i = 0; i < n; i++) {
            if (chars[i] >= 65 && chars[i] <= 90) {
                chars[i] += 32;
            }
        }
        return new String(chars);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

字符串转换整数

这个题目主要考虑到转出数字的时候溢出的问题，我们会在后面继续讨论，先小试牛刀一下。

参考题目地址：8. 字符串转换整数 (atoi) - 力扣（LeetCode）

很多时候，需要考虑的是问题的分析能力。这道题目很长，给的实例也很多，当然这些要求也是我们必须要知道的。写代码的时候必须要考虑的。面试官也不会告诉你，如果你写代码不周，他可能提醒你，错不过三，不然后面你就废了。

题目最好需要用什么高级特性，就是最近本的写法。这里没有考察算法的知识，更多的是开发种对数据的处理问题（你要明确面试官在考察什么）【如参数校验等】。如果面试中遇到了，应该仔细阅读题目字说明，认真分析，可能存在的情况，有疑问即使和面试官确认，千万别阴沟翻船。

这里面我们罗列一些要点：

• 需要去掉前导 空格；
• 需要首先判断第一个字符是 + -的情况，因此需要设计一个变量sign，初始化的时候是1，如果遇到- ，将sign需要改为-1
• 判断是否位数字，可以使用ASCII码值，进行比较，即 “0” <= c <= “9”,如果0在最前面，则应该去掉；
• 如果第1个不是数字的字符时就停止，退出循环。
• 如果转换以后数字超过int类型的范围，需要截取不能将res变量设置为long类型，注意：由于输入字符串转换以后可能超过long类型，因此需要在循环内部就判断时候越界如果越界就直接退出，这样也可以不必继续计算了。
• 由于涉及下标的访问，因此全程需要考虑数组是否越界的情况。

特别注意：

1. 由于题目中说【环境只能保存32位整数】，因此这里再每一轮循环之前需要先检查，具体看代码
2. Java、Python和c++字符串的是设计都是不可边的，即使用trim()会产生新的变量，因此我们尽量不要使用库函数，使用一个变量index取遍历，这样遍历完成以后就可以转换以后的数值。

   /**
         * 字符串转整数 
         * @param str
         * @return
         */
    public static int myAtoi(String str) {
        int n = str.length();
        char[] chars = str.toCharArray();
        // 1.取出前导“ ”
        int index = 0;
        while(index < n && chars[index] == ' '){
            index++;
        }
        // 2.当然需要排除极端情况（全空）
        if (index == n){
            return 0;
        }
        // 3.如果出现符号字符，仅第1个有效，并记录正负值
        int sign = 1;
        char firstChar = chars[index];
        if (firstChar == '+'){
            index++;
        }else if(firstChar == '-'){
            index ++;
            sign = -1;
        }
        // 4.将后续出现的数字字符进行转换
        // 当然使用long是不行的，这丫是题目说的
        int res = 0;
        while(index < n){
            char currentChar = chars[index];
            // 4.1 先判断是否合法
            if (currentChar < '0' || currentChar > '9'){
                break;
            }
            // 题目中说只能存储32位大小的有符号整数 下面的两个if需要分别处理整数和负数情况
            // 前提是乘以10以后是否越界，但是res*10可能会越界，所以这里需要特殊处理,使用Integer.MAX_VALUE / 10，这样才不会越界。
            // 这里有经典处理溢出的问题
            if (res > Integer.MAX_VALUE /10 || (res == Integer.MAX_VALUE / 10 && (currentChar - '0') >Integer.MAX_VALUE % 10)){
                return Integer.MAX_VALUE;
            }
            if (res < Integer.MIN_VALUE / 10 || (res == Integer.MIN_VALUE / 10 && (currentChar - '0') > -(Integer.MIN_VALUE % 10))){
                return Integer.MIN_VALUE;
            }
            // 合法的情况下，才考虑率转换，每一步都把符号位乘进入
            // 想想这里为什么要带sign作乘法呢
            res = res * 10 + sign * (currentChar - '0');
            index++;
        }
        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

上面这个实现确实能解决问题，但是太长了，但是太长了，我们可以使用JDK自带的库函数来简化都分操作，例如这里去掉前导空格，我们就可以使用trim。

---

总结

提示：字符串问题；字符串转换；字符串转整数；字符串转整数溢出问题；字符串特殊值

---

如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ ("▔□▔)/

如有不理解的地方，欢迎你在评论区给我留言，我都会逐一回复 ~

也欢迎你 关注我 ，喜欢交朋友，喜欢一起探讨问题。