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:1
2
3
4nums1 = [1, 3]
nums2 = [2]
The median is 2.0
Example 2:1
2
3
4nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
解法一: 根据中位数的特性
题目要求需要时间复杂度为 $O(log (m+n))$.
空间复杂度: $O(1)$, 未使用额外空间
首先我们思考中位数的作用: 中位数可以将一个数组分成两个长度相同的部分, 并且一部分中的数字总比另一部分中的小. 那么对于两个数组的情况, 我们需要做的就是找到一个数字, 可以使这两个数组分别分成两部分, 这两部分长度相等(当个数为奇数时, 前一部分多一个元素), 同时前一部分的元素小于等于后一部分的元素. 首先,我们将数组 A 分成两部分, 由于 A 有 m 个数字, 所以它可以有 m 种不同的分法, 我们以下标 i 对应的数字为界限, 将A分成两部分, 前一部分的长度为 i (从0到 i-1 ), 后一部分的长度为 m-i (从 i 到 m-1): A[1,2,...,i-1] | A[i, i+1, ..., m-1]. 同理,数组 B 也可以做如下分割: B[1,2,...,j-1] | B[j, j+1, ..., n-1].
这里需要注意一个细节, 我们需要确保 A[i] 这个数字可以将两个数组等长的分割, 那么 A 数组的长度 必须小于等于 B 数组的长度. 因为如果 A 数组的长度大于 B 数组的长度, 那么就会出现一种情况: A[i] 前的数字个数已经大于两数组总个数的一半, 此时无论如何也做不到等长分割, 因此, 我们需要先对数组长度判断, 令 A 数组代表的是较短的数组, 利用 swap() 方法可以在 $O(1)$ 时间复杂度内完成.
当两个数组 A 和 B 都被分到了两部分以后, 将它们合起来, 第一部分的数字为 A[1,2,...,i-1] 和 B[1,2,...,j-1], 第二部分的数字为 A[i, i+1, ..., m-1] 和 B[j, j+1, ..., n-1], 我们并不关系两部分内部的顺序, 我们只关心一件事, 那就是: 第一部分和第二部分的长度相等, 并且第一部分的数字都比第二部分小, 于是, i 和 j和取值就必须满足下列关系:
- 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位置刚好时, 根据数组整体长度的奇偶, 返回正确的中位数:
- 奇数: 返回前半段的最大元素
- 偶数: 返回前半段最大元素和后半段最小元素的平均值
非递归写法
1 | class Solution { |
递归写法
写法一:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
if(nums1.size() <= nums2.size())
return helper(nums1, 0 , nums1.size(),nums2);
else
return helper(nums2, 0 , nums2.size(),nums1);
}
double helper(vector<int>& nums1, int start1, int end1, vector<int>& nums2){
int i = (start1+end1)/2;
int j = (nums1.size()+nums2.size()+1)/2 - i;
// if(start1 > end1) return 0.0; 因为数组一定是有效的, 因此不会出现这种情况
if( (i==0 || nums1[i-1]<=nums2[j]) && (i==nums1.size() || nums2[j-1]<=nums1[i])){ // 如果找到i
int res11, res12;
int res21, res22;
// 首先将左边部分的两个数组分别赋值, 如果i或j为0, 说明对应数组在左边
//只有0个元素 , 将其赋值为INT_MIN(因为要取max(res11, res21))
if(i==0) res11= INT_MIN;
else res11=nums1[i-1];
if(j==0) res21= INT_MIN;
else res21=nums2[j-1];
//同理, 对右边进行处理, 取min(res12, res22)
if(i==nums1.size()) res12= INT_MAX;
else res12=nums1[i];
if(j==nums2.size()) res22= INT_MAX;
else res22=nums2[j];
// 根据数组奇偶个数返回结果
if((nums1.size() + nums2.size())%2 == 1 ){
return max(res11, res21);
}
else{
return ( max(res11,res21)+min(res12,res22) ) / 2.0;
}
}else if(nums1[i-1] > nums2[j]){
return helper(nums1, start1, i-1, nums2);
}else{
return helper(nums1, i+1, end1, nums2);
}
}
};
写法二:
1 | class Solution { |
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:1
2
3
4
5Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
Example 2:1
2
3
4
5Input:
s = "aa"
p = "a*"
Output: true
Explanation: '*' means zero or more of the precedeng element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".
Example 3:1
2
3
4
5Input:
s = "ab"
p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".
Example 4:1
2
3
4
5Input:
s = "aab"
p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore it matches "aab".
Example 5:1
2
3
4Input:
s = "mississippi"
p = "mis*is*p*."
Output: false
解法一: 递归实现( 速度很慢, 只超过0.97%的提交)
采用递归法, 首先判断当前字符串 p 是否已经走到尽头, 如果是, 则看 s 是否走到尽头, 返回 true 或者 false.
然后在第一个字符的匹配情况, 并记录之.
然后看是否存在 ‘‘, 并根据情况进行递归调用.
若不存在 ‘‘, 则按正常匹配处理.
1 | class Solution { |
解法二: 动态规划
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.
1 | class Solution { |
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:1
2
3
4
5
6
7Input:
[
1->4->5,
1->3->4,
2->6
]
Output: 1->1->2->3->4->4->5->6
解法一: 基于比较的合并
时间复杂度: $O(k \times N)$ k为需要合并和链表个数, 在比较时需要遍历k个链表的头结点, 以便找出最小的. 每插入一个节点, 就要重新遍历一次, 故需要遍历 $N$ 次, $N$ 为所有链表的节点总数.
空间复杂度: $O(1)$
将该问题看做是两个有序链表的合并问题, 只不过每次选择最小的节点时, 需要从vector.size()个节点中选择, 同时还要注意及时移除vector中已经走到头的空链表, 并判断size当前的大小, 当vector中的size大小为1时, 说明其余链表都已经合并完成, 此时退出循环, 直接将该链表接入即可.
另外要注意vector为空, 以及vector中全是nullptr链表的特殊情况.
1 | /** |
解法二: 用小顶堆对解法一的比较操作进行优化
时间复杂度: $O(logk \times N)$, N 代表所有链表的节点总数.
空间复杂度: $O(k)$ 由于要构造堆, 所以需要额外空间
由于我们只需要找到k个节点里面数值最小的那一个, 因此可以利用Priority Queue (实际上就是大顶堆和小顶堆)对上面的比较操作进行优化, 使得比较操作的复杂度从 $k$ 降到 $logk$. 由于每个节点都会进入小顶堆一次, 所有总共需要执行 $N$ 次入堆操作, 故最终的复杂度的 $logk\times N$.
1 | /** |
解法三: 转化成双列表合并问题
时间复杂度: $O(k \times N)$
空间复杂度: $O(1)$
双列表合并问题的时间复杂度为 $O(m+n)$ , 可以将多链表合并问题看做是k次双列表合并.
解法四: 对解法三进行优化
时间复杂度: $O(logk \times N)$
空间复杂度: $O(1)$
对列表合并时, 每次都是两两合并(不是解法三中的逐一合并), 这样, 只需要经过 $logk$ 次两两合并就可完成所有合并过程.
迭代实现:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34class Solution {
private:
ListNode* mergeTwoLists(ListNode *l1, ListNode *l2){
ListNode *dummy = new ListNode(0);
ListNode *cur = dummy;
while(l1!=nullptr && l2!=nullptr){
if(l1->val < l2->val){
cur->next = l1;
cur = cur->next;
l1 = l1->next;
}else{
cur->next = l2;
cur = cur->next;
l2 = l2->next;
}
}
if(l1==nullptr) cur->next = l2;
else cur->next = l1;
return dummy->next;
}
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
if(lists.empty()) return nullptr;
int len = lists.size();
int interval = 1;
while(interval < len){
for(int i=0; i+interval<len; i+= 2*interval){//i应满足: 0,2,4... / 0,4,.. / 0
lists[i] = mergeTwoLists(lists[i], lists[i+interval]);//i+interval必须<len, 否则溢出
}
interval *= 2; //区间大小翻倍
}
return lists[0];
}
};
递归实现: 递归实现需要额外的 $O(logk)$ 的栈空间(调用递归的次数)1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
private:
ListNode* mergeTwoLists(ListNode *l1, ListNode *l2){
ListNode *dummy = new ListNode(0);
ListNode *cur = dummy;
while(l1!=nullptr && l2!=nullptr){
if(l1->val < l2->val){
cur->next = l1;
cur = cur->next;
l1 = l1->next;
}else{
cur->next = l2;
cur = cur->next;
l2 = l2->next;
}
}
if(l1==nullptr) cur->next = l2;
else cur->next = l1;
return dummy->next;
}
ListNode* partition(vector<ListNode*>& lists, int start, int end){
if(start==end){
return lists[start];
}else if(start < end){
int mid = (start+end)/2;
ListNode* l1 = partition(lists, start, mid);
ListNode* l2 = partition(lists, mid+1, end);
return mergeTwoLists(l1, l2);
}else
return nullptr;
}
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
if(lists.empty()) return nullptr;
return partition(lists, 0, lists.size()-1);
}
};
将双链表合并也写成递归形式:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
private:
ListNode* mergeTwoLists(ListNode *l1, ListNode *l2){
if(l1==nullptr) return l2;
else if(l2==nullptr) return l1;
else if(l1->val < l2->val){
l1->next = mergeTwoLists(l1->next, l2);
return l1;
}else{
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
}
ListNode* partition(vector<ListNode*>& lists, int start, int end){
if(start==end){
return lists[start];
}else if(start < end){
int mid = (start+end)/2;
ListNode* l1 = partition(lists, start, mid);
ListNode* l2 = partition(lists, mid+1, end);
return mergeTwoLists(l1, l2);
}else
return nullptr;
}
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
if(lists.empty()) return nullptr;
return partition(lists, 0, lists.size()-1);
}
};
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.
解法一: 下标与正数对应
时间复杂度: $O(n)$
空间复杂度: $O(1)$ (但是对改变了原始的数组, 这是一个小缺陷)
将下标与正数相应对, 例如对于正数5, 我们就将放置在nums[4]上, 这样一来, 再次遍历数组的时候, 当遇到第一个与下标不对应的数字时, 该下标对应的正数(i+1)就是缺少的正数.
放置正数到正确位置上时, 需要注意几点:
- swap之后需要继续将原来位置上(nums[4])的数放置到正确的位置上, 这里需要一个while循环
- 在检查数组时, 如果所有数组内所有数字都处在正确位置上, 那么就应该返回nums.size+1 (包括了数组为空的情况: 返回0+1=1)
写法一: for+while
1 | class Solution { |
写法二: while1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int i = 0;
while(i<nums.size()){
if(nums[i] > 0 &&nums[i]<nums.size() && nums[i] != nums[nums[i]-1])
std::swap(nums[i], nums[nums[i]-1]); // 如果进行了swap, 就不要i++
else
i++;
}
for(int i =0; i<nums.size(); i++){
if(nums[i] != i + 1)
return i+1;
}
return nums.size()+1;
}
};
解法二: 哈希
时间复杂度: $O(n)$ (3次for循环, 毫无争议的 $O(n)$ )
空间复杂度: $O(1)$ (但是对改变了原始的数组, 这是一个小缺陷)
注意: 虽然这里的时间复杂度是毫无争议的 $O(n)$ , 但是不一定会上面的速度快, 因为上面只有两次循环, 内第一次内部的循环次数一般情况下都不会很大.
从哈希的角度理解: 可以将数组下标看成是hash的key
- 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. - we can use the array index as the hash to restore the frequency of each number within
the range [1,…,l+1]
1 | class Solution { |
042 Trapping Rain Water
数组中每个值代表柱状体的高度, 每个柱状体的宽度都为1, 根据数组内的值组成的高低不同的块, 能够存储多少个bin (1×1)的水
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
解法一: 左右指针
时间复杂度: $O(n)$
空间复杂度: $O(1)$
分别用两个变量left和right指向左边和右边的柱子, 并再用两个变量maxleft和maxright维护左边最高的柱子和右边最高的柱子, 统计的时候, 先固定left和right当中柱子高度较高的那一个, 然后统计较低柱子上存储的水量. 利用, 如果当前left的高度小于right的高度, 则我们计算left上面能够存储的水量, 有两种情况, 当left柱子的高度大于等于maxleft时, 则left柱子上没法存储水, 因为谁会从左边全部流失(右边比左边高, 所以不会从右边流失). 如果left的高度小于maxleft时, 由于水无法从左边流失, 也不能从右边流失, 因此当前柱子上就会存储水, 存储的水量为maxleft-height[left] (不考虑maxright, 因为maxright大于maxleft).
注意: 此题中的柱子是有 宽度 的, 这一点很重要, 如果柱子的宽度为0 , 那么就是另一种情况了.
1 | class Solution { |
更简洁的写法:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21class Solution {
public:
int trap(vector<int>& height) {
if (height.empty()) return 0;
int left = 0, right = height.size() -1;
int maxLH = height[left], maxRH = height[right];
int res = 0;
while (left < right) {
maxLH = std::max(maxLH, height[left]);
maxRH = std::max(maxRH, height[right]);
if (height[left] < height[right]) {
res += maxLH - height[left];
left++;
} else {
res += maxRH - height[right];
right--;
}
}
return res;
}
};
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:
s = “adceb”
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
解法一: 迭代
时间复杂度: $O(m+n)$
空间复杂度: $O(1)$
对于每次循环迭代, i和j其中至少有一个前进一步, 所以时间复杂度为 $O(m+n)$.
1 | class Solution { |
解法二: DP
时间复杂度: $O(nm)$, $n$ 为s的长度, $m$ 为p的长度
空间复杂度: $O(n)$
1 | class Solution { |
解法三: DP
时间复杂度: $O(nm)$, $n$ 为s的长度, $m$ 为p的长度
空间复杂度: $O(nm)$
采用和第 10 题相同的思路, 令dp[i][j]代表s[0, i)和p[0,j)是否匹配, 该解法的空间复杂度比解法二高.
1 | class Solution { |
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.
解法: 两个变量记录当前窗口大小
时间复杂度: $O(n)$
空间复杂度: $O(1)$
1 | class Solution { |
子串相关题目的模板解法
对于大多数的子串相关的问题, 通常可以描述为给定一个字符串, 要求找到满足某些限制条件的子串, 这类都可以用下面的基于哈希表和两个辅助指示变量的模板来求解:
1 | int findSubstring(string s){ |
例如, 对于问题 Longest Substring At Two Distinct Characters 的模板解法如下:
对于问题 Longest Substring Without Repeating Characters 的模板解法如下:1
2
3
4
5
6
7
8
9
10int lengthOfLongestSubstring(string s){
vector<int> map(256,0);
int begin=0,end=0,len_sub=0,count=0;
while(end<s.size()){
if(map[int(s[end])] > 0) count++;
map[int(s[end])]++;
end++;
while(count>0) if(map[int(s[begin])] > 1) count;
}
}
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
解法一: 穷举
时间复杂度: $O(n^2)$, 超时
空间复杂度: $O(1)$
列出以每一个i上的值为矩形高度的矩形面积, 然后取得最大值1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int max_area = 0;
for(int i =0; i<heights.size(); i++){
int low = i;
while(low>=0 && heights[low] >=heights[i]) low--;
low++;
int high = i;
while(high<heights.size() && heights[high] >= heights[i]) high++;
high--;
int cur_area = heights[i]* (high-low+1);
if(max_area<cur_area) max_area = cur_area;
}
return max_area;
}
};
解法二: 解法一的改进-空间换时间
时间复杂度: $O(n)$, 前面省略常数项(因为不好确定常数项的值)
空间复杂度: $O(2n)$
从解法一中我们可以看出, 核心的要点就在于求取每一个i对应的矩形的左端和右端, 如下图所示:
那么, 如果我们可以在 $O(1)$ 的时间内获取到左端和右端的值, 则时间复杂度就可以降低到 $O(n)$, 因此, 首先想到的是用数组将每个i对应的左端和右端的值保存起来. 于是, 我们需要先求取这两个数组(左端,右端)的值, 在对左端和右端求值时, 我们要确保时间复杂度不能超过 $O(n)$, 因此, 我们不能每次都重新从i出发分别向左向右遍历(如解法一那样), 反之, 我们可以利用左端和右端中已经求好的值, 对于左端来说, 我们可以利用左端数组跳跃式的向左前进, 对于右端来说, 我们可以利用右端数组跳跃式的向右前进(这里不太好用语言描述, 具体请看程序代码).
1 | class Solution { |
解法三: 最优-栈
时间复杂度: $O(n)$, 无常数项
空间复杂度: $O(n)$, 无常数项
上面的解法二, 虽然时间复杂度为 $O(n)$, 但实际上其时间复杂度是略微高于 $O(n)$, 因为在求取左端右端时, 每次跳跃的次数是大于等于1, 而不是仅为1次的.(只不过大O记法不考虑常数项). 而对于空间复杂度来说, 实际上是 $O(2n)$. 下面我们从另外一个角度出发: 不再以当前i对应的高度为最低, 向左右两边探索, 改为以当前i对应的高度为最低, 仅仅向左边探索, 实现算法如下:
- 首先, 构造一个空栈
- 从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.
复杂度分析: 由于入栈出栈的元素仅为heights数组元素, 可以栈的size就是heights数组的大小, 即空间复杂度为 $O(n)$, 时间复杂度从代码中可看出约为 $O(n)$.
1 | class Solution { |
124. Binary Tree Maximum Path Sum
求二叉树中, 以任意节点为起始的路径和(这里是将二叉树看成无向图来计算路径的)的最大值, 例如对于下面的二叉树, 具有最大值的为:2->1->3 = 61
2
3 1
/ \
2 3
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:1
2
3
4
5Input: [1,2,3]
1
/ \
2 3
Output: 6
Example 2:1
2
3
4
5
6
7Input: [-10,9,20,null,null,15,7]
-10
/ \
9 20
/ \
15 7
Output: 42
解法一: 递归
这道题的难点在于能否解读出题目的求值过程实际上是一个后序遍历的过程.
对于本题来说, 我们需要求得每个节点所在的路径的最大值, 以下面的例子来说:1
2
3
4
5 4
/ \
11 13
/ \
7 2
我们需要求的最大和的路径为: 7->11->4->13. 而根据二叉树的遍历性质, 我们假设现在已经遍历到节点7, 此时, 左右子树均为空, 所以左右子树的最大和为0, 那么此时节点7所在的路径的最大和为: 左子树+右子树+当前节点值 = 7. 然后, 回溯到了节点11, 此时同理, 节点11所在的路径的最大和为: 左子树+右子树+当前节点值 = 11.(忽略节点2的遍历过程). 接下来对于节点4, 同理也应为: 左子树+右子树+当前节点值. 右子树返回的值很容易看出是13, 但是左子树应该返回多少呢? 由于我们希望求得当前的最大和, 因此, 左子树就应该返回它的最大和, 但是, 不能统计两条路径, 而应该选择以左节点为根节点的左右子树的较大者, 因此, 应该返回的是: max(左节点左子树, 左节点右子树)+左节点的值, 因此, 返回的是: 7+11 = 18. 于是, 节点4对应的最大和就为: 18+13+4. 可以看到, 这实际上就是一个后序遍历的过程.
1 | /** |
解法二: 迭代
后序遍历的迭代实现
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.
解法一: 排序
时间复杂度: $O(nlogn)$
空间复杂度: $O(1)$
先排序, 然后在从头往后遍历, 并用一个变量维护当前的最长连续序列的长度.
解法二: 利用哈希表
时间复杂度: $O(n)$
空间复杂度: $O(n)$
利用 unordered_set 将所有的数字存储起来, 然后遍历每一个数字 num, 查看这个数字是否为所在连续序列的开头(即查看 num-1 是否存在). 若 num 就是所在连续序列的开头, 则查看当前序列的长度, 并更新最大长度. 故而时间复杂度为 $O(n+n) = O(n)$. 同时, 因为使用了 unordered_set, 所以空间复杂度为 $O(n)$.1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class Solution {
public:
int longestConsecutive(vector<int>& nums) {
unordered_set<int> sets(nums.begin(), nums.end());
int longest = 0;
for(auto num : sets){
if(sets.find(num-1) == sets.end()){
int cur_len = 1;
while(sets.find(num+1) !=sets.end()){
num++;
cur_len++;
}
if(longest < cur_len) longest = cur_len;
}
}
return longest;
}
};
解法三: 另一种哈希表用法
时间复杂度: $O(n)$
空间复杂度: $O(n)$
主题思想与解法二相同, 不过是从另一角度来使用 unordered_map, 首先, 依然利用 unordered_map 将 nums 存储起来, 然后遍历 nums, 对于 nums 中的每一个 num, 查看其是否存在于 unordered_map 中, 如果存在, 则分别向左向右查找当前数字 num 所在序列的最左端和最右端的数字, 同时, 将在 unordered_map 中遍历过的数字都移除(因为每个数字只可能唯一的属于一个连续序列). 之后, 利用最左端和最右端来更新最长连续序列的长度. 这样, 遍历的时间复杂度也为 $O(n+n) = O(n)$
1 | class Solution { |
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:
[]
解法一: DP
直接使用回溯法, 有大量重复计算, 导致时间超时, 无法通过 OJ, 因此考虑 DP 思想. 将中间的计算结果缓存起来, 再次遇到的时候无需重复计算, 只需直接使用即可.
利用一个哈希表将每个字符串与该字符串能拆分出的句子联系起来, 其中, key 为字符串, value 为字符串拆分后的句子. 假设我们已经求出一个字符串的解为 res, 并将其存入到哈希表中, 此时, 如果在该字符串的前面再加上一个单词(单词表的中任意一个), 那么新的解就应该为: word+" "+res[i]. 代码实现如下.
注意, 这里我们要对 wordDict 进行遍历来查找可以拆分的情况, 如果是对字符串 s 查找可拆分情况, 那么哈希表中的键将会大幅增加, 例如对于"aaaaaaaaaaa"这种情况.
1 | class Solution { |
内存超限的写法:
1 | class Solution { |
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
解法一: 哈希表
时间复杂度: $O(n^2)$, 求取任意两点间的斜率
空间复杂度: $O(n)$, 哈希表, 存储斜率
由于要求共线点个数, 就必须获取任意两点间的斜率, 因此, 时间复杂度最少为 $O(n^2)$. 算法流程如下:
- 对于每一个点来说, 构造一个哈希表, 表中的键为斜率, 表中的值为对应斜率的点的个数, 这里注意, 当我们求完第i个点与第j个点之间的斜率之后, 就不用再求第j个点与第i个点之间的斜率情况了(即令
int j = i+1, 而不是int j = 0) - 对于重点的情况, 需要单独设置一个变量来记录, 之后将该重复次数加入到该点所在的每条直线上(因为重点也算是共线)
- 对于斜率不存在的情况, 可以考虑利用
INT_MAX来作为键值 - 精度: 在求取斜率时, 会进行除法, 而在计算机内部, 除法在精度上始终会有一定误差, 会造成斜率相同的两对点在计算成浮点数以后斜率不同, 因此, 要 避免使用除法, 解决办法是利用 最大公约数, 求取
y2-y1与x2-x1之间的最大公约数, 然后对进行约分, 用约分后的值作为键来存储, 就不会造成精度上的损失, 但是, 此时需要用pair作为键, 故不能用unordered_map(C++没有为pair类型提供对应的哈希函数), 而只能用map(键只有重载了<和>就可以使用map, 搜索的时间复杂度为 $O(logn)$), 另一种可选做法是利用string类型, 将两个int数值转换成string后再拼接, 此时就可以使用unordered_map了(搜索的时间复杂度为 $O(1)$, 但是int和string的类型转换也需要消耗时间). - 当采用公约数以后, 因为没有了除法, 因此可以不用特殊处理斜率不存在的情况, 代码更加简洁.
1 | C/** |
用 string 做键, 使用哈希表而不是map:
1 | class Solution { |
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”]
解法一: 穷举
时间复杂度: $O(w mn 4^k)$, 暴力求解, $mn$ 为字符矩阵的宽和高, 也即 cell 数量, 对于 dfs 中的每个 cell, 有4个扩展方向, 一共需要扩展 $k$ 次($k$ 为单词的长度). 总共有 $w$ 个单词, 因此复杂度为$O(w mn 4^k)$
空间复杂度: $O(mn)$ , 和79题相同, 回溯时, 用#来记录已经遍历过的点, 无需申请额外空间来记录. 但是递归程序需要占用 $O(mn)$ 的空间复杂度.
该题和79题类似, 只不过给定的是一个单词列表, 而不是一个单词, 因此, 可以对这个单词列表循环调用79题的解. 不过时间复杂度过高, 无法通过 OJ.
解法二: 字典树
时间复杂度: $O(mn 4^k)$, 暴力求解, $mn$ 为字符矩阵的 cell 数量, 对于 dfs 中的每个 cell, 有4个扩展方向, 一共需要扩展 $k$ 次($k$ 为单词的长度).
空间复杂度: $O(mn)$ , 和79题相同, 回溯时, 用#来记录已经遍历过的点, 无需申请额外空间来记录. 但是递归程序需要占用 $O(mn)$ 的空间复杂度. 另外, 还有构建字典树所需的空间复杂度, 这部分复杂度与具体的字符串数组有关, 当字符串公共部分较多时, 复杂度较低, 反之, 复杂度较高, 最差情况下为 $O(wk)$, 即无公共前缀
相对于第79题来说, 本题增加的复杂度主要体现在需要同时查看 $w$ 个单词的字符, 查询这些单词字符的复杂度约为 $O(wk)$, 其中, $k$ 为单词的最大长度, 那么, 我们能否将这里的复杂度降低成 $k$ 呢? 如果降低成 $k$ 的话, 就相当是在查找一个单词, 那么整体的复杂度就和79题相同, 变成了 $O(mn 4^k)$.
实际上, 字典树正是这种数据结构! 在由 $w$ 个字符串构成的字典树中查询某个字符串或者字符子串的复杂度为 $k$. 因此, 我们可以借助字典树来降低整体的时间复杂度. 代码如下:
1 | class TrieNode{ |
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
时间复杂度: $O(nlogn)$, 拆分三元组到二元组为 $O(n)$, 排序为 $O(nlogn)$, 更新轮廓节点为 $O(nlogn)$ (插入高度为 $O(log)$, 总共有 $O(n)$ 组高度).
空间复杂度: $O(n)$, 存储高度的二元组 vector, 以及维护当前建筑物高度顺序的 multiset.
首先我们将表示建筑物的所有三元组(Li, Ri, Hi)进行拆分, 将其分成(Li, -Hi), (Ri, Hi)的两个二元组, 将这些二元组存放在一个数组 vector 中, 然后按照 x 轴的下标进行排序, 注意如果当一个建筑物的右侧和另一个建筑物的左侧重叠时, 我们为了不丢失当前建筑物的高度, 必须先考虑将另一个建筑物的左侧添加进 multiset 里, 然后获取最高高度. 接着在下一次循环时, 再将重合的右侧边界对应的建筑物剔除, 因此我们需要令二元组中的左侧为负, 使其在排序时可以排到前面.
得到有序的建筑物二元组序列以后, 我们遍历该序列, 如果遇到了某个建筑物的左侧边界, 则将该边界对应建筑物的高度加入到 multiset 中, 如果遇到了某个建筑物的右侧边界, 则将对应建筑物的高度剔除. 假设我们已经得到了前 i 个坐标的建筑物组成的轮廓坐标点, 现在来到第 i+1 个坐标, 只有可能对应下面几种情况:
- i+1 坐标上新来的建筑物(遇到该建筑物左侧就行)完全被之前的建筑物覆盖, 此时不更新 res 轮廓. 说明添加了该建筑物后, 并不改变当前建筑群的最高高度.
- i+1 坐标上新来的建筑物比当前建筑群最高的高度还要高, 则需要记录当前的点.
- i+1 坐标上没有新来建筑物, 但是有一个建筑物遇到了右侧边界, 此时建筑群的高度会变成第二高建筑物的高度, 同样需要记录当前的坐标点.
- i+1 坐标上既没有新来建筑物, 也没有遇到建筑物右侧, 此时无需记录任何值, 可继续探测 i+2 坐标.
1 | class Solution { |
解法二: priority_queue(堆)
在解法一中, 用了 multiset, 之所以不用 priority_queue 的原因是因为, C++ 的 priority_queue 容器并没有提供erase或者find之类的方法, 因此, 在删除指定高度时, 比较麻烦. 而 multiset 不仅完成堆的功能(最后一个元素就是最大的), 同时还支持在对数复杂度时间内删除指定的高度.
因此, 如果想要使用 priority_queue 的话, 就需要调整算法的逻辑, 下面是使用 priority_queue 的解法:
1 | class Solution { |
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:1
2
3
4
5
6
7
8
9
10
11
12Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3
Output: [3,3,5,5,6,7]
Explanation:
Window position Max
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
Note:
You may assume k is always valid, 1 ≤ k ≤ input array’s size for non-empty array.
Follow up:
Could you solve it in linear time?
解法一: 双端队列
时间复杂度: $O(n)$, 一次遍历
空间复杂度: $O(k)$, 双端队列的 size 为 $k$.
使用双端队列deque, 从下标0开始, 一直到n-1, 每次进行如下步骤:
- 当前元素是否比队列中最后一个元素大, 如果大, 说明队列元素以后也不可能再成为较大值, 直接pop, 如此循环, 直到队列为空或者遇到比当前值大的元素
- 判断队列中队首的元素是否过期(若队空则直接下一步, 无需判断), 若过期, 则pop, 否则, 不管( 只看队首, 队内的元素是否过期不影响算法, 因为就算过期后面也会将其淘汰)
- 将当前元素的下标存到队尾
- 将新的队首元素存到结果向量max_res中
注意: 队列里面存的是下标, 而不是元素本身的值, 后面在提到队列的元素值时, 均是指队列中存储的下标对应的元素值.
1 | class Solution { |
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
2
3
4
5addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3)
findMedian() -> 2
Follow up:
- If all integer numbers from the stream are between 0 and 100, how would you optimize it?
- If 99% of all integer numbers from the stream are between 0 and 100, how would you optimize it?
解法一: 传统排序
时间复杂度: $O(nlogn)$, 添加数字时不排序, 返回中位数时排序
空间复杂度: $O(n)$, 排序需要额外空间
添加数字时, 直接添加, 时间复杂度为 $O(1)$, 每次需要输出中位数时, 都对数组内当前所有元素排序, 时间复杂度为 $O(nlogn)$, 该方法超时.
解法二: 插入排序
时间复杂度: $O(n)$, 二分搜索位置需要 $O(logn)$, 插入需要 $O(n)$.
空间复杂度: $O(n)$
每次新来一个数字时, 都执行插入排序, 先利用二分搜索(因为当前数组已经有序)找到应该插入的位置, 时间复杂度为 $O(logn)$, 然后将数字插入到该位置, 插入的时间复杂度是 $O(n)$, 由于已经排序好, 因此返回中位数的时间复杂度是 $O(1). 该解法 同样超时.
解法三: 大顶堆+小顶堆
时间复杂度: $O(5\times logn) = O(logn)$
空间复杂度: $O(n)$, 大顶堆和小顶堆的大小之和为 $n$.
元素首先加入大顶堆($O(logn)$), 得到前面数字的最大值, 然后将该最大值弹出($O(logn)$)并加入到小顶堆当中($O(logn)$), 以维护当前小顶堆的元素合法(例如, 新的大顶堆堆顶的元素大于当前小顶堆堆顶元素, 这就不合法了), 然后, 看看当前大顶堆和小顶堆的元素个数是否符合要求, 如果不符合的话, 就小顶堆的堆顶弹出($O(logn)$)并加入大顶堆($O(logn)$). 由此可知, 添加元素的时间复杂度为: $O(5\times logn)$. 返回中位数时可以直接获取堆顶, 而无需更改堆结构, 故而为 $O(1)$. 所以, 最终的时间复杂度就为 $O(5\times logn) = O(logn)$
1 | class MedianFinder { |
解法四: multiset+指示器
时间复杂度: $O(logn+1) = O(logn)$
空间复杂度: $O(n)$, multiset 容器需要 $n$ 大小的空间.
用两个迭代指示器分别指向当前数组内的中位数(元素数目为奇数时, 二者指向同一点), 那么当新来一个元素时, 这个元素只可能有三种插入情况:
- 插在两指示器的前面
- 插在两指示器的后面
- 插在两指示器的中间(只在未插入前元素数目为偶数时才可以)
由于迭代指示器是随着元素移动而移动的(这点和下标就有区别了), 因此, 我们可以通过对指示器操作来使其指向新的中位数, 对应三种情况分别为:
- 前面元素变多, 说明指示器应该后挪(最多一位)
- 后面元素变多, 说明指示器应该前挪(最多一位)
- 插在中间, 说明当前插入的元素正是中位数, 令指示器指向即可.
当然, 上面只是核心思想, 具体的挪动算法还要分元素数目的奇偶性来分情况讨论, 代码如下所示:
1 | class MedianFinder { |
上面的指示器实际上可以简化成一个(因为两个指示器只能互相挨着或者重叠), 因此, 我们可以只维护一个指示器, 简化代码如下(但是不太好理解):
1 | class MedianFinder { |
Follow Up
- If all integer numbers from the stream are between 0 and 100, how would you optimize it?
用bucket?
- If 99% of all integer numbers from the stream are between 0 and 100, how would you optimize it?
297. Serialize and Deserialize Binary Tree
Description: 序列化和反序列化二叉树
Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.
Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.
Example:1
2
3
4
5
6
7
8
9You may serialize the following tree:
1
/ \
2 3
/ \
4 5
as "[1,2,3,null,null,4,5]"
Clarification: The above format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.
Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.
解法一: DFS
时间复杂度: $O(n)$, 在序列化和反序列化递归中, 各遍历每个节点一次
空间复杂度: $O(n\times v + n) = O(n)$, 其中, $n$ 为节点个数, $v$ 为节点上的值所占空间大小, 最后的一个 $n$ 代表递归调用所占的空间大小.
使用 ostringstream 和 istringstream 来缓存字符串, 中间用空格分隔, 利用流操作 << 和 >> 可以方便的对字符串进行存入和读取, 而无需额外进行分词操作.
1 | /** |
解法二: BFS
时间复杂度: $O(n)$, 在序列化和反序列化中, 每个节点都遍历一次
空间复杂度:
BFS 的会按照层次遍历的顺序将树的节点序列化, 序列化的代码比较好写, 只需对普通的层次遍历稍加改动即可. 反序列化的代码有一点麻烦, 需要控制树节点的左右子节点的值, 具体如下.
1 | class Codec { |
315. Count of Smaller Numbers After Self
Description: 统计右边比当前数字小的个数
You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].
Example:1
2
3
4
5
6
7Input: [5,2,6,1]
Output: [2,1,1,0]
Explanation:
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.
解法一: multiset
时间复杂度: $O(n\times(logn+n+logn)=O(n^2)$
空间复杂度: $O(n+n) = O(n)$
先介绍一下利用 multiset 的解法, multiset 的底层实现使用了红黑树, 所以在插入和查找的时候复杂度都为 $O(logn)$, 但是求 distance 时, 由于 multiset 的迭代器不是随机访问的, 因此复杂度为 $O(n)$, 故而最后的时间复杂度为 $O(n^2)$. 该方法在 OJ 上超时, 此处仅用于记录.
1 | class Solution { |
解法二: 有序数组
时间复杂度: $O(n\times (logn+n) = O(n^2)$, 在有序数组中找指定位置需要 $O(logn)$, 将当前元素插入到数组的指定位置需要 $O(n)$, 这个过程需要进行 $n$ 次.
空间复杂度: $O(n+n) = O(n)$, 一个有序数组, 一个结果数组, 大小都为 $n$.
我们从后往前遍历, 将遍历过的数字维护成一个有序数组, 然后对于任意一个新来的数字, 我们可以在有序数组中查询小于该数字的元素个数, 查询的时间复杂度为 $O(logn)$, 然后我们需要将该数字也插入到有序数组中并保持有序, 插入操作需要的时间复杂度为 $O(n)$, 总共有 $n$ 个数字, 因此需要执行 $n$ 次, 故时间复杂度约为 $O(n^2)$, (虽然是 $O(n^2)$, 但是仍然没超时, 考虑是因为只有一个 $logn$, 而解法一具有两个 $logn$.) 代码如下:
1 | class Solution { |
解法三: 二叉搜索树(BST)
时间复杂度: $O(nlogn)$, 内部只有一个 $logn$ 复杂度的插入操作, 没有其他操作, 但是由于不是平衡的, 所以在最坏情况下的复杂度为 $O(n^2)$, 最好情况即为平衡树, 复杂度为 $O(nlogn)$.
空间复杂度: $O(n+n)$, res 数组和二叉树结构各占 $n$ 大小的空间. 如果采用递归实现插入, 则可能额外需要 $n$ 大小的递归空间.
在解法一中, 通过 multiset 红黑树的结构使得插入时的复杂度为 $logn$, 但是最终需要进行的操作过多, 导致时间超时, 为此, 我们可以自己实现一个二叉搜索树, 从后往前的遍历数组, 并且在插入元素的时候就统计出小于当前元素的节点的个数(为此我们需要在树的结构中额外添加一个变量 smaller, 只是小于当前节点的元素个数), 故而只需要一次 $logn$, 且没有其他多于操作, 代码如下:
1 | class Solution { |
解法四: 归并排序
时间复杂度: $O(nlogn)$
空间复杂度: $O(n+n) = O(n)$
由于解法三构造的二叉树并不是一个平衡的二叉树, 导致在树的极端情况下, 时间复杂度为 $O(n^2)$, 而要手动实现二叉树的平衡逻辑, 又有些复杂, 不适合解此题. 所以, 我们可以考虑此题的另一种解法, 即利用归并排序来解决.
329. Longest Increasing Path in a Matrix
Description: 寻找矩阵中的最长递增序列
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
2
3
4
5
6
7
8Input: nums =
[
[9,9,4],
[6,6,8],
[2,1,1]
]
Output: 4
Explanation: The longest increasing path is [1, 2, 6, 9].
Example 2:1
2
3
4
5
6
7
8Input: nums =
[
[3,4,5],
[3,2,6],
[2,2,1]
]
Output: 4
Explanation: The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.
解法一: DP + dfs
时间复杂度: $O(mn)$, 每个节点都会遍历一次, 当遍历一次后, 下次再访问时可以直接通过 dp 数组得知答案.
空间复杂度: $O(mn+mn=mn)$, $n$ 行 $m$ 列的 DP 数组所占用的空间大小, 另外还有递归所占用的空间($mn?$)
申请和矩阵相同大小的 DP 数组, 令 dp[i][j] 代表从 (i,j) 位置为起点的绝对递增数列的长度, 每遍历一个位置后, 下一次再访问该位置时就无需重复计算, 可以直接通过 dp 数组获取到相应长度. 在查找当前节点的最大长度时, 我们利用 dfs 算法, 依次从四个方向进行查找, 最终取最大值作为本位置的最长递增序列长度
1 | class Solution { |
解法二: DP + BFS
TODO: http://www.cnblogs.com/grandyang/p/5148030.html
1 | class Solution { |