06数据结构与算法刷题之【字符串】篇
【摘要】 除了去年11月份以及今年近几月的算法刷题之外，只有在当时20年蓝桥杯准备的时候才刷过一些题，在当时就有接触到一些动归、递归回溯、贪心等等，不过那会也还是一知半解，做的题目也特别少，因为考虑到之后面试有算法题以及数据结构算法对于一个程序员十分重要，我也开始了刷题之路。我目前的学习数据结构与算法及刷题路径：1、学习数据结构的原理以及一些常见算法。2、代码随想录：跟着这个github算法刷题项目进行分类
@[toc]
前言
除了去年11月份以及今年近几月的算法刷题之外，只有在当时20年蓝桥杯准备的时候才刷过一些题，在当时就有接触到一些动归、递归回溯、贪心等等，不过那会也还是一知半解，做的题目也特别少，因为考虑到之后面试有算法题以及数据结构算法对于一个程序员十分重要，我也开始了刷题之路。
我目前的学习数据结构与算法及刷题路径：
1、学习数据结构的原理以及一些常见算法。
2、代码随想录：跟着这个github算法刷题项目进行分类刷，在刷题前可以学习一下对应类别的知识点，而且这里面每道题都讲的很详细。
3、牛客网高频面试101题：牛客网—面试必刷101题，在刷的过程中可以在leetcode同步刷一下。
4、接下来就是力扣上的专栏《剑指offer II》、《程序员面试金典（第 6 版）》…有对应的精选题单来对着刷即可。
5、大部分的高频面试、算法题刷完后，就可以指定力扣分类专栏进行一下刷题了。
刚开始刷的时候真的是很痛苦的，想到去年一道题可能就需要好几小时，真的就很难受的，不过熬过来一切都会好起来，随着题量的增多，很多题目你看到就会知道使用什么数据结构或者算法来去求解，并且思考对应的时间空间复杂度，并寻求最优解，我们一起加油！
我的刷题历程
截止2022.8.18：
1、牛客网101题(其中1题是平台案例有问题)：
2、剑指offerII：
力扣总记录数：
加油加油！
剑指offer
剑指 Offer 58 - II. 左旋转字符串【简单】
题目内容：
字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。
示例 1：
输入: s = "abcdefg", k = 2
输出: "cdefgab"
示例 2：
输入: s = "lrloseumgh", k = 6
输出: "umghlrlose"
思路：
1、翻转字符串
思路：对原始字符数组进行操作，首先整体进行反转，之后对两个区间进行反转。
代码：未申请额外空间，直接在原始串上操作
public String reverseLeftWords(String s, int n) {
//步骤1：整体进行反转，例如："lrloseumgh" => "hgmuesolrl"
char[] chars = s.toCharArray();
reverse(chars, 0, chars.length - 1);
//步骤2：前后两个区间进行反转
reverse(chars, 0, chars.length - 1 - n);//"hgmuesolrl" => "umghesolrl"
reverse(chars, chars.length - n, chars.length - 1);//"umghesolrl" => "umghlrlose"
return new String(chars);
}
/**
* 反转字符数组指定范围内容：[begin,end]
*/
public void reverse(char[] chars, int begin, int end) {
for (int i = begin, j = end; i < j; i++, j--) {
chars[i] ^= chars[j];
chars[j] ^= chars[i];
chars[i] ^= chars[j];
}
}
该解法执行用时2ms，竟然只击败了49.27%，我看了下击败100%的题解，使用的substring与append拼接的方式，在下面NO3中有题解。
2、字符数组
思路：创建一个新的字符数组，依次填充即可。
复杂度分析：时间复杂度O(n)
public String reverseLeftWords(String s, int n) {
char[] chars = new char[s.length()];
int k = 0;
//非左转的先遍历填充
for (int i = n; i < s.length(); i++) {
chars[k++] = s.charAt(i);
}
//需左转的后遍历填充
for (int i = 0; i < n; i++) {
chars[k++] = s.charAt(i);
}
return new String(chars);
}
3、借助API（最高效）
刚开始看到题解我也有点懵，用API反而效率更高啥情况，之后去研究了下，与底层实现有关。该题主要还是核心重点放在NO1题解的思路解法上。
思路：其实与NO2思路填充完全一致，只不过这里使用API来进行字符串截取与拼接。
- 为什么快？与
substring有关，其底层使用的是System.arraycopy进行拷贝。①在NO2中写的for循环拷贝方式若是没有被编译器优化，就是遍历数组操作的字节码，接着执行引擎会根据这些字节码循环获取数组的每个元素再执行拷贝。②而System.arraycopy为JVM内部固有方法，通过手工编写汇编或其他优化方法来进行Java数组拷贝，该方式比for循环更高效尤其数组越大越明显。- 参考文章，上述内容摘自：【java】System.arraycopy为什么快
代码：
public String reverseLeftWords(String s, int n) {
StringBuilder strBuilder = new StringBuilder();
strBuilder.append(s.substring(n));
strBuilder.append(s.substring(0,n));
return strBuilder.toString();
}
剑指 Offer 05. 替换空格【简单】
题目链接：剑指 Offer 05. 替换空格
题目内容：请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
思路：
1、双指针：
思路： 对于字符串中空格=>"%20"，由一个字符填充为3个字符，普通解法就是遍历一遍的过程中遇到空白字符串先将后面的统一移动两个接着进行填充，该思路时间复杂度为O(n^2^)；
所以这里我们使用双指针的方案，首先遍历一遍字符串确定其中有多少个空格对原始字符串进行扩容，紧接着来定义两个指针，一个指针指向原始字符串最后一个位置，另一个指针指向扩展之后最后一个位置，每次移动两个指针同时向前移动，若是左指针碰到空格，右指针进行%、0、2向前以前填充前进两步；若不是空格，右指针指向的值改为左指针当前指向的值，根据此规则不断重复即可！时间复杂度为O(n)。这里我直接引用 代码随想录—题目：剑指Offer 05.替换空格 中的思路图，十分推荐该博主的算法指南，十分清晰
public String replaceSpace(String s) {
//扩充空间，空格数量2倍
StringBuilder str = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
if(s.charAt(i) == ' '){
str.append(" ");
}
}
//若是没有空格直接返回
if(str.length() == 0){
return s;
}
//有空格情况 定义两个指针
int left = s.length() - 1;//左指针：指向原始字符串最后一个位置
s += str.toString();
int right = s.length()-1;//右指针：指向扩展字符串的最后一个位置
char[] chars = s.toCharArray();
while(left>=0){
if(chars[left] == ' '){
chars[right--] = '0';
chars[right--] = '2';
chars[right] = '%';
}else{
chars[right] = chars[left];
}
left--;
right--;
}
return new String(chars);
}
剑指 Offer 58 - I. 翻转单词顺序【简单】
题目内容：输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. “，则输出"student. a am I”。
思路：
1、从后往前排除空格法
优化前(Stringbuilder拼接)：
思路：从前往后进行遍历，遇到空格往后移动一步，遇到非空格先记录下当前索引，接着一直遍历到该单词的后一个位置，取出该单词最终进行拼接返回。
代码：
//"the sky is blue" => "blue is sky the"
public String reverseWords(String s) {
StringBuilder str = new StringBuilder();
int i = 0;
//遍历字符串结束
while(i<s.length()){
//过滤空字符串
while(i<s.length() && s.charAt(i) == ' '){i++;}
if( i == s.length()){
break;
}
int temp = i;
while(i<s.length() && s.charAt(i) != ' '){i++;}
String word = s.substring(temp,i);
str = new StringBuilder(word).append(" ").append(str);
}
if(str.length()>0){
return str.substring(0,str.length() - 1);
}
return "";
}
这里直接使用了String的api来进行截取字符串操作，并且来进行合并多个单词时频繁创建StringBuilder，不仅仅影响时间还有空间复杂度。
优化后(char[]，时间复杂度最优解)：
思路：这里是从后往前进行遍历，首先遇到!=空格的先记录索引left，紧接着继续向前移动直到为邻接点或者=空格停止，此时我们就能够拿到对应单词的范围索引，将该单词取出依次存储到新字符数组中。
代码：时间复杂度O(n)、空间复杂度O(n)
- 这里是没有任何API进行调用的，纯对字符数组进行操作，所以比优化前的效果好很多
代码：
public String reverseWords(String s) {
//源字符数组
char[] initialArr = s.toCharArray();
//新字符数组
char[] newArr = new char[initialArr.length+1];//下面循环添加"单词 "，最终末尾的空格不会返回
int newArrPos = 0;
//i来进行整体对源字符数组从后往前遍历
int i = initialArr.length-1;
while(i>=0){
while(i>=0 && initialArr[i] == ' '){i--;} //跳过空格
//此时i位置是边界或!=空格，先记录当前索引，之后的while用来确定单词的首字母的位置
int right = i;
while(i>=0 && initialArr[i] != ' '){i--;}
//指定区间单词取出(由于i为首字母的前一位，所以这里+1,)，取出的每组末尾都带有一个空格
for (int j = i+1; j <= right; j++) {
newArr[newArrPos++] = initialArr[j];
if(j == right){
newArr[newArrPos++] = ' ';//空格
}
}
}
//若是原始字符串没有单词，直接返回空字符串；若是有单词，返回0-末尾空格索引前范围的字符数组(转成String返回)
if(newArrPos == 0){
return "";
}else{
return new String(newArr,0,newArrPos-1);
}
}
No2：双反转+移位
思路：并没有开辟新的数组或字符串来进行拼接，而是在原始字符数组上来进行操作。
①反转字符串 "the sky is blue "=> " eulb si yks eht"
②遍历" eulb si yks eht"，过程中先对某个单词进行反转再移位
- 对第一个单词进行操作举例：
" eulb si yks eht"=反转>" blue si yks eht"=移位>"blue si yks eht"
代码：时间复杂度O(n)、空间复杂度O(1)
/**
* 空间复杂度O(1)解法
*/
public String reverseWords(String s) {
//步骤1：字符串整体反转（此时其中的单词也都反转了）
char[] initialArr = s.toCharArray();
reverse(initialArr, 0, s.length() - 1);
//步骤2：遍历循环字符串
int k = 0;
for (int i = 0; i < initialArr.length; i++) {
if (initialArr[i] == ' ') {
continue;
}
int tempCur = i;
while (i < initialArr.length && initialArr[i] != ' ') {
i++;
}
for (int j = tempCur; j < i; j++) {
if (j == tempCur) { //遍历开始前
reverse(initialArr, tempCur, i - 1);//对指定范围字符串进行反转，不反转从后往前遍历一个个填充有问题
}
initialArr[k++] = initialArr[j];
if (j == i - 1) { //遍历结束
//避免越界情况，例如=> "asdasd df f"，不加判断最后就会数组越界
if (k < initialArr.length) {
initialArr[k++] = ' ';
}
}
}
}
if (k == 0) {
return "";
} else {
//参数三：以防出现如"asdasd df f"=>"f df asdasd"正好凑满不需要省略空格情况
return new String(initialArr, 0, (k == initialArr.length) && (initialArr[k - 1] != ' ') ? k : k - 1);
}
}
public void reverse(char[] chars, int begin, int end) {
for (int i = begin, j = end; i < j; i++, j--) {
chars[i] ^= chars[j];
chars[j] ^= chars[i];
chars[i] ^= chars[j];
}
}
No3：拆成多组字符串来进行拼接
复杂度分析：时间复杂度O(n)，空间复杂度O(n)
class Solution {
//api方法：拆成多组，然后从后往前进行添加
public String reverseWords(String s) {
String[] str = s.trim().split(" ");
StringBuilder b = new StringBuilder();
for (int i = str.length - 1; i >= 0; i--) {
//若是碰到空单词进行跳过
if ("".equals(str[i])) {
continue;
}
b.append(str[i]);
if (i != 0) {
b.append(" ");
}
}
return b.toString();
}
}
剑指 Offer 67. 把字符串转换成整数【中等】
题目内容：
写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。
首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。
当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。
该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。
注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。
在任何情况下，若函数不能进行有效的转换时，请返回 0。
思路：
1、越界处理
System.out.println(Integer.MAX_VALUE);//2147483647
System.out.println(Integer.MAX_VALUE + 1);//-2147483648
System.out.println(Integer.MIN_VALUE);//-2147483648
System.out.println(Integer.MIN_VALUE - 1);//2147483647
复杂度分析：时间复杂度O(n)，空间复杂度O(1)
在进行合并前来进行判断校验
class Solution {
//注意点
//1、截止到数字前只有负号或者空白字符才有效
//2、若是第一个非空白字符或负号，那么无法有效转换数字
//3、若是越界int类型，那么返回负数或正数的最大值
//步骤：①去除空白字符。②确定第一个字符是否是正负数，不是直接返回。③来进行遍历，过程中需要去进行校验是否有越界情况
//负数最小：-2147483648 正数最大：2147483647
public int strToInt(String str) {
//1、去除空格
char[] arr = str.trim().toCharArray();
if (arr == null || arr.length == 0) {
return 0;
}
int sign = 1;
int res = 0, bndry = Integer.MAX_VALUE / 10;//bndry是214748364
int i = 1;//初始的遍历位置
if (arr[0] == '-') {
sign = -1;
}else if (arr[0] != '+') {
i = 0;
}
//开始进行遍历
for (int j = i; j < arr.length; j++) {
//若是非数字直接结束
if (arr[j] < '0' || arr[j] > '9') {
break;
}
//这里很巧妙，利用最后一位是否>'7'来表示是否越界
if (res > bndry || (res == bndry && arr[j] > '7')) {
return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
}
res = res * 10 + arr[j] - '0';
}
return sign * res;
}
}
其中同样可以进行优化，针对于trim()我们来自己手写实现，将对应trim()行替换为下面的：
if (str == null || str.length() == 0) {
return 0;
}
char[] arr = str.toCharArray();
int i = 0;
while (i < arr.length && arr[i] == ' ') {
i++;
}
if (i == arr.length) {
return 0;
}
i = i + 1;//进位1
完整的是：
public int strToInt(String str) {
if (str == null || str.length() == 0) {
return 0;
}
//1、去除空格
char[] arr = str.toCharArray();
int i = 0;
while (i < arr.length && arr[i] == ' ') {
i++;
}
if (i == arr.length) {
return 0;
}
i = i + 1;//进位1
int sign = 1;
int res = 0, bndry = Integer.MAX_VALUE / 10;//bndry是214748364
if (arr[i - 1] == '-') {
sign = -1;
}else if (arr[i - 1] != '+') {
i = i - 1;
}
//开始进行遍历
for (int j = i; j < arr.length; j++) {
//若是非数字直接结束
if (arr[j] < '0' || arr[j] > '9') {
break;
}
//这里很巧妙，利用最后一位是否>'7'来表示是否越界
if (res > bndry || (res == bndry && arr[j] > '7')) {
return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
}
res = res * 10 + arr[j] - '0';
}
return sign * res;
}
剑指 Offer 20. 表示数值的字符串【中等】
题目内容：
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。
数值（按顺序）可以分成以下几个部分：
若干空格
一个 小数 或者 整数
（可选）一个 'e' 或 'E' ，后面跟着一个 整数
若干空格
小数（按顺序）可以分成以下几个部分：
（可选）一个符号字符（'+' 或 '-'）
下述格式之一：
至少一位数字，后面跟着一个点 '.'
至少一位数字，后面跟着一个点 '.' ，后面再跟着至少一位数字
一个点 '.' ，后面跟着至少一位数字
整数（按顺序）可以分成以下几个部分：
（可选）一个符号字符（'+' 或 '-'）
至少一位数字
部分数值列举如下：
["+100", "5e2", "-123", "3.1416", "-1E-16", "0123"]
部分非数值列举如下：
["12e", "1a3.14", "1.2.3", "+-5", "12e+5.4"]
思路：
1、有限状态机
2、遍历判断状态校验
复杂度分析：时间复杂度O(n)；空间复杂度O(1)
class Solution {
//+-号：出现在第一个位置或者E or e后一个位置合法
//.：前面不能出现.或者e
//e or E：e之前不能出现e，且必须有数字。e之后必须要有数字（我们设置isNum=false即可）
public boolean isNumber(String s) {
//三个状态量
boolean isNum = false;
boolean isE = false;
boolean isDot = false;
//去除空格
s = s.trim();
char[] arr = s.toCharArray();
for (int i = 0; i < arr.length; i++) {
char ch = arr[i];
//首先判断数字
if (ch >= '0' && ch <= '9') {
isNum = true;
}else if (ch == '+' || ch == '-') { //判断 + - 号
if (i != 0 && arr[i - 1] != 'e' && arr[i - 1] != 'E') {
return false;
}
}else if (ch == '.') { //判断.号
if (isDot || isE) {
return false;
}
isDot = true;
}else if (ch == 'e' || ch == 'E') { //判断e
if (isE || !isNum) {
return false;
}
isE = true;
isNum = false;//e之后必须要有数字，防止出现12e之类
}else { //其他字符
return false;
}
}
return isNum;
}
}
剑指 Offer 44. 数字序列中某一位的数字【中等】
题目内容：数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。
请写一个函数，求任意第n位对应的数字。
思路：
1、迭代求整（找规律）
关键：start(新的n位数开始位置)、digit（位数）、count（当前位数有的个数）
复杂度分析：时间复杂度O(logn)；空间复杂度O(logn)
class Solution {
//范围 位数 数量
//0-9 1 10
//10-99 2 180
//100-999 3 2700
//start digit 9 * start * digit
//1、找到指定的数位 n = n - count
//2、确定数字范围值 num = 10 + (n - 1) / digit
//3、找到对应的索引 charAt((n - 1) % digit) - '0'
public int findNthDigit(int n) {
int start = 1;
long digit = 1;
long count = 9;
//1、确定数位，在哪个档n
while (n > count) {
n -= count;
digit++;
start *= 10;
count = 9 * digit * start;
}
//2、求得实际的值
long num = start + (n - 1) / digit;
//3、确定指定的索引数字
return Long.toString(num).charAt((int)((n - 1) % digit)) - '0';
}
}
数组中出现次数超过一半的数字（28）
题目描述
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
程序代码：哈希表来进行存储计算。
程序代码：
//方式一：Map进行筛检法
//假设数组是非空的，并且给定的数组总是存在多数元素
/**
* 执行用时：13 ms, 在所有 Java 提交中击败了20.01%的用户
* 内存消耗：46.3 MB, 在所有 Java 提交中击败了16.10%的用户
*/
public int majorityElement(int[] nums) {
if (nums == null || nums.length == 0){
return 0;
}
if (nums.length == 1) {
return nums[0];
}
Map<Integer,Integer> numsMap = new HashMap<>();
for (int num : nums) {
//判断是否有该key，有的话来进行判断当前值，没有的话进行赋值
Integer value = numsMap.getOrDefault(num, 0);
if (value == 0) {
numsMap.put(num, 1);
}else {
//注意：数量是大于总数的二分之一
if (value + 1 > nums.length / 2) {
return num;
}
numsMap.put(num, value + 1);
}
}
return 0;
}
执行用时：13 ms, 在所有 Java 提交中击败了20.01%的用户
内存消耗：46.3 MB, 在所有 Java 提交中击败了16.10%的用户
//方式二：排序法
/**
* 执行用时：2 ms, 在所有 Java 提交中击败了54.68%的用户
* 内存消耗：44.6 MB, 在所有 Java 提交中击败了68.89%的用户
*/
public int majorityElement(int[] nums) {
if (nums == null || nums.length == 0){
return 0;
}
if (nums.length == 1) {
return nums[0];
}
//O(logn)
Arrays.sort(nums);
int medium = nums.length / 2;
if (nums[medium] == nums[medium - 1] || nums[medium] == nums[medium + 1]){ //奇、偶数情况
return nums[medium];
}
return 0;
}
最优解来了：O(n)
注意后半段话：假设数组是非空的，并且给定的数组总是存在多数元素。题目给定案例是大于一半数字的。
思路：既然要找出现次数大于一半元素，那么可以采用抵消法。
//方式三：抵消法，数组必定存在多数
/**
* 执行用时：1 ms, 在所有 Java 提交中击败了99.96%的用户
* 内存消耗：44.7 MB, 在所有 Java 提交中击败了53.99%的用户
*/
public int majorityElement(int[] nums) {
int curMaxNum = 0;
int counts = 0;
for (int i = 0; i < nums.length; i++) {
if (counts == 0) {
curMaxNum = nums[i];
}
//核心抵消思路
if (nums[i] == curMaxNum) {
counts++;
}else{
counts--;
}
}
return curMaxNum;
}
最小的K个数（29）
题目描述
输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
题解1：
/**
* 执行用时：6 ms, 在所有 Java 提交中击败了72.26%的用户
* 内存消耗：42.5 MB, 在所有 Java 提交中击败了21.53%的用户
*/
//1、API调用排序法
//输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
public int[] getLeastNumbers(int[] arr, int k) {
if (arr == null || arr.length <= k){
return arr;
}
//1、排序
// Arrays.sort(int[]) 使用双轴快速排序算法,时间复杂度为0(logn)
// Collections.sort(List) 是一种优化过的合并排序算法,时间复杂度是O(n)
Arrays.sort(arr);
//2、取出前k个数（优化：使用API取）
// int[] numArr = new int[k];
// for (int i = 0; i < k; i++) {
// numArr[i] = arr[i];
// }
// return numArr;
return Arrays.copyOfRange(arr, 0, k);//[0，4)
}
其他思路：手写快排来进行测试
效率最高方式：待探索，手写
//执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
//内存消耗：42.3 MB, 在所有 Java 提交中击败了30.04%的用户
// 快排 不用排全部/荷兰国旗快排
// 优先级队列（堆）
// 二叉搜索树
public int[] getLeastNumbers(int[] arr, int k) {
quickSort(arr, k, 0, arr.length-1);
return Arrays.copyOfRange(arr, 0, k);//使用API来优化进行复制
}
public void quickSort(int[] arr, int k, int lo, int hi){
int res = partition(arr, lo, hi);
if(k == res) return;
else if(k < res){
quickSort(arr, k, lo, res-1);
}else{
quickSort(arr, k, res+1, hi);
}
}
public int partition(int[] nums, int lo, int hi){
if(hi-lo < 1) return lo;
int tmp = nums[lo];
int l = lo;
int r = hi;
while(l < r){
while(nums[r] >= tmp && l < r) r--;
nums[l] = nums[r];
while(nums[l] <= tmp && l < r) l++;
nums[r] = nums[l];
}
nums[l] = tmp;
return l;
}
牛客网
字符串变形【简单】
题目链接：字符串变形
题目内容：对于一个长度为 n 字符串，我们需要对它做一些变形。首先这个字符串中包含着一些空格，就像"Hello World"一样，然后我们要做的是把这个字符串中由空格隔开的单词反序，同时反转每个字符的大小写。
思路1：①先反转整个字符串(按照相应的规则)。②然后再对整个字符串中的单词进行单独反转。
复杂度分析：
- 时间复杂度：O(n)
- 空间复杂度：O(n)
import java.util.*;
public class Solution {
public String trans(String s, int n) {
StringBuilder str = new StringBuilder();
for (int i = n-1;i >=0;i--) {
str.append(transfer(s.charAt(i)));
}
//1、获取到反转过后的字符串（按照相应的规则进行转换）
String str1 = str.toString();
//2、再对整个字符串中的各个单词来进行反转
StringBuilder resStr = new StringBuilder();
for(int i = 0;i < n;i++) {
int j = i;
while(j < n && str1.charAt(j) != ' ') {
j++;
}
//获取到这个转换后的字符串
StringBuilder reverseStr = new StringBuilder(str1.substring(i, j));
resStr.append(reverseStr.reverse().toString());
if (j < n && str1.charAt(j) == ' ') {
resStr.append(' ');
}
i = j;
}
return resStr.toString();
}
//按照规则转换
public char transfer(char ch) {
if (ch >= 'a' && ch <= 'z') {
ch -= 32;
}else if (ch >= 'A' && ch <= 'Z') {
ch += 32;
}
return ch;
}
}
思路2：利用栈来进行反转单词顺序。①遍历字符串，将所有单词取出依次入栈。②从栈中弹出不断的进行拼接（需要注意原始字符串初始最后为空格情况）。
复杂度分析：
- 时间复杂度：O(n)，遍历字符串+出栈的单词数量，差不多就是2n。
- 空间复杂度：O(n)，使用了栈这个存储空间，存储了所有的单词。
import java.util.*;
public class Solution {
//利用栈来进行
public String trans(String s, int n) {
Stack<String> stack = new Stack<>();
//遍历字符串
for (int i = 0;i < s.length();i++) {
//遍历得到某个单词
int j = i;
while (j < n && s.charAt(j) != ' ') {
j++;
}
String subStr = s.substring(i, j);
//入栈
stack.push(replaceStr(subStr));
i = j;
}
//使用StringBuilder来进行拼接
StringBuilder builder = new StringBuilder();
//**初始添加空格情况，举例："changlu abc "**
if (s.charAt(n - 1) == ' ') {
builder.append(' ');
}
while (!stack.isEmpty()) {
builder.append(stack.pop());
if (!stack.isEmpty()) {
builder.append(" ");
}
}
return builder.toString();
}
public String replaceStr(String str) {
if (str == null || str.length() == 0) {
return str;
}
char[] chars = str.toCharArray();
for (int i = 0;i < str.length();i++) {
chars[i] = transfer(chars[i]);
}
return new String(chars);
}
//按照规则转换
public char transfer(char ch) {
if (ch >= 'a' && ch <= 'z') {
ch -= 32;
}else if (ch >= 'A' && ch <= 'Z') {
ch += 32;
}
return ch;
}
}
验证IP地址【中等】
做题前知识点
ipv4： 1、十进制数和点来表示，每个地址包含4个十进制数，其范围为 0 - 255。②使用.来分割。
2、IPv4 地址内的数不会以 0 开头，例如 172.16.254.01 是不合法。
ipv6: 1、8组16进制的数字来表示，每组表示 16 比特。
2、可以加入一些以 0 开头的数字，字母可以使用大写，也可以是小写。
3、通过:来分割
问题1：\\.表示什么意思？【ipv4校验】
- 正则中一个单独的点表示任意字符，所有字符都作为分隔符当然不会有任何结果
\\.实际上被转义为两次，\在java中被转换为一个’‘字符，然后’.‘被传给正则，.表示对点字符进行转义，使.就表示字符’.’,而不使用它在正则中的特殊意义
问题2：.split(“,“, -1) 和 .split(“,“) 的区别？【ipv6校验】
- 举例：String a=
"河南省，，金水区";- a.split(",") = [河南省,金水区 ]
- 而
a.split(",",-1) = [河南省, ,金水区 ]，即 .split(",", -1);会保存空值。
做题
题目链接：验证IP地址
题目内容：编写一个函数来验证输入的字符串是否是有效的 IPv4 或 IPv6 地址。
思路1：分割字符串比较法【推荐】
复杂度分析：
- 时间复杂度：O(n)
- 空间复杂度：O(1)
import java.util.*;
public class Solution {
/**
* 验证IP地址
* @param IP string字符串 一个IP地址字符串
* @return string字符串
*/
public String solve (String IP) {
if (isIPV4(IP)) {
return "IPv4";
}else if (isIPV6(IP)) {
return "IPv6";
}else {
return "Neither";
}
}
public boolean isIPV4(String IP) {
//IP.length() > 15：提前结束。【最大：255.255.255.255】
if (IP == null || IP.length() == 0 || IP.length() > 15) {
return false;
}
//额外：校验最后一位是否为.的情况
if (IP.charAt(IP.length() - 1) == '.') {
return false;
}
String[] strs = IP.split("\\.");
if (strs.length != 4) {
return false;
}
//开始进行校验IPV4了
for (String str : strs) {
//判断是否字符串长度为0
if (str.length() == 0) {
return false;
}
//字符串长度>3（如2555）、第一位为o即总长度不为1个的情况（如：01）
if (str.length() > 3 || (str.charAt(0) == '0' && str.length() != 1)) {
return false;
}
//计算数字之和
int num = 0;
for (int i = 0; i < str.length(); i++) {
num = num * 10 + str.charAt(i) - '0';
}
if (num < 0 || num > 255) {
return false;
}
}
return true;
}
//4*8+7=39
public boolean isIPV6(String IP) {
if (IP == null || IP.length() == 0 || IP.length() > 39) {
return false;
}
//额外：校验最后一位是否为:的情况
if (IP.charAt(IP.length() - 1) == ':') {
return false;
}
String[] strs = IP.split(":", -1);//将::中间的空格也作为情况
if (strs.length != 8) {
return false;
}
for (String str : strs) {
if (str.length() == 0 || str.length() > 4) {
return false;
}
for (int i = 0; i < str.length(); i++) {
char ch = str.charAt(i);
//十六进制范围在a-f中
boolean expr = (ch >= 'a' && ch <= 'f' ) || (ch >= 'A' && ch <= 'F') || (ch >= '0' && ch <= '9');
if (!expr) {
return false;
}
}
}
return true;
}
}
【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）