知识点枚举遍历思路我们从左到右遍历数组，并维护一个最高值，如果当前值比最大值大，那么可见的牛数+1且更新最大值的值。AC Code（C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param cowHeights int整型vector * @return int整型 */ int visibleCows(vector<int>& cowHeights) { int m...

知识点枚举思路我们枚举买入的日子，并找到后面的最大的值作为卖出的日子，正常可以二重循环。如果从后向前枚举，并维护最大值，可以做到的时间复杂度。AC Code（C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param prices int整型vector * @return int整型 */ int max_profit(vector<int>& prices) { i...

知识点字符串查找思路把words中的字符串拼接起来，在原串中查找即可。AC Code（C++） #include <numeric> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param s string字符串 * @param words string字符串vector * @return int整型 */ int findLongestSubstring(string s, vec...

知识点栈 字符串思路建立一个每层名字的栈，把原串按照/进行分割。如果遇到空串或者. 则可以跳过如果遇到.. 若栈非空则抛出栈顶如果其他情况则压栈最后把整个栈连起来即可AC Code (python) # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param path string字符串 # @return string字符串 # class Solution: def find_dangerous_cow_path(self , path: str) -> str: stk = [] for...

知识点二分思路首先和 NB79 旋转排列之找出最矮的牛这道题一样找到分界点，分界点两边都是有序的，可以直接二分查找是否存在对应的值。即两次二分，时间复杂度AC Code（C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型vector * @param target int整型 * @return int整型 */ int search(vector<int&...

知识点二分思路首先特判首位两个元素的大小来排除没有移动的情况。在移动后，数组变成了两段递减的拼接，我们需要找到第一段的末尾，可以使用二分，如果当前的mid元素比首元素要大，那么在mid右端的部分将舍弃。每次会减少一半的范围。所以时间复杂度为AC Code（C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param heights int整型vector * @return int整型 */ int fin...

知识点贪心思路由于需要分割出更多的组，我们先预处理出每个字母出现的最后一个位置。之后我们指定一个开头，遍历从开头到当前字母的最后的位置（必须包含的位置），随着我们向后遍历会逐渐遇到新的字母，会把至少应该包含的末尾向后移动，直到我们遍历到末尾之后，就可以形成一个分割。之后加入答案即可。时间复杂度 AC Code（C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param s string字符串 * @return int整型...

知识点双指针 计数思路同向双指针，并维护两段指针之间的字母的计数，双指针每次右指针移动一次，左指针不断试探下一个位置是否可以，每次找到满足条件的最近的左指针。时间复杂度 AC Code（C++） class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param s string字符串 * @param t string字符串 * @return string字符串 */ string minWindow(s...

知识点动态规划思路维护每个点的上边的连续的C的个数, 左边的连续的C的个数, 以及以该点为右下角的由C组成的正方形的长度; 上边和左边是很好维护的, 我们考虑如果当前点不是左上两条边的点的话, 那么如果满足当前点上面连续的C的个数和左边的连续的C的个数均大于f[i-1][j-1], 那么f[i][j]就可以在f[i-1][j-1]的基础上+1AC Code (C++) class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param land cha...

知识点动态规划思路定义 f[i][j] 为从起点到 (i, j)的最小的路径和每次转移可以从f[i-1][j-1] f[i-1][j]进行转移答案是最后一行的最小值时间复杂度 AC Code (C++) class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param cows int整型vector<vector<>> * @return int整型 */ const int INF = 1e9...

知识点动态规划思路状态表示: 定义 f[i] 为总和为i的最小个数，状态转移: 每一次转移是选定当前选哪一个数字，即时间复杂度为 AC Code (C++) class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param weights int整型vector * @param totalWeight int整型 * @return int整型 */ const int INF = 1e9; int...

知识点乘法原理 动态规划思路下面我们讨论DP解法。首先由于只能向右或者向下移动，那么说明任意值为2的点的横纵坐标大小关系必须是一致的，也就是对于点（x1，y1）和（x2，y2）而言，如果存在（x1 < x2）且 (y1 > y2)的情况一定是无解的排除掉这一点后，我们发现假如存在m个有牛的位置，他会把整个图分成若干段，每一段都是求从左上角到右下角的方案数，而且互不干扰，这可以用乘法原理解决。而每一部分求从左上角到右下角的方法数是很基本的DP，和上一道题是一样的。最差的时间复杂度应该是没有牛的时候从左上角到右下角，此时的时间复杂度是AC Code (c++) #define x fi...

知识点哈希表 动态规划思路定义状态表示f[i] 表示 前i个字母能否被合法分割; 那么只需要枚举当前字母所在的子串, 查询是否在wordList即可进行转移。使用哈希表将所有的word存起来可以做到O(len)的时间内查询是否存在；在枚举子串的时候倒着枚举可以减少复制字符串的时间消耗.时间复杂度 字符串长度为mAC Code (C++) class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param s string字符串 * @...

知识点最长公共子序列 LCSDP思路两个序列的公共子序列部分是不需要更改的，剩下的则需要增加或者减少，所以只需要求出最长公共子序列，每个序列除去最长公共子序列的部分就是需要更改的部分。定义 f[i][j]表示word1前i个字母和word2的前j个字母的最长公共子序列。时间复杂度 AC Code (C++) class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param word1 string字符串 * @param word2 st...