剑指Offer --- 字符串篇

思路

**(线性扫描) ** O(n)

这个题在C++里比较好做，我们可以从前往后枚举原字符串：

• 1、如果遇到空格，则在string类型的答案中添加 "%20"；
• 2、如果遇到其他字符，则直接将它添加在答案中；

时间复杂度分析: 原字符串只会被遍历常数次，所以总时间复杂度是 O(n).

Java代码

class Solution {public String replaceSpace(String s) {StringBuilder res = new StringBuilder();char[] c = s.toCharArray();for(int i = 0; i < c.length; i ++){if(c[i] == ' ') res.append("%20");else res.append(c[i]);}return res.toString();}
}

思路

(字符串)

具体过程如下：

• 1、记录要转移的字符串str。
• 2、记录不转移的字符串res。
• 3、最后返回拼接到字符串res + str。

Java代码

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

思路
(模拟，字符串处理) O(n)

遍历整个字符串，将所有的不合法情况都去除掉，剩下的就是合法情况。

具体过程如下：

1、首先去除行首和行尾空格，如果去除完之后，整个字符串为空，则返回false。

2、行首如果有一个正负号，直接忽略。

3、如果字符串为空或只有一个'.'，则不是一个合法方案。
4、遍历整个字符串s，对于当前字符s[i]：

• s[i]为数字，则不做任何处理。

• s[i] == '.'，.的个数加1。如果此时'.'在'e'后面出现或者'.'的个数多于1个，则返回false。【1e2.1，1e2.1.1】

• s[i] == 'e' || s[i] == 'E'，e的个数加1。

• • 如果此时'e'的后面为空或者'e'多于1个或者'e'的前面为空或者为'.e'，则返回false。【12e，12e3e，e12，12.e3，.e】
  • 'e'后面紧跟着正负号，但正负号后面为空，则返回false。【1e2+】

• s[i]为其他字符，返回false。

5、排除了各种非法情况，此时s则为合法方案，我们返回true。

Java代码

class Solution {public boolean isNumber(String s) {if(s == null || s.length() <= 0){return false;}char[] res = s.trim().toCharArray();if(res.length <= 0) return false;int n = res.length;boolean is_dot = false;boolean is_e_or_E = false;boolean is_num = false;for(int i = 0; i < n; i++){if(res[i] >= '0' && res[i] <= '9'){is_num = true;} else if(res[i] == '.'){//-+ 8.  8.8  .8// 前面：不能有重复的小数点，也不能出现 e/Eif(is_dot || is_e_or_E){return false;}is_dot = true;} else if(res[i] == 'e' || res[i] == 'E'){// 前面必须要有一个数字 || 前面不能出现重复的 e/Eif(is_e_or_E || !is_num){return false;}is_e_or_E = true;is_num =false;//11E+ 11E} else if(res[i] == '-' || res[i] == '+'){if(i!=0 && res[i-1] != 'e' && res[i-1] != 'E'){return false;}} else {return false;}}return is_num;}
}

思路

(模拟) O(n)

先来看看题目的要求：

• 1、忽略所有行首空格，找到第一个非空格字符，可以是 ‘+/−’表示是正数或者负数，紧随其后找到最长的一串连续数字，将其解析成一个整数。
• 2、整数后可能有任意非数字字符，请将其忽略。
• 3、如果整数大于INT_MAX，请返回INT_MAX；如果整数小于INT_MIN，请返回INT_MIN；

具体过程：

• 1、定义k = 0，用k来找到第一个非空字符位置。

• 2、使用flag记录数字的正负性，false表示正号，true表示负号。

• 3、使用res来存贮结果，当str[k]为数字字符时进入while循环，执行res = res * 10 +str[k] - '0'。

• • 根据flag判断，如果res大于INT_MAX，则返回INT_MAX；如果res * -1小于INT_MIN，则返回INT_MIN；

• 4、计算res。

**时间复杂度分析：**字符串长度是 n，每个字符最多遍历一次，所以总时间复杂度是O(n)。

Java代码

class Solution {public int strToInt(String str) {int res = 0, bndry = Integer.MAX_VALUE / 10;int i = 0, sign = 1, length = str.length();if(length == 0) return 0;while(str.charAt(i) == ' ')if(++i == length) return 0;if(str.charAt(i) == '-') sign = -1;if(str.charAt(i) == '-' || str.charAt(i) == '+') i++;for(int j = i; j < length; j++) {if(str.charAt(j) < '0' || str.charAt(j) > '9') break;if(res > bndry || res == bndry && str.charAt(j) > '7')return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;res = res * 10 + (str.charAt(j) - '0');}return sign * res;}
}