2024.4.1
- 题目来源
- 我的题解
- 方法一 直接利用StringBuilder的反转函数
- 方法二 字符数组
题目来源
力扣每日一题;题序:2810
我的题解
方法一 直接利用StringBuilder的反转函数
使用StringBuilder构造结果,并利用其反转函数进行翻转
时间复杂度:O( n 2 n^2 n2)
空间复杂度:O(1)
public String finalString(String s) {StringBuilder sb=new StringBuilder();for(char ch:s.toCharArray()){if(ch=='i')sb=sb.reverse();elsesb.append(ch);}return sb.toString();}
方法二 字符数组
使用字符数组代替StringBuilder,自定义实现reverse方法,使得时间复杂度降低到O(logn)
时间复杂度:O(nlogn)
空间复杂度:O(1)。char数组是结果数组,不计算入空间复杂度
public String finalString(String s) {char[] sb=new char[s.length()];int i=0;for(char ch:s.toCharArray()){if(ch=='i')reverse(sb,i);elsesb[i++]=ch;}return new String(sb,0,i);
}
public void reverse(char[] s,int n){for(int i=0;i<n/2;i++){char t=s[i];s[i]=s[n-i-1];s[n-i-1]=t;}
}
有任何问题,欢迎评论区交流,欢迎评论区提供其它解题思路(代码),也可以点个赞支持一下作者哈😄~