# 快速搜索相关

## Kth Largest Element in an Array

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

1 | Example 1: |

1 | class Solution { |

## Wiggle Sort II

Given an unsorted array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]….

1 | Example 1: |

1 | class Solution { |

Follow Up: Can you do it in O(n) time and/or in-place with O(1) extra space?

主要思想是先用快速找到中间的数，然后利用快搜中partition的思想将前半数据放到奇数位上，后半段的数放入偶数位，解释可以参考Discuss

1 | void wiggleSort(vector<int>& nums) { |

# 并查集

## Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Your algorithm should run in O(n) complexity.

Example:

1 | Input: [100, 4, 200, 1, 3, 2] |

1 | class Solution { |

# BFS

BFS因为占用的空间比较大且一般时间比较长，所以经常用在需要全部数据都要检索的题目上，一般的类型包括：

- 图上任意两点之间的距离
- 图的拓扑排序
- 树与层数相关的题目，例如树形图的直径，寻找根节点等
- 可能还有其他的类型，之后会来补充…

## Course Schedule （拓扑排序）

There are a total of n courses you have to take, labeled from 0 to n-1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

1 | Example 1: |

1 | class Solution { |

## Minimum Height Trees

For a undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a list of their root labels.

Format

The graph contains n nodes which are labeled from 0 to n - 1. You will be given the number n and a list of undirected edges (each edge is a pair of labels).

You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

Example 1 :

1 | Input: n = 4, edges = [[1, 0], [1, 2], [1, 3]] |

Example 2 :

1 | Input: n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]] |

1 | class Solution { |

## Reconstruct Itinerary

Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK.

Note:

If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary [“JFK”, “LGA”] has a smaller lexical order than [“JFK”, “LGB”].

All airports are represented by three capital letters (IATA code).

You may assume all tickets form at least one valid itinerary.

Example 1:

1 | Input: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]] |

Example 2:

1 | Input: [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]] |

1 | // 欧拉环路 |

## Populating Next Right Pointers in Each Node

Given a binary tree

1 | struct TreeLinkNode { |

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Note:

You may only use constant extra space.

Recursive approach is fine, implicit stack space does not count as extra space for this problem.

You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

Example:

1 | Given the following perfect binary tree, |

1 | /** |

# DFS

## Binary Tree Maximum Path Sum

Given a non-empty binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

Example 1:

1 | Input: [1,2,3] |

Example 2:

1 | Input: [-10,9,20,null,null,15,7] |

1 | /** |

## Kth Smallest Element in a BST

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note:

You may assume k is always valid, 1 ≤ k ≤ BST’s total elements.

Example 1:

1 | Input: root = [3,1,4,null,2], k = 1 |

Example 2:

1 | Input: root = [5,3,6,2,4,null,null,1], k = 3 |

1 | /** |

## Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

1 | [ |

1 | class Solution { |

## House Robber III

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the “root.” Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that “all houses in this place forms a binary tree”. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

Example 1:

1 | Input: [3,2,3,null,3,null,1] |

Example 2:

1 | Input: [3,4,5,1,3,null,1] |

1 | /** |

## Decode String

Given an encoded string, return it’s decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.

Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won’t be input like 3a or 2[4].

Examples:

1 | s = "3[a]2[bc]", return "aaabcbc". |

1 | class Solution { |

## Matchsticks to Square

Remember the story of Little Match Girl? By now, you know exactly what matchsticks the little match girl has, please find out a way you can make one square by using up all those matchsticks. You should not break any stick, but you can link them up, and each matchstick must be used exactly one time.

Your input will be several matchsticks the girl has, represented with their stick length. Your output will either be true or false, to represent whether you could make one square using all the matchsticks the little match girl has.

Example 1:

1 | Input: [1,1,2,2,2] |

Example 2:

1 | Input: [3,3,3,3,4] |

1 | class Solution { |

follow up: Partition to K Equal Sum Subsets

Given an array of integers nums and a positive integer k, find whether it’s possible to divide this array into k non-empty subsets whose sums are all equal.

Example 1:

1 | Input: nums = [4, 3, 2, 3, 5, 2, 1], k = 4 |

1 | class Solution { |

## Subsets II

DescriptionHintsSubmissionsDiscussSolution

Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

1 | Input: [1,2,2] |

1 | class Solution { |

## Word Search

DescriptionHintsSubmissionsDiscussSolution

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example:

1 | board = |

1 | class Solution { |

## Longest Increasing Path in a Matrix

Given an integer matrix, find the length of the longest increasing path.

From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

Example 1:

1 | Input: nums = |

Example 2:

1 | Input: nums = |

1 | class Solution { |

## Word Break II

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.

Note:

The same word in the dictionary may be reused multiple times in the segmentation.

You may assume the dictionary does not contain duplicate words.

Example 1:

1 | Input: |

Example 2:

1 | Input: |

Example 3:

1 | Input: |

1 | class Solution { |

## Add and Search Word - Data structure design

Design a data structure that supports the following two operations:

void addWord(word)

bool search(word)

search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.

Example:

1 | addWord("bad") |

1 | struct TrieNode { |

## Reconstruct Itinerary

Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK.

Note:

If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary [“JFK”, “LGA”] has a smaller lexical order than [“JFK”, “LGB”].

All airports are represented by three capital letters (IATA code).

You may assume all tickets form at least one valid itinerary.

Example 1:

1 | Input: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]] |

Example 2:

1 | Input: [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]] |

1 | // dfs 版本 |

## Construct Binary Tree from Inorder and Postorder Traversal

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:

You may assume that duplicates do not exist in the tree.

For example, given

1 | inorder = [9,3,15,20,7] |

1 | /** |

## Restore IP Addresses

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

Example:

1 | Input: "25525511135" |

1 | class Solution { |

## Different Ways to Add Parentheses

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *.

Example 1:

1 | Input: "2-1-1" |

Example 2:

1 | Input: "2*3-4*5" |

1 | class Solution { |

## Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

Example:

1 | Input: "aab" |

1 | class Solution { |

## Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Example:

1 | Input: [1,1,2] |

1 | class Solution { |

## Permutation Sequence

The set [1,2,3,…,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order, we get the following sequence for n = 3:

1 | "123" |

Note:

Given n will be between 1 and 9 inclusive.

Given k will be between 1 and n! inclusive.

Example 1:

1 | Input: n = 3, k = 3 |

Example 2:

1 | Input: n = 4, k = 9 |

1 | class Solution { |

1 | // next permutation 版本 |

# 二分查找

二分查找一般用来简化查找逻辑，将O(n)降低成O(logn)，但是由于左右边界更新的细节比较多，每个题都需要单独推导分析

## Missing Number

Given an array containing n distinct numbers taken from 0, 1, 2, …, n, find the one that is missing from the array.

Example 1:

1 | Input: [3,0,1] |

Example 2:

1 | Input: [9,6,4,2,3,5,7,0,1] |

1 | // 除此之外还有循环替换算法以及位操作算法 |

## Search a 2D Matrix

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

- Integers in each row are sorted from left to right.
- The first integer of each row is greater than the last integer of the previous row.

Example 1:

1 | Input: |

Example 2:

1 | Input: |

1 | // 线性扫描 |

1 | // 二分法 |

## Search a 2D Matrix II

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

- Integers in each row are sorted in ascending from left to right.
- Integers in each column are sorted in ascending from top to bottom.

Example:

1 | Consider the following matrix: |

1 | // 其实也就是二分查找的思想，右侧路过的值就是查找空间的上界，左侧路过的值是下界 |

## Kth Smallest Element in a Sorted Matrix

Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.

Note that it is the kth smallest element in the sorted order, not the kth distinct element.

Example:

1 | matrix = [ |

1 | // upper_bound是找到大于该值的第一个数，lower_bound是找到大于等于该值的第一个数 |

## Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

1 | nums1 = [1, 3] |

Example 2:

1 | nums1 = [1, 2] |

1 | typedef vector<int>::iterator Iter; |

## Find Right Interval

Given a set of intervals, for each of the interval i, check if there exists an interval j whose start point is bigger than or equal to the end point of the interval i, which can be called that j is on the “right” of i.

For any interval i, you need to store the minimum interval j’s index, which means that the interval j has the minimum start point to build the “right” relationship for interval i. If the interval j doesn’t exist, store -1 for the interval i. Finally, you need output the stored value of each interval as an array.

Note:

You may assume the interval’s end point is always bigger than its start point.

You may assume none of these intervals have the same start point.

Example 1:

1 | Input: [ [1,2] ] |

Example 2:

1 | Input: [ [3,4], [2,3], [1,2] ] |

Example 3:

1 | Input: [ [1,4], [2,3], [3,4] ] |

1 | /** |

## Find First and Last Position of Element in Sorted Array

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

Example 1:

1 | Input: nums = [5,7,7,8,8,10], target = 8 |

Example 2:

1 | Input: nums = [5,7,7,8,8,10], target = 6 |

1 | class Solution { |

## Find Minimum in Rotated Sorted Array

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

Find the minimum element.

You may assume no duplicate exists in the array.

Example 1:

1 | Input: [3,4,5,1,2] |

Example 2:

1 | Input: [4,5,6,7,0,1,2] |

1 | class Solution { |

## Search in Rotated Sorted Array

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Your algorithm’s runtime complexity must be in the order of O(log n).

Example 1:

1 | Input: nums = [4,5,6,7,0,1,2], target = 0 |

Example 2:

1 | Input: nums = [4,5,6,7,0,1,2], target = 3 |

1 | class Solution { |

## Search in Rotated Sorted Array II

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]).

You are given a target value to search. If found in the array return true, otherwise return false.

Example 1:

1 | Input: nums = [2,5,6,0,0,1,2], target = 0 |

Example 2:

1 | Input: nums = [2,5,6,0,0,1,2], target = 3 |

Follow up:

- This is a follow up problem to Search in Rotated Sorted Array, where nums may contain duplicates.
- Would this affect the run-time complexity? How and why?

1 | class Solution { |

## Koko Eating Bananas (*)

Koko loves to eat bananas. There are N piles of bananas, the i-th pile has piles[i] bananas. The guards have gone and will come back in H hours.

Koko can decide her bananas-per-hour eating speed of K. Each hour, she chooses some pile of bananas, and eats K bananas from that pile. If the pile has less than K bananas, she eats all of them instead, and won’t eat any more bananas during this hour.

Koko likes to eat slowly, but still wants to finish eating all the bananas before the guards come back.

Return the minimum integer K such that she can eat all the bananas within H hours.

Example 1:

1 | Input: piles = [3,6,7,11], H = 8 |

Example 2:

1 | Input: piles = [30,11,23,4,20], H = 5 |

Example 3:

1 | Input: piles = [30,11,23,4,20], H = 6 |

Note:

- 1 <= piles.length <= 10^4
- piles.length <= H <= 10^9
- 1 <= piles[i] <= 10^9

1 | // 二分答案，类似于求绝对值差值第K大那道题 |

# 特殊题目

还未归类的题目放到这里，此部分待编辑

## 数组中的逆序对 (*)

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007

思路可以参考牛客网

1 | class Solution { |