面试必备：高频算法题汇总「图文解析 + 教学视频 + 范例代码」之 字符串处理+动态规划 汇总！ (2)

将拆分后的字符串倒序插入数组中即可

public String reverseWords(String s) { if(s.length() == 0 || s == null){ return " "; } //按照空格将s切分 String[] array = s.split(" "); StringBuilder sb = new StringBuilder(); //从后往前遍历array，在sb中插入单词 for(int i = array.length - 1; i >= 0; i--){ if(!array[i].equals("")) { // 为防止字符串首多一个 “ ” 判断当前是不是空字符串 // 是字符串第一个就不输出空格 if (sb.length() > 0) { sb.append(" "); } sb.append(array[i]); } } return sb.toString(); }

字符串转换整数 (atoi)

实现atoi这个函数，将一个字符串转换为整数。如果没有合法的整数，返回0。如果整数超出了32位整数的范围，返回 INT_MAX(2147483647) 如果是正整数，或者 INT_MIN(-2147483648) 如果是负整数。

示例 :

输入: "4193 with words" 输出: 4193 解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。 示例 4: 输入: "words and 987" 输出: 0 解释: 第一个非空字符是 'w', 但它不是数字或正、负号。 因此无法执行有效的转换。 解题思路

首先我们要知道该数正负

根据题意调用 trim() 去掉空格

去完多余空格之后，首位有三种情况 ‘+’ ‘-’ 其他

设一个 falg 叫做 sign 默认值为一，如果监测到 ‘-’ 则设为 -1

这样一来后面求出的结果乘以 sigh 就能带上正负值

在定义一个 num 值用于保存答案数值

for 循环从头到尾访问字符串

先判断当前位是否为数字，这时分两种情况

如果字符串首位就不是数字和 -+ 号，根据题意直接退出循环

如果为数字就将 sum 的值 *10 倍，再将其加入 sum 中

如果值超过 MAX_VALUE 跳出循环

对应 *sigh 输出正负值，或者 MAX_VALUE 或 MIN_VALUE 即可

视频

视频讲解和源码-字符串转换整数

public int myAtoi(String str) { if(str == null) { return 0; } str = str.trim(); if (str.length() == 0) { return 0; } int sign = 1; int index = 0; if (str.charAt(index) == '+') { index++; } else if (str.charAt(index) == '-') { sign = -1; index++; } long num = 0; for (; index < str.length(); index++) { if (str.charAt(index) < '0' || str.charAt(index) > '9') { break; } num = num * 10 + (str.charAt(index) - '0'); if (num > Integer.MAX_VALUE ) { break; } } if (num * sign >= Integer.MAX_VALUE) { return Integer.MAX_VALUE; } if (num * sign <= Integer.MIN_VALUE) { return Integer.MIN_VALUE; } return (int)num * sign; }

注：trim() 函数是去掉String字符串的首尾空格;

最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

示例 :

输入: ["flower","flow","flight"] 输出: "fl" 解题思路

标签：链表
当字符串数组长度为 0 时则公共前缀为空，直接返回
令最长公共前缀 ans 的值为第一个字符串，进行初始化
遍历后面的字符串，依次将其与 ans 进行比较，两两找出公共前缀，最终结果即为最长公共前缀
如果查找过程中出现了 ans 为空的情况，则公共前缀不存在直接返回
s 为所有字符串的长度之和

视频

最长公共前缀

public String longestCommonPrefix(String[] strs) { if (strs == null || strs.length == 0) { return ""; } String prefix = strs[0]; for(int i = 1; i < strs.length; i++) { int j = 0; while (j < strs[i].length() && j < prefix.length() && strs[i].charAt(j) == prefix.charAt(j)) { j++; } if( j == 0) { return ""; } prefix = prefix.substring(0, j); } return prefix; } 时间复杂度：

\(O(s)\)

回文数

判断一个正整数是不是回文数。回文数的定义是，将这个数反转之后，得到的数仍然是同一个数。

示例 :

输入: 121 输出: true 解题思路

通过取整和取余操作获取整数中对应的数字进行比较。

举个例子：1221 这个数字。

通过计算 1221 / 1000， 得首位1
通过计算 1221 % 10， 可得末位 1
进行比较
再将 22 取出来继续比较

视频