[NC]89. 字符串变形

🚩传送门：牛客题目

题目

对于一个长度为 n 字符串，我们需要对它做一些变形。字符串中含有空格，就像"Hello World"一样，我们要做的是把这个字符串中由空格隔开的单词反序，同时反转每个字符的大小写。

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

数据范围: , 字符串中包括大写英文字母、小写英文字母、空格。
进阶：空间复杂度 ， 时间复杂度
输入描述：给定一个字符串str以及它的长度n
返回值描述：请返回变形后的字符串。题目保证给定的字符串均由大小写字母和空格构成。

示例

输入：“This is a sample”,16 返回值：“SAMPLE A IS tHIS”

解题思路：栈

题目要求将单词逆序输出，很容易想到一个思路就是利用栈的先入后出特性。

复杂度分析

时间复杂度：，其中 是字符串长度。

空间复杂度：，需要栈将分割后的字符串重新存储一次。

我的代码

public class Solution {
    public String trans(String s, int n) {
        LinkedList<StringBuffer>stack=new LinkedList<>();    // 栈
        StringBuffer tempbuffer =new StringBuffer();        // 存储临时转换的 String
        for(int i=0;i<=n;i++){                                // 依次遍历字符串
            char c='+';
            if(i==n||(c=s.charAt(i))==' '){                    // 遇到末尾结束或者空格时入栈
                stack.push(tempbuffer);
                tempbuffer = new StringBuffer();            // 重置清空当前StringBuffer
            }else{                                            // 大小写转换
                if(c >= 'a' && c <= 'z') tempbuffer.append((char)(c-'a'+'A'));    
                else tempbuffer.append((char)(c-'A'+'a'));
            }
        }
        while(!stack.isEmpty()){                            // 栈不空,出栈存储追加空格
            tempbuffer.append(stack.pop()).append(" ");
        }
        tempbuffer.deleteCharAt(tempbuffer.length()-1);        // 删除最后一个末尾的空格
        return tempbuffer.toString();                        // 转为String类型返回
    }
}

解题思路：双指针

首先将原来的字符串整体反转，接着从前往后，以单个单词为整体逐个反转 。具体流程如下图所示：

复杂度分析

时间复杂度：，其中 是字符串长度。

空间复杂度：，需要栈将分割后的字符串重新存储一次。

我的代码

public class Solution {
    public String trans(String s, int n) {
        // write code here
        if(s==null || n<=0){return s;}
        char[] sArr=s.toCharArray();
        //双指针 将字符串作为一个整体反转
        reverse(0,n-1,sArr);
        //各个单词作为一个整体 再反转一次
        int index=0;
        while(index<n){
            int end=index;
            while(end<n && sArr[end]!=' '){
                sArr[end]=upLower(sArr[end]);//大小写
                end++;
            }
            //找到空格了 单词的右边界为空格减一的位置
            reverse(index,end-1,sArr);
            index=end+1;//更新index 指向单词的首字母
        }
        return String.valueOf(sArr);
    }
    public void swap(int a,int b,char[]sArr){
             char tmp=sArr[a];
            sArr[a]=sArr[b];
            sArr[b]=tmp;
    }
    public void reverse(int start,int end,char[] sArr){
        int left=start,right=end;
        while(left<right){
            swap(left,right,sArr);
            left++;
            right--;
        }
    }
    public char upLower(char c){
        if(c>='a' && c<='z'){
            return (char)(c-32);//小写转大写
        }else if(c>='A' && c<='Z'){
            return (char)(c+32);//大写转小写
        }else{
            return c;//空格
        }
    }
}