知识点dp思路状态表示 f[i] 表示到达每一个位置的最小步数状态转移是从f[i] 向每个 f[j] 转移 其中最后的结果是 f[j]时间复杂度为 AC code (C++) class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param rivers int整型vector * @return int整型 */ const int INF = 1e9; int min_jumps(vector<int...

知识点哈希表思路如果两个字符串不一样长，则是不可以的。从左到右依次匹配s的字母和t的字母，同时用哈希表记录s的字母和t的字母的对应关系，以及t中被占用的字母。在匹配过程中出现矛盾则返回“NO”。时间复杂度 AC Code（C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param s string字符串 * @param t string字符串 * @return string字符串 */ s...

知识点哈希表思路把plan按照空格分割成字符串数组a.如果两个字符串不一样长，则是不可以的。从左到右依次匹配s的字母和a的字符串，同时用哈希表记录s的字母和a的字符串的对应关系，以及a的被占用的字符串。在匹配过程中出现矛盾则返回 False。时间复杂度 AC Code (Python) from collections import defaultdict # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param pattern string字符串 # @param plan string字符串 # @return bool布尔型 # c...

知识点双指针思路维护两个指针，右指针表示枚举每一段的末尾，每次向后移动一位，左指针每次移动到合法的最左端即可，之后如果满足条件则更新答案。时间复杂度 AC Code（C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param target int整型 * @param nums int整型vector * @return int整型 */ int findMinSubarrayLength(i...

知识点计数思路对allocations和requirements的字母个数进行计数，如果allocations的每个字母都比requirements多则为“YES”时间复杂度 AC Code（C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param requirements string字符串 * @param allocations string字符串 * @return string字符串 */...

知识点栈思路题目有问题，居然能出现非法字符串和错误的答案，离大谱。我们建立一个数栈和符号栈，每次运算把数栈的顶端两个数抛出，在抛出符号位，进行运算。由于乘法的优先级更高，我们用一个map定义乘法和加减法的运算等级。出现负数的时候一定是符号在首位或者前面有左括号，根据这点将负数和减号区分开。AC Code (C++) class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param s string字符串 * @return int整型 ...

知识点Manacher算法思路很经典的求最长回文子串的问题，一般来说有三种办法动态规划 时间复杂度 中心扩展 时间复杂度 Manacher算法 时间复杂度 这道题的范围 显然不可以使用的算法，但是Manacher算法的难度远超面试难度。以下代码为链表形式的Manacher算法。时间复杂度 AC Code（C++） /** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr) {} * }; */ class Solution { ...

知识点前缀异或和思路题目样例有问题，给出5,7要求的是6^7=1即[left+1, right]的区间异或和我们可以把区间异或和转化为前缀异或和的差，所以只需要实现函数get（x）来求0到x的异或和我们观察到结果是具有规律性的：当x%4为0时结果是x当x%4为1时结果是1当x%4为2时结果是x+1当x%4为3时结果是0因此我们可以在时间内计算得到结果AC Code（C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param left ...

知识点双指针思路维护双指针，右指针每次向右移动一次，表示当前的末尾位置，左指针移动到满足最大元素和最小元素的差值小于等于k的最左位置，更新答案。维护最大最小值可以用multiset或者map实现。时间复杂度是 AC Code（C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param heights int整型vector * @param k int整型 * @return int整型 */ ...

知识点异或 哈希表思路需要找出唯一一个出现两次的元素，我们可以对原数组去重后，把所有的数的异或和再异或去重数组，这样的话就是找出唯一一个出现三次的（其他是出现四次）的元素，结果即为答案。时间复杂度 AC Code（C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型vector * @return int整型 */ int twoCountNumber(vector<in...

知识点位运算思路将每个数的每一位进行计数，对每一位的个数模3，如果不为0说明那个单独的数这一位有这个数，累加即可。时间复杂度 AC Code（C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型vector * @return int整型 */ int singleNumberII(vector<int>& nums) { vector&lt...

知识点异或思路由于同一个异或两次为0，所以只要求异或和即能得到只出现一次的数。时间复杂度 AC Code（Python） from functools import reduce # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param nums int整型一维数组 # @return int整型 # class Solution: def singleNumber(self , nums: List[int]) -> int: return reduce(lambda x, y : x ^ y, nums)

知识点数学思路计算数字2和数字5的个数，翻倍等于2的个数+1；后缀零的个数等于2和5个数较小的一个。时间复杂度 AC Code（C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param n int整型 * @param m int整型 * @return int整型 */ int trailingZeroes(int n, int m) { int c2 = m, c5 = ...

知识点双指针思路维护记录每个字符的个数的计数器，维护双指针，每次右指针向右移动一步，左指针不断右移找到合法的最靠左的位置，更新答案即可。时间复杂度 AC Code（C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param s string字符串 * @return int整型 */ int lengthOfLongestContinuousTasks(string s) { vector...