字符串
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”]
func reverseString(s []byte) {
l := 0
r := len(s) - 1
for l < r{
temp := s[l]
s[l] = s[r]
s[r] = temp
l++
r--
}
}
541. 反转字符串II
力扣题目链接(opens new window)
给定一个字符串 s 和一个整数 k，从字符串开头算起, 每计数至 2k 个字符，就反转这 2k 个字符中的前 k 个字符。
如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
示例:
输入: s = “abcdefg”, k = 2 输出: “bacdfeg”
func reverseStr(s string, k int) string {
st := []byte(s)
i := 0
for i = 0; i < len(st); i+=2*k{
l := i
r := i+k - 1
for l < r && r < len(st){
temp := st[l]
st[l] = st[r]
st[r] = temp
l++
r--
}
}
if i > len(st){
i-=2*k
}
if len(st) - i < k {
l := i
r := len(st) - 1
for l < r && r < len(st){
temp := st[l]
st[l] = st[r]
st[r] = temp
l++
r--
}
}else{
}
return string(st)
}
替换数字
卡码网题目链接(opens new window)
给定一个字符串 s，它包含小写字母和数字字符，请编写一个函数，将字符串中的字母字符保持不变，而将每个数字字符替换为number。
例如，对于输入字符串 “a1b2c3”，函数应该将其转换为 “anumberbnumbercnumber”。
对于输入字符串 “a5b”，函数应该将其转换为 “anumberb”
输入：一个字符串 s,s 仅包含小写字母和数字字符。
输出：打印一个新的字符串，其中每个数字字符都被替换为了number
样例输入：a1b2c3
样例输出：anumberbnumbercnumber
数据范围：1 <= s.length < 10000。
package main
import "fmt"
func main(){
var strByte []byte
fmt.Scanln(&strByte)
for i := 0; i < len(strByte); i++{
if strByte[i] <= '9' && strByte[i] >= '0' {
inserElement := []byte{'n','u','m','b','e','r'}
strByte = append(strByte[:i], append(inserElement, strByte[i+1:]...)...)
i = i + len(inserElement) -1
}
}
fmt.Printf(string(strByte))
}
151.翻转字符串里的单词
力扣题目链接(opens new window)
给定一个字符串，逐个翻转字符串中的每个单词。
示例 1： 输入: “the sky is blue” 输出: “blue is sky the”
示例 2： 输入: “ hello world! “ 输出: “world! hello” 解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
示例 3： 输入: “a good example” 输出: “example good a” 解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
#
func reverseWords(s string) string {
b :=[]byte(s)
slow := 0
for i := 0; i < len(b); i++{
if b[i] != ' '{
if slow != 0{
b[slow] = ' '
slow++
}
for i < len(b) && b[i] != ' '{
b[slow] = b[i]
slow++
i++
}
}
}
b = b[0:slow]
reverse(b)
last := 0
for i := 0; i < len(b); i++{
if i == len(b)-1 {
reverse(b[last:i+1])
continue
}
if b[i] == ' ' {
reverse(b[last:i])
last = i+1
}
}
return string(b)
}
func reverse(b []byte) {
l ,r := 0,len(b)-1
for l < r{
temp := b[l]
b[l] = b[r]
b[r] = temp
l++
r--
}
}
java
lass Solution {
public String reverseWords(String s) {
StringBuilder sb = trimSpaces(s);
// 翻转字符串
reverse(sb, 0, sb.length() - 1);
// 翻转每个单词
reverseEachWord(sb);
return sb.toString();
}
public StringBuilder trimSpaces(String s) {
int left = 0, right = s.length() - 1;
// 去掉字符串开头的空白字符
while (left <= right && s.charAt(left) == ' ') {
++left;
}
// 去掉字符串末尾的空白字符
while (left <= right && s.charAt(right) == ' ') {
--right;
}
// 将字符串间多余的空白字符去除
StringBuilder sb = new StringBuilder();
while (left <= right) {
char c = s.charAt(left);
if (c != ' ') {
sb.append(c);
} else if (sb.charAt(sb.length() - 1) != ' ') {
sb.append(c);
}
++left;
}
return sb;
}
public void reverse(StringBuilder sb, int left, int right) {
while (left < right) {
char tmp = sb.charAt(left);
sb.setCharAt(left++, sb.charAt(right));
sb.setCharAt(right--, tmp);
}
}
public void reverseEachWord(StringBuilder sb) {
int n = sb.length();
int start = 0, end = 0;
while (start < n) {
// 循环至单词的末尾
while (end < n && sb.charAt(end) != ' ') {
++end;
}
// 翻转单词
reverse(sb, start, end - 1);
// 更新start，去找下一个单词
start = end + 1;
++end;
}
}
}
作者：力扣官方题解
链接：https://leetcode.cn/problems/reverse-words-in-a-string/solutions/194450/fan-zhuan-zi-fu-chuan-li-de-dan-ci-by-leetcode-sol/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
右旋字符串
卡码网题目链接(opens new window)
字符串的右旋转操作是把字符串尾部的若干个字符转移到字符串的前面。给定一个字符串 s 和一个正整数 k，请编写一个函数，将字符串中的后面 k 个字符移到字符串的前面，实现字符串的右旋转操作。
例如，对于输入字符串 “abcdefg” 和整数 2，函数应该将其转换为 “fgabcde”。
输入：输入共包含两行，第一行为一个正整数 k，代表右旋转的位数。第二行为字符串 s，代表需要旋转的字符串。
输出：输出共一行，为进行了右旋转操作后的字符串。
样例输入：
2 abcdefg 样例输出：
fgabcde 数据范围：1 <= k < 10000, 1 <= s.length < 10000;
#
go语言版本
package main
import "fmt"
func reverse (strByte []byte, l, r int){
for l < r {
strByte[l], strByte[r] = strByte[r], strByte[l]
l++
r--
}
}
func main(){
var str string
var target int
fmt.Scanln(&target)
fmt.Scanln(&str)
strByte := []byte(str)
reverse(strByte, 0, len(strByte) - 1)
reverse(strByte, 0, target - 1)
reverse(strByte, target, len(strByte) - 1)
fmt.Printf(string(strByte))
}
28. 实现 strStr()
链接 力扣题目链接(opens new window)
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。
示例 1：
输入：haystack = “sadbutsad”, needle = “sad” 输出：0 解释：”sad” 在下标 0 和 6 处匹配。 第一个匹配项的下标是 0 ，所以返回 0 。 示例 2：
输入：haystack = “leetcode”, needle = “leeto” 输出：-1 解释：”leeto” 没有在 “leetcode” 中出现，所以返回 -1 。
提示：
1 <= haystack.length, needle.length <= 104 haystack 和 needle 仅由小写英文字符组成
https://programmercarl.com/0028.%E5%AE%9E%E7%8E%B0strStr.html
1.暴力法
class Solution:
def strstr(self, haystack: str, needle: str) -> int:
hl = len(haystack)
nl = len(needle)
for i in range(0,hl-nl+1):
m = 0
while m < nl and haystack[i+m] == needle[m]:
m+=1
if m == nl :
return i
return -1
2.kmp算法
class Solution:s
def getNext(self,next: List[int], s: str) -> None:
j = 0
next[0] = 0
for i in range(1,len(s)):
while j != 0 and s[i] != s[j]:
j = next[j-1]
if s[i] == s[j]:
j += 1
next[i] = j
def strstr(self,hs: str,nd :str) -> int:
if len(nd) == 0:
return 0
next = [0] * len(nd)
self.getNext(next,nd)
j = 0
for i in range(len(hs)):
while j != 0 and hs[i] != nd[j]:
j = next[j-1]
if hs[i] == nd[j]:
j+=1
if j == len(nd):
return i - len(nd) + 1
return -1
28. 实现 strStr()
链接 力扣题目链接(opens new window)
给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。
示例 1:
输入: “abab” 输出: True 解释: 可由子字符串 “ab” 重复两次构成。 示例 2:
输入: “aba” 输出: False 示例 3:
输入: “abcabcabcabc” 输出: True 解释: 可由子字符串 “abc” 重复四次构成。 (或者子字符串 “abcabc” 重复两次构成。)
class Solution:
def repeatedSubstringPattern(self, s: str) -> bool:
return (s+s).find(s,1) != len(s)
替换数字
卡码网题目链接(opens new window)
给定一个字符串 s，它包含小写字母和数字字符，请编写一个函数，将字符串中的字母字符保持不变，而将每个数字字符替换为number。
例如，对于输入字符串 “a1b2c3”，函数应该将其转换为 “anumberbnumbercnumber”。
对于输入字符串 “a5b”，函数应该将其转换为 “anumberb”
输入：一个字符串 s,s 仅包含小写字母和数字字符。
输出：打印一个新的字符串，其中每个数字字符都被替换为了number
样例输入：a1b2c3
样例输出：anumberbnumbercnumber
数据范围：1 <= s.length < 10000。
#
class Solution:
def change(self,s):
lst = list(s)
for i in range(len(lst)):
if lst[i].isDigit():
lst[i] = "number"
return ''.join(lst[i])
151.翻转字符串里的单词
力扣题目链接(opens new window)
给定一个字符串，逐个翻转字符串中的每个单词。
示例 1： 输入: “the sky is blue” 输出: “blue is sky the”
示例 2： 输入: “ hello world! “ 输出: “world! hello” 解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
示例 3： 输入: “a good example” 输出: “example good a” 解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
#
python
class Solution:
def change(self,s):
s = s.strip()
s = s[::-1]
sarr = s.split()
for i in sarr:
i = i[::-1]
s = ' '.join(i)
return s
two pointer
class Solution:
def reverseWords(self, s: str) -> str:
# 将字符串拆分为单词，即转换成列表类型
words = s.split()
# 反转单词
left, right = 0, len(words) - 1
while left < right:
words[left], words[right] = words[right], words[left]
left += 1
right -= 1
# 将列表转换成字符串
return " ".join(words)
class Solution:
def change(self,s):
sarr = s.split()
sarr = sarr[::-1]
return ' '.join(sarr)
28. 实现 strStr()
力扣题目链接(opens new window)
实现 strStr() 函数。
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。
示例 1: 输入: haystack = “hello”, needle = “ll” 输出: 2
示例 2: 输入: haystack = “aaaaa”, needle = “bba” 输出: -1
说明: 当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。 对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。
https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/solutions/575568/shua-chuan-lc-shuang-bai-po-su-jie-fa-km-tb86/
https://programmercarl.com/0028.%E5%AE%9E%E7%8E%B0strStr.html#%E5%85%B6%E4%BB%96%E8%AF%AD%E8%A8%80%E7%89%88%E6%9C%AC
class Solution:
def getNext(self, next: List[int], s: str) -> None:
j = 0
next[0] = 0
for i in range(1, len(s)):
while j > 0 and s[i] != s[j]:
j = next[j - 1]
if s[i] == s[j]:
j += 1
next[i] = j
def strStr(self, haystack: str, needle: str) -> int:
if len(needle) == 0:
return 0
next = [0] * len(needle)
self.getNext(next, needle)
j = 0
for i in range(len(haystack)):
while j > 0 and haystack[i] != needle[j]:
j = next[j - 1]
if haystack[i] == needle[j]:
j += 1
if j == len(needle):
return i - len(needle) + 1
return -1
