# 004. Median of Two Sorted Arrays

## Description: 寻找两个有序数组的中位数

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:

Example 2:

## 解法一: 根据中位数的特性

• i+j = m-i + n-j 或 m-i + n-j + 1 (加1的原因是因为有可能数组总长为奇数, 我们令前一部分比后一部分多1个元素)
• i=0 或 A[i-1] <= B[j] (前者说明 A 中元素全部被分配到后半段, 即前半段元素均由 B 中元素组成)
• i=m 或 B[j-1] <= A[i] (前者说明 A 中元素全部在前半段, 即后半段元素均由 B 中元素组成)
• 由于上式 i+j = m-i + n-j 或 m-i + n-j + 1 , 因此有 j = (m+n+1)/2 - i ; (向下取整). 故而可以只对 i 进行判断 i 是否越界, 只要 i 满足条件, j就不会等于0或n(前提条件是 A 数组长度小于等于 B 数组长度)

• 根据两数组的长度, 将短的一方设为A数组 (j要对应较长的那个数组, 否则的话j有可能小于0 ), 令start=0, end=A.size
• 令 i=(start+end)/2
• 计算j = (m+n+1)/2 - i
• 判断当前 i 和 j 是否满足条件,有三种情况(对这三种情况不断重复, 直到i,j位置刚刚好):
• i > 0 并且 A[i-1] > B[j], 说明 i 的位置过大, 令 end = i-1.
• i < m 并且 B[j-1] > A[i], 说明 i 的位置过小, 令 start = i+1;
• 其他情况(i==0 或 A[i-1] <= B[j] 并且 i==m 或 B[j-1] <= A[i]), 说明 i 和 j的位置刚刚好.
• 当i,j位置刚好时, 根据数组整体长度的奇偶, 返回正确的中位数:
• 奇数: 返回前半段的最大元素
• 偶数: 返回前半段最大元素和后半段最小元素的平均值

# 010 Regular Expression Matching

## Description: 正则表达式匹配

Given an input string (s) and a pattern (p), implement regular expression matching with support for ‘.’ and ‘*’.

‘.’ Matches any single character.
‘*’ Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).

Note:
s could be empty and contains only lowercase letters a-z.
p could be empty and contains only lowercase letters a-z, and characters like . or *.

Example 1:

Example 2:

Example 3:

Example 4:

Example 5:

‘, 则按正常匹配处理.

## 解法二: 动态规划

This problem has a typical solution using Dynamic Programming. We define the state P[i][j] to be true if s[0..i) matches p[0..j) and false otherwise. Then the state equations are:

• P[i][j] = P[i - 1][j - 1], if p[j - 1] != ‘*’ && (s[i - 1] == p[j - 1] || p[j - 1] == ‘.’);
• P[i][j] = P[i][j - 2], if p[j - 1] == ‘*’ and the pattern repeats for 0 times;
• P[i][j] = P[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == ‘.’), if p[j - 1] == ‘*’ and the pattern repeats for at least 1 times.

Putting these together, we will have the following code.

# 023. Merge k Sorted Lists

## Description: 合并 k 个有序链表

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

# 041. First Missing Positive

## Description

Given an unsorted integer array, find the smallest missing positive integer.

Example 1:

Input: [1,2,0]
Output: 3
Example 2:

Input: [3,4,-1,1]
Output: 2
Example 3:

Input: [7,8,9,11,12]
Output: 1
Note:

Your algorithm should run in O(n) time and uses constant extra space.

## 解法一: 下标与正数对应

• swap之后需要继续将原来位置上(nums[4])的数放置到正确的位置上, 这里需要一个while循环
• 在检查数组时, 如果所有数组内所有数字都处在正确位置上, 那么就应该返回nums.size+1 (包括了数组为空的情况: 返回0+1=1)

## 解法二: 哈希

1. for any array whose length is l, the first missing positive must be in range [1,…,l+1],
so we only have to care about those elements in this range and remove the rest.
2. we can use the array index as the hash to restore the frequency of each number within
the range [1,…,l+1]

# 042 Trapping Rain Water

## Description

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Example:

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

# 044. Wildcard Matching

## Description: 通配符匹配

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for ‘?’ and ‘*’.

‘?’ Matches any single character.
‘*’ Matches any sequence of characters (including the empty sequence).
The matching should cover the entire input string (not partial).

Note:

s could be empty and contains only lowercase letters a-z.
p could be empty and contains only lowercase letters a-z, and characters like ? or *.
Example 1:

Input:
s = “aa”
p = “a”
Output: false
Explanation: “a” does not match the entire string “aa”.
Example 2:

Input:
s = “aa”
p = “
Output: true
Explanation: ‘
‘ matches any sequence.
Example 3:

Input:
s = “cb”
p = “?a”
Output: false
Explanation: ‘?’ matches ‘c’, but the second letter is ‘a’, which does not match ‘b’.
Example 4:

Input:
p = “ab”
Output: true
Explanation: The first ‘‘ matches the empty sequence, while the second ‘‘ matches the substring “dce”.
Example 5:

Input:
s = “acdcb”
p = “a*c?b”
Output: false

# 076. Minimum Window Substring

## Description

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

Example:

Input: S = “ADOBECODEBANC”, T = “ABC”
Output: “BANC”
Note:

If there is no such window in S that covers all characters in T, return the empty string “”.
If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

## 子串相关题目的模板解法

https://leetcode.com/problems/minimum-window-substring/discuss/26808/Here-is-a-10-line-template-that-can-solve-most-'substring'-problems

# 084. Largest Rectangle in Histogram

## Description

Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Example:
Input: [2,1,5,6,2,3]
Output: 10

## 解法三: 最优-栈

• 首先, 构造一个空栈
• 从heights数组的第一个bar开始, 遍历所有的bar值(0~n-1), 并执行以下逻辑:
• 如果当前栈为空, 或者当前数组bar值大于等于栈顶bar值, 则将bar值下标入栈
• 否则, 将栈顶出栈, 并以栈顶下标对应的bar值作为最低的高度, 求该高度对应的面积, 因为当前数组bar值小于栈顶下标对应的bar值, 因此可以将当前bar值下标作为right_index, 又因为栈顶bar值下标的前一个元素, 要么小于栈顶, 要么等于栈顶, 不论哪种情况, 都可以将其下标作为left_index(因为栈顶退出对, 次栈顶就会成为新的栈顶, 所以可以包括bar值相等的情况), 得到了高度, right_index, left_index, 即可计算当前栈顶对应的面积, 并与max_area判断, 更新max_area的值
• 最后, 如果遍历完以后栈顶不为空(说明后面有几个连续的bar值相等, 或者bar只呈递增排序), 则依次强制弹出栈顶计算面积, 并更新max_area.

# 124. Binary Tree Maximum Path Sum

## Description: 求最长路径加权和

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:

Example 2:

# 128. Longest Consecutive Sequence

## Description

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

Your algorithm should run in O(n) complexity.

Example:

Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

# 140. Word Break II

## Description

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:

Input:
s = “catsanddog”
wordDict = [“cat”, “cats”, “and”, “sand”, “dog”]
Output:
[
“cats and dog”,
“cat sand dog”
]
Example 2:

Input:
s = “pineapplepenapple”
wordDict = [“apple”, “pen”, “applepen”, “pine”, “pineapple”]
Output:
[
“pine apple pen apple”,
“pineapple pen apple”,
“pine applepen apple”
]
Explanation: Note that you are allowed to reuse a dictionary word.
Example 3:

Input:
s = “catsandog”
wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]
Output:
[]

# 149. Max Points on a Line

## Description 最大的共线点个数

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

Example 1:

Input: [[1,1],[2,2],[3,3]]
Output: 3
Explanation:
^
|
| o
| o
| o
+——————->
0 1 2 3 4
Example 2:

Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4
Explanation:
^
|
| o
| o o
| o
| o o
+—————————->
0 1 2 3 4 5 6

## 解法一: 哈希表

• 对于每一个点来说, 构造一个哈希表, 表中的键为斜率, 表中的值为对应斜率的点的个数, 这里注意, 当我们求完第i个点与第j个点之间的斜率之后, 就不用再求第j个点与第i个点之间的斜率情况了(即令int j = i+1, 而不是int j = 0)
• 对于重点的情况, 需要单独设置一个变量来记录, 之后将该重复次数加入到该点所在的每条直线上(因为重点也算是共线)
• 对于斜率不存在的情况, 可以考虑利用INT_MAX来作为键值
• 精度: 在求取斜率时, 会进行除法, 而在计算机内部, 除法在精度上始终会有一定误差, 会造成斜率相同的两对点在计算成浮点数以后斜率不同, 因此, 要 避免使用除法, 解决办法是利用 最大公约数, 求取y2-y1x2-x1之间的最大公约数, 然后对进行约分, 用约分后的值作为键来存储, 就不会造成精度上的损失, 但是, 此时需要用pair作为键, 故不能用unordered_map(C++没有为pair类型提供对应的哈希函数), 而只能用map(键只有重载了<>就可以使用map, 搜索的时间复杂度为 $O(logn)$), 另一种可选做法是利用string类型, 将两个int数值转换成string后再拼接, 此时就可以使用unordered_map了(搜索的时间复杂度为 $O(1)$, 但是intstring的类型转换也需要消耗时间).
• 当采用公约数以后, 因为没有了除法, 因此可以不用特殊处理斜率不存在的情况, 代码更加简洁.

# 212. Word Search II

## Description: 返回字符矩阵中含有的所有单词

Given a 2D board and a list of words from the dictionary, find all words in the board.

Each word must 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 in a word.

Example:

Input:
words = [“oath”,”pea”,”eat”,”rain”] and board =
[
[‘o’,’a’,’a’,’n’],
[‘e’,’t’,’a’,’e’],
[‘i’,’h’,’k’,’r’],
[‘i’,’f’,’l’,’v’]
]

Output: [“eat”,”oath”]

# 218. The Skyline Problem

## Description: 天际线问题

A city’s skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you are given the locations and height of all the buildings as shown on a cityscape photo (Figure A), write a program to output the skyline formed by these buildings collectively (Figure B).

The geometric information of each building is represented by a triplet of integers [Li, Ri, Hi], where Li and Ri are the x coordinates of the left and right edge of the ith building, respectively, and Hi is its height. It is guaranteed that 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX, and Ri - Li > 0. You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.

For instance, the dimensions of all buildings in Figure A are recorded as: [ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] .

The output is a list of “key points” (red dots in Figure B) in the format of [ [x1,y1], [x2, y2], [x3, y3], … ] that uniquely defines a skyline. A key point is the left endpoint of a horizontal line segment. Note that the last key point, where the rightmost building ends, is merely used to mark the termination of the skyline, and always has zero height. Also, the ground in between any two adjacent buildings should be considered part of the skyline contour.

For instance, the skyline in Figure B should be represented as:[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ].

## 解法一: multiset

• i+1 坐标上新来的建筑物(遇到该建筑物左侧就行)完全被之前的建筑物覆盖, 此时不更新 res 轮廓. 说明添加了该建筑物后, 并不改变当前建筑群的最高高度.
• i+1 坐标上新来的建筑物比当前建筑群最高的高度还要高, 则需要记录当前的点.
• i+1 坐标上没有新来建筑物, 但是有一个建筑物遇到了右侧边界, 此时建筑群的高度会变成第二高建筑物的高度, 同样需要记录当前的坐标点.
• i+1 坐标上既没有新来建筑物, 也没有遇到建筑物右侧, 此时无需记录任何值, 可继续探测 i+2 坐标.

# 239. Sliding Window Maximum

## Description: 滑动窗口的最大值

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.

Example:

Note:
You may assume k is always valid, 1 ≤ k ≤ input array’s size for non-empty array.

Could you solve it in linear time?

## 解法一: 双端队列

• 当前元素是否比队列中最后一个元素大, 如果大, 说明队列元素以后也不可能再成为较大值, 直接pop, 如此循环, 直到队列为空或者遇到比当前值大的元素
• 判断队列中队首的元素是否过期(若队空则直接下一步, 无需判断), 若过期, 则pop, 否则, 不管( 只看队首, 队内的元素是否过期不影响算法, 因为就算过期后面也会将其淘汰)
• 将当前元素的下标存到队尾
• 将新的队首元素存到结果向量max_res中

# 295. Find Median from Data Stream

## Description: 返回数据流的中位数

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

For example,
[2,3,4], the median is 3
[2,3], the median is (2 + 3) / 2 = 2.5

Design a data structure that supports the following two operations:

• void addNum(int num) - Add a integer number from the data stream to the data structure.
• double findMedian() - Return the median of all elements so far.

Example:

1. If all integer numbers from the stream are between 0 and 100, how would you optimize it?
2. If 99% of all integer numbers from the stream are between 0 and 100, how would you optimize it?