目录

• 前言
• 问题介绍
• 解决方案
• 代码编写
• • java语言版本
  • c语言版本
  • c++语言版本
• 思考感悟
• 写在最后

前言

当前所有算法都使用测试用例运行过，但是不保证100%的测试用例，如果存在问题务必联系批评指正~

在此感谢左大神让我对算法有了新的感悟认识！

问题介绍

原问题
给定一个字符串String， 替换String中的‘ ’字符为20%
如 ：str=“1 23 4”
结果为：res = “120%2320%4”
进阶问题
给定一个字符串完全由‘*’和数字字符组成，将‘*’全部移动到数字字符的前面去
如:str = 1235
结果为 res = “**1235”
请实现空间复杂度为O(1)的方式，并且数组中的数字顺序不可以颠倒

解决方案

原问题：
1、首先计算出最坏的情况，也就是整个字符串都是’ ‘字符，那么需要 str.length * 3 的长度的字符串用来保存字符。
2、其次从后往前遍历，如果不是’ ’ 的就直接复制，是’ '字符的话直接复制为‘%’ ，‘0’，‘2’ 个字符即可
进阶问题
1、跟原问题相同解法，找到倒数第一个*，计为index1，然后从* 开始往前找到第一个数字的index计为index2
2、从index2开始往前遍历,遇到* 则略过，如果是数字则复制到index2。

代码编写

java语言版本

原问题：

    /*** 二轮测试：问题1* @param chars* @return*/public static char[] pro1Cp1(char[] chars) {if (chars == null || chars.length == 0) {return null;}int index1 = chars.length-1;while (chars[index1] == 0) {index1--;}int index2 = chars.length-1;while (index1 >= 0) {if (chars[index1] == ' '){chars[index2--] = '%';chars[index2--] = '0';chars[index2--] = '2';}else {chars[index2--] = chars[index1];}chars[index1] = 0;index1--;}return chars;}

进阶问题：

   /*** 二轮测试：问题二* @param chars* @return*/public static char[] moveCp2(char[] chars){if (chars == null || chars.length == 0) {return null;}int index1 = chars.length-1;while (chars[index1] != '*') {index1--;}int index2 = index1;while (chars[index2] == '*') {index2--;}while (index2 >= 0) {if (chars[index2] != '*') {chars[index1--] = chars[index2];chars[index2] = '*';}index2--;}return chars;}public static void main(String[] args) {char[] chars1 = {'1', '2', '*', '3', '5'};char[] chars2 = new char[chars1.length * 3];for (int i = 0; i < chars1.length; i++) {chars2[i] = chars1[i];}System.out.println(moveCp2(chars1));}

c语言版本

正在学习中

c++语言版本

正在学习中

思考感悟

这道题刚开始我觉得很简单，但是写着发现空间复杂度为O(1)的方式如果没有想到倒着来的话其实还是不太好实现的，会发现顺序倒过来了，不过题目中不允许倒过来这句话其实就暗示着倒着遍历，以后要有这个肌肉记忆。

写在最后

方案和代码仅提供学习和思考使用，切勿随意滥用！如有错误和不合理的地方，务必批评指正~
如果需要git源码可邮件给2260755767@qq.com
再次感谢左大神对我算法的指点迷津！