一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 880|回复: 5
收起左侧

[算法题] 【Java】关于数组/字符串结束符的疑问……(From CareerCup1_4)

[复制链接] |试试Instant~ |关注本帖
sanguine 发表于 2014-6-25 20:10:38 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本帖最后由 sanguine 于 2014-6-25 20:22 编辑

/*

* Write a method to replace all spaces in a string with'%20'.
        You may assume that the string has sufficient space at the end of the string
        to hold the additional characters, and that you are given the "true" length of the string.
* (if implementing in Java, please use a character array so that you can perform this operation in place.)

* EXAMPLE
        Input: "Mr John Smith       "
        Output: "Mr%20Dohn%20Smith"
*/


做CareerCup1.4的时候发现一个问题,下面是我的代码:
  1. import java.util.Scanner;

  2. public class ReplaceSpace1_4 {

  3.     /*
  4.      * The Question required to implements this Q in place, which means the parameter of the method
  5.            should be char[] rather than String, and cannot use another char[] inside the method.
  6.      * Because the length of the char[] is fixed when initial char[]
  7.            So we initial the char[] have enough space to store char.
  8.      * 1. count the number of spaces in the input string except the space at the end of char[]
  9.        2. calculate the new length needed after replace the space with '%20'
  10.        3. Traverse the char[] from the tail(the new length location rather than the whole char[])
  11.                                     to the front to avoid rewrite

  12.      * Time Complexity: O(n)
  13.        Space Complexity: O(1)
  14.      */
  15.     private static void ReplaceSpace1(char[] str, int length) {
  16.         int count = 0;  // count the number of spaces(except the space at the end of char[])
  17.         int temp = 0;   // temporary count the number of successive spaces
  18.         // the last temp will count the number of space at the end of char[]
  19.         int num;
  20.         for (num = 0; num < length; num++) {
  21.             if (str[num] == ' ') {
  22.                 temp++;
  23.             } else {
  24.                 count = count + temp;
  25.                 temp = 0;   //spaces here are not at the end of the input string, set the temp to 0
  26.             }
  27.         }

  28.         int oldLength = num - temp;  //length except the spaces at the end of char[]
  29.         int newLength = oldLength + (count << 1);  //calculate the target length of the output char[]

  30.         for (int i = oldLength - 1; i >= 0; i--) {
  31.             if (str[i] == ' ') {    //changes begin from the char[newLength - 1]
  32.                 str[newLength - 1] = '0';
  33.                 str[newLength - 2] = '2';
  34.                 str[newLength - 3] = '%';
  35.                 newLength = newLength - 3;
  36.             } else {
  37.                 str[--newLength] = str[i];
  38.             }
  39.         }
  40.     }

  41.     public static void main(String[] args) {
  42.         Scanner input = new Scanner(System.in);
  43.         System.out.println("Please enter a string: ");

  44.         while (input.hasNextLine()) {
  45.             char[] str = new char[inputStr.length() * 3];
  46.             for (int i = 0; i < inputStr.length(); i++) {
  47.                 str[i] = inputStr.charAt(i);
  48.             }
  49.             ReplaceSpace1(str, inputStr.length());
  50.             System.out.print("String after replace all the spaces: ");
  51.             for (int i = 0; str[i] != '\0'; i++) {
  52.                 System.out.print(str[i]);
  53.             }
  54.             System.out.println();

  55.             System.out.println("Please enter another string: ");
  56.         }
  57.     }
  58. }
复制代码
有个感觉自己绕不清楚的问题:

查了很多资料,知道Java是没有数组/字符串结束符的,自己也写代码试了下,发现确实如此,在Java中新建一个char[1000]的数组,并只往前面10个添加数据,然后length还是1000,(在C/C++中英文结束符是\0,所以会自动判断到length是2【求证实】)

这样的话上面这个代码感觉无解了==
首先函数中传入了char[]和字符串的长度,然后因为字符串由空格变成了‘%20’,字符串的长度是增加了的,即代码里的newLength长度,但是因为Java里面没有指针,所以newLength没法返回给main函数,所以需要在void main里面自己判断replace后的数组有多长……但是又因为Java没有结束符==没法判断!

现在的写法是for (int i = 0; str != '\0'; i++) ,但是万一字符串中本身就有\0呢?还是说不要考虑这种情况%>_<%


---------------------------------------------------------------------update--------------------------------------------------------------------------
测试了下,输入的是“aaa\0  bb    ”,输出的时候也是正常的
这是因为我在void main函数中
用的是
char[] str = new char[inputStr.length() * 3];
            for (int i = 0; i < inputStr.length(); i++) {
                str = inputStr.charAt(i);
            }

实现的把string类型放到char[]中,如果使用str = inputStr.tocharArray方法的话,\0就会作为一个整体存入char[]中,这样的话,输出的时候就会直接输出到aaa截止,后面的并不会输出
readman 发表于 2014-6-25 20:45:46 | 显示全部楼层
所以你的问题是?
回复 支持 反对

使用道具 举报

 楼主| sanguine 发表于 2014-6-25 21:09:13 | 显示全部楼层
readman 发表于 2014-6-25 20:45
所以你的问题是?

好像又木有问题了……因为不能用tocharArray()把string转成char[]类型,所以这里直接for循环用\0来判断结尾是可以的

但是,,,我上面的乱七八糟的分析==对了么云里雾里的这一块

以及。。。代码有木有可优化的地方==
回复 支持 反对

使用道具 举报

七00夜 发表于 2014-6-27 05:35:20 | 显示全部楼层
让用户输入完字符串str1之后先统计一下里面的空格个数n,再根据这个新建一个长度为str1.length()+2*n的字符数组arr1, 而不是直接创建一个长度1000的? 然后正常顺次赋值给arr1,遇到空格就分别赋值'%',2','0',就这样就不会出现你说的问题了吧?但是有一个问题,如果str1最后面故意敲了N个空格,在最后就会重复显示N次”%20“。
用str1.trim().replace(" ","%20")更简单几条语句就可以解决了, 也可以解决开头末尾的空格问题。不知道能不能帮到你.
回复 支持 反对

使用道具 举报

 楼主| sanguine 发表于 2014-6-27 10:18:21 | 显示全部楼层
七00夜 发表于 2014-6-27 05:35
让用户输入完字符串str1之后先统计一下里面的空格个数n,再根据这个新建一个长度为str1.length()+2*n的字符 ...

你的意思是在void main中根据str1就算好char[]的长度?然后新建一个char[]类型传入函数中?

研究了这个题目,好像只需要实现的是函数,它默认说会给定实现后所需要的长度……我好像想的太多了orz……

果然还有好多函数我都不知道%>_<%,看了下trim()不仅仅是用来去除两端的空格的
http://blog.darkmi.com/2013/04/01/3000.html
回复 支持 反对

使用道具 举报

七00夜 发表于 2014-6-27 20:36:09 | 显示全部楼层
恩,是的。加油!
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-9 04:32

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表