窗外的大厦, 桌子上的水杯, 手中的笔.
面试官:"先来一点基础的吧, 用 Java 写一个方法, 入参是一个字符串, 返回逆序后的字符串."
我暗想确实很基础, 于是便写下:
- public static String reverse(String str) {
- StringBuffer sb = new StringBuffer(str);
- return sb.reverse().toString();
- }
面试官看了看, 说:"写的很好, 用 StringBuffer 的 reverse 方法. 如果你来实现其中算法, 你会怎么写?"
我直接说:"从最后一个字符开始, 一直向前添加字符就可以了." 重新写了一个遍代码:
- public static String reverse(String str) {
- char[] chars = str.toCharArray();
- StringBuilder sb = new StringBuilder();
- for (int i = chars.length - 1; i>= 0; i--) {
- sb.append(chars[i]);
- }
- return sb.toString();
- }
面试官看了看, 说:"写的很好, 逆序的功能完成了. 不过再想想, 有什么可以优化的地方?"
我想了想, 说:"好像没有什么可以优化的?"
面试官提示了一句:"比如, 采用首尾替换的方式呢? 是不是可以减少时间复杂度?"
我恍然大悟, 说:"的确是, 我再改一下." 又重新写了一个遍代码:
- public static String reverse(String str) {
- char[] chars = str.toCharArray();
- int n = chars.length - 1;
- for (int i = 0; i <= n / 2; i++) {
- int j = n - i;
- char temp = chars[i];
- chars[i] = chars[j];
- chars[j] = temp;
- }
- return new String(chars);
- }
- "第一, for 循环的布尔表达式里不应该放除 2 的计算, 否则每次循环都会计算一次."
- "第二, 除 2 的计算可以用右移一位代替, 这样效率更高."
- public static String reverse(String str) {
- char[] chars = str.toCharArray();
- int n = chars.length - 1;
- for (int i = (n - 1)>> 1; i>= 0; i--) {
- int j = n - i;
- char temp = chars[i];
- chars[i] = chars[j];
- chars[j] = temp;
- }
- return new String(chars);
- }
来源: https://www.cnblogs.com/heihaozi/p/11904145.html