leetcode前400题分类

• 算法小抄

Array

• 27. Remove Element
• 26. Remove Duplicates from Sorted Array
• 189. Rotate Array: 解析

方法一：每次移动一个数字，进行k次移动
方法二：翻转：[1, 2, 3, 4, 5, 6, 7]；第一次，[1, 2, 3, 4, 7, 6, 5]；第二次，[4, 3, 2, 1, 7, 6, 5]；第三次：[5, 6, 7, 1, 2, 3, 4]
方法三：循环swap：不太好理解

• 41. First Missing Positive: 解析

解析中用到原地交换，这个方法不太好理解

• 299. Bulls and Cows: 解析
• 134. Gas Station: 解析
• 119. Pascal's Triangle II: 解析

O(k)空间复杂度，注意方法

• 169. Majority Element: 解析

常规方法：HashMap存放数字出现次数，找出众数；摩尔投票：设定候选，进行计数，每走一步，相等计数加1，不等减1，计数为0，重设候选

• 229. Majority Element II: 解析
• 274. H指数 : 解析

H指数不好理解，简单说，有h篇文章引用不小于h次；解析中的计数排序方法很不错.

• 243. Shortest Word Distance

顺便可以看看follow up

• 244. Contains Duplicate II: 解析
• 245. Contains Duplicate III : 解析

这两道题用了 TreeSet, 桶排序算法

二分查找

• 278. First Bad Version

二分查找，注意两处翻转：mid = (right + left) / 2；left + 1 < right

• 162. Find Peak Element : 解析

栈

• 84. Largest Rectangle in Histogram: 解析

堆 & QuickSelect 算法 --- TopK问题

• TopK问题一般有两种解法，一是利用最大/小堆，一是利用quickSelect算法

java中的PriorityQueue默认是最小堆；
QuickSelect算法，还是两步，一是partition,二是递归
[215. Kth Largest Element in an Array](Kth Largest Element in an Array)可以用这道题练习

• 347. Top K Frequent Elements: 解析

lambda表达式实现ComparatorComparator<Integer> c = (n1, n2) -> {n1 - n2}；lambda表达式是利用闭包原理