【必备算法】字符串（基础问题）：LeetCode题 709. 转换成小写字母，8. 字符串转换整数 (atoi)

709. 转换成小写字母¹

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

示例 1：

输入: "Hello"
输出: "hello"

示例 2：

输入: "here"
输出: "here"

示例 3：

输入: "LOVELY"
输出: "lovely"

解法：ASCII码

• 思路：大写字母转小写直接ASCII+32
• 复杂度：
  • Time：O(n)
  • Space：O(1)

public String toLowerCase(String str) {
        if (str.length() == 0) return "";
		// 由于字符串是不变的，因此新建一个数组来存
    	// 注：这里可以直接新建一个数组，但是toCharArray就只用修改大写字母的地方
        char[] c = str.toCharArray();
        for (int i = 0; i < str.length(); i++) {
            // 判断哪个是大写字母
            // 注：这里不用记具体ASCII值，只要char进行比较就是用ASCII了
            if (str.charAt(i) >= 'A' && str.charAt(i) <= 'Z') 
                c[i] = (char)(str.charAt(i) + 32);
            else 
                c[i] = str.charAt(i);
        }
    	// 将char[]转String，也可以直接new String
        return String.valueOf(c);
    }

8. 字符串转换整数 (atoi)²

请你来实现一个 atoi 函数，使其能将字符串转换成整数。

首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。接下来的转化规则如下：

• 如果第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字字符组合起来，形成一个有符号整数。
• 假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成一个整数。
• 该字符串在有效的整数部分之后也可能会存在多余的字符，那么这些字符可以被忽略，它们对函数不应该造成影响。

注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换，即无法进行有效转换。

在任何情况下，若函数不能进行有效的转换时，请返回 0 。

提示：

• 本题中的空白字符只包括空格字符 ' ' 。
• 假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。

示例 1:

输入: "42"
输出: 42

示例 2:

输入: "   -42"
输出: -42
解释: 第一个非空白字符为 '-', 它是一个负号。
     我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。

示例 3:

输入: "4193 with words"
输出: 4193
解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。

示例 4:

输入: "words and 987"
输出: 0
解释: 第一个非空字符是 'w', 但它不是数字或正、负号。
     因此无法执行有效的转换。

示例 5:

输入: "-91283472332"
输出: -2147483648
解释: 数字 "-91283472332" 超过 32 位有符号整数范围。 
     因此返回 INT_MIN (−231) 。

解法：ASCII

• 思路：本题就是根据要求一点一点判断，没什么要说的地方，就是细节。从字符转化为数字：c-‘0’。步骤见注释。
• 复杂度
  • Time：O(n)
  • Space：O(1)

public int myAtoi(String str) {
        int start = 0, i = 0, n = str.length();
        boolean negative = false;
    	// 1.寻找start位置
    	// 1.1 去处空格
        while (i < n && str.charAt(i) == ' ') i++;
        if (i == n) return 0;
	    // 1.2 正负判断
        if (str.charAt(i) == '+') {
            i++;
        } else if (str.charAt(i) == '-') {
            i++;
            negative = true;
        }
        // 1.3 去除前置0
        while (i < n && str.charAt(i) == '0') i++;
        start = i;
    
		// 2.寻找end位置
        // 2.1 寻找 '0' - '9'，这里就去除了示例3情况
        while (i < n && str.charAt(i) >= '0' && str.charAt(i) <= '9') i++;
        if (start == i) return 0;
		// 2.2 越界判断，位数大于10一定越界
        if (i - start > 10) {
            if (negative) return Integer.MIN_VALUE;
            else return Integer.MAX_VALUE;
        }
		
    	// 3.字符串转换
    	// 注：这里先用long，是因为可能转出来的数越界了如999999999
        long res = 0;
    	// 3.1 进行转换：得到每一位数字(charAt(i) - '0')。核心一步！！！
    	// 注：是从最高位开始转换的，因此res * 10
        for (int j = start; j < i; j++) 
            res = res * 10 + (str.charAt(j) - '0');
    	// 3.2 正负判断
        res = negative ? -res : res;
		// 3.3 越界判断
        if (res < Integer.MIN_VALUE) return Integer.MIN_VALUE;
        else if (res > Integer.MAX_VALUE) return Integer.MAX_VALUE;
    	// 注：这里要转回int
        else return (int) res;
    }