LeetCode 269. Alien Dictionary

There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of non-empty words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language. Example 1:

Example 2:

Example 3:
Continue reading LeetCode 269. Alien Dictionary

LeetCode 611. Valid Triangle Number

https://leetcode.com/problems/valid-triangle-number/description/ 有点类似3Sum的题目。形成三角形的充要条件是最小两边之和大于第三边。可以先给数组排序,然后确定一个最大边,然后在它左边找另外两边。 时间复杂度是O(n*log(n) + n^2) = O(n^2)

   

LeetCode 523. Continuous Subarray Sum

https://leetcode.com/problems/continuous-subarray-sum/description/ 这道题跟https://leetcode.com/problems/subarray-sum-equals-k/description/ 其实是很像的,但本题的特点就是corner case非常多…

 

LeetCode 560. Subarray Sum Equals K

https://leetcode.com/problems/subarray-sum-equals-k/description/ O(N^2)的方法想必所有人都会,这里有个用到prefix sum的O(N)方法。 试想一下,如果当前检查到end位置且目前所有项的和为sum,如果有那么一个(start, end)子序列的和为k,那么肯定有一个(0, start-1)的序列它的和是sum – k.

 

LeetCode LIS系列 (Longest Increasing Path in a Matrix)

类似的东西还有: 674. Longest Continuous Increasing Subsequence https://leetcode.com/problems/longest-continuous-increasing-subsequence/description/ 300. Longest Increasing Subsequence https://leetcode.com/problems/longest-increasing-subsequence/description/ longest path increasing by 1 https://www.geeksforgeeks.org/find-the-longest-path-in-a-matrix-with-given-constraints/   下面的代码是这个题的: 329. Longest Increasing Path in a Matrix https://leetcode.com/problems/longest-increasing-path-in-a-matrix/description/  主要思路就是瞎JB搜索,不过某一个位置的结果可以记录下来给后续的重复搜索使用。

 

LeetCode 128. Longest Consecutive Sequence

https://leetcode.com/problems/longest-consecutive-sequence/description/

 

LeetCode 200. Number of Islands

https://leetcode.com/problems/number-of-islands/description/ DFS of a map, O(N^2)

 

LeetCode 23. Merge k Sorted Lists

https://leetcode.com/problems/merge-k-sorted-lists/description/ Use max heap, the time complexity is O( log(k) * N )

 

LeetCode 222. Count Complete Tree Nodes

https://leetcode.com/problems/count-complete-tree-nodes/description/ 简单的二分法分治,探测(子)树的左右侧是否相等即可。 (下面代码没实现)想要更快的话,其实自从第一次算出左侧的深度后,后面的左测深度直接可以通过减法求出,不用再去探测一次了。

 

LeetCode 76. Minimum Window Substring

76. Minimum Window Substring 思路: 构造一个哈希表结构统计我们的需求,也就是字符串t中每个字符的数量,方便起见如果有需求则哈希表的对应值-1。另外存储一下当前解的起始位置START以及最优解的位置。 扫描字符串s,在位置s[i]时如果能够满足需求(即哈希表中没有负值),则从START开始清除无用的字符直至无法满足需求位置。比如需求是A:1, B:2,START开始的字符是DEFBAB,则清除DEF。清除完成后更新START值并跟当前已知的最优解比较,更新最优解。 啰嗦一句,似乎相当一部分substring类型的题目都能用hash table + two pointers的方式解决。