字符串

不含重复字符的最长子字符串 原题链接：https://leetcode.cn/problems/wtcaE1/ 给定一个字符串 s ，请你找出其中不含有重复字符的 最长连续子字符串 的长度。 1.静态滑动窗口11

字符串中的变位词 原题链接：https://leetcode.cn/problems/MPnaiL/ 给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的某个变位词。第一个字符串的排列之一是第二个字符串的 子串 。 1.静态滑动窗口1由于知道目标字符串的长度，故可以通过暴力枚举的方式（一个静态的滑动窗口）来枚举出所有的情况， 并对枚举的每种情况进行字母数量的统计，利用哈希表实现字母数量的统计， 123456789101112131415class Solution {public: bool checkInclusion(string pattern, string text) { for (int i = 0, j = i + pattern.length(); j <= text.length(); ++i, ++j) { int flag = 0; vector<int> cnt(26); for (int k = 0; k < pattern.length(); ++k) cnt[pattern[k] - 'a']++;//查找目标的字母数量统计 for (int k = i; k < j; ++k) cnt[text[k] - 'a']--;//遍历的字符串的字母数量统计 for (int i = 0; i < 26; ++i) if (cnt[i] != 0) flag = 1;//判断字母数量是否相同 if (flag) continue; return true; } return false; }}; 勉强能过，时间复杂度与空间复杂度都很高。 2.静态滑动窗口2对每次的字母数量判断操作进行修改，对边界值进行加入与减出操作，思路没有问题的，先做记录在此。 1234567891011121314151617181920212223class Solution {public ...

字符串中的所有变位词 原题链接：https://leetcode.cn/problems/VabMRr/ 给定两个字符串 s 和 p，找到 s 中所有 p 的 变位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。 变位词 指字母相同，但排列不同的字符串。 1.静态滑动窗口11

最后一个单词的长度 原题链接：https://leetcode.cn/problems/length-of-last-word/ 给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中最后一个单词的长度。 单词是指仅由字母组成、不包含任何空格字符的最大子字符串。 1.参考解答123456789101112131415class Solution {public: int lengthOfLastWord(string s) { int l = -1, r = -1; for (int i = s.length() - 1; i >= 0; --i) { if (s[i] != ' ' && r == -1) r = i; if (s[i] == ' ' && r != -1) { l = i; break; } } if (r == -1) return 0; return r - l; }};

有效的括号 原题链接：https://leetcode.cn/problems/valid-parentheses/ 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。 有效字符串需满足： 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 每个右括号都有一个对应的相同类型的左括号。 1.化简思维可以将问题先简化为1种括号的匹配问题（判断左括号、右括号的数量是否相等），再扩展括号匹配的种类： +1可以等价为进入，-1可以等价为出去 一对()可以等价为一个完整的事件 (())可以看做事件与事件之间的完全包含关系 1种括号匹配123456789101112131415//写法1bool isValid(char *s) { int lum = 0, rnum = 0; int len = strlen(s); for (int i = 0; i < len; ++i) { switch (s[i]) { case '(' : ++lnum; break; case ')' : ++rnum; break; default : return flase; } if (lnum >= rnum) continue; return false; } return lnum = rnum;} 123456789101112131415//写法2bool isValid(char *s) { int lum = 0; int len = strlen(s); for (int i = 0; i < len; ++i) { switch (s[i]) { case '(' : ++lnum; break; ...

外观数列 原题链接：https://leetcode.cn/problems/count-and-say/ 给定一个正整数 n，输出外观数列的第 n 项。 外观数列是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。你可以将其视作是由递归公式定义的数字字符串序列： countAndSay(1) = "1" countAndSay(n) 是对 countAndSay(n-1) 的描述，然后转换成另一个数字字符串。 前五项如下： 123456789101. 12. 113. 214. 12115. 111221第一项是数字 1 描述前一项，这个数是 1 即 “ 一 个 1 ”，记作 "11"描述前一项，这个数是 11 即 “ 二 个 1 ” ，记作 "21"描述前一项，这个数是 21 即 “ 一 个 2 + 一 个 1 ” ，记作 "1211"描述前一项，这个数是 1211 即 “ 一 个 1 + 一 个 2 + 二 个 1 ” ，记作 "111221" 要描述一个数字字符串，首先要将字符串分割为最小数量的组，每个组都由连续的最多相同字符组成。 对于每个组，先描述字符的数量然后描述字符，形成一个描述组。 要将描述转换为数字字符串，先将每组中的字符数量用数字替换，再将所有描述组连接起来。 例如，数字字符串 "3322251" 的描述如下图： 1.遍历上个字符串得到下个遍历前一个字符串 得到后一个字符串 1234567891011121314151617181920212223242526class Solution {public: void work(string &str, int cnt, char c) { str += (char)(cnt + '0');//数字数量 str += c;//数字字符 } void func(string &str1, string &str2) { int cnt = 0; for ( ...

最长公共前缀 原题链接：https://leetcode.cn/problems/longest-common-prefix/ 编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀，返回空字符串。 1.substr解法1：暴力循环 + substr字符串截取 runtime beats 73.15 % of cpp submissions memory usage beats 27.86 % of cpp submissions (9 MB) 12345678910111213class Solution {public: string longestCommonPrefix(vector<string>& strs) { if (strs.size() == 0) return ""; string ans = strs[0]; for (int i = 1; i < strs.size(); ++i) { int index = 0; for (;index < max(strs[i].length(), ans.length()) && ans[index] == strs[i][index]; ++index); ans = strs[i].substr(0, index); } return ans; }}; 2.+=操作解法2：暴力循环 + 字符串的+=操作（取消了对substr的引用，性能更优） runtime beats 73.15 % of cpp submissions memory usage beats 92.63 % of cpp submissions (8.8 MB) 1234567891011121314151617181920class Solution {public: string longestCommonPrefix(vector<string>& strs) { ...