和极值相关的题目：

  • DP
  • Map / Set
  • Sort

problems that involved 1 or 2 passes from left to right/right to left:

42.Trapping Rain Water 3
53 Maximum Subarray  
121 Best Time to Buy and Sell Stock  
152 Maximum Product Subarray  
238 Product of Array Except Self  
739 Daily Temperatures  
769 Max Chunks to Make Sorted  
770 Max Chunks to Make Sorted II  
821 Shortest Distance to a Character  
845 Longest Mountain in Array
849 Maximize Distance to Closest Person

几个必须“背诵”的贪心算法题

2018年4月更新 https://www.jiuzhang.com/qa/2099/
http://www.lintcode.com/problem/majority-number/
http://www.lintcode.com/problem/create-maximum-number/
http://www.lintcode.com/problem/jump-game-ii/
http://www.lintcode.com/problem/jump-game/
http://www.lintcode.com/problem/gas-station/
http://www.lintcode.com/problem/delete-digits/
http://www.lintcode.com/problem/task-scheduler/

BFS

图的遍历 Traversal in Graph

图的遍历，比如给出无向连通图(Undirected Connected Graph)中的一个点，找到这个图里的所有点。这就是一个常见的场景。
LintCode 上的Clone Graph就是一个典型的练习题。

更细一点的划分的话，这一类的问题还可以分为：

  • 层级遍历 Level Order Traversal
  • 由点及面 Connected Component
  • 拓扑排序 Topological Sorting

层级遍历，也就是说我不仅仅需要知道从一个点出发可以到达哪些点，还需要知道这些点，分别离出发点是第几层遇到的，比如Binary Tree Level Order Traversal就是一个典型的练习题。

由点及面，前面已经提到。

拓扑排序，让我们在后一节中展开描述。

最短路径 Shortest Path in Simple Graph

最短路径算法有很多种，BFS 是其中一种，但是他有特殊的使用场景，即必须是在简单图中求最短路径。
大部分简单图中使用 BFS 算法时，都是无向图。当然也有可能是有向图，但是在面试中极少会出现。

什么是简单图（Simple Graph）？

即，图中每条边长度都是1（或边长都相同）。

BFS求最短路径 (包括隐式图126. Word Ladder II

126. Word Ladder II Hard Two-end BFS
127. Word Ladder Medium
296. Best Meeting Point Hard BFS会TLE
317. Shortest Distance from All Buildings Hard
542. 01 Matrix Medium
787. Cheapest Flights Within K Stops Medium Dijkstra's Algorithm
847. Shortest Path Visiting All Nodes Hard
854. K-Similar Strings Hard

Merge Sort

315. Count of Smaller Numbers After Self
327. Count of Range Sum
363. Max Sum of Rectangle No Larger Than K
493. Reverse Pairs 
Subarray
53. Maximum Subarray 返回最大的子数组和 (L, M) DP O(n); O(n)
152. Maximum Product Subarray 返回最大的子数组积 ALL 双DP O(n); O(n)
209. Minimum Size Subarray Sum 正数 返回子数组和大于等于给定值的，最短的子数组的长度 (F) 模板 同向Two Pointers O(n);O(1)
325 Maximum Size Subarray Sum Equals k 返回和为k的，最长的子数组的长度 (F, Pa) 模板 preSum index 考简化版HashSet O(n);O(n)HashMap O(n);O(n)
410. Split Array Largest Sum 难 返回将原数组分成m个子数组中的最小的最大和 Binary Search O(n sum(array)); O(n)
523. Continuous Subarray Sum 非负数 返回是否存在一个子数组，和等于给定值的倍数且长度大于等于2 (F) 模板 preSum index HashSet O(n);O(k) HashMap O(n);O(k)
525. Contiguous Array 返回有相等数量的0和1的，最长的子数组的长度 (F) 模板 preSum index HashMap O(n);O(n) DP O(n);O(n) 比HashMap快一倍
560. Subarray Sum Equals K 返回和为k的子数组的总数 (G) 模板 preSum count HashMap O(n);O(1)
548. Split Array with Equal Sum 比较难 (F) 好像不考这题，考简化版
581. Shortest Unsorted Continuous Subarray 返回未排序的，最短的子数组的长度 (G)与众不同 Sort O(n log n); O(n) Ascending Stack + Descending Stack O(n); O(n)
643. Maximum Average Subarray I 返回长度为k，平均值最大的子数组的平均值 (A, G) 最简单的滑动窗口 PreSum O(n);O(1)
644. Maximum Average Subarray II 难 返回长度>=k，平均值最大的子数组的平均值 (G) Binary Search O(n log(max - min)); O(1)
689. Maximum Sum of 3 Non-Overlapping Subarrays 难 返回3个不重叠&和最大的子数组的开始索引 (F, G) 双DP O(n); O(n)
697. Degree of an Array 返回和原数组有相同度数的最短子数组的长度 (B, Po) 解法很tricky，value存3个信息 HashMap O(n);O(n)
713. Subarray Product Less Than K 返回子数组积小于k的数量 (F, B) 模板 有变化 同向Two Pointers O(n); O(1)
718. Maximum Length of Repeated Subarray 返回A B两个数组中最长重复子数组的长度 和最长公共子串一样 HashMap O(m * n * min (m, n)); O(n) DP O(m * n); O(n)
795. Number of Subarrays with Bounded Maximum 返回子数组中最大值在[L, R]区间的数量 (Ad) 不是模板 同向Two Pointers O(n); O(1)
862. Shortest Subarray with Sum at Least K 难 返回和至少为k的最短子数组的长度 (F) Deque O(n); O(n)

results matching ""

    No results matching ""