字符串变形

知识点 字符串

一、描述

        对于一个长度为 n 字符串，我们需要对它做一些变形。

        首先这个字符串中包含着一些空格，就像"Hello World"一样，然后我们要做的是把这个字符串中由空格隔开的单词反序，同时反转每个字符的大小写。

        比如"Hello World"变形后就变成了"wORLD hELLO"。

数据范围: 1\le n \le 10^61≤n≤106 , 字符串中包括大写英文字母、小写英文字母、空格。

进阶：空间复杂度 O(n) ， 时间复杂度 O(n)

输入描述：

        给定一个字符串s以及它的长度n(1 ≤ n ≤ 10^6)

返回值描述：

        请返回变形后的字符串。题目保证给定的字符串均由大小写字母和空格构成。

 二、解题思路

        很容易想到，要从后面往前遍历字符数组。我的思路是使用循环遍历j从后往前遍历，并使用一个变量lastBlankIndex来存储右边位置最近一个空格的下标位置。并且把字符串转换成字符数组方便遍历。

        当 j 遍历到非空格时，如果是大写则转成小写，如果是小写则换成大写；

        当 j 遍历到空格时， 则把 j + 1 到上一个空格位置之间的子字符数组追加到stringbuilder对象中；

        当j=0时，循环结束，并且处理0位置处不为空格的情况。

下面是我写的代码，但是通过率是14/15，第15个输入程序运行后超时了。

import java.util.*;
 
public class Solution {
    public String trans(String s, int n) {
        // write code here
        //通过率14/15，第15个输入程序计算超时了
        StringBuilder builder = new StringBuilder();
        char [] chars = s.toCharArray();
        int lastBlankIndex = n; //用来编辑当前遍历到的单词后面的空格的下标位置
        int j = n - 1; //用来从后往前遍历字符串
        while(j >= 0) {
            if (s.charAt(j) == ' ') {
                builder.append(new String(chars).substring(j + 1, lastBlankIndex) + " ");
                lastBlankIndex = j;
            } else {
                if (chars[j]>='A' && chars[j] <= 'Z') {
                    //chars[j] = (char) (chars[j] - 'A' + 'a');
                   chars[j] = Character.toLowerCase(chars[j]);
                } else {
                    //chars[j] = (char) (chars[j] - 'a' + 'A');
                   chars[j] = Character.toUpperCase(chars[j]);
                }
            }
            j--;
        }
        //需要考虑第一个字符不是空格，第一个字符是空格情况在循环中已经处理了
        if (chars[0] != ' ') {
            builder.append(new String(chars).substring(0, lastBlankIndex));
        }
        return builder.toString();
    }
}

        为什么会超时呢？算法时间负责度是O(n)， 空间复杂度也是O(n)啊。真是百思不得解！！不过后来知道超时原因所在了。不过这里我们先看下网上别人的代码，运行不会超时。

import java.util.*;
 
public class Solution {
    public String trans(String s, int n) {
        char[] arr = s.toCharArray();
        StringBuilder res = new StringBuilder();
        StringBuilder temp = new StringBuilder();
        for (int i = n - 1; i >= 0; i --) {
            if (arr[i] == ' ') {
                res.append(temp.toString() + " ");
                temp.delete(0, temp.length());
            }
            else {
                if (arr[i] >= 'a' && arr[i] <= 'z') {
                    temp.insert(0, Character.toUpperCase(arr[i]));
                }
                else if (arr[i] >= 'A' && arr[i] <= 'Z') {
                    temp.insert(0, Character.toLowerCase(arr[i]));
                }
            }
        }
        return res.append(temp.toString()).toString();
    }
}

        你会发现，其实他的思路也是从后往前遍历字符数组。不过他使用了一个StringBuffer来存储遍历到的单词。并且每遍历到一个字符，很巧妙地插入到StringBuffer的下标0位置，这样能保证单词的顺序不受反向遍历的影响。在遍历到空格后，把单词添加到StringBuilder中，并及时情况了StringBuffer。

        所以这种思路是可行的，不会超时。 现在就要想想为什么我自己的算法超时了？

        通过对比发现，我在使用StringBuilder对象来追加单词时使用的是下面的写法

builder.append(new String(chars).substring(j + 1, lastBlankIndex) + " ");

        这样写的话会利用chars字符数组来创建一个字符串，然后取出字符串的子字符串。当chars里的字符数量少的时候没什么问题，可是题目说明的是字符串长度为1 ≤ n ≤ 10^6。这样如果每次append的时候都创建一个这么长的字符串，需要的内存空间可想而知是多么的大！！ 所以不是时间复杂度超了，而是内存空间超了。

        那有没有什么办法可以直接取出字符数组的子数组呢？通过百度发现jdk提供了相关api能满足要求，即Arrays.copyOfRange(chars, j + 1, lastBlankIndex)。Arrays类中封装了很多数组相关的操作，必须掌握！！ 

        所以改进后的代码为：

public class Solution {
    public String trans(String s, int n) {
        // write code here
        //通过率14/15，第15个输入程序计算超时了
        StringBuilder builder = new StringBuilder();
        char [] chars = s.toCharArray();
        int lastBlankIndex = n; //用来编辑当前遍历到的单词后面的空格的下标位置
        int j = n - 1; //用来从后往前遍历字符串
        while(j >= 0) {
            if (s.charAt(j) == ' ') {
                //builder.append(new String(chars).substring(j + 1, lastBlankIndex) + " ");
                builder.append(new String(Arrays.copyOfRange(chars, j + 1, lastBlankIndex)) + " ");
                lastBlankIndex = j;
            } else {
                if (chars[j]>='A' && chars[j] <= 'Z') {
                    //chars[j] = (char) (chars[j] - 'A' + 'a');
                   chars[j] = Character.toLowerCase(chars[j]);
                } else {
                    //chars[j] = (char) (chars[j] - 'a' + 'A');
                   chars[j] = Character.toUpperCase(chars[j]);
                }
            }
            j--;
        }
        //需要考虑第一个字符不是空格，第一个字符是空格情况在循环中已经处理了
        if (chars[0] != ' ') {
            //builder.append(new String(chars).substring(0, lastBlankIndex));
            builder.append(new String(Arrays.copyOfRange(chars, 0, lastBlankIndex)));
        }
        return builder.toString();
    }
}

        一运行就通过了，看来的确是空间复杂度超了。

三、拾遗

1、需要了解Arrays类都具有哪些能力（单独写篇文章记录）；

2、字符转大小写

        判断字符是不是大写或小写字母：

if (chars[j]>='A' && chars[j] <= 'Z')

       大小写转换，这里有两种方法都可以

        第一种：自己写逻辑

        chars[j] - 'A' 能得出char[j]偏移A的偏移量，a + 偏移量就是char[j]的小写形式。这种方式在记不住字母的ascii值的情况下特别好用。

chars[j] = (char) (chars[j] - 'A' + 'a');

        第二种：利用Character类的方法

chars[j] = Character.toLowerCase(chars[j]);