当前位置：首页 > news >正文

代码随想录之字符串

news 2024/10/29 0:14:37

代码随想录之字符串篇

T344-反转字符串

见力扣第344题[反转字符串]

题目描述

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须**原地修改输入数组**、使用 O(1) 的额外空间解决这一问题。

示例 1：

输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]

我的思路

使用双指针交换头尾的字符
循环条件为l < r

/*** 反转字符串* @param s*/
public void reverseString(char[] s) {if (s.length <= 1) return;int l = 0;int r = s.length - 1;while (l < r) {char temp = s[l];s[l] = s[r];s[r] = temp;l++;r--;}
}

时间复杂度： $O (N)$ ，遍历一遍数组
空间复杂度： $O (1)$ ，额外的临时变量保存交换的字符

T541-反转字符串II

见力扣第541题[反转字符串II]

题目描述

给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。

如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

示例 1：

输入：s = "abcdefg", k = 2
输出："bacdfeg"

我的思路

使用滑动窗口，窗口固定为2k的长度
在窗口里面反转字符

public String reverseStr(String s, int k) {if (s.length() <= 1) return s;char[] chars = s.toCharArray();int l = 0;int r = 2 * k - 1;while (r < s.length()) {// 窗口内的前k个字符反转int i = l;int j = l + k - 1;while (i < j) {swap(chars, i, j);i++;j--;}l = r + 1;r = l + 2 * k - 1;}r = s.length() - 1; // r 置位为末尾// 判断 l 和 r 之间窗口的大小if (r - l + 1 >= k) {// 反转前 k 个字符r = l + k - 1;}while (l < r) {swap(chars, l, r);l++; r--;}return new String(chars);
}private void swap(char[] chars, int l, int r) {char temp = chars[l];chars[l] = chars[r];chars[r] = temp;
}

时间复杂度： $O (N)$ ，遍历了一遍字符数组
空间复杂度： $O (N)$ ，使用了额外的空间存储char[]数组

T1844-将所有的数字用字符替代

见力扣第1844题[将所有的数字用字符替代]

题目描述

给你一个下标从 0 开始的字符串 s ，它的偶数下标处为小写英文字母，奇数下标处为数字。

定义一个函数 shift(c, x) ，其中 c 是一个字符且 x 是一个数字，函数返回字母表中 c 后面第 x 个字符。

比方说，shift('a', 5) = 'f' 和 shift('x', 0) = 'x' 。

对于每个奇数下标 i ，你需要将数字 s[i] 用 shift(s[i-1], s[i]) 替换。

请你替换所有数字以后，将字符串 s 返回。题目保证 shift(s[i-1], s[i]) 不会超过 'z' 。

示例 1：

输入：s = "a1c1e1"
输出："abcdef"
解释：数字被替换结果如下：
- s[1] -> shift('a',1) = 'b'
- s[3] -> shift('c',1) = 'd'
- s[5] -> shift('e',1) = 'f'

我的思路

模拟，将指定位置设置为字符char[i] = (char)(char[i - 1] + (int)(char[i] - '0'))

/*** 将所有数字用字符替换* @param s* @return*/
public String replaceDigits(String s) {if (s.length() <= 1) return s;char[] chars = s.toCharArray();for (int i = 1; i < chars.length; i+=2) {chars[i] = (char)(chars[i - 1] + (int) (chars[i] - '0'));}return new String(chars);
}

时间复杂度： $O (N)$ ，遍历char[]数组的偶数位
空间复杂度： $O (N)$ ，额外空间char[]操作字符串

T151-反转字符串中的单词

见力扣第151题[反转字符串中的单词]

题目描述

给你一个字符串 s ，请你反转字符串中单词的顺序。

单词是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的单词分隔开。

返回单词顺序颠倒且单词之间用单个空格连接的结果字符串。

**注意：**输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

示例 1：

输入：s = "the sky is blue"
输出："blue is sky the"

我的思路

使用split(" ")提取单词
倒序遍历单词数组，使用StringBuilder接收，添加空格
去除最后一个空格

public String reverseWords(String s) {String[] words = s.split(" ");StringBuilder sb = new StringBuilder();for (int i = words.length - 1; i >= 0; i--) {if (words[i].length() > 0) {sb.append(words[i]).append(" ");}}return sb.toString().trim();
}

时间复杂度： $O (N)$
空间复杂度： $O (N)$

T796-旋转字符串

见力扣第796题[旋转字符串]

题目描述

给定两个字符串, s 和 goal。如果在若干次旋转操作之后，s 能变成 goal ，那么返回 true 。

s 的 旋转操作 就是将 s 最左边的字符移动到最右边。

例如, 若 s = 'abcde'，在旋转一次之后结果就是'bcdea' 。

示例 1:

输入: s = "abcde", goal = "cdeab"
输出: true

我的思路

首先比较两个字符串的长度是否相等，如果不相等直接返回false
将两个s拼接起来，即s + s，已经包含了旋转操作的所有可能性，再判断goal是否在s中

/*** 旋转字符串* @param s* @param goal* @return*/
public boolean rotateString(String s, String goal) {if (s.length() != goal.length()) return false;String t = s + s;return t.contains(goal);
}

时间复杂度： $O (N)$ ，contains()方法是由KMP算法实现的
空间复杂度： $O (N)$ ，使用了额外的空间存储拼接后的字符串s + s

T28-KMP算法

见力扣第28题[KMP算法]

题目描述

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

题解

public int strStr(String haystack, String needle) {int[] next = getNext(needle);int i = 0; // 主串int j = 0; // 字串while (i < haystack.length() && j < needle.length()) {if (j == -1 || haystack.charAt(i) == needle.charAt(j)) {i++; j++;} else {j = next[j];}if ( j == needle.length()) return i - j;}return -1;
}private int[] getNext(String needle) {int n = needle.length();int j = 0; // 主串指针，不回溯int k = -1; // 子串指针int[] next = new int[n];next[0] = -1;// 模式串对自身进行匹配while (j < n-1) {if (k == -1 || needle.charAt(j) == needle.charAt(k)) { // 匹配成功，或者刚开始匹配k++; j++;next[j] = k; // 表示最长公共前后缀的长度 回溯指针为第一个不满足的，正好是 k - 1 + 1} else {k = next[k]; // 回溯到最长公共前后缀的地方}}return next;
}

时间复杂度： $O (N)$
空间复杂度： $O (N)$

T459-重复的子字符串

见力扣第459题[重复的子字符串]

题目描述

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

示例 1:

输入: s = "abab"
输出: true
解释: 可由子串 "ab" 重复两次构成。

我的思路

假设一个字符串是周期的，即s = T * sub，那么两个字符串2s = 2 * T * sub，掐头去尾，一定包含有sub

/*** 重复的字符子串* @param s* @return*/
public boolean repeatedSubstringPattern(String s) {String t = s + s;String trim = t.substring(1, t.length() - 1);return trim.contains(s);
}

方法二：使用KMP算法

使用自定义的KMP算法查询s + s的字符串中索引1~length()-2的位置有没有出现过s

public boolean kmp(String query, String pattern) {int n = query.length();int m = pattern.length();int[] fail = new int[m];Arrays.fill(fail, -1);for (int i = 1; i < m; ++i) {int j = fail[i - 1];while (j != -1 && pattern.charAt(j + 1) != pattern.charAt(i)) {j = fail[j];}if (pattern.charAt(j + 1) == pattern.charAt(i)) {fail[i] = j + 1;}}int match = -1;for (int i = 1; i < n - 1; ++i) {while (match != -1 && pattern.charAt(match + 1) != query.charAt(i)) {match = fail[match];}if (pattern.charAt(match + 1) == query.charAt(i)) {++match;if (match == m - 1) {return true;}}}return false;
}