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 码表中的可打印字符
class Solution {
public void reverseString(char[] s) {
int left = 0;
int right = s.length - 1;
while(left < right){
char temp = s[left];
s[left++] = s[right];
s[right--] = temp;
}
}
}简单的双指针
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
重点在于left和right指针的位置
class Solution {
// 定义一个方法，接收一个字符串s和一个整数k作为参数
public String reverseStr(String s, int k) {
// 将字符串s转换为字符数组arr
char[] arr = s.toCharArray();
// 遍历字符数组arr，步长为2 * k
for(int i = 0;i < arr.length;i += 2 * k){
// 初始化左指针left为当前索引i
int left = i;
// 判断尾数够不够k个来取决end指针的位置
int right = Math.min(arr.length - 1,left + k - 1);
// 当左指针小于右指针时，执行循环
while(left < right){
// 交换左右指针所指向的字符
char temp = arr[left];
arr[left++] = arr[right];
arr[right--] = temp;
}
}
// 将字符数组arr转换为字符串并返回
return new String(arr);
}
}
151.反转字符串中的单词
中等
给你一个字符串 s ，请你反转字符串中 单词 的顺序。
单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。
示例 1：
输入：s = "the sky is blue" 输出："blue is sky the"
示例 2：
输入：s = " hello world " 输出："world hello" 解释：反转后的字符串中不能存在前导空格和尾随空格。
示例 3：
输入：s = "a good example" 输出："example good a" 解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。
提示：
1 <= s.length <= 104s包含英文大小写字母、数字和空格' 's中 至少存在一个 单词
进阶：如果字符串在你使用的编程语言中是一种可变数据类型，请尝试使用 O(1) 额外空间复杂度的 原地 解法。
class Solution {
// 反转字符串的方法
public String reverseString(String str) {
char[] s = str.toCharArray();
int left = 0;
int right = s.length - 1;
while(left < right){
char temp = s[left];
s[left++] = s[right];
s[right--] = temp;
}
return new String(s);
}
// 反转单词的方法
public String reverseWords(String s) {
s = reverseString(s); // 先反转整个字符串
StringBuilder builder = new StringBuilder(); // 创建一个StringBuilder对象，用于存储反转后的单词
char[] arr = s.toCharArray(); // 将字符串转换为字符数组
int left = 0; // 初始化左指针
while(left < arr.length && arr[left] == ' '){ // 跳过字符串开头的空格
left++;
}
int right = left; // 初始化右指针
for(;right < arr.length; right++){ // 遍历字符数组
if(arr[right] == ' '){ // 如果遇到空格，说明一个单词结束
String temp = new String(arr,left,right - left); // 截取单词
builder.append(reverseString(temp) + " "); // 反转单词并添加到StringBuilder中
left = right; // 更新左指针
while(left < arr.length && arr[left] == ' '){ // 跳过单词之间的空格
left++;
right++;
}
}
if(right == arr.length - 1 && arr[right] != ' '){ // 如果到达字符串末尾且最后一个字符不是空格，说明还有一个单词没有处理
String temp = new String(arr,left,right - left + 1); // 截取最后一个单词
builder.append(reverseString(temp) + " "); // 反转单词并添加到StringBuilder中
break;
}
}
builder.deleteCharAt(builder.length() - 1); // 删除最后一个多余的空格
return builder.toString(); // 返回反转后的单词字符串
}
}
28.找出字符串中第一个匹配项的下标
459.重复的子字符串
已解答
简单
相关标签
相关企业
给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
示例 1:
输入: s = "abab" 输出: true 解释: 可由子串 "ab" 重复两次构成。
示例 2:
输入: s = "aba" 输出: false
示例 3:
输入: s = "abcabcabcabc" 输出: true 解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)
提示：
1 <= s.length <= 104s由小写英文字母组成
class Solution {
public boolean repeatedSubstringPattern(String s) {
if (s.equals("")) return false;
int len = s.length();
// 原串加个空格(哨兵)，使下标从1开始，这样j从0开始，也不用初始化了
s = " " + s;
char[] chars = s.toCharArray();
int[] next = new int[len + 1];
// 构造 next 数组过程，j从0开始(空格)，i从2开始
for (int i = 2, j = 0; i <= len; i++) {
// 匹配不成功，j回到前一位置 next 数组所对应的值
while (j > 0 && chars[i] != chars[j + 1]) j = next[j];
// 匹配成功，j往后移
if (chars[i] == chars[j + 1]) j++;
// 更新 next 数组的值
next[i] = j;
}
// 最后判断是否是重复的子字符串，这里 next[len] 即代表next数组末尾的值
if (next[len] > 0 && len % (len - next[len]) == 0) {
return true;
}
return false;
}
}
