一、反转字符串
题目:
力扣344:反转字符串
编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
示例1:
输入:s = [“h”,“e”,“l”,“l”,“o”]
输出:[“o”,“l”,“l”,“e”,“h”]
示例2:
输入:s = [“H”,“a”,“n”,“n”,“a”,“h”]
输出:[“h”,“a”,“n”,“n”,“a”,“H”]
提示:
- 1 <= s.length <= 105
- s[i] 都是 ASCII 码表中的可打印字符
解题思路分析:
自己的思路:
用两个指针,一个从头开始遍历,一个从尾部开始遍历,并且一边遍历一边交换字符位置,直到左右指针相遇(指向同一个位置,这是奇数个字符的时候;或者错过,即left>right),这是偶数个字符的时候);
交换的时候,用一个临时变量temp来存储left位置的字符,把right赋给left,temp赋给right,完成交换。
代码:
//定义左右指针
int left = 0;
int right = s.length - 1;
//循环遍历,进行交换
while(left < right) {//临时变量,存储取出来的字符char temp;//利用temp完成字符交换temp = s[left];s[left] = s[right];s[right] = temp;//交换结束后left和right同时向中间移动一个位置left++;right--;
}
复杂度分析:
- 时间复杂度:O(n)
- 空房间复杂度:O(1)
说明:
如果题目关键的部分直接用库函数就可以解决,建议不要使用库函数。
双指针法图示:
补充:
还可以使用异或操作来完成交换:也可以避免使用额外空间
异或操作:比较两个二进制位。如果两个二进制位相同,则结果为 0;如果两个二进制位不同,则结果为 1。
s[left] ^= s[right]; //构造 a ^ b 的结果,放入a中
s[right] ^= s[left]; //将a ^ b 的结果再 ^b,存入b中,此时b=a,a=a ^ b
s[left] ^= s[right]; //a ^ b 的结果再 ^ a ,存入 a 中,此时 b = a, a = b 完成交换
题解:
用temp交换数值
用异或操作交换数值:
二、反转字符串II
题目:
力扣541:反转字符串II
给定一个字符串 s 和一个整数 k,从字符串开头算起,每计数至 2k 个字符,就反转这 2k 字符中的前 k 个字符。
- 如果剩余字符少于 k 个,则将剩余字符全部反转。
- 如果剩余字符小于 2k 但大于或等于 k 个,则反转前 k 个字符,其余字符保持原样。
示例1:
输入:s = “abcdefg”, k = 2
输出:“bacdfeg”
示例2:
输入:s = “abcd”, k = 2
输出:“bacd”
提示:
- 1 <= s.length <= 104
- s 仅由小写英文组成
- 1 <= k <= 104
解题思路分析:
这道题目其实就是比上一题多了一些规则;
这里for循环中可以不写i++,而是直接写i += (2*k),直接让i移动2k个位置,而不是一个一个去移动;
大家如果习惯性写i++的话,还得移动并计数判断有没有到2k,这样代码就变得很复杂了。
所以当需要固定规律一段一段去处理字符串的时候,要想想在在for循环的表达式上做做文章。
代码讲解:
//将字符串转换成数组去操作
char[] ch = s.toCharArray();
//循环遍历字符串数组
for(int i = 0; i < s.length(); i += (2 * k)) {//判断是否还剩k个字符,避免操作空字符串//左闭右开,反转的时候不包含第i+k这个字符,所以边界条件可以等于i+kif(i + k < s.length()) {//对前k个字符进行反转int left = i;int right = i + k - 1;while(left < right) {char temp = s.charAt(i);ch[left] = ch[right];ch[right] = temp;left++;right--;}}else{//对尾部不够k时剩余的字符进行反转int left = i;int right = ch.length - 1;while(left < right) {char temp = ch[left];ch[left] = ch[right];ch[right] = temp;left++;right--;}}
}
return new String(ch);
代码可以更加简洁:
让right等于ch.length-1和i+k-1的最小值;
也就是判断尾部剩余的字符个数够不够k,来决定right是取i+k-1(剩余字符大于等于k个),还是取ch.length-1(不够k个)。
因为如果剩余字符大于等于k个,那么ch.length-1大于等于i+k-1;剩余字符不够k个时,i+k-1大于ch.length-1。
相当于直接用取最小值来完成了尾部剩余字符个数够不够k个的判断。
代码如下:
//将字符串转换成数组去操作
char[] ch = s.toCharArray();
//循环遍历字符串数组
for(int i = 0; i < ch.length; i += (2 * k)) {int left = i;//判断是否还剩k个字符,避免操作空字符串int right = Math.min(ch.length - 1, i + k - 1);//对字符串进行翻转while(left < right) {char temp = ch[left];ch[left] = ch[right];ch[right] = temp;left++;right--;}
}
return new String(ch);
复杂度分析:
- 时间复杂度:O(n)
- 空间复杂度:O(1)
总结:
如果操作字符串或者数组,是成段的去操作的,那么可以考虑让指针成段的跳,而不是i++一个一个去走;
这里就需要跳出固有思维,更加灵活的解决问题。
另外,在遇到边界问题时,别忘了前面学过的区间开闭原则!
题解:
三、替换数字
题目:
卡码网54:替换数字
时间限制:1.000s 空间限制:128MB
题目描述
给定一个字符串 s,它包含小写字母和数字字符,请编写一个函数,将字符串中的字母字符保持不变,而将每个数字字符替换为number。 例如,对于输入字符串 “a1b2c3”,函数应该将其转换为 “anumberbnumbercnumber”。
输入描述:
输入一个字符串 s,s 仅包含小写字母和数字字符。
输出描述:
打印一个新的字符串,其中每个数字字符都被替换为了number
输入示例:
a1b2c3
输出示例:
anumberbnumbercnumber
提示信息:
数据范围:
1 <= s.length < 10000。
解题思路分析:
首先扩充数组到每个数字字符替换成 “number” 之后的大小。
例如 字符串 “a5b” 的长度为3,那么 将 数字字符变成字符串 “number” 之后的字符串为 “anumberb” 长度为 8。
如图:
然后从后向前替换数字字符,也就是双指针法:
i 指向新长度的末尾,j指向旧长度的末尾;
为什么要从后向前填充,从前向后填充不行么?
从前向后填充就是O(n^2)的算法了,因为每次添加元素都要将添加元素之后的所有元素整体向后移动。
其实很多数组填充类的问题,其做法都是先预先给数组扩容带填充后的大小,然后在从后向前进行操作。
这么做有两个好处:
- 不用申请新数组。
- 从后向前填充元素,避免了从前向后填充元素时,每次添加元素都要将添加元素之后的所有元素向后移动的问题。
代码讲解:(ACM模式)
import java.utils.*
public class Main {public static void main(String[] args) {//输入字符串sScanner sc = new Scanner(System.in);String s = sc.next();//计算出新数组所需要的长度int len = s.length();for(int i = 0; i < s.length(); i++) {//如果是数字,就把数组长度+5(因为原来的数字所在的位置也会被覆盖,所以只用+5)if(s.charAt(i) >= 0 && s.charAt(i) <= 9) {len += 5;}}//申请新数组,把字符串s先放进数组char[] ch = new char[len];for(int i = 0; i < s.length(); i++) {ch[i] = s.charAt(i);}//开始双指针法,将数字替换成numberfor(int i = s.length() - 1, j = len - 1; i >= 0; i--) {//如果是数字,就从后往前插入number if(ch[i] >= '0' && ch[i] <= '9') {ch[j--] = 'r';ch[j--] = 'e';ch[j--] = 'b';ch[j--] = 'm';ch[j--] = 'u';ch[j--] = 'n';} else {//如果是字母,就直接放到后面ch[j--] = ch[i];}}}//输出结果System.out.println(ch);
}