DMOZ中文网站分类目录-免费收录各类优秀网站的中文网站目录.
  • DmozDir.org
DMOZ目录快速登录入口-免费收录各类优秀网站的中文网站目录.由人工编辑,并提供网站分类目录检索及地区分类目录检索,是站长免费推广网站的有力平台!

面试题精选:字符串替换

  • 面试题精选:字符串替换

  • 已被浏览: 26 次2020年09月23日    来源:  https://www.dmozdir.org/
  • 字符串处理在程序猿日常工作工作中非常常见,常见到几乎各种语言中都已经封装好了字符串相关的API,我们只需要直接拿过来用就好。就拿Java为例,jdk中的String()类几乎封装了所有字符串相关的操

    字符串处理在程序猿日常工作工作中非常常见,常见到几乎各种语言中都已经封装好了字符串相关的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)

    欢迎关注我的面试专栏面试题精选,永久免费 持续更新,本专栏会收集我遇到的比较经典面试题,除了提供详尽的解法外还会从面试官的角度提供扩展题,希望能帮助大家找到更好的工作。另外,也征集面试题,如果你遇到了不会的题 私信告诉我,有价值的题我会给你出一篇博客。

    xindoo CSDN认证博客专家 Linux 分布式 Spring 一个有趣有料的程序猿,9年技术博主,曾在阿里做过3年运维相关工作,现为某厂Java后端开发工程师,拥有丰富的挖坑踩坑填坑背锅经验[狗头],专注于Java,对操作系统、网络、编译原理也有涉猎,正在写一门编程语言和一部科幻小说。
    以上信息来源于网络,如有侵权,请联系站长删除。

    TAG:字符串 面试题

  • 上一篇:Python爬虫系列之美团网页美食版块商家数据爬取
  • 与“面试题精选:字符串替换”相关的资讯
  • 2020某医药行业公司面试题
  • 经典算法—BF算法(字符串匹配)
  • LeetCode 767. 重构字符串
  • Qt5字符串编码转换学习
  • 2021年Java高频面试题分享(中高级版):JVM+Redis+Kafka +数据库+设计模式