NC103 反转字符串_入门

发表于 更新于 分类于 ， ， Waline： 本文字数： 2.5k 阅读时长 ≈ 2 分钟

NC103 反转字符串

描述

写出一个程序，接受一个字符串，然后输出该字符串反转后的字符串。（字符串长度不超过1000）

数据范围： $0 \le n \le 10000≤n≤1000$
要求：空间复杂度 $O(n)$，时间复杂度 $O(n)$

示例1

1
2
输入："abcd"
返回值："dcba"

示例2

1
2
输入：""
返回值：""

关联企业

百度
微盟
携程
腾讯

关联职位

测试
研发
前端
算法

我的题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import java.util.*;

public class Solution {
    /**
     * 反转字符串
     * @param str string字符串 
     * @return string字符串
     */
    public String solve (String str) {
        StringBuilder sb=new StringBuilder(str.length());
        for(int i=str.length()-1;i>=0;i--){
            sb.append(str.charAt(i));
        }
        return sb.toString();
    }
}
1
2
3
4
5
6
7
8
9
// 方式2
char[] arr=str.toCharArray();
char temp;
for(int i=0;i<arr.length/2;i++){
    temp=arr[i];
    arr[i]=arr[arr.length-1-i];
    arr[arr.length-1-i]=temp;
}
return new String(arr);
1
2
3
4
5
6
7
8
9
10
11
// 方式3：使用亦或进行交换
// a^=b;
// b^=a;
// a^=b;
char[] arr=str.toCharArray();
for(int i=0;i<arr.length/2;i++){
    arr[i]^=arr[arr.length-1-i];
    arr[arr.length-1-i]^=arr[i];
    arr[i]^=arr[arr.length-1-i];
}
return new String(arr);
1
2
3
4
5
6
7
8
// 方式4：使用valueOf(char[])方法返回字符串
char[] arr=str.toCharArray();
for(int i=0;i<arr.length/2;i++){
    arr[i]^=arr[arr.length-1-i];
    arr[arr.length-1-i]^=arr[i];
    arr[i]^=arr[arr.length-1-i];
}
return String.valueOf(arr);
1
2
3
4
// 方式5：库函数实现
StringBuilder sb=new StringBuilder(str.length());
sb.append(str);
return sb.reverse().toString();

方式5：库函数实现2：

1
return new StringBuilder(str).reverse().toString();

官方 精华题解

视频

https://www.nowcoder.com/practice/c3a6afee325e472386a1c4eb1ef987f3?tab=note

<video src=’https://uploadfiles.nowcoder.com/files/20210122/993000_1611283786722/nc103%E5%8F%8D%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2.mp4' type=’video/mp4’controls=’controls’ preload=”auto” width=’100%’ height=’100%’>

文字题解

解法一:

开辟一个和str长度大小相同的一个字符串ans，把传入的str倒序赋值到ans字符串上， 时间复杂度$O(n)$,额外空间复杂度$O(n)$。

1
2
3
4
5
6
7
8
9
10
11
12
import java.util.*;
public class Solution {
    public String solve (String str) {
        char[] ans = str.toCharArray();
        int len = str.length();
        for(int i = 0 ; i < len ;i++)
        {
                ans[i] = str.charAt(len-1-i);
        }
        return new String(ans);
    }
}

解法二:

原地交换，img,注意：交换进行的次数是img次

时间复杂度img,额外空间复杂度img

1
2
3
4
5
6
7
8
9
10
11
12
13
import java.util.*;
public class Solution {
    public String solve (String str) {
        char[] cstr = str.toCharArray();
        int len = str.length();
        for(int i = 0 ;i < len/2 ;i++){
            char t = cstr[i];
            cstr[i] = cstr[len-1-i];
            cstr[len-1-i]=t;
        }
        return new String(cstr);
    }
}

解法三:

直接调用库函数

1
2
3
4
5
6
7
import java.util.*;
public class Solution {
    public String solve (String str) {
        StringBuffer sb =new StringBuffer(str);//此方法针对的是io流，不能针对字符串。
        return sb.reverse().toString();
    }
}