知识点字符串思路把备选答案设置为第一个名字，遍历整个字符串数组，取出备选答案和当前字符串的最长公共前缀作为下一轮的答案。时间复杂度 n为字符串数组的长度，m为每个字符串的长度。AC Code（C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param names string字符串vector * @return string字符串 */ string findAncestor(vector<string>& names) { string res = names...

知识点字符串 模拟思路用一个idx表示当前应该加入的行号, t表示应该移动的方向; 遍历字符串的每一行把字符加入对应的行最后把整个字符串拼接起来时间复杂度为AC Code (C++) class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param s string字符串 * @param numRows int整型 * @return string字符串 */ string decodeFlag(string s, int numRows) { vector<string> row(n...

知识点字符串 双指针思路按照.将字符串分成两半，将前后缀的0去掉之后，双指针判断是否是回文串即可。AC Code（C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param x string字符串 * @return bool布尔型 */ bool isPalindromeNumber(string x) { int idx = x.find("."); if (idx == string::npos) return check(x); return check(...

知识点双指针思路将x的每一位分解到一个数组中，双指针判断是否回文。时间复杂度AC Code（C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param x int整型 * @return bool布尔型 */ bool isPalindrome(int x) { vector<int> v; while (x) { v.push_back(x % 10); x /= 10; } for (int i = 0, j = (int)v.size() - 1; i < j...

知识点DP 前后缀分解思路 合法的情况有第一种是正常的最大子段和，第二种是使用的左右两段的最大和，这可以预处理前缀的最大和和后缀的最大和，然后枚举前缀和对应最大的后缀，也可以处理。当全是负数时会影响判断，可以先特判。时间复杂度为AC Code （C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param energy int整型vector * @return int整型 */ int maxEnergyCircular(vector<int>& energy) ...

知识点贪心 字符串思路从左到右一次遍历s，贪心地匹配t中的字符，如果都能匹配就可以返回true；假如出现不匹配则返回false时间复杂度 AC Code（C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param s string字符串 * @param t string字符串 * @return bool布尔型 */ bool isSubsequence(string s, string t) { int n = s.size(), m = t.size(); for (int i...

知识点BFS 哈希表思路我们首先可以知道一些点构成了连通块, 他们之间存在着换算的关系, 也就是说连通块之间可以互相换算, 不连通的点或者根本没有出现的点是不能换算的.所以我们现在考虑用bfs将每一个连通块的换算标准统一 (即把整个连通块的第一个元素当做换算的代表元素), 在询问的过程中如果双方均出现过而且属于同一个连通块, 则可以有答案, 否则没有确切的答案如果有答案, 则答案是两者换算为同一元素的值之比 可以时间内计算出来跑bfs每个点最多入队一次, n为点数, m为询问的次数, 总的时间复杂度为AC Code (C++) #include <unordered_map> cl...

知识点动态规划思路考虑以每个点结尾的最长上升子串的长度, 假如当前节点比前一个大, 则可以从上一个转移时间复杂度 AC Code (C++) class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param ids int整型vector * @param n int整型 * @return int整型 */ int longestConsecutive(vector<int>& ids, int n) { vector<int> f(n); f[0] = 1; in...

知识点回文字符串 哈希表思路首先用哈希表对字符串去重，如果个数大于k则返回false其次开始判断是否是回文串（有一个容错），如果发现不能相等的时候，应该分别去除掉不相等的那对中的一个字符后再进行正常的回文串判断。因为只会判断一次，所以时间复杂度是的注意当出现不一样的时候根据是否和下一个位置是否相等选择一个继续判断回文串的思路是错误的。因为可能存在“abab”这样的字符串，即当出现第一个a和最后一个b不等的时候，把左指针右移和右指针左移都可以继续相等时，不能擅自选一个方向移动。例如hack数据："abccbab",10"abaccab",10目前我在时间榜...

知识点字符串思路按照要求模拟即可，这里用python很方便。AC Code（python） # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param s string字符串 # @return bool布尔型 # class Solution: def isPalindromeNickname(self , s: str) -> bool: lst = [x for x in s.lower() if x.isalpha() or x.isdigit()] return lst == lst[::-1]

知识点字符串匹配思路可以上KMP，但没必要；直接暴力匹配也行，我选择string的库函数AC Code（C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param message string字符串 * @param keyword string字符串 * @return int整型 */ int findKeyword(string message, string keyword) { auto res = message.find(keyword); return res == ...

知识点字符串思路将字符串分割后翻转再拼接AC Code (python) # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param s string字符串 # @return string字符串 # class Solution: def reverseWords(self , s: str) -> str: return ' '.join(s.split()[::-1])

知识点字符串思路将字符串按照空格分隔；返回最后一个的长度字符串python是无敌的AC code（python） # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param s string字符串 # @return int整型 # class Solution: def lengthOfLastWord(self , s: str) -> int: return len(s.split()[-1])

知识点动态规划思路我们可以维护一个当前的前缀和，然后用当前的前缀和去更新答案。当当前的前缀和小于0的时候我们可以认为它对答案没有贡献，置为0。时间复杂度为AC Code（C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param energy int整型vector * @return int整型 */ const int INF = 1e9; int maxEnergy(vector<int>& energy) { int n = energy.size(); ...