地方门户网站app,信息化网站建设的请示,电商软件开发费用,宁阳网站seo推广344.反转字符串 力扣题目链接(opens new window) 编写一个函数#xff0c;其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。 不要给另外的数组分配额外的空间#xff0c;你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。 你可以假设数…344.反转字符串 力扣题目链接(opens new window) 编写一个函数其作用是将输入的字符串反转过来。输入字符串以字符数组 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) {s[l] ^ s[r]; //构造 a ^ b 的结果并放在 a 中s[r] ^ s[l]; //将 a ^ b 这一结果再 ^ b 存入b中此时 b a, a a ^ bs[l] ^ s[r]; //a ^ b 的结果再 ^ a 存入 a 中此时 b a, a b 完成交换l;r--;}}
}// 第二种方法用temp来交换数值更多人容易理解些
class Solution {public void reverseString(char[] s) {int l 0;int r s.length - 1;while(l r){char temp s[l];s[l] s[r];s[r] temp;l;r--;}}
} 建议 本题是字符串基础题目就是考察 reverse 函数的实现同时也明确一下 平时刷题什么时候用 库函数什么时候 不用库函数 题目链接/文章讲解/视频讲解代码随想录 541. 反转字符串II 力扣题目链接(opens new window) 给定一个字符串 s 和一个整数 k从字符串开头算起, 每计数至 2k 个字符就反转这 2k 个字符中的前 k 个字符。 如果剩余字符少于 k 个则将剩余字符全部反转。 如果剩余字符小于 2k 但大于或等于 k 个则反转前 k 个字符其余字符保持原样。 示例: 输入: s abcdefg, k 2 输出: bacdfeg 在遍历字符串的过程中只要让 i (2 * k)i 每次移动 2 * k 就可以了然后判断是否需要有反转的区间。
因为要找的也就是每2 * k 区间的起点这样写程序会高效很多。
所以当需要固定规律一段一段去处理字符串的时候要想想在for循环的表达式上做做文章 //解法一
class Solution {public String reverseStr(String s, int k) {StringBuffer res new StringBuffer();int length s.length();int start 0;while (start length) {// 找到k处和2k处StringBuffer temp new StringBuffer();// 与length进行判断如果大于length了那就将其置为lengthint firstK (start k length) ? length : start k;int secondK (start (2 * k) length) ? length : start (2 * k);//无论start所处位置至少会反转一次temp.append(s.substring(start, firstK));res.append(temp.reverse());// 如果firstK到secondK之间有元素这些元素直接放入res里即可。if (firstK secondK) { //此时剩余长度一定大于k。res.append(s.substring(firstK, secondK));}start (2 * k);}return res.toString();}
}//解法二似乎更容易理解点
//题目的意思其实概括为 每隔2k个反转前k个尾数不够k个时候全部反转
class Solution {public String reverseStr(String s, int k) {char[] ch s.toCharArray();for(int i 0; i ch.length; i 2 * k){int start i;//这里是判断尾数够不够k个来取决end指针的位置int end Math.min(ch.length - 1, start k - 1);//用异或运算反转 while(start end){ch[start] ^ ch[end];ch[end] ^ ch[start];ch[start] ^ ch[end];start;end--;}}return new String(ch);}
}// 解法二还可以用temp来交换数值会的人更多些
class Solution {public String reverseStr(String s, int k) {char[] ch s.toCharArray();for(int i 0;i ch.length;i 2 * k){int start i;// 判断尾数够不够k个来取决end指针的位置int end Math.min(ch.length - 1,start k - 1);while(start end){char temp ch[start];ch[start] ch[end];ch[end] temp;start;end--;}}return new String(ch);}
} 建议本题又进阶了自己先去独立做一做然后在看题解对代码技巧会有很深的体会。 题目链接/文章讲解/视频讲解代码随想录 卡码网54.替换数字 卡码网题目链接(opens new window) 给定一个字符串 s它包含小写字母和数字字符请编写一个函数将字符串中的字母字符保持不变而将每个数字字符替换为number。 例如对于输入字符串 a1b2c3函数应该将其转换为 anumberbnumbercnumber。 对于输入字符串 a5b函数应该将其转换为 anumberb 输入一个字符串 s,s 仅包含小写字母和数字字符。 输出打印一个新的字符串其中每个数字字符都被替换为了number 样例输入a1b2c3 样例输出anumberbnumbercnumber 数据范围1 s.length 10000 如果想把这道题目做到极致就不要只用额外的辅助空间了 不过使用Java和Python刷题的录友一定要使用辅助空间因为Java和Python里的string不能修改
首先扩充数组到每个数字字符替换成 number 之后的大小。
例如 字符串 a5b 的长度为3那么 将 数字字符变成字符串 number 之后的字符串为 anumberb 长度为 8。
如图 然后从后向前替换数字字符也就是双指针法过程如下i指向新长度的末尾j指向旧长度的末尾。 有同学问了为什么要从后向前填充从前向后填充不行么
从前向后填充就是O(n^2)的算法了因为每次添加元素都要将添加元素之后的所有元素整体向后移动。
其实很多数组填充类的问题其做法都是先预先给数组扩容带填充后的大小然后在从后向前进行操作。
这么做有两个好处
不用申请新数组。从后向前填充元素避免了从前向后填充元素时每次添加元素都要将添加元素之后的所有元素向后移动的问题。
解法1
import java.util.Scanner;public class Main {public static String replaceNumber(String s) {int count 0; // 统计数字的个数int sOldSize s.length();for (int i 0; i s.length(); i) {if(Character.isDigit(s.charAt(i))){count;}}// 扩充字符串s的大小也就是每个空格替换成number之后的大小char[] newS new char[s.length() count * 5];int sNewSize newS.length;// 将旧字符串的内容填入新数组System.arraycopy(s.toCharArray(), 0, newS, 0, sOldSize);// 从后先前将空格替换为numberfor (int i sNewSize - 1, j sOldSize - 1; j i; j--, i--) {if (!Character.isDigit(newS[j])) {newS[i] newS[j];} else {newS[i] r;newS[i - 1] e;newS[i - 2] b;newS[i - 3] m;newS[i - 4] u;newS[i - 5] n;i - 5;}}return new String(newS);};public static void main(String[] args) {Scanner scanner new Scanner(System.in);String s scanner.next();System.out.println(replaceNumber(s));scanner.close();}
} 解法2
// 为了还原题目本意先把原数组复制到扩展长度后的新数组然后不再使用原数组、原地对新数组进行操作。
import java.util.*;public class Main {public static void main(String[] args) {Scanner sc new Scanner(System.in);String s sc.next();int len s.length();for (int i 0; i s.length(); i) {if (s.charAt(i) 0 s.charAt(i) 9) {len 5;}}char[] ret new char[len];for (int i 0; i s.length(); i) {ret[i] s.charAt(i);}for (int i s.length() - 1, j len - 1; i 0; i--) {if (0 ret[i] ret[i] 9) {ret[j--] r;ret[j--] e;ret[j--] b;ret[j--] m;ret[j--] u;ret[j--] n;} else {ret[j--] ret[i];}}System.out.println(ret);}
} 建议对于线性数据结构填充或者删除后序处理会高效的多。好好体会一下。 题目链接/文章讲解替换数字
