zijing2333...大约 14 分钟

5. 最长回文子串open in new window

给你一个字符串 s，找到 s 中最长的回文子串。

解题思路

遍历字符串 s 中的每一个字符 i，以 i 为中心，向左右两侧扩展，找到以 i 为中心的最长回文子串 s1 和以 i 和 i+1 为中心的最长回文子串 s2，最后返回其中最长的回文子串。

isPalding() 函数用于找到以 left 和 right 为中心的最长回文子串。具体实现是，从 left 和 right 开始向左右两侧扩展，如果左右两侧字符相等，则继续扩展，否则停止扩展。返回回文子串的长度，使用 substr() 函数提取回文子串。

这个算法的时间复杂度是 O(n2)O(n^2)，空间复杂度是 O(1)O(1)，其中 n 是字符串 s 的长度。

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);
    }
};

3. 无重复字符的最长子串open in new window

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

解题思路

这道题的思路是滑动窗口或双指针，窗口内维持的是内部没有出现重复字符，我们可用一个hash表保存窗口内最长无重复子串中出现字符的下标，如果滑动到一个新的r碰到在窗口内出现的字符，那么l肯定就要往前滑动到之前出现的字符下标的下一位来保证l到r之间没有重复出现的字符。算法复杂度O(n)。

函数的解题思路如下：

  1. 使用一个哈希表unordered_map<char, int>来存储当前窗口中每个字符的最后出现位置。

  2. 初始化两个整数变量n和l，分别表示字符串s的长度和滑动窗口的左边界。

  3. 初始化一个整数变量ans，用于存储最长无重复字符子串的长度。

  4. 使用一个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)。

  5. 返回最长无重复字符子串的长度ans。

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;
}

76. 最小覆盖子串open in new window

给你一个字符串 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的子串。

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);
    }
};

151. 反转字符串中的单词open in new window

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

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

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

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

解题思路

这道题分为两个部分，第一部分修字符串格式，第二部分反转单词，反转的方法就是先将整个字符串反转，然后再分别反转每个单词。

具体操作如下：

  1. 初始化两个变量 writeIdx 和 readIdx，分别用于写入和读取输入字符串 s 的位置。

  2. 使用一个循环，从左到右遍历输入字符串 s，执行以下操作： a. 如果当前字符（s[readIdx]）不是空格，则将其写入 s（s[writeIdx++] = s[readIdx++]），并同时递增 writeIdx 和 readIdx。 b. 如果当前字符是空格，则跳过所有连续的空格。如果 writeIdx 不为零且 readIdx 不等于字符串长度，表示这是一个单词之间的空格，将一个空格写入 s，并递增 writeIdx。

  3. 使用 s.resize(writeIdx) 方法调整字符串 s 的大小，以去除尾部的多余字符。

  4. 使用 reverse 函数反转整个字符串。这是 C++ 标准库中的一个函数，它接受两个迭代器参数，分别表示字符串的开始和结束位置。

  5. 初始化一个变量 start，用于存储每个单词的起始位置。遍历字符串 s，找到每个单词的结束位置（s[i] 为 ' ' 或者 i 等于字符串长度）。

  6. 对于每个找到的单词，调用 reverse 函数反转该单词。传入两个迭代器参数，分别表示单词的开始和结束位置。

  7. 返回处理后的字符串。

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;
    }
};

394. 字符串解码open in new window

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

解题思路

用两个栈，一个栈只要不是]就往进放东西，如果遇到了]号，那就开始处理，从当前栈加到备用栈里，遇到[停止，然后把数字算出来，再反过来把备用栈的数往当前栈中加几遍，最后把结果放到一个string数组。

具体操作如下：

  1. 首先，初始化一个栈 stack，用于存储字符串中的字符。

  2. 遍历输入字符串 s 的每个字符：

    a. 如果当前字符不是 ']'，则将其推入栈中。

    b. 如果当前字符是 ']'，则执行以下操作：

    i. 从栈顶弹出字符，直到遇到字符 '['。将这些字符存储在一个临时字符串构建器 temp 中。注意，我们需要反转从栈中弹出的字符，以便获得正确的子串顺序。

    ii. 弹出字符 '['。

    iii. 继续从栈中弹出字符，直到遇到非数字字符。使用这些数字字符计算 time，即需要重复的次数。我们从右到左处理数字字符，并使用 factor 乘以它们，以确保得到正确的数值。

    iv. 使用 strings.Repeat 函数重复 temp 字符串 time 次，并将结果存储在 repeated 中。

    v. 将 repeated 中的字符逐个推入栈中。

  3. 遍历栈中的所有字符，并使用一个新的字符串构建器 ans 将它们连接起来。这将形成最终的解码字符串。

  4. 返回解码字符串。

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;
    }
};

14. 最长公共前缀open in new window

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

解题思路

其实就是两遍遍历，具体操作如下：

  1. 初始化两个整数变量n和m，分别表示字符串向量strs的大小（字符串数量）和第一个字符串的长度。

  2. 初始化一个空字符串ans，用于存储最长公共前缀。

  3. 使用一个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中。

  4. 返回最长公共前缀ans。

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;
    }
};
你认为这篇文章怎么样？
  • 0
  • 0
  • 0
  • 0
  • 0
  • 0
0  字
评论
  • 按正序
  • 按倒序
  • 按热度
Powered by Waline v2.14.8