最后一个单词的长度
最后一个单词的长度
原题链接：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) { ...