字符串
字符串--反转字符串
编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
示例 1:
输入:["h","e","l","l","o"]
输出:["o","l","l","e","h"]
示例 2:
输入:["H","a","n","n","a","h"]
输出:["h","a","n","n","a","H"]
题解:
class Solution {
public void reverseString(char[] s) {
int l=0;
int r=s.length-1;
while(l<r){
char t=s[l];
s[l]=s[r];
s[r]=t;
l++;
r--;
}
}
}
解析:双指针法:
![344.反转字符串](https://code-thinking.cdn.bcebos.com/gifs/344.%E5%8F%8D%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2.gif)
如图所示定义两个指针,一个在最前面,一个在最后面,当他们没相遇之前,交换他们的值,直到相遇结束。
字符串--反转字符串II
给定一个字符串 s 和一个整数 k,从字符串开头算起, 每计数至 2k 个字符,就反转这 2k 个字符中的前 k 个字符。
如果剩余字符少于 k 个,则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个,则反转前 k 个字符,其余字符保持原样。
示例:
输入: s = "abcdefg", k = 2
输出: "bacdfeg
题解:
class Solution {
public String reverseStr(String s, int k) {
char[] c= s.toCharArray();
// 1. 每隔 2k 个字符的前 k 个字符进行反转
for(int i=0;i<c.length;i+=2*k){
// 2. 剩余字符小于 2k 但大于或等于 k 个,则反转前 k 个字符
if(i+k<=s.length()){
reverse(c,i,i+k-1);
continue;
}
// 3. 剩余字符少于 k 个,则将剩余字符全部反转
reverse(c,i,c.length-1);
}
return new String(c);
}
public void reverse(char[] c,int l,int r){
while(l<r){
char t=c[l];
c[l]=c[r];
c[r]=t;
l++;
r--;
}
}
}
解析:我们直接按题意进行模拟:反转每个下标从 2k 的倍数开始的,长度为 k*的子串。若该子串长度不足 k,则反转整个子串。
字符串--替换空格
请实现一个函数,把字符串 s 中的每个空格替换成"%20"。
示例 1: 输入:s = "We are happy."
输出:"We%20are%20happy."
题解:
class Solution {
public String replaceSpace(String s) {
if(s==null){
return null;
}
StringBuilder sb= new StringBuilder();
for(int i=0;i<s.length();i++){
//if (" ".equals(String.valueOf(s.charAt(i)))){}
if(s.charAt(i)==' '){
sb.append("%20");
}else{
sb.append(s.charAt(i));
}
}
return sb.toString();
}
}
解析:1.选用 StringBuilder 单线程,速度快
2.遍历字符串,当该字符串为空格时,把%20添加上,否则添加上该字符串。
字符串--反转字符串中的单词
给定一个字符串,逐个翻转字符串中的每个单词。
示例 1:
输入: "the sky is blue"
输出: "blue is sky the"
示例 2:
输入: " hello world! "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格,但是反转后的字符不能包括。
示例 3:
输入: "a good example"
输出: "example good a"
解释: 如果两个单词间有多余的空格,将反转后单词间的空格减少到只含一个
题解:
class Solution {
public String reverseWords(String s) {
//split(" +") 是正则表达式写法,表示至少一个空格,如果有多个空格就以多个空格切分
String[] words=s.trim().split(" +");
Collections.reverse(Arrays.asList(words));
return String.join(" ",words);
}
}
解析:trim()删除字符串的头尾空白符,空白符包括:空格、制表符 tab、换行符等其他空白符等,用split(" +") 正则表达式写法切分一个或多个空格,用把数组转化为list集合再调用api反转,最后在每个words之间连接上空格结束。
字符串--左旋转字符串
题目:
字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如,输入字符串"abcdefg"和数字2,该函数将返回左旋转两位得到的结果"cdefgab"。
示例 1:
输入: s = "abcdefg", k = 2
输出: "cdefgab"
示例 2:
输入: s = "lrloseumgh", k = 6
输出: "umghlrlose"
限制:
1 <= k < s.length <= 10000
题解:
1.字符串切片
class Solution {
public String reverseLeftWords(String s, int n) {
return s.substring(n,s.length())+s.substring(0,n);
}
}
解析:调用api切分字符串,拼接结果
2.列表遍历拼接
class Solution {
public String reverseLeftWords(String s, int n) {
StringBuilder sb= new StringBuilder();
for(int i=n;i<s.length();i++){
sb.append(s.charAt(i));
}
for(int i=0;i<n;i++){
sb.append(s.charAt(i));
}
return sb.toString();
}
}
解析:for循环遍历从n开始拼接到最后,在拼接0到n部分。
字符串--实现strStr()
题目:
实现 strStr() 函数。
给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在,则返回 -1。
示例 1: 输入: haystack = "hello", needle = "ll" 输出: 2
示例 2: 输入: haystack = "aaaaa", needle = "bba" 输出: -1
说明: 当 needle 是空字符串时,我们应当返回什么值呢?这是一个在面试中很好的问题。 对于本题而言,当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。
题解:
class Solution {
public int strStr(String haystack, String needle) {
int n=haystack.length();
int m=needle.length();
char[] k=haystack.toCharArray();
char[] e=needle.toCharArray();
for(int i=0;i<=n-m;i++){
int a=i;
int b=0;
while(b<m&&e[b]==k[a]){
a++;
b++;
}
if(b==m){
return i;
}
}
return -1;
}
}
解析:
- 把haystack和needle转化为字符数组
- i从0遍历到n-m,让a指针和b指针分别指向两个字符的首字母
- 如果指针符合条件并且指针对应的字符串相等的话,让两个指针右移。遍历之后,如果b指针的值等于m,则找到匹配的字符串,返回i索引,否则未找到,返回-1