做电商网站费用,wordpress制作婚礼网页,wordpress主题漂亮,重庆在线最新招聘信息一、反转字符串
题目#xff1a;
力扣344#xff1a;反转字符串
编写一个函数#xff0c;其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间#xff0c;你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题…一、反转字符串
题目
力扣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 105s[i] 都是 ASCII 码表中的可打印字符
解题思路分析 自己的思路
用两个指针一个从头开始遍历一个从尾部开始遍历并且一边遍历一边交换字符位置直到左右指针相遇指向同一个位置这是奇数个字符的时候或者错过即leftright这是偶数个字符的时候
交换的时候用一个临时变量temp来存储left位置的字符把right赋给lefttemp赋给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中此时baaa ^ 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 104s 仅由小写英文组成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个字符避免操作空字符串//左闭右开反转的时候不包含第ik这个字符所以边界条件可以等于ikif(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和ik-1的最小值
也就是判断尾部剩余的字符个数够不够k来决定right是取ik-1剩余字符大于等于k个还是取ch.length-1不够k个。
因为如果剩余字符大于等于k个那么ch.length-1大于等于ik-1剩余字符不够k个时ik-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因为原来的数字所在的位置也会被覆盖所以只用5if(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);
}
题解
