LeetCode 151.翻转字符串里的单词
题目描述
给你一个字符串 s ，请你反转字符串中 单词 的顺序。
单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
**注意：**输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。
示例
输入：s = "the sky is blue"
输出："blue is sky the"
题目链接
https://leetcode.cn/problems/reverse-words-in-a-string/description/
解题思路
- 清除多余的空格
- 整个字符串反转
- 每个单词翻转
class Solution {
public String reverseWords(String s) {
StringBuilder sb = new StringBuilder();
char prev = ' ';
// 去除多余空格
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == ' ' && prev == ' ') {
continue;
} else {
sb.append(s.charAt(i));
prev = s.charAt(i);
}
}
String str = sb.toString();
// 取出末尾空格
if (str.charAt(str.length() - 1) == ' ') {
str = str.substring(0, str.length() - 1);
}
// 拆分为单词
String[] parts = str.split(" ");
sb = new StringBuilder();
// 逐个单词反转
for (String part : parts) {
sb.append(reserve(part) + " ");
}
return reserve(sb.toString()).substring(1);
}
public String reserve(String s) {
char[] ch = s.toCharArray();
int left = 0, right = ch.length - 1;
while (left < right) {
char temp = ch[left];
ch[left] = ch[right];
ch[right] = temp;
left++;
right--;
}
return new String(ch);
}
}
不实用 StringBuilder
class Solution {
public String reverseWords(String s) {
char[] ch = s.toCharArray();
int start = 0;
// 去除前驱空格
while (ch[start] == ' ') {
start++;
}
int end = start;
// 取出中间和末尾空格
for (int i = start; i < ch.length; i++) {
if (i < ch.length - 1 && ch[i] == ' ' && ch[i + 1] == ' ') {
continue;
}
ch[end++] = ch[i];
}
if (ch[end - 1] == ' ') {
end--;
}
// 创建新数组
char[] str = new char[end - start];
for (int i = 0; i < end - start; i++) {
str[i] = ch[i + start];
}
int prev = 0;
// 反转整个数组
reverse(str, 0, str.length - 1);
// 反转单词
for (int i = 0; i < str.length; i++) {
if (str[i] == ' ' ) {
reverse(str, prev, i - 1);
prev = i + 1;
}
}
// 反转最后一个单词
reverse(str, prev, str.length - 1);
return new String(str);
}
public void reverse(char[] ch, int start, int end) {
while (start < end) {
char temp = ch[start];
ch[start] = ch[end];
ch[end] = temp;
start++;
end--;
}
}
}
卡码网：55.右旋转字符串
题目描述
字符串的右旋转操作是把字符串尾部的若干个字符转移到字符串的前面。给定一个字符串 s 和一个正整数 k，请编写一个函数，将字符串中的后面 k 个字符移到字符串的前面，实现字符串的右旋转操作。
例如，对于输入字符串 "abcdefg" 和整数 2，函数应该将其转换为 "fgabcde"。
输入描述
输入共包含两行，第一行为一个正整数 k，代表右旋转的位数。第二行为字符串 s，代表需要旋转的字符串。
输出描述
输出共一行，为进行了右旋转操作后的字符串。
输入示例
2
abcdefg输出示例
fgabcde
题目链接
https://kamacoder.com/problempage.php?pid=1065
解题思路
要得到目标字符串, 可以分为三步
- 翻转整个字符串
- 反转前
k个字符 - 反转剩下的字符
解决代码一
// 直接末尾k个和前n - k个进行拼接
import java.util.*;
class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int k = in.nextInt();
String s = in.next();
System.out.println(s.substring(s.length() - k) + s.substring(0, s.length() - k));
}
}
解决代码二
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int k = scanner.nextInt();
String s = scanner.next();
char[] ch = s.toCharArray();
reverse(ch, 0, ch.length - 1);
reverse(ch, 0, k - 1);
reverse(ch, k, ch.length - 1);
System.out.println(new String(ch));
}
public static void reverse(char[] ch, int l, int r){
while(l < r){
char temp = ch[l];
ch[l] = ch[r];
ch[r] = temp;
l++;
r--;
}
}
}
LeetCode 28. 实现 strStr()
题目描述
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。
示例
输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。
题目链接
https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/description/
解题思路
暴力匹配
// 7m44s
class Solution {
public int strStr(String haystack, String needle) {
if (needle.length() > haystack.length()) {
return -1;
}
for (int i = 0; i <= haystack.length() - needle.length(); i++) {
int hayIndex = i;
boolean flag = true;
for (int j = 0; j < needle.length(); j++) {
if (haystack.charAt(hayIndex) != needle.charAt(j)) {
flag = false;
break;
}
hayIndex++;
}
if (flag) {
return i;
}
}
return -1;
}
}
可以用 h和 n代表遍历到这两个字符串转换为数组后的下标位置, 如果不同则重置 h和 n的大小。否则持续遍历, 直至 n = needle.length。
class Solution {
public int strStr(String haystack, String needle) {
char[] hay = haystack.toCharArray();
char[] need = needle.toCharArray();
//haystack长度小于needle直接退出
if(hay.length < need.length)
return -1;
//hay搜索下标为h，needle搜索下标n，hay[h] == need[n], h++,n++; n == needle.length, return h - n;
//hay[h] != need[n], h = h - n + 1, n = 0
int h = 0, n = 0;
while(n < need.length && h < hay.length){
if(hay[h] == need[n]){
h++;
n++;
}
else{
h = h - n + 1;
n = 0;
}
}
if(n == need.length)
return h - n;
else
return -1;
}
}
kmp匹配
class Solution {
public int strStr(String haystack, String needle) {
int[] next = getNext(needle);
int nedInex = 0;
// 主串从0 -> n走，模式串根据next数组跳
for (int i = 0; i < haystack.length(); i++) {
while (nedInex > 0 && needle.charAt(nedInex) != haystack.charAt(i))
nedInex = next[nedInex - 1];
if (needle.charAt(nedInex) == haystack.charAt(i))
nedInex++;
if (nedInex == needle.length())
return i - needle.length() + 1;
}
return -1;
}
public int[] getNext(String s) {
int[] next = new int[s.length()];
// 当前公共前后缀长度
int j = 0;
next[0] = 0;
for (int i = 1; i < s.length(); i++) {
// 查找最长前后缀长度
while (j > 0 && s.charAt(j) != s.charAt(i)) {
j = next[j - 1];
}
if (s.charAt(j) == s.charAt(i)) j++;
next[i] = j;
}
return next;
}
}
LeetCode 459.重复的子字符串
题目描述
给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
示例
输入: s = "abab"
输出: true
解释: 可由子串 "ab" 重复两次构成。
题目链接
https://leetcode.cn/problems/repeated-substring-pattern/description/
解题思路
暴力求解
// 12m11s
class Solution {
public boolean repeatedSubstringPattern(String s) {
for (int sonLen = 1; sonLen <= s.length() / 2; sonLen++) {
String son = s.substring(0, sonLen);
if (kmp(son, s.substring(sonLen))) {
return true;
}
}
return false;
}
public boolean matchString(String s1, String s2) {
if (s2.length() % s1.length() != 0) {
return false;
}
for (int i = 0; i <= s2.length() - s1.length(); i += s1.length()) {
if (!s1.equals(s2.substring(i, i + s1.length()))) {
return false;
}
}
return true;
}
}
移动匹配
如果一个字符串可以由它的字串组成，则两个字符串拼接后去头去尾的字符串一定含有它本身
// 充分性
假设字符串为
[a][b]][c][a][b][c]
拼接后
[a][b][c][a][b][c][a][b][c][a][b][c]
去头去尾
[b][c][a][b][c][a][b][c][a][b]
含有它本身
[b][c] [a][b][c][a][b][c] [a][b]
// 必要性
假设字符串为
[a][b][c][d][e][f]
拼接后
[a][b][c][d][e][f][a][b][c][d][e][f]
去头去尾
[b][c][d][e][f][a][b][c][d][e]
假设含有它本身的是
[b][c][d] [e][f][a][b][c][d] [e]
[a][b][c][d][e][f]
则
[a][b] = [e][f]
[a][b] = [c][d]
[c][d] = [e][f]
字符串可由[a][b]组成
class Solution {
public boolean repeatedSubstringPattern(String s) {
String ss = s + s;
return ss.substring(1, ss.length() - 1).contains(s);
}
}
评论