剑指offer系列之二:字符串空格替换

题目描述:
请实现一个函数,将一个字符串中的空格替换成”%20”。例如,当字符串为We Are Happy,则经过替换之后的字符串为We%20Are%20Happy。

看到这题,我的第一思路是这样的:一组单词不是有空格嘛,所以直接使用String类的split函数直接分割为char数组不就好了,不过在这之前需要判断一下第一个位置和最后一个位置是否有空格,然后针对空格的出现情况再进行替换。发现OJ的时候,如你所猜,自然是失败的。因为我忽略一个问题,就是如果一个句子中都是空格,调用split函数之后会发生什么,会是一组空串。那么根据题目要求,应该全部替换成%20才对。所以这种思路被毙掉了。

于是,我寻找下一种思路,联想到从尾部循环替换的思想(在冒泡排序算法之中也是从尾部往前进行比较然后交换的),于是形成如下的思路:首先统计出该字符串中所有的空格数量,并重新计算新串所需的char数组的长度,把旧串转化成的char数组拷贝到一个临时数组中,并同时创建一个新的char数组,该新数组的长度是计算之后的长度。从该新数组的尾部开始循环,依次往前比较,只要遇到了空格就替换为%20。如果没有遇到空格就直接复制过来就行。

OK,基于以上思路,我写出了如下的代码(已被牛客OJ平台AC了):

package com.rhwayfun.offer;

/**
 * 题目描述
 *
 * 请实现一个函数,将一个字符串中的空格替换成“%20”。 例如,当字符串为We Are Happy.则经过替换之后的
 * 字符串为We%20Are%20Happy。
 *
 * @author Administrator
 *
 */
public class ReplaceSpace {
    public String replaceSpace(StringBuffer str) {
        String s = str.toString();
        //统计空格数
        int count = getBlankNum(str.toString());
        //获取原来字符串的长度
        int originalStrLen = s.toCharArray().length;
        //计算替换空格之后需要的长度
        int newStrLen = count * 2 + originalStrLen;
        char[] tempArray = new char[newStrLen];
        //把原字符串复制到tempArray数组中
        System.arraycopy(s.toCharArray(), 0, tempArray, 0, originalStrLen);
        int originalStrIndex = originalStrLen - 1;
        int newStrIndex = newStrLen -1;
        //当originalStrIndex == newStrIndex的时候替换完毕
        while(originalStrIndex >= 0 && originalStrIndex != newStrIndex){
            if(tempArray[originalStrIndex] == ' '){
                tempArray[newStrIndex--] = '0';
                tempArray[newStrIndex--] = '2';
                tempArray[newStrIndex--] = '%';
            }else{
                tempArray[newStrIndex--] = tempArray[originalStrIndex];
            }
            originalStrIndex--;
        }
        return new String(tempArray);
    }

    /**
     * 计算空格数
     * @param string
     * @return
     */
    private int getBlankNum(String string) {
        int count = 0;
        for (int i = 0; i < string.length(); i++) {
            if(string.charAt(i) == ' '){
                count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        String s = new ReplaceSpace().replaceSpace(new StringBuffer(""));
        System.out.println(s);
    }
}

由于只有一层循环,加上统计空格的时间开销,就是两个循环的时间开销,其他的操作都是O(1)的时间复杂度。所以该算法综合起来的时间复杂度是O(n)。

时间: 2024-10-31 15:05:23

剑指offer系列之二:字符串空格替换的相关文章

剑指offer系列之二十六:输出字符串的全排列

题目描述 输入一个字符串,按字典序打印出该字符串中字符的所有排列.例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba. 结果请按字母顺序输出. 输入描述: 输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母. 此题与剑指offer原题存在一些初入,在原题中并没有规定字符串中字符是否有重复的出现.不过思路是一致的,只不过是添加额外的判断罢了.下面说说我的思路吧:先不考虑是否出现重读字符,要对一个字符进行全排列,可以

剑指offer系列之二十五:二叉搜索树与双向链表

题目描述 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表.要求不能创建任何新的结点,只能调整树中结点指针的指向. 由于二叉搜索树的中序遍历就是排序的,如果是构造单链表,只需要一次中序遍历就可以了,但现在需要构造双链表,也就是在中序遍历的过程中需要设置每个节点的left与right指针,现在问题是如何设置这两个指针?二叉搜索树有一个特点,就是根节点的左子树上所有节点都比根节点的值小,而右子树上的所有节点的值都比根节点的值大,利用这个性质,当遍历根节点的左孩子的时候,可以继续把其当做左子

剑指offer系列之二十二:二叉搜索树的后续遍历序列

题目描述 输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果.如果是则输出Yes,否则输出No.假设输入的数组的任意两个数字都互不相同. 此题仍然是对二叉树遍历方法的考察,但是与直接对遍历方法的考察不太一样,因为这里的输入是后续遍历的序列,所以要判断该序列是否是某二叉树的后续遍历结果,关键在于找出根节点,根节点的左子树和根节点的右子树,然后继续对左子树和右子树进行判断,直到全部元素访问完毕.这里很显然是一个递归的过程.由于后续遍历是先访问双亲节点,接着访问左孩子,再访问右孩子,所以需

剑指offer系列之二十:栈的压入、弹出序列

题目描述 输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序.假设压入栈的所有数字均不相等.例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该压栈序列的弹出序列. 要判断一个序列是不是另一个序列的弹出序列,首先我们得知道栈的特点是FIFO,其次,由于压入序列是确定的(这里指的"确定"是说相对位置是确定的),就是说压入序列之间的元素可能会经历压入后马上被弹出的情况.具体思路是:

剑指offer系列之二十九:连续子数组的最大和

题目描述 HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学.今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决.但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢?例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止).你会不会被他忽悠住? 这实际上是一个逐步比较的过程,假设累加进行到某一步,继续累加下一个数的时候发现和变小了,就应该重新计算当前累加的

剑指offer系列之二十七:数组中出现次数超过一半的数

题目描述 数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字.例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}.由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2.如果不存在则输出0. 思路分析:由于是一个数字,因为其次数超过1,那么其出现的出现综合肯定实际大于其他所有数字之和的.因为如此,我们可以设置一个变量用于辨识这个变量,遇到相同的数字就把次数增加1,如果没有没有遇到就把次数减少1,那么肯定次数有可能变为0,因为没有遇到相同的.因为那个数字的次数出现了超

剑指offer系列之二十一:从上到下打印二叉树

题目描述 从上往下打印出二叉树的每个节点,同层节点从左至右打印. 此题实际上就是二叉树层序遍历方法的考察,具体思路是:使用一个集合(或者栈,但是相对来说使用栈操作会方便一些)来保存遍历的节点,还需要创建一个集合用来保存最后输出的遍历序列.从根节点开始遍历,首先把该节点放入集合中,并输出其值,之后便从集合中移除该节点,不过在此之前需要判断该节点是否有左右孩子,如果有左右(满足其一就可以)孩子,便把左右孩子放入集合中.每次输出值后便把节点具体的值放入遍历集合中,作为最后的返回结果. 下面是基于这种思

剑指offer系列之二十三:二叉树中和为某一值得所有路径

题目描述 输入一颗二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径.路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径. 由于是从根节点开始遍历的,所以自然联想到前序遍历,但是问题并没有那么简单,在遍历的过程中需要记录遍历的所有节点值的和,当某条路径遍历完毕之后,还需要切换到另一个节点,比如从某个节点的左孩子切换到右孩子,然后需要重新计算总和,并且需要减去原来那个节点的值.大概思路是:使用前序遍历的方式,如果遍历到叶子节点,和恰好是目标值,那么就将遍历经过的所有节点

剑指offer系列之二十四:复杂链表的复制

题目描述 输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点). 下面是我第一想到的思路:因为next指针是固定的,在复制的时候这点比较好处理,由于特殊指针是任意的,可能是在节点之前,也可能在节点之后,所以必须解决这个棘手问题.不管至少,可以从链表的第一个节点开始遍历,直到该特殊指针指向的节点,并设置该节点的特殊指针.还有一种思路(也是书上的思路):第一步,复制原来链表的节点,并设置next指针,这一步不同于简单的复制节点,而是把每个复制的节点