给你一个字符串
s，找到s中最长的回文子串。
解题思路
遍历字符串 s 中的每一个字符 i，以 i 为中心，向左右两侧扩展，找到以 i 为中心的最长回文子串 s1 和以 i 和 i+1 为中心的最长回文子串 s2，最后返回其中最长的回文子串。
isPalding() 函数用于找到以 left 和 right 为中心的最长回文子串。具体实现是，从 left 和 right 开始向左右两侧扩展，如果左右两侧字符相等，则继续扩展，否则停止扩展。返回回文子串的长度，使用 substr() 函数提取回文子串。
这个算法的时间复杂度是
::: code-tabs
@tab cpp
class Solution {
public:
string longestPalindrome(string s) {
string res = "";
for (int i = 0; i < s.length(); i++) {
string s1 = isPalding(s, i, i);
string s2 = isPalding(s, i, i + 1);
if (s1.length() > res.length()) {
res = s1;
}
if (s2.length() > res.length()) {
res = s2;
}
}
return res;
}
string isPalding(string s, int left, int right) {
while (left >= 0 && right < s.length() && s[left] == s[right]) {
left--;
right++;
}
return s.substr(left + 1, right - left - 1);
}
};@tab java
class Solution {
public String longestPalindrome(String s) {
int n = s.length();
String res = "";
for(int i=0;i<n;i++) {
String s1 = palindrome(s, i, i);
String s2 = palindrome(s, i, i+1);
res = s1.length() > res.length() ? s1 : res;
res = s2.length() > res.length() ? s2 : res;
}
return res;
}
private String palindrome(String s, int l, int r) {
String res = "";
while(l>=0 && r<s.length() && s.charAt(l) == s.charAt(r)) {
res = s.substring(l, r+1);
l--;
r++;
}
return res;
}
}@tab golang
func longestPalindrome(s string) string {
res := ""
for i:=0;i<len(s);i++{
s1 := isPalding(s,i,i)
s2 := isPalding(s,i,i+1)
if len(s1)>len(res){
res = s1
}
if len(s2)>len(res){
res = s2
}
}
return res
}
func isPalding(s string,left,right int)string{
for left>=0&&right<len(s)&&s[left]==s[right]{
left--
right++
}
return s[left+1:right]
}:::
给定一个字符串
s，请你找出其中不含有重复字符的 最长子串 的长度。
解题思路
这道题的思路是滑动窗口或双指针，窗口内维持的是内部没有出现重复字符，我们可用一个hash表保存窗口内最长无重复子串中出现字符的下标，如果滑动到一个新的r碰到在窗口内出现的字符，那么l肯定就要往前滑动到之前出现的字符下标的下一位来保证l到r之间没有重复出现的字符。算法复杂度O(n)。
函数的解题思路如下：
-
使用一个哈希表
unordered_map<char, int>来存储当前窗口中每个字符的最后出现位置。 -
初始化两个整数变量n和l，分别表示字符串s的长度和滑动窗口的左边界。
-
初始化一个整数变量ans，用于存储最长无重复字符子串的长度。
-
使用一个for循环，遍历字符串s中的所有字符。r表示滑动窗口的右边界。
a. 如果当前字符s[r]已经在哈希表中存在（表示该字符在当前窗口已出现过），则需要更新窗口的左边界l。
i. 获取该字符s[r]在哈希表中存储的最后出现位置last。
ii. 遍历当前窗口，从左边界l到last，从哈希表中删除这些字符。
iii. 将左边界l更新为last + 1，以排除重复字符。
b. 将字符s[r]及其在字符串s中的位置r存入哈希表中。
c. 更新最长无重复字符子串的长度ans，将ans设置为max(ans, r - l + 1)。
-
返回最长无重复字符子串的长度ans。
::: code-tabs
@tab cpp
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> hash;
int n = s.size();
int l = 0;
int ans = 0;
for(int r = 0; r < n; r++) {
if(hash.count(s[r])) {
int last = hash[s[r]];
for(int j = l; j <= last; j++) {
hash.erase(s[j]);
}
l = last + 1;
}
hash[s[r]] = r;
ans = max(ans, r - l + 1);
}
return ans;
}@tab java
class Solution {
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> hash = new HashMap<>();
int n = s.length();
int l = 0;
int ans = 0;
for (int r = 0; r < n; r++) {
if (hash.containsKey(s.charAt(r))) {
int last = hash.get(s.charAt(r));
for (int j = l; j <= last; j++) {
hash.remove(s.charAt(j));
}
l = last + 1;
}
hash.put(s.charAt(r), r);
ans = Math.max(ans, r - l + 1);
}
return ans;
}
}@tab golang
func lengthOfLongestSubstring(s string) int {
hash := make(map[byte]int)
n := len(s)
l := 0
ans := 0
for r := 0; r < n; r++ {
if _, ok := hash[s[r]]; ok {
last := hash[s[r]]
for j := l; j <= last; j++ {
delete(hash, s[j])
}
l = last + 1
}
hash[s[r]] = r
ans = max(ans, r - l + 1)
}
return ans
}
func max(a, b int) int {
if a > b {
return a
}
return b
}:::
给你一个字符串
s、一个字符串t。返回s中涵盖t所有字符的最小子串。如果s中不存在涵盖t所有字符的子串，则返回空字符串""。
解题思路
首先，我们使用两个哈希映射数据结构（在Java中是HashMap，在Go中是map）：need和window。need用于存储目标字符串t中每个字符出现的次数，window用于存储源字符串s中当前窗口内每个字符出现的次数。
初始化两个指针：left和right，分别表示窗口的左右边界。还需要初始化minLength和minStart变量，用于存储找到的最短子串的长度和起始位置。validCount变量用于跟踪当前窗口内有效字符的计数（即在t中存在的字符）。
在right指针未超出源字符串s的长度时，执行以下循环： a. 获取right指针所指的字符c，并将right指针向右移动一位。 b. 如果字符c在need映射中存在，将其加入window映射并增加其计数。如果window中字符c的计数小于等于need中的计数，将validCount加1。 c. 当validCount等于目标字符串t的长度时，表示当前窗口包含了t的所有字符。执行以下操作： i. 如果当前窗口的长度（即right - left）小于已找到的最短子串长度（即minLength），则更新minLength和minStart。 ii. 获取left指针所指的字符d，并将left指针向右移动一位，以缩小窗口。 iii. 如果字符d在need映射中存在，检查其在window映射中的计数。如果window中字符d的计数小于等于need中的计数，将validCount减1。最后，减少window中字符d的计数。
当循环结束后，检查minLength是否仍等于其初始值（即最大整数）。如果是，则表示未找到符合条件的子串，返回空字符串。否则，返回源字符串s中从minStart开始、长度为minLength的子串。
::: code-tabs
@tab cpp
class Solution {
public:
string minWindow(string s, string t) {
unordered_map<char, int> need, window;
for (char c : t) {
need[c]++;
}
int left = 0, right = 0;
int minLength = INT_MAX, minStart = 0;
int validCount = 0;
while (right < s.size()) {
char c = s[right];
right++;
if (need.count(c)) {
window[c]++;
if (window[c] <= need[c]) {
validCount++;
}
}
while (validCount == t.size()) {
if (right - left < minLength) {
minLength = right - left;
minStart = left;
}
char d = s[left];
left++;
if (need.count(d)) {
if (window[d] <= need[d]) {
validCount--;
}
window[d]--;
}
}
}
return minLength == INT_MAX ? "" : s.substr(minStart, minLength);
}
};@tab java
import java.util.HashMap;
class Solution {
public String minWindow(String s, String t) {
HashMap<Character, Integer> need = new HashMap<>(), window = new HashMap<>();
for (char c : t.toCharArray()) {
need.put(c, need.getOrDefault(c, 0) + 1);
}
int left = 0, right = 0;
int minLength = Integer.MAX_VALUE, minStart = 0;
int validCount = 0;
while (right < s.length()) {
char c = s.charAt(right);
right++;
if (need.containsKey(c)) {
window.put(c, window.getOrDefault(c, 0) + 1);
if (window.get(c) <= need.get(c)) {
validCount++;
}
}
while (validCount == t.length()) {
if (right - left < minLength) {
minLength = right - left;
minStart = left;
}
char d = s.charAt(left);
left++;
if (need.containsKey(d)) {
if (window.get(d) <= need.get(d)) {
validCount--;
}
window.put(d, window.get(d) - 1);
}
}
}
return minLength == Integer.MAX_VALUE ? "" : s.substring(minStart, minStart + minLength);
}
}@tab golang
import (
"math"
)
func minWindow(s string, t string) string {
need := make(map[rune]int)
window := make(map[rune]int)
for _, c := range t {
need[c]++
}
left, right := 0, 0
minLength := math.MaxInt32
minStart := 0
validCount := 0
for right < len(s) {
c := rune(s[right])
right++
if _, ok := need[c]; ok {
window[c]++
if window[c] <= need[c] {
validCount++
}
}
for validCount == len(t) {
if right-left < minLength {
minLength = right - left
minStart = left
}
d := rune(s[left])
left++
if _, ok := need[d]; ok {
if window[d] <= need[d] {
validCount--
}
window[d]--
}
}
}
if minLength == math.MaxInt32 {
return ""
}
return s[minStart : minStart+minLength]
}:::
给你一个字符串 s ，请你反转字符串中 单词 的顺序。
单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。
解题思路
这道题分为两个部分，第一部分修字符串格式，第二部分反转单词，反转的方法就是先将整个字符串反转，然后再分别反转每个单词。
具体操作如下：
-
初始化两个变量
writeIdx和readIdx，分别用于写入和读取输入字符串s的位置。 -
使用一个循环，从左到右遍历输入字符串
s，执行以下操作： a. 如果当前字符（s[readIdx]）不是空格，则将其写入s（s[writeIdx++] = s[readIdx++]），并同时递增writeIdx和readIdx。 b. 如果当前字符是空格，则跳过所有连续的空格。如果writeIdx不为零且readIdx不等于字符串长度，表示这是一个单词之间的空格，将一个空格写入s，并递增writeIdx。 -
使用
s.resize(writeIdx)方法调整字符串s的大小，以去除尾部的多余字符。 -
使用
reverse函数反转整个字符串。这是 C++ 标准库中的一个函数，它接受两个迭代器参数，分别表示字符串的开始和结束位置。 -
初始化一个变量
start，用于存储每个单词的起始位置。遍历字符串s，找到每个单词的结束位置（s[i]为' '或者i等于字符串长度）。 -
对于每个找到的单词，调用
reverse函数反转该单词。传入两个迭代器参数，分别表示单词的开始和结束位置。 -
返回处理后的字符串。
::: code-tabs
class Solution {
public:
string reverseWords(string s) {
int writeIdx = 0, readIdx = 0;
while (readIdx < s.size()) {
if (s[readIdx] != ' ') {
s[writeIdx++] = s[readIdx++];
} else {
while (readIdx < s.size() && s[readIdx] == ' ') {
readIdx++;
}
if (writeIdx != 0 && readIdx != s.size()) {
s[writeIdx++] = ' ';
}
}
}
s.resize(writeIdx);
reverse(s.begin(), s.end());
int start = 0;
for (int i = 0; i <= s.size(); i++) {
if (i == s.size() || s[i] == ' ') {
reverse(s.begin() + start, s.begin() + i);
start = i + 1;
}
}
return s;
}
};@tab java
class Solution {
public String reverseWords(String s) {
StringBuilder sb = new StringBuilder();
int writeIdx = 0, readIdx = 0;
while (readIdx < s.length()) {
if (s.charAt(readIdx) != ' ') {
sb.append(s.charAt(readIdx++));
writeIdx++;
} else {
while (readIdx < s.length() && s.charAt(readIdx) == ' ') {
readIdx++;
}
if (writeIdx != 0 && readIdx != s.length()) {
sb.append(' ');
writeIdx++;
}
}
}
sb.reverse();
int start = 0;
for (int i = 0; i <= sb.length(); i++) {
if (i == sb.length() || sb.charAt(i) == ' ') {
reverse(sb, start, i - 1);
start = i + 1;
}
}
return sb.toString();
}
private void reverse(StringBuilder sb, int start, int end) {
while (start < end) {
char temp = sb.charAt(start);
sb.setCharAt(start, sb.charAt(end));
sb.setCharAt(end, temp);
start++;
end--;
}
}
}@tab golang
import (
"strings"
)
func reverseWords(s string) string {
sb := strings.Builder{}
writeIdx, readIdx := 0, 0
for readIdx < len(s) {
if s[readIdx] != ' ' {
sb.WriteByte(s[readIdx])
writeIdx++
readIdx++
} else {
for readIdx < len(s) && s[readIdx] == ' ' {
readIdx++
}
if writeIdx != 0 && readIdx != len(s) {
sb.WriteByte(' ')
writeIdx++
}
}
}
revStr := reverseString(sb.String())
words := strings.Split(revStr, " ")
revWords := make([]string, len(words))
for i, word := range words {
revWords[i] = reverseString(word)
}
return strings.Join(revWords, " ")
}
func reverseString(s string) string {
runes := []rune(s)
left, right := 0, len(runes)-1
for left < right {
runes[left], runes[right] = runes[right], runes[left]
left++
right--
}
return string(runes)
}:::
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
解题思路
用两个栈，一个栈只要不是]就往进放东西，如果遇到了]号，那就开始处理，从当前栈加到备用栈里，遇到[停止，然后把数字算出来，再反过来把备用栈的数往当前栈中加几遍，最后把结果放到一个string数组。
具体操作如下：
-
首先，初始化一个栈
stack，用于存储字符串中的字符。 -
遍历输入字符串
s的每个字符：a. 如果当前字符不是 ']'，则将其推入栈中。
b. 如果当前字符是 ']'，则执行以下操作：
i. 从栈顶弹出字符，直到遇到字符 '['。将这些字符存储在一个临时字符串构建器
temp中。注意，我们需要反转从栈中弹出的字符，以便获得正确的子串顺序。ii. 弹出字符 '['。
iii. 继续从栈中弹出字符，直到遇到非数字字符。使用这些数字字符计算
time，即需要重复的次数。我们从右到左处理数字字符，并使用factor乘以它们，以确保得到正确的数值。iv. 使用
strings.Repeat函数重复temp字符串time次，并将结果存储在repeated中。v. 将
repeated中的字符逐个推入栈中。 -
遍历栈中的所有字符，并使用一个新的字符串构建器
ans将它们连接起来。这将形成最终的解码字符串。 -
返回解码字符串。
::: code-tabs
@tab cpp
class Solution {
public:
string decodeString(string s) {
vector<char> stack;
for (int i = 0; i < s.size(); i++) {
if (s[i] != ']') {
stack.push_back(s[i]);
} else {
string temp = "";
while (!stack.empty() && stack.back() != '[') {
temp = stack.back() + temp;
stack.pop_back();
}
if (!stack.empty()) stack.pop_back();
int time = 0, factor = 1;
while (!stack.empty() && stack.back() >= '0' && stack.back() <= '9') {
time += (stack.back() - '0') * factor;
stack.pop_back();
factor *= 10;
}
string repeated = "";
while (time--) {
repeated += temp;
}
for (char ch : repeated) {
stack.push_back(ch);
}
}
}
string ans = "";
for (char ch : stack) {
ans += ch;
}
return ans;
}
};@tab java
import java.util.Stack;
class Solution {
public String decodeString(String s) {
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) != ']') {
stack.push(s.charAt(i));
} else {
StringBuilder temp = new StringBuilder();
while (!stack.empty() && stack.peek() != '[') {
temp.insert(0, stack.pop());
}
if (!stack.empty()) stack.pop();
int time = 0, factor = 1;
while (!stack.empty() && Character.isDigit(stack.peek())) {
time += (stack.pop() - '0') * factor;
factor *= 10;
}
StringBuilder repeated = new StringBuilder();
while (time-- > 0) {
repeated.append(temp);
}
for (int j = 0; j < repeated.length(); j++) {
stack.push(repeated.charAt(j));
}
}
}
StringBuilder ans = new StringBuilder();
for (char ch : stack) {
ans.append(ch);
}
return ans.toString();
}
}@tab golang
import (
"strings"
"unicode"
)
func decodeString(s string) string {
var stack []rune
for _, ch := range s {
if ch != ']' {
stack = append(stack, ch)
} else {
var temp strings.Builder
for len(stack) > 0 && stack[len(stack)-1] != '[' {
temp.WriteRune(stack[len(stack)-1])
stack = stack[:len(stack)-1]
}
tempStr := temp.String()
temp.Reset()
for i := len(tempStr) - 1; i >= 0; i-- {
temp.WriteRune(rune(tempStr[i]))
}
if len(stack) > 0 {
stack = stack[:len(stack)-1]
}
time := 0
factor := 1
for len(stack) > 0 && unicode.IsDigit(stack[len(stack)-1]) {
time += int(stack[len(stack)-1]-'0') * factor
stack = stack[:len(stack)-1]
factor *= 10
}
repeated := strings.Repeat(temp.String(), time)
for _, r := range repeated {
stack = append(stack, r)
}
}
}
var ans strings.Builder
for _, ch := range stack {
ans.WriteRune(ch)
}
return ans.String()
}:::
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串
""。
解题思路
其实就是两遍遍历，具体操作如下：
-
初始化两个整数变量n和m，分别表示字符串向量strs的大小（字符串数量）和第一个字符串的长度。
-
初始化一个空字符串ans，用于存储最长公共前缀。
-
使用一个for循环，从0到m-1遍历第一个字符串的所有字符。
a. 初始化一个字符变量match，将其设置为第一个字符串的当前字符(strs[0][i])。
b. 使用一个内部for循环，从1到n-1遍历其他字符串。
如果当前字符的索引i大于等于当前字符串strs[j]的长度，或者当前字符串strs[j]的当前字符与match不相等，则直接返回当前已找到的最长公共前缀ans。
c. 如果所有字符串的当前字符都与match相等，将match追加到ans中。
-
返回最长公共前缀ans。
::: code-tabs
@tab cpp
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
int n = strs.size();
int m = strs[0].size();
string ans = "";
for(int i = 0; i < m; i++){
char match = strs[0][i];
for(int j = 1; j < n; j++){
if(i >= strs[j].size() || strs[j][i] != match) return ans;
}
ans += match;
}
return ans;
}
};@tab java
class Solution {
public String longestCommonPrefix(String[] strs) {
if(strs.length == 0)
return "";
String ans = strs[0];
for(int i =1;i<strs.length;i++) {
int j=0;
for(;j<ans.length() && j < strs[i].length();j++) {
if(ans.charAt(j) != strs[i].charAt(j))
break;
}
ans = ans.substring(0, j);
if(ans.equals(""))
return ans;
}
return ans;
}
}@tab golang
type DictTreeNode struct {
depth int
next []*DictTreeNode
}
func newDictTreeNode() *DictTreeNode {
return &DictTreeNode{next: make([]*DictTreeNode, 26)}
}
type DictTree struct {
root *DictTreeNode
}
func (t *DictTree) insert(str string) {
cur := t.root
for _, ch := range str {
if cur.next[ch-'a'] == nil {
cur.next[ch-'a'] = newDictTreeNode()
cur.next[ch-'a'].depth = cur.depth + 1
}
cur = cur.next[ch-'a']
}
}
func (t *DictTree) prefixMatch(str string) int {
cur := t.root
for i := 0; i < len(str) && cur.next[str[i]-'a'] != nil; i++ {
cur = cur.next[str[i]-'a']
}
return cur.depth
}
func longestCommonPrefix(strs []string) string {
tree := &DictTree{root: newDictTreeNode()}
tree.insert(strs[0])
length := len(strs[0])
for _, str := range strs {
length = min(length, tree.prefixMatch(str))
}
return strs[0][:length]
}
func min(a, b int) int {
if a > b {
return b
}
return a
}@tab java
class Solution {
public String longestCommonPrefix(String[] strs) {
int n = strs.length;
int m = strs[0].length();
StringBuilder ans = new StringBuilder();
for (int i = 0; i < m; i++) {
char match = strs[0].charAt(i);
for (int j = 1; j < n; j++) {
if (i >= strs[j].length() || strs[j].charAt(i) != match) {
return ans.toString();
}
}
ans.append(match);
}
return ans.toString();
}
}@tab golang
func longestCommonPrefix(strs []string) string {
n := len(strs)
m := len(strs[0])
ans := make([]rune, 0)
for i := 0; i < m; i++ {
match := rune(strs[0][i])
for j := 1; j < n; j++ {
if i >= len(strs[j]) || rune(strs[j][i]) != match {
return string(ans)
}
}
ans = append(ans, match)
}
return string(ans)
}:::