LeetCode 402. Remove K Digits

https://leetcode.com/problems/remove-k-digits/description/ 如果直接用DFS做的话轻轻松松就会stack overflow。 这道题可以用贪心法,题目换个思路说就是尽可能保证得到的数字是递增的。在拿到一个新数字时,尽可能(只要还能删)把该数字之前的比它大的数字移掉。 贪心法之所以能用是因为我们去尽量保证了a1<a2< …< x< y,如果这些个数字里要选一个删掉的话,肯定是删掉y带来的结果最好。

 

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/ 简单的二分法分治,探测(子)树的左右侧是否相等即可。 (下面代码没实现)想要更快的话,其实自从第一次算出左侧的深度后,后面的左测深度直接可以通过减法求出,不用再去探测一次了。