654. Maximum Binary Tree

Given an integer array with no duplicates. A maximum tree building on this array is defined as follow:

  1. The root is the maximum number in the array.
  2. The left subtree is the maximum tree constructed from left part subarray divided by the maximum number.
  3. The right subtree is the maximum tree constructed from right part subarray divided by the maximum number.

Construct the maximum tree by the given array and output the root node of this tree.

 

 

LeetCode 89. Gray Code

Divide and conquer!

Add a leading 0 or 1 bit to your existing results so here comes two sub-results: 0{xxxxx} and 1{xxxxx}. How to merge them? Just keep the first sub group and append the second group items reversely so that there is only a 1-bit difference between the end of group 0 and “start” of group 2.

 

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:

Note:

  1. You may assume all letters are in lowercase.
  2. You may assume that if a is a prefix of b, then a must appear before b in the given dictionary.
  3. If the order is invalid, return an empty string.
  4. There may be multiple valid order of letters, return any one of them is fine.

 

Solution:

The solution is to build a directed map and find the topological ordering of the characters. Once the map is built, we can always find the “terminal” character which has no succeeding, i.e. the out-degree of that node would be zero. The we remove the character (the node and its edges) from the map and try to find the next such character, so on so forth.

For example,  the map built will be:

 

 

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)