乐趣区

关于java:面试题精选字符串替换

字符串解决在程序猿日常工作工作中十分常见,常见到简直各种语言中都曾经封装好了字符串相干的 API,咱们只须要间接拿过去用就好。就拿 Java 为例,jdk 中的 String()类简直封装了所有字符串相干的操作,其办法数量有近百个,简直满足了程序猿所有字符串相干的操作。

正是因为这么不便,预计大多数 Java 程序猿都没本人实现过字符串的 replace。这里正式引入一下明天的精选面试题:不依赖第三方库 实现一个字符串替换 replace(String str, String target, String replacement) 函数,其性能是将 str 中所有的 target 替换为 replacement。其实这道题并不波及任何简单或者浅近的算法,只须要把握根本的编程就能够做,但当我某次把这道题拿进去面试某个应届生时,他代码写的磕磕绊绊的,起初我也陆陆续续用这题考过好几个人,鲜有顺畅写进去的,是我低估了这道题的难度??

解题思路

回到题目自身,我多说两句,认真想想这道题其实也很简略,然而这就难倒了一大批人,大家刷面试题前还是要先打好编程根底。这题的解题思路也很简略,咱们新建个 StringBuilder,只须要把 str 中不是 target 的局部加进去,如果是遇到 target,就把 replacement 字符串加进去,真的没有任何简单的算法 就是单纯考你编程的基本功,代码如下。

    public static String replace(String str, String target, String replacement) {
        // 失常这里须要对 str,target,replacement 做输出校验,这里我省略,比方 str 比 target 端的时候能够间接返回空字符串  
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < str.length(); ) {if (isMatch(str, i, target)) {i += target.length();  // 如果匹配,须要间接向前跳 target.length  
                res.append(replacement);
                continue;
            }
            res.append(str.charAt(i++));
        }
        return res.toString();}

    // 单纯确认从 str 的 pos 地位开始,是否和 target 相匹配  
    private static boolean isMatch(String str, int pos, String target) {for (int i = 0; i < target.length() && i + pos < str.length(); i++) {if (str.charAt(i + pos) != target.charAt(i)) {return false;}
        }
        return true;
    }

看吧,代码其实没啥难度,但咋就好多显著刷过其余面试题的人都不会呢!!!

Jdk 中的 replace 实现

预计大多数人都没看过 Jdk 中的实现,所以顺带咱们来观赏下 java String 类中的 replace 办法是如何实现的。

    public String replace(CharSequence target, CharSequence replacement) {String tgtStr = target.toString();
        String replStr = replacement.toString();
        int j = indexOf(tgtStr);
        if (j < 0) {return this;}
        int tgtLen = tgtStr.length();
        int tgtLen1 = Math.max(tgtLen, 1);
        int thisLen = length();

        int newLenHint = thisLen - tgtLen + replStr.length();
        if (newLenHint < 0) {throw new OutOfMemoryError();
        }
        StringBuilder sb = new StringBuilder(newLenHint);
        int i = 0;
        do {sb.append(this, i, j).append(replStr);   // 先把未匹配字符增加进去,而后间接增加 replStr  
            i = j + tgtLen;
        } while (j < thisLen && (j = indexOf(tgtStr, j + tgtLen1)) > 0);  // 找到下一个匹配的下标 
        return sb.append(this, i, thisLen).toString();}

jdk 中的思路和咱们下面写的思路是统一的,但 jdk 的代码更为精简,其实 jdk 也没用啥浅近的货色,只是在 indexOf()中思考了更多数据编码的问题。

题目扩大

别看这道题简略,其实它也有好多能够扩大的中央,我来轻易扩几个供大家参考下。

  1. Java 中字符解决必定免不了 String StringBuffer 和 StringBuilder,都有啥区别?
  2. 之前老程序猿不举荐应用 str = str + “xx” 的形式拼接字符串, 为什么?而当初其实大多数状况下用 StringBuilder.append 和 + 拼接字符串就没那么多差别了? (提醒:高版本的 java 对 + 的字符串拼接形式有优化)!
  3. 上文中咱们用到了字符串匹配的形式,咱们用的是最一般的匹配工夫复杂度最差是 O(mn),应用其余的匹配算法能够大幅晋升性能,你都晓得有哪些字符串匹配算法?(比方大家最耳熟能详的就是 KMP)

欢送关注我的面试专栏面试题精选,永恒收费 继续更新,本专栏会收集我遇到的比拟经典面试题,除了提供详尽的解法外还会从面试官的角度提供扩大题,心愿能帮忙大家找到更好的工作。另外,也征集面试题,如果你遇到了不会的题 私信通知我,有价值的题我会给你出一篇博客。

退出移动版