002. Add Two Numbers
Description: 链表数之和
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Example:
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.
解法一: 顺序相加, 注意进位
从链表的第一个节点开始, 将两个节点的值和进位位想加, 如果大于10, 则当前结果节点的值对10取余, 同时将进位位置1, 如果小于10, 则直接赋值给当前结果节点, 同时将进位位置0.
特别注意 l1
和 l2
的长度问题, 当二者节点遇到 nullptr
时, 将较长的剩余部分重新赋给l1, 并继续判断
最后, 需要注意是否有进位位, 如果有, 则要申请一个新节点, 并将其置为1
时间复杂度: $O(\max(m,n))$
空间复杂度: $O(1)$ (这种做法会破坏原有链的结构)
1 | /** |
解法二: 顺序相加, 维持原链表
时间复杂度: $O(\max(m,n))$
空间复杂度: $O(\max(m,n))$ (这种做法需要额外申请空间, 但不会破坏原有链的结构)
该解法思路与解法一一致, 只不过每次都申请一个新的节点, 确保不会改变原有链表的结构.
1 | class Solution { |
扩展问题
What if the the digits in the linked list are stored in non-reversed order? For example:
$(3 \to 4 \to 2) + (4 \to 6 \to 5) = 8 \to 0 \to 7 (3→4→2)+(4→6→5)=8→0→7$
思路:
先将链表转置 , 再用上面的方法求解
转置时间复杂度: $O(n)$
转置空间复杂度: $O(1)$
003. Longest Substring Without Repeating Characters
Description: 寻找无重复字符的最长子串
Given a string, find the length of the longest substring without repeating characters.
Example 1:1
2
3Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:1
2
3Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:1
2
3Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Note that the answer must be a substring, “pwke” is a subsequence and not a substring.
解法一:暴力
时间复杂度: $O(n^3)$ 对于每一个字符, 子串的添加以及查重过程时间复杂度为 $O(n^2)$ , 总共n个字符, 所以为 $O(n^3)$
空间复杂度: $O(min(n,m))$ 需要将当前子串存在起来以便查询是否相等, n为字符串length, m为字符集size
解法二: 前后两个指示变量
时间复杂度: $O(2n) = O(n)$
空间复杂度: $O(min(n,m))$
思路: 首先构造一个哈希表, 用来存储当前子串中出现的字符, 这样, 新来的字符可以直接查询哈希表来判断字符是否存在, 构建哈希表空间复杂度为 ( $m$ 为字符集合的大小,一般为26(字母), 128(ASCII), 256(ASCII), $n$ 为字符串的长度)
然后, 使用两个指示变量, 分别指向当前未重复子串的首字符, 和超尾字符, 进行如下几个判断:
- 如果超尾字符与当前子串中的字符不重复, 那么将超尾字符加入到当前子串中,并将length加1
- 如果超尾字符与当前子串中的字符重复, 利用哈希表查的重复字符的所在位置, 将当前子串的首字符直接跳向该重复字符的下一个位置( 这样可以保证只遍历一遍 ), 并将包括重复字符在内的之前所有字符都从哈希表中删除(之前的字符不再可能组成更长的子串了), 同时将超尾字符加入, length赋予新值: 超尾位置-重复位置-1;
- 判断首字符与超尾字符是否相等, 如果相等, 将超尾字符加1, 并将length置为1
- 看当前length是否比maxlength大, 并重复以上过程,直到超尾字符超出size
1 | class Solution { |
解法三: 只需一次遍历
时间复杂度: $O(n)$, 只需一次遍历
空间复杂度: $O(min(m,n)$, 与解法二相同
当我们在 [i,j)
之间发现了一个重复的下标为 j'
的字符时, 我们不用一点点的增加 i
的值, 而是可以直接将 i
的值跳到 j'+1
处. 故, 我们可以只利用一次遍历就找到最长的不重复子串.
1 | class Solution { |
用数组做哈希表:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class Solution {
public:
int lengthOfLongestSubstring(string s){
int hash[256];// 哈希表中存在的值代表下标
for(auto &item : hash) item = -1; // 赋初值
int max_len = 0;
for(int i=0, j=0; j < s.size(); j++){
if(hash[s[j]] != -1){ // 当哈希表中值不为-1时, 说明存在重复
i = std::max(hash[s[j]] + 1, i); // 注意这里必须保证 i 不会倒退, 因此要使用 max
}
max_len = std::max(max_len, j-i+1);
hash[s[j]] = j;
}
return max_len;
}
};
005. Longest Palindromic Substring
Description: 最大回文子串
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example 1:
Input: “babad”
Output: “bab”
Note: “aba” is also a valid answer.
Example 2:
Input: “cbbd”
Output: “bb”
解法一:最长公共子串
时间复杂度: $O(n^2)$
空间复杂度: $O(n)$
先将字符串 s
利用 reverse
逆置成 s'
, 然后查找 s
和 s'
的最长公共子串, 即为最长的回文子串.
解法二: 穷举
时间复杂度: $O(n^3)$
空间复杂度: $O(1)$
对于字符串中的每一个字符, 共有 $\frac{n(n-1)}{2}$ 种包含该字符的子串, 所以如果对所有可能的子串判断, 需要 $O(n^3)$ 的时间复杂度
解法三: 动态规划
时间复杂度: $O(n^2)$
空间复杂度: $O(n^2)$
我们令 DP 数组为一个 $n\times n$ 的矩阵, $dp(i,j)$ 代表从 s[i]
开始, 到 s[j]
结束的子串是否为回文串, 如果是, 则为 true
. 那么, $dp(i,j)$ 为真的条件就是必须满足 $dp(i+1, j-1)=true$ 并且 $s[i]=s[j]$. dp 数组的初始值为: $dp(i,i)=true$, $dp(i,i+1)= s[i]==s[i+1]$. 由于需要遍历 dp 矩阵中每一个位置的值, 因此时间复杂度为 $O(n^2)$, 空间复杂度很明显为 $O(n^2)$.
解法三: 扩展中心法
时间复杂度: $O(n^2)$
空间复杂度: $O(1)$ 或者 $O(n)$
以每一个字符为中心, 向两边扩展, 将当前能够扩展的长度 len 和最大扩展长度 max_len 作比较, 记录较大者, 同时记录较大者的所对应的中心字符的下标 max_index. 最后, 根据最大扩展的长度max_len 和中心字符的下标 max_index 计算最大回文子串的开始位置和总长度
此处注意, 回文子串有奇偶两种情况, 可采用以下举措之一解决:
- 分别检查奇数和偶数的情况, 这样多检查一次(虽然多检查一次, 但和下面的检查总次数差不多, 因为下面虽然只检查一次, 但次数较多)
- 向字符内插入特殊符号 ‘#’, 这样不管偶数奇数, 都可以当做奇数处理, 缺点是占用了额外的 $O(n)$ 空间.
注意: 既然已经使用了空间复杂度为 $O(n)$ 的方法, 实际上更应该将其该写成马拉车算法
1 | // 空间复杂度 $O(1)$ |
另一种写法:
1 | // 空间复杂度 $O(1)$ |
1 | // 空间复杂度 $O(n)$ |
解法五: 马拉车(Manacher) 算法
时间复杂度: $O(n)$
空间复杂度: $O(n)$
There is even an O(n), O(n) algorithm called Manacher’s algorithm, explained here in detail. However, it is a non-trivial algorithm, and no one expects you to come up with this algorithm in a 45 minutes coding session. But, please go ahead and understand it, I promise it will be a lot of fun.
马拉车算法的核心思想还是从中心扩展发出发, 不过他必须使用 ‘#’ 字符先对原始字符串插入, 如下所示:
接下来, 在每一次 for
循环当中, 都需要保存这么几个值(命名是个人习惯, 可以用其他名字代替):
- P: P 为最大右边界下标值, 对应的是所有已检测的回文子串中, 右边界下标最大的那个
- P_center: 该值是P对应的回文子串的中心下标
- max_len: 对应当前最大回文子串的半径(aba的半径为1, a的半径为0)
- max_index: 对应当前最大回文子串的中心下标
然后, 还需要构建一个和插入’#’后的字符串长度相关的数组 p_len
, 里面存放着对应位置的回文串半径, 用以后续的计算, 这一步是关键, 有了这个数组 ,才能实现利用之前计算结果
接下来, 遍历 “新字符串”(即插入’#’之后的字符串) 的每一个字符, 设当前下标为 i, 则有如下情况, 分别处理:
- P>i, 说明 i 在 P 的范围内, 可以利用前面的计算结果
- P<=i, 说明 i 不在 P 的范围内, 无法利用前面的计算结果, 只能逐个判断
对上面两种情况具体分析如下:
第一种情况: P>i
找到i相对于 P_center 的对称位置, 设为j, 那么如果Len[j]<P-i, 如下图所示:
则以i为中心的回文串的长度至少和以j为中心的回文串一样 , 即Len [i]>=Len[j] , 因此可以直接从Len[j]+1开始判断回文
如果Len[j]>=P-i, 如下图所示:
由对称性, 说明以i为中心的回文串可能会延伸到P之外, 而大于P的部分我们还没有进行匹配, 所以要从P+1位置开始一个一个进行匹配, 直到发生失配
第二种情况: P<=i
如果i比P还要大, 说明对于中点为i的回文串还一点都没有匹配, 这个时候, 就只能老老实实地一个一个匹配了
在这一次循环完成之前, 更新上面提及的四个变量
循环结束后, 根据 max_index 和 max_len 的值返回最长回文子串
时间复杂度分析:
对于每一个字符, 由于如果直接比较过, 那么就可以利用之前比较的结果直接判断, 所以每个字符都只进行了一次比较, 故而时间复杂度为 $O(n)$
1 |
|
008. String to Integer (atoi)
Description: 将字符串转换成整数
解法一: 考虑多种情况
此题时间复杂度为 $O(n)$ , 重点考察是否考虑的全面, 主要有以下几种情况, 缺一不可:
- +123 dd // 返回123
- +123d // 返回123
- d-123 // 返回0
- -123+ //返回-123
- -123+4 // 返回-123
- 323123423423423 // 返回INT_MAX
- -1231238923894234 // 返回INT_MIN
- 1234-5 // 返回1234
1 | class Solution { |
011. Container With Most Water
Description
Given n non-negative integers a1, a2, …, an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container and n is at least 2.
The below vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.
解法一: 暴力
时间复杂度: $O(n^2)$
用max_area标记当前最大容器的取值, 然后两个for循环遍历所有容器的可能取值
1 | class Solution { |
解法二: 用两个指针
时间复杂度: $O(n)$
空间复杂度: $O(1)$
分别用两个指针指向数组的第一个元素和最后一个元素, 并计算当前的area, 然后移动指针元素值较小的一方, 移动过程中更新max_area的值
原理:
首先假设容器可以具有最大长度的宽, 也就是分别指向首尾元素, 这时候 , 我们想查看是否还有比当前最大容积更大的容器, 那么, 我们必须维持较高的垂直边不动, 而将较低的垂直边移动, 因为只有这样, 我们才 有可能 (注意不是一定)获得比当前容积更大的容器, 这个时候虽然宽变小了, 但是高度却可能增加(因为新增的边有可能大于当前较低边的高). 如果移动较高的边, 那么新增的边由于受到当前较低边的作用, 只有可能减小容器的面积
1 | class Solution { |
015. 3Sum
Description: 三数和为零
Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:
The solution set must not contain duplicate triplets.
Example:1
2
3
4
5
6
7Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
解法一: 固定一个数, 剩余两个数用双指针法求
时间复杂度: $O(n^2+nlogn)=O(n^2)$
空间复杂度: $O(1)$, 无需额外空间
解题步骤:
- 对整个数组排序, $O(nlogn)$;
- 固定下标
i
, 令下标j=i+1
, 令k=nums.size()-1
. - 如果
nums[i]
为正数, 说明不可能组成和为零的三元组, 直接返回当前结果; - 为了消除重复, 对于相同的相邻元素, 我们只选其中的一个参与组合. 注意: 这里的重复是指三元组的值的重复, 而不是下标重复, 也就是说, 对于下标不同但值相同的元素, 也算作重复.
- 重复(2)(3)(4)过程直到循环终止.
排序的必要性: 这里我们排序的主要目的是为了消除重复, 如果题目允许重复, 那么可以不进行排序, 而采用基于哈希表的 TwoSum 来求解.
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
25vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
if(nums.size()<=2)return result;
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size() - 2; i++) {
int a = nums[i];
if(a > 0) break;
if (i > 0 && a == nums[i - 1]) continue;// 这里不能用nums[i]==nums[i+1], 因为会丢掉类似于 -1,-1,2 的解.
for (long j = i + 1, k = nums.size() - 1; j < k;) {
int b = nums[j];
int c = nums[k];
int value = a + b + c;
if (value == 0) {
result.push_back(vector<int>({a, b, c}));
while (j < k && b == nums[++j]); // 主要是这里的写法很优雅, 其他地方和上面差不多
while (j < k &&c == nums[--k]);
} else if (value > 0) {
k--;
} else {
j++;
}
}
}
return result;
}
解法二: python写法
1 | class Solution: |
017. Letter Combinations of a Phone Number
Description: 九键字母组合
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
Example:1
2Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.
C++
解法一: 递归
时间复杂度: $O(n4^n)$, $n$ 为数字的长度
*空间复杂度: $O(4^n)$
1 | class Solution { |
解法二: 非递归
时间复杂度: $O(n4^n)$, $n$ 为数字数组的长度
*空间复杂度: $O(4^n)$
1 |
|
Python
解法一: 利用reduce实现
1 | class Solution: |
018. 四数之和
解法:
转换成两数之和
1 | class Solution: |
019. Remove Nth Node From End of List
Description: 移除链表的倒数第 N 个字符
Given a linked list, remove the n-th node from the end of list and return its head.
Example:1
2
3Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.
Note:
Given n will always be valid.
Follow up:
Could you do this in one pass?
解法一: 遍历两次
第一次遍历求出链表长度, 第二次遍历在对应位置删除节点
解法二: 双指针, 只遍历一次
时间复杂度: $O(n)$ 且只遍历一次
空间复杂度: $O(1)$
维护两个指针, 两指针之间的距离刚好相差n, 当第二个指针到达链表尾部时, 第一个指针刚好指向倒数第n个节点, 直接删除该节点即可.
1 | /** |
下面是有一种写法, 新申请了一个节点空间, 用于指向head节点, 可以使代码看起来更容易理解, 对边界条件的判断也更加方便
1 | /** |
022. Generate Parentheses
Description
解法一: 暴力
先求出所有可能性, 然后验证每一种可能性是否正确
解法二: 回溯
有关递归的时间空间复杂度分析起来都不太容易, 这里只上答案(//TODO 具体怎么来没搞懂)
时间复杂度: $O(\frac{4^n}{\sqrt n})$
空间复杂度: $O(\frac{4^n}{\sqrt n})$ 以及 $O(n)$ 的空间来存储组合序列
考虑合法括号组合的规律: 必须首先出现左括号, 然后才能出现右括号, 如果当前的string里面的右括号数量大于左括号数量, 那么就一定会出现)(
这种不匹配的情况.
核心思路: 从头开始构建组合, 每次接入一个字符, 接入的字符只有两种可能性, 即左括号或者右括号, 而一旦接入的字符使得当前字符中右括号数量大于左括号, 就会变得不合法组合,其它均为合法. 根据此性质, 进行如下递归:
维护两个变量left_rest, right_rest分别代表 剩余 可以添加的括号的 数量. 采用递归算法, 每次添加一个 ‘(‘ 或者一个 ‘)’, 添加时需要考虑下面几种情况:
- 为了保证当前string内左括号数量多于右括号数量, left_rest一定要小于right_rest
- 如果
left_rest = right_rest = 0
, 则说明此时没有可以添加的括号了.
1 | class Solution { |
解法三: Closure Number
时间复杂度: $O(\frac{4^n}{\sqrt n})$, 同解法4
空间复杂度: $O(\frac{4^n}{\sqrt n})$, 同解法4
该方法可以看做是一种插入法, 选定一组括号 ()
, 由此便消耗了一组括号的数量, 此时还剩下 n-1
组括号, 我们将这 n-1
组括号插入到选定的括号中, 即 (left)right
, 其中, left
和 right
都是有效的括号组合, 它们的括号组数加起来刚好为 n-1
, 因此, left
的括号组数的情况共有 n
种情况: [0, …, n-1], 对应的 right
的组数有 n-1-left
组. 具体代码实现如下所示:
1 | class Solution { |
解法四: 用栈来模拟递归
首先是最厚的括号包裹状态, 即一开始左边是连续的左括号, 右边是连续的右括号, 然后执行以下逻辑:
- 右括号不能比左括号多;
- 弹出右括号, 直到遇到第一个左括号, 如果左括号改成右括号仍然合法, 则把它改成右括号; 否则, 左括号继续弹出;
- 改完之后一个劲加左括号, 直到所有可以用的左括号都加完为止; 然后再一个劲的加右括号, 直到加完位置;
- 循环一直执行到不能弹出括号为止, 即直到栈为空.
这里刚好凸显了一件事情, 那就是要注意尽可能不要将自增或自减操作写在 while()
条件句里面, 否则会造成一些很难发现的错误, 下面代码中的注释会说明
1 | class Solution { |
029. Divide Two Integers
Description: 实现除法
Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator.
Return the quotient after dividing dividend by divisor.
The integer division should truncate toward zero.
Example 1:1
2Input: dividend = 10, divisor = 3
Output: 3
Example 2:1
2Input: dividend = 7, divisor = -3
Output: -2
Note:
Both dividend and divisor will be 32-bit signed integers.
The divisor will never be 0.
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: $[−2^{31}, 2^{31 − 1}]$. For the purpose of this problem, assume that your function returns 2^{31 − 1} when the division result overflows.
解法一: 循环加法
时间复杂度: $O(dividend)$
这种方法很容易时间超限: 当被除数很大(INT_MAX), 除数很小(1), 则需要循环INT_MAX次才能完成计算.
解法二: 左移法
时间复杂度: $O(log(dividend))$, dividend 为被除数的大小.
对除数进行左移, 相当于每次乘以2, 直到左移后大于被除数, 用被除数减去左移后的数字, 记录左移对应除数的倍数, 然后再次将从除数开始左移, 直到被除数小于除数.
以上是除法的基本实现思路, 但是在具体实现时, 还需要特别考虑下面的情况
- 当被除数为 INT_MIN, 除数为 -1 时, 此时的返回值为 INT_MAX+1. (根据题目要求, 溢出时刻直接返回 INT_MAX)
- 当除数为 0 时, 也应该看做是溢出情况.
- 处理上面情况最方便的方法使用
long
长整型, 而不是unsigned int
无符号类型. 因为unsigned int
类型在进行乘以 2 的操作时, 很容易也溢出, 最终造成程序的死循环, 为了防止溢出, 最好使用long
, 具体请看代码.
1 | class Solution { |
扩展: 这道题如果不允许使用 long 或者long long 怎么解?
031. Next Permutation
Description: 实现 next_permutation 函数逻辑
Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
The replacement must be in-place and use only constant extra memory.
Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.1
2
31,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
解法一: next_permutation 实现
时间复杂度: $O(n)$
空间复杂度: $O(1)$
STL中的 next_permutation
函数和 prev_permutation
两个函数提供了对于一个特定排列P, 求出其后一个排列P+1和前一个排列P-1的功能.
next_permutation
的实现方法如下:
- 先 从后往前 找第一个小于后一个数的元素
nums[i]
:nums[i]<nums[i+1]
- 再 从后往前 找第一个大于
nums[i]
的数nums[j]
:nums[j]>nums[i]
- 交换
nums[i]
和nums[j]
- 将
i
之后的元素逆置(reverse
)
1 | class Solution { |
033. Search in Rotated Sorted Array
Description: 在循环有序数组中查找元素
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
2Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:1
2Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
解法一: 二分查找
时间复杂度: $O(logn)$
空间复杂度: $O(1)$
对于数组[4,5,6,7,0,1,2], 可以将其看成是两段: [4,5,6,7] 和 [0,1,2], 可以看出, 前一段中的任意一个数字都大于后一段中的数字, 于是, 令low=0, high=size()-1, 进行二分查找, 其中 mid 对应的数字要么落在前半段(nums[low] <= nums[mid]
), 要么落在后半段.
如果落在的前半段, 则看 target 的值是否在 low与mid之间. 是则 high = mid-1
, 否则 low = mid+1
反之, 如果落在后半段, 则看 target
的值是否在 mid
与 high
之间, 是则 low=mid+1
, 否则high = mid-1
1 | class Solution { |
解法二: 二分查找
时间复杂度: $O(logn)$
空间复杂度: $O(1)$
该方法同样是二分查找, 只不过与上面有一点不同, 对于数组nums
=[4,5,6,7,0,1,2]来说, 如果 target < nums[0]
, 说明 target
位于数组的后半段, 那么可以将数组看做是nums
=[INT_MIN,INT_MIN,INT_MIN,INT_MIN,0,1,2] , 这样一来, 就变成了最常规的有序数组, 反之, 如果 target
位于数组的前半段, 那么可以将数组看做是nums
=[4,5,6,7,INT_MAX,INT_MAX,INT_MAX].
注意, 这里并不会改变数组内部的值, 我们只是利用一个临时变量num
来代替当前的nums[mid]的值, 然后利用 num
与 target
比较进行二分查找.
1 | class Solution { |
更精简的写法:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19class Solution {
public:
int search(vector<int>& nums, int target) {
int n = nums.size();
int low=0, high=n-1;
while(low<=high){
int mid = (low+high)/2;
int num;
if(target<nums[0])
num = nums[mid]<nums[0] ? nums[mid] : INT_MIN;
else
num = nums[mid]<nums[0] ? INT_MAX : nums[mid];
if(target > num) low = mid+1;
else if(target < num) high = mid-1;
else return mid;
}
return -1;
}
};
034. Find First and Last Position of Element in Sorted Array
Description: 在有序数组中查找目标的开始位置和结束位置
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
2Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Example 2:1
2Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
解法一: 二分查找
时间复杂度: $O(logn)$
空间复杂度: $O(1)$
先用常规的二分查找找到target, 然后分别用二分查找找到最左边的target和最右边的target下标.
1 | class Solution { |
解法二: 二分查找
同样是二分查找, 更加精炼, 先找到最左边的target, 然后以最左边为low, 开始找最右边的target, 需要注意的是不能在nums[mid] == target
时就退出循环.
1 | class Solution { |
解法三: STL 函数
时间复杂度: $O(logn)$
空间复杂度: $O(1)$
直接利用 STL 的 lower_bound()
和 upper_bound()
函数分别找到其实位置和终止位置即可, 在使用这两个函数时, 需要注意以下几点:
lower_bound()
函数返回首个 不小于 target 的迭代器, 如果数组中所有元素 都小于 target, 则会返回超尾迭代器.upper_bound()
函数返回首个 大于 target 的迭代器, 如果数组中所有元素 都小于等于 target, 则会返回超尾迭代器.- 注意
upper_bound()
返回的迭代器是首个 大于 目标值的迭代器, 因此需要将其减一才是我们要找的 target 的终止位置.
1 | class Solution { |
036. Valid Sudoku
Description: 验证一个矩阵是否是数独数据
Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:
Each row must contain the digits 1-9 without repetition.
Each column must contain the digits 1-9 without repetition.
Each of the 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.
解法一: 利用flag数组存储判断矩阵
时间复杂度: $O(9^2)$
空间复杂度: $O(3\times 9^2)$ 虽然要申请三个二维数组, 但都是常数级.
用三个 9×9 大小的矩阵, 分别储存每一行上, 每一列上, 每一个子块上1-9数字是否出现.1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
// 下面三个矩阵分别存储了 行上1-9是否出现, 列上1-9是否出现, sub-box上1-9是否出现的bool值
// 如果row_flag[1][3] 为真, 则说明第1行(从第0行算起)上已经具有数字4(数字比下标大1)了
bool row_flag[9][9] {0}, col_flag[9][9] {0}, sub_flag[9][9] {0};
for(int i = 0 ; i<board.size(); i++){
for(int j = 0; j<board[i].size(); j++){
if(board[i][j] == '.') continue; // 如果为 '.' 则可以直接跳过此次判断
int num = board[i][j] - '0' - 1; //这里-1主要是为了能够直接将num作为下标使用
int k = i/3*3 + j/3;
if(row_flag[i][num] || col_flag[j][num] || sub_flag[k][num])
return false;
row_flag[i][num]=col_flag[j][num]=sub_flag[k][num]=true;
}
}
return true;
}
};
解法二: 位操作
时间复杂度: $O(n^2)=O(9^2)$
空间复杂度: $O(3\times 9)$
这是目前看到的最好的方法, 核心思想就是用一个 short
类型变量的某一位来作为 flag, 这样, 我们可以进一步节省空间的使用, 将空间复杂度从 $O(n^2)$ 降低到 $O(n)$.
1 | class Solution { |
046. Permutations
全排列, 注意是distict的数字, 故而不需要进行重复检查
Description: 不含重复数字的全排列
Given a collection of distinct integers, return all possible permutations.
Example:
Input: [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
解法一: 递归
时间复杂度: $O(A^n_n)$ , 每一种情况都是 $O(1)$ , 共有 $O(A^n_n)$ 种情况. (对吗?)
用一个变量pos指向nums的第一个位置, 然后将pos与后面所有位置上的数字交换(包括自己), 最终会得到n种可能性, 这n种可能性就是出现在第一位置上的所有可能字符的情况集合, 然后将第一位固定, 并将pos指向下一位, 此时问题转换成了n-1个字符的全排列, 按照这种想法一致递归下去, 就可以找到所有位置上的所有组合情况(用pos==nums.size()判断)
1 | class Solution { |
解法二: 迭代
时间复杂度: $O(n^3)$
空间复杂度: $O(A_n^n)$ 全排列的size
对于n个数的全排列问题, 可以想象成已经获得了n-1个数的全排列, 然后将第n个数插入到n-1个数的n个空位上( 如将3插入到12的空位上分别为: 312,132,123).
1 | class Solution { |
解法三: 利用C++的内置函数 next_permutation
关于 next_permutation()
的详细解析请看这里
STL中的 next_permutation
函数和 prev_permutation
两个函数提供了对于一个特定排列P, 求出其后一个排列P+1和前一个排列P-1的功能.
1 | class Solution { |
这道题利用 prev_permutation
也可以解决, 但是这里就多了一步 reverse
的操作, 这里贴出来只是帮助理解 STL 函数的内部实现, 对于 Permutation2 题也是同理:1
2
3
4
5
6
7
8
9
10
11class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> res;
sort(nums.begin(), nums.end(), greater<int>()); // 倒序排序
do{
res.push_back(nums);
}while(prev_permutation(nums.begin(), nums.end()));//使用 prev
return res;
}
};
解法四: 自己实现 next_permutation
用迭代器作为参数:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23class Solution {
template <typename T>
bool nextPermutation(T first, T last) {
auto i = last - 2;
auto j = last - 1;
while (i >= first && *i >= *(i+1)) i--;
if (i >= first) {
while (j >= first && *i >= *j) j--;
std::iter_swap(i, j);
std::reverse(i+1, last);
}
return i>=first ? true : false;
}
public:
vector<vector<int>> permute(vector<int>& nums) {
std::sort(nums.begin(), nums.end());
std::vector<std::vector<int>> res;
do {
res.push_back(nums);
} while (nextPermutation(nums.begin(), nums.end()));
return res;
}
};
用数组作为参数:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23class Solution {
private:
bool nextPermutation(vector<int>& nums) {
int n=nums.size();
int i = n-2, j = n-1;
while(i>=0 && nums[i]>=nums[i+1]) i--;
if(i>=0){
while(j>=0 && nums[i]>=nums[j]) j--;
swap(nums[i], nums[j]);
}
reverse(nums.begin()+i+1, nums.end());
return i>=0 ? true : false;
}
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> res;
sort(nums.begin(), nums.end());
do{
res.push_back(nums);
}while(nextPermutation(nums));
return res;
}
};
prev_permutation 实现:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23class Solution {
private:
bool prevPermutation(vector<int>& nums) {
int n=nums.size();
int i = n-2, j = n-1;
while(i>=0 && nums[i]<=nums[i+1]) i--;
if(i>=0){
while(j>=0 && nums[i]<=nums[j]) j--;
swap(nums[i], nums[j]);
}
reverse(nums.begin()+i+1, nums.end());
return i>=0 ? true : false;
}
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int>> res;
sort(nums.begin(), nums.end(), greater<int>());
do{
res.push_back(nums);
}while(prevPermutation(nums));
return res;
}
};
next_permutation
python 实现:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19class Solution:
def nextPermutation(self, nums: List[int]) -> None:
n = len(nums)
i = n - 2
j = n - 1
while (i >= 0 and nums[i] >= nums[i+1]): i -= 1 # 找到i
if (i >= 0):
while (j > i and nums[i] >= nums[j]): j -= 1 # 找到 j
nums[i], nums[j] = nums[j], nums[i] # 交换, 并将 i 之后的进行逆置
nums[i+1:] = nums[i+1:][::-1]
return True if i != -1 else False
def permute(self, nums: List[int]) -> List[List[int]]:
nums.sort()
res = []
res.append(nums.copy()) # 注意这里一定要用copy, 否则后续的更改会影响前面的nums的值
while(self.nextPermutation(nums)):
res.append(nums.copy())
return res
prev_permutation
python 实现1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19class Solution:
def prevPermutation(self, nums: List[int]) -> None:
n = len(nums)
i = n - 2
j = n - 1
while (i >= 0 and nums[i] <= nums[i+1]): i -= 1 # 找到i
if (i >= 0):
while (j > i and nums[i] <= nums[j]): j -= 1 # 找到 j
nums[i], nums[j] = nums[j], nums[i] # 交换, 并将 i 之后的进行逆置
nums[i+1:] = nums[i+1:][::-1]
return True if i != -1 else False
def permute(self, nums: List[int]) -> List[List[int]]:
nums.sort(reverse=True)
res = []
res.append(nums.copy()) # 注意这里一定要用copy, 否则后续的更改会影响前面的nums的值
while(self.prevPermutation(nums)):
res.append(nums.copy())
return res
047. Permutations II
Description: 带有重复元素的全排列
解法一: 递归+set
时间复杂度:
空间复杂度:
set
插入元素的时间复杂度为 $O(logn)$, $n$ 为当前 set
的大小.
1 | class Solution { |
解法二: STL 的 next_permutation 函数
关于 next_permutation()
的详细解析请看这里
1 | class Solution { |
使用 prev_permutation()
也可解决, 不过需要记得要倒序排序.1
2
3
4
5
6
7
8
9
10
11class Solution {
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int>> res;
sort(nums.begin(), nums.end(), greater<int>()); // 倒序排序
do{
res.push_back(nums);
}while(prev_permutation(nums.begin(), nums.end())); // prev
return res;
}
};
解法三: 自己实现 next_permutation()
python 实现:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
def nextPermutation(nums):
n = len(nums)
i = n - 2
j = n - 1
while (i >= 0 and nums[i] >= nums[i+1]): i -=1
if (i>=0):
while (j > i and nums[i] >= nums[j]): j -=1
nums[i], nums[j] = nums[j], nums[i]
nums[i+1:] = nums[i+1:][::-1]
return True if i != -1 else False
nums.sort()
res = []
res.append(nums.copy())
while (nextPermutation(nums)):
res.append(nums.copy())
return res
用迭代器做参数:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24class Solution {
template <typename T>
bool nextPermutation(T first, T last) {
auto i = last - 2;
auto j = last - 1;
while (i >= first && *i >= *(i+1)) i--;
if (i >= first) {
while (j >= first && *i >= *j) j--;
std::iter_swap(i, j);
std::reverse(i+1, last);
}
return i>=first ? true : false;
}
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
std::sort(nums.begin(), nums.end());
std::vector<std::vector<int>> res;
do {
res.push_back(nums);
} while(nextPermutation(nums.begin(), nums.end()));
return res;
}
};
用数组做参数:
1 | class Solution { |
048. Rotate Image
Description: 图片旋转 90 度
You are given an n x n 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).
Note:
You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.
Example 1:
Given input matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],
rotate the input matrix in-place such that it becomes:
[
[7,4,1],
[8,5,2],
[9,6,3]
]
Example 2:
Given input matrix =
[
[ 5, 1, 9,11],
[ 2, 4, 8,10],
[13, 3, 6, 7],
[15,14,12,16]
],
rotate the input matrix in-place such that it becomes:
[
[15,13, 2, 5],
[14, 3, 4, 1],
[12, 6, 8, 9],
[16, 7,10,11]
]
解法一: 逆置+转置
时间复杂度: $O(n^2)$, 因为转置的复杂度为 $O(n^2)$
将图像矩阵看做是线性代数中的行列式, 首先将所有的行逆置(行与行交换), 然后对整个矩阵转置.
原理: 利用线性代数行列式的运算法则可证明(数学归纳法)
clockwise rotate
first reverse up to down, then swap the symmetry1
2
31 2 3 7 8 9 7 4 1
4 5 6 => 4 5 6 => 8 5 2
7 8 9 1 2 3 9 6 3
1 | class Solution { |
解法二: 转置+列逆置
先求转置, 再对列逆置(列与列交换):
1 | class Solution { |
补充: 逆时针旋转90度
先使用列逆置(列与列交换), 然后对矩阵使用转置
1 | 1 2 3 3 2 1 3 6 9 |
1 | void anti_rotate(vector<vector<int> > &matrix) { |
补充: 图片旋转 180 度(上下翻转)
将所有的行逆置1
2
31 2 3 7 8 9
4 5 6 => 4 5 6
7 8 9 1 2 3
1 | reverse(matrix.begin(), matrix.end()) |
补充: 图片左右翻转
将所有的列逆置1
2
31 2 3 3 2 1
4 5 6 => 6 5 4
7 8 9 9 8 7
1 | for (auto vi : matrix) reverse(vi.begin(), vi.end()); |
049. Group Anagrams
Description: 找出同字母的异序词, 并按字母分组输出
Given an array of strings, group anagrams together.
Example:
Input: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”],
Output:
[
[“ate”,”eat”,”tea”],
[“nat”,”tan”],
[“bat”]
]
Note:
All inputs will be in lowercase.
The order of your output does not matter.
解法一: 哈希表+sort
用哈希表来存, 键为有序的字符序列, 值为string数组, 里面存着各个与有序字符序列包含字符相同的其他序列
时间复杂度: $O(nmlogm)$ , 其中, n为输入字符串数组的长度, m为每个字符串的长度, 对于n个字符串, 要进行n次哈希表的插入, 同时每次插入时, 需要对字符串进行排序, 排序复杂度为 $O(mlogm)$.
空间复杂度: $O(mn)$
1 | class Solution { |
解法二: 哈希表(不使用sort)
时间复杂度: $O(nm)$ , 其中, n为string个数, m为每个string的字母数.
空间复杂度: $O(nm)$
由于上面的解法二需要使用排序, 故而时间上不够优化, 因此, 这里我们可以设计新的键来代替sort, 基本思想是对26个字母, 分别赋予一个素数值, 然后, 计算键的时候, 将对应字母的素数 相乘 即可, 这样一来, 每一种字符串的key都是唯一的( 因为最终的乘积可以唯一的表示成素数相乘的序列 ).
1 | // 该解法是错误的 |
解法三: 另一种生成 key 的解法(不用sort)
应该将字符count作为键, 所谓字符count就是统计每个字符出现的次数, 然后根据该信息就可以生成唯一的一个字符串, 例如, 对于 “abbb”, 来说, ‘a’ 出现了一次, ‘b’ 出现了三次, 因此, 其字符count就应该为: (1,3,0,…0), 总共有 26 个元素, 为了将其转换成字符串, 需要用一个特殊符号来做分隔符, 因此可以生成如下的字符串: "#1#3#0#0...#0"
(这也是通常的内置 hash 的键的实现方法之一).
该解法的时间复杂度为 $O(mn)$, 其中, $n$ 为遍历字符串数组的时间, $m$ 为获取 key 的时间, 无需进行排序.
1 | class Solution { |
050. Pow(x, n)
实现幂乘操作
Descriptin
Implement pow(x, n), which calculates x raised to the power n (x^n).
Example 1:
Input: 2.00000, 10
Output: 1024.00000
Example 2:
Input: 2.10000, 3
Output: 9.26100
Example 3:
Input: 2.00000, -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25
Note:
-100.0 < x < 100.0
n is a 32-bit signed integer, within the range $[−2^{31}, 2^{31} − 1]$
解法一: 递归
时间复杂度: $O(logn)$
空间复杂度: $O(1)$
当n为偶数时: $x^n = x^{n/2} \times x^{n/2}$
当n为奇数时: $x^n = x\times x^{n/2} \times x^{n/2}$
这里需要注意一点: abs(INT_MIN) 的值仍然是负值, 因为 int
只有 32 位, abs(INT_MIN) 时, 仍然是 32 位, 因此不会变成正值, 解决方法是先把该值赋给 long
型变量, 然后对 long
型变量调用 abs()
函数, 另一种解决方法是利用 unsigned int
:1
2
3
4
5
6
7
8int min = INT_MIN; // -2147483648
long min_abs1 = abs(min); // 2147483648, 这里 min_abs1 的值仍然是 INT_MIN, 因为调用 abs 的时候, 仍然是32位
long min_abs2 = min;
min_abs2 = abs(min_abs2); // 2147483648, 这里是对64位调用 abs, 所以成功转化成正数
// 解决方法二是利用 unsigned int
unsigned int abs_min = abs(min) //2147483648
1 | class Solution { |
解法二: 非递归
时间复杂度: $O(logn)$
空间复杂度: $O(1)$
n 要么为偶数, 要么为奇数, 我们每一次都将 n 的值减半, 并且将 x 与自身相乘, 每次当 n 为奇数时, 我们都将 res 与 x 相乘, 最终, res 的值就是我们要求的幂乘. 举例来说,
对于 x=2, n=10 , 每次将x和自身相乘, 同时将 n 减半, n 和 x 的值分别为:1
2n: 10, 5, 2, 1, 0
x: 2, 4, 16, 256, 65536
可以看到, 我们将 n 为奇数时的 x 相乘, 就是最终的幂乘: $4\times 256 = 2^{10} = 1024$. 当 n 为奇数时也是同理, 如下所示:
1 | n: 11, 5, 2, 1, 0 |
最终幂乘: $2\times 4\times \times 256 = 2^{11} = 2048$
1 | class Solution { |
054. Spiral Matrix
以顺时针螺旋顺序返回矩阵元素, 顺时针打印矩阵
Description
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
Example 1:
Input:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
Output: [1,2,3,6,9,8,7,4,5]
Example 2:
Input:
[
[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10,11,12]
]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]
解法: 按层次输出(由外而内)
时间复杂度: $O(n)$
空间复杂度: $O(n)$
输出形式如下(按层次编码, 以4×6的矩阵为例), 需要注意边界控制条件:
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
34class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
std::vector<int> res;
if (matrix.empty() or matrix[0].empty()) return res;
int n = matrix.size();
int m = matrix[0].size();
int rowUp = -1; // 记录上边界
int rowDown = n; // 下边界
int colLeft = -1; // 左边界
int colRight = m; // 右边界
while (rowUp < rowDown and colLeft < colRight) {
rowUp++;
rowDown--;
if (rowUp > rowDown) break; // 如果越界, 则直接退出
colLeft++;
colRight--;
if (colLeft > colRight) break; // 越界则退出
for (int j = colLeft; j <= colRight; j++) {
res.emplace_back(matrix[rowUp][j]);
}
for (int i = rowUp+1; i <= rowDown-1; i++) {
res.emplace_back(matrix[i][colRight]);
}
for (int j = colRight; rowUp != rowDown and j >= colLeft; j--) {
res.emplace_back(matrix[rowDown][j]);
}
for (int i = rowDown-1; colLeft != colRight and i >= rowUp+1; i--) {
res.emplace_back(matrix[i][colLeft]);
}
}
return res;
}
};
055. Jump Game
数组的数字为最大的跳跃步数, 根据数组判断是否能跳到最后一位上
Description
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
Example 1:
Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:
Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
jump length is 0, which makes it impossible to reach the last index.
解法一: 回溯
时间复杂度: $O(2^n)$ 总共有 $2^n$ 种跳法来跳到最后一个位置上(对于任意一个位置, 有经过和不经过两个种可能性)
空间复杂度: $O(n)$
试遍所有的可能性, 正常来说会超时, 并且也肯定不是最佳答案
1 | class Solution { |
解法二: top-down 动态规划(递归)
时间复杂度: $O(n^2)$ , 对于每个点来说, 都是要找到下一个good_position
, 则需要进行 $(O)$ 的查找, 又因为总共有 $O(n)$个元素, 所以复杂度为 $O(n^2)$.
空间复杂度: $O(2n)$, 递归需要 $O(n)$ , memo
需要 $O(n)$.
设计一个数组, 用来记录当前下标对应位置是否可又达到终点, 如果能, 则该位置为good position
, 如果不能, 则为bad position
, 刚开始的时候都是unknown position
(除了最后一个位置为good
).
1 | class Solution { |
解法三: down-top 动态规划(非递归)
时间复杂度: $O(n^2)$ , 对于每个点来说, 都是要找到下一个good_position
, 则需要进行 $(O)$ 的查找, 又因为总共有 $O(n)$个元素, 所以复杂度为 $O(n^2)$.
空间复杂度: $O(n)$, 无需递归 , 只需要memo
, $O(n)$.
动态规划的非递归版本.
1 | class Solution { |
解法四: 贪心
时间复杂度: $O(n)$
空间复杂度: $O(1)$
由上面的down-top递归可以看出, 当前下标位置的点是否为good点, 实际上只取决于当前点是否能够达到右边坐标中(从右往左走)最左边的good(可以看上面的break语句), 如果能够达到, 则当前点一定为good点, 因此, 我们只需要用一个变量left_most_good
来维护当前点右边的最左good点下标即可, 无需任何其他空间和操作.(速度极快)
1 | class Solution { |
另一种贪心的形式: 记录当前能够达到的最大位置
1 | class Solution { |
056. Merge Intervals
融合区间
Description
Given a collection of intervals, merge all overlapping intervals.
Example 1:
Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
Example 2:
Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considerred overlapping.
解法一: sort+O(n)
时间复杂度: $O(nlogn)$, 主要是排序
空间复杂度: $O(n)$
最简单的实现方法, 先按照interval.start用sort排序, 排好序以后, 能够融合的interval都会聚到一起, 这个时候, 因为start是呈递增的, 只需要看end的大小关系就可以.
最简单的实现方法就是sort之后, 通过额外申请空间来存储融合后的interval, 最后返回
1 | class Solution { |
解法二: sort+O(1)
时间复杂度: $O(nlogn)$ , 主要是排序
空间复杂度: $O(1)$
上面的方法在逻辑上不够好, 因为既然已经申请了额外的内存来存储放回结果, 说明我们不希望改变原vector内部的数据, 但是sort之后, 数据顺序已经被破坏了, 既然已经破坏了, 那最好就是直接使用原地融合的办法, 来减少内存的开销1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20class Solution {
public:
vector<Interval> merge(vector<Interval>& intervals) {
if(intervals.size()==0) return vector<Interval>{};
//vector<Interval> res; 既然决定使用sort, 就说明已经改变了intervals, 此时不应该在额外申请空间, 而应该进行原地融合.
std::sort(intervals.begin(), intervals.end(), [](Interval a, Interval b){return a.start < b.start;});
auto cur_iv = intervals.begin();
auto next_iv = intervals.begin()+1;
for(; next_iv!=intervals.end(); next_iv++){
if( (*cur_iv).end < (*next_iv).start ){
cur_iv++;
(*cur_iv) = (*next_iv);
}else{
(*cur_iv).end = std::max( (*cur_iv).end, (*next_iv).end );
}
}
intervals.erase(cur_iv+1, intervals.end());
return intervals;
}
};
解法三: 不使用sort
有时, 我们要求不能改变原向量intervals的内容, 此时, 就不能使用sort (除非牺牲大量空间留副本,但单肯定不推荐).
//TODO, 未细看, 但时间复杂度应该会高于 O(nlogn)
https://leetcode.com/problems/merge-intervals/discuss/153979/Elegant-c++-solutions.-One-without-modifying-intervals-and-one-inplace1
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
Without modifying intervals
Since we can't sort interval, we want to instead ensure our destination vector is sorted. A insertion sort is required then. Insertion should be done as follows;
Find first destination interval that ends after the incoming interval starts. Called it
If no such interval is found or the incoming interval end is less than found intervals start then we can just insert and be done.
Otherwise there must be an overlap, but it could be more than one. Do another search, this time for the first interval whose start is greater than incoming interval end. Called last
Everything from [it, last) can be merged together with incoming interval into a single interval
vector<Interval> merge(vector<Interval>& intervals) {
std::vector<Interval> ret;
for (auto& interval : intervals) {
auto it = std::lower_bound(ret.begin(), ret.end(), interval.start, [](const Interval& l, int r) { return l.end < r; });
if (it == ret.end() || interval.end < it->start)
// No overlap, insert as is
ret.insert(it, interval);
else {
// There is an overlap, there might be more, so find the upper bound too
it->start = std::min(it->start, interval.start);
auto last = std::upper_bound(it, ret.end(), interval.end, [](int l, const Interval& r) { return l < r.start; });
it->end = std::max((last - 1)->end, interval.end);
ret.erase(it + 1, last);
}
}
return ret;
}
062. Unique Paths
Description
A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).
How many possible unique paths are there?
解法一: DP
时间复杂度: $O(mn)$
空间复杂度: $O(mn)$
这是一道经典的DP问题, 当机器人处于某一点时, 它只能从上面或者左边到达该点, 因此很容易得出path[i][j] = path[i-1][j] + path[i][j-1];
, 其中 path[i][j]
指到达 $(i,j)$ 点的可能路径数量.
1 | class Solution { |
解法二: 优化的DP
时间复杂度: $O(mn)$
空间复杂度: $O(n)$
通过分析知道, 当前点的可能路径数量只与上面点和左边点的值有关, 在上面的方法中, 我们用一个 $m\times n$ 的数组来存储当前点上面和左边的值, 实际上, 我们只需要用一行数组就可以完成这个功能, 首先, 求出第一行的所有点的值, 这里只会用每个点左边的值, 然后, 对于第二行的第一个点来说, 它只会用到上面的值, 也就是第一行的第一个值, 因此可以通过行数组直接得到, 然后, 对于第二行的第二个值, 它可以从第二行的第一个值, 以及第二行的第二个值得到, 这些值都是已知的, 所以可以直接求的, 由于在求得以后, 我们就再也不需要第一行的第二个值了, 所以我们可以用这个存储空间来存储第二行的第二个值, 如此递归执行, 我们只需要 $O(n)$ 的空间即可.
1 | class Solution { |
解法三: 排列组合(最优)
时间复杂度: $O(n)$
空间复杂度: $O(1)$
实际上, 仔细分析该问题, 可以把该问题看成是一个典型的排列组合问题. 首先, 将机器人向右走记为 1, 将机器人向下走记为 0. 题目问有多少种不同的走法, 实际上就是在问1/0序列的不同排列有多少种, 并且, 1/0 的长度必须为 $(m -1 + n - 1)$. 因此, 这个问题可以看做是从 $(m-1+n-1)$ 个空槽位上选择 $(m-1)$ 个槽位, 将其置为1, 并将剩余的 $n-1$ 个槽位置为0, 故而就是组合问题: $C_{m-1+n-1}^{m-1}$ . 又因为 $C_{m-1+n-1}^{m-1} = C_{m-1+n-1}^{n-1}$ , 所以为了防止溢出, 我们可以选择小的进行计算
注意, 在排列如何时, 因为涉及到出发, 所以一定要注意计算法则的先后顺序, 具体请看代码
1 | class Solution { |
073. Set Matrix Zeroes
Description
Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place.
Example 1:
Input:
[
[1,1,1],
[1,0,1],
[1,1,1]
]
Output:
[
[1,0,1],
[0,0,0],
[1,0,1]
]
Example 2:
Input:
[
[0,1,2,0],
[3,4,5,2],
[1,3,1,5]
]
Output:
[
[0,0,0,0],
[0,4,5,0],
[0,3,1,0]
]
Follow up:
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?
解法一: 穷举
时间复杂度: $O(nm)$
空间复杂度: $O(nm)$
记录所有出现0的位置, 然后根据这些位置坐标将对应的行和列上的值置为0.
1 | class Solution { |
解法二: 穷举(减少空间复杂度)
时间复杂度: $O(nm)$
空间复杂度: $O(n+m)$
上面在记录位置坐标时没有进行重复检查, 实际上, 对于已经记录过的行或列, 可以不用再记录, 此时, 空间复杂度可以降为 $O(m+n)$.
1 | class Solution { |
解法三: 穷举(无空间复杂度)
时间复杂度: $O(nm\times (m+n))$
空间复杂度: $O(1)$
遍历矩阵时, 如果遇到 $(i,j)$ 上的值为0, 那么就将对应的行和列上的所有非0值全部置为一个矩阵范围外的值NAN(解答里面用的是-100000, 实际上这种解法存在问题, 因为理论上矩阵中的元素可以是表示范围内的任何值 ).
之后将所有的NAN值置为0, 就可以完成置0任务, 并且没有使用额外的空间. 由于每次找到一个0时, 都要遍历这个位置上的行和列, 因此时间复杂度较高
解法四: 用第一行和第一列记录
时间复杂度: $O(nm)$
空间复杂度: $O(1)$
用第一行和第一列的值记录是否应该将对应的行和列置为0, 此时由于第一行和第一列被用作了标记数组, 因此第一行和第一列的0不能用来判断是否应该置为全0, 所以需要额外设置两个变量记录.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
35class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
bool is_row=false, is_col = false; // 用第一行和第一列的值来做标记, 因此需要额外的记录第一行和第一列本身是有应该全0
for(int i=0; i<matrix.size(); i++){
for(int j=0; j<matrix[0].size(); j++){
if(matrix[i][j] == 0){
if(i==0) is_row=true;
if(j==0) is_col=true;
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
for(int i=1; i<matrix.size(); i++){
if(matrix[i][0]!=0) continue;
for(int j=0; j<matrix[0].size(); j++){
matrix[i][j] = 0;
}
}
for(int j=1; j<matrix[0].size(); j++){
if(matrix[0][j]!=0) continue;
for(int i=0; i<matrix.size(); i++){
matrix[i][j] = 0;
}
}
if(is_row){ //需要特别判断第一行和第一列是否应该置为0
for(int j=0; j <matrix[0].size();j++) matrix[0][j]=0;
}
if(is_col){
for(int i=0; i< matrix.size(); i++) matrix[i][0]=0;
}
}
};
075. Sort Colors
对0,1,2 (颜色: RGB) 进行排序
Description
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Note: You are not suppose to use the library’s sort function for this problem.
Example:
Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
Follow up:
A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0’s, 1’s, and 2’s, then overwrite array with total number of 0’s, then 1’s and followed by 2’s.
Could you come up with a one-pass algorithm using only constant space?
解法一: 两次遍历
时间复杂度: $O(n)$
空间复杂度: $O(1)$
第一次遍历统计0,1,2的个数, 第二次遍历根据0,1,2的个数覆盖数组原有值
解法二: 一次遍历
时间复杂度: 大于 $O(n)$
空间复杂度: $O(1)$
设置mid, low, high三个指示变量, 如果mid==0, 则将其与low交换, 如果mid==2, 则将其与high交换, 直到mid>high为止.
1 | class Solution { |
077. Combinations
Description: 输出所有的组合
Given two integers n and k, return all possible combinations of k numbers out of 1 … n.
Example:1
2
3
4
5
6
7
8
9
10Input: n = 4, k = 2
Output:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
解法一: 回溯
时间复杂度:
空间复杂度:
标准的回溯(深度游戏遍历)解法
1 | class Solution { |
解法二: 迭代
TODO: 未看懂
1 | class Solution { |
078. Subsets
返回给定数字序列的子集, 序列中每个元素都不同(这是一个很重要的条件!!)
Description
Given a set of distinct integers, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.
Example:
Input: nums = [1,2,3]
Output:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
解法一: 迭代直接求出子集
时间复杂度: $O(2^n)$ , 对于任意一个元素, 有包含和不包含两种情况
空间复杂度: $O(2^n)$
由于序列中的每个元素都不同, 因此, 对于任意一个元素, 只需要将其添加都前面序列所组成的子集的每一个子序列的末尾即可, 无需考虑是否包含重复元素的情况.
1 | class Solution { |
解法二: 回溯
https://leetcode.com/problems/subsets/discuss/27281/A-general-approach-to-backtracking-questions-in-Java-(Subsets-Permutations-Combination-Sum-Palindrome-Partitioning)
回溯法可以解决一系列相关问题, 先看Subsets的求解
1 | class Solution { |
其他问题:
Subsets II (contains duplicates) : https://leetcode.com/problems/subsets-ii/
悠悠 11:05:53
Permutations : https://leetcode.com/problems/permutations/
悠悠 11:06:01
Permutations II (contains duplicates) : https://leetcode.com/problems/permutations-ii/
悠悠 11:06:09
Combination Sum : https://leetcode.com/problems/combination-sum/
悠悠 11:06:16
Combination Sum II (can’t reuse same element) : https://leetcode.com/problems/combination-sum-ii/
悠悠 11:06:23
Palindrome Partitioning : https://leetcode.com/problems/palindrome-partitioning/
解法三: bit控制
时间复杂度: $O(n\times 2^n)$ , 最慢的方法.
空间复杂度: $O(2^n)$
因为对于任意一个数只有两种可能性, 出现在子序列中, 或者不出现在子序列中, 因此对于长度为 n 的(无相同元素的)序列来说, 共有 $2^n$ 个子序列, 我们先为这些子序列申请空间, 然后根据位操作(刚好有0,1两种情况)来决定对应位置上的字符出现还是不出现.
在实现时, 观察到, 第一个元素每隔两个子序列出现一次, 第二个元素每隔四个子序列出现两次, 第三个元素每隔八个子序列出现四次…
依次类推, 我们可以根据当前元素的位置来决定当前元素是否出现(间隔的前一半出现, 后一半不出现)
1 | class Solution { |
079. Word Search
判断指定单词是否存在于字符矩阵中(可以通过上下左右邻接字符相连的才算是一个单词)
Description: 判断指定单词是否存在于字符矩阵中
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:
board =
[
[‘A’,’B’,’C’,’E’],
[‘S’,’F’,’C’,’S’],
[‘A’,’D’,’E’,’E’]
]
Given word = “ABCCED”, return true.
Given word = “SEE”, return true.
Given word = “ABCB”, return false.
解法一: dfs+回溯
时间复杂度: $O(mn 4^k)$, 暴力求解, $mn$ 为字符矩阵的宽和高, 也即 cell 数量, 对于 dfs 中的每个 cell, 有4个扩展方向, 一共需要扩展 $k$ 次($k$ 为单词的长度).
空间复杂度: $O(mn)$ , 回溯时, 用#
来记录已经遍历过的点, 无需申请额外空间来记录. 但是递归程序需要占用 $O(mn)$ 的空间复杂度.
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
36class Solution {
private:
bool dfs(vector<vector<char>> &board, string &word, int i, int j, int pos){
if(board[i][j] != word[pos]) return false;
if(pos == word.size()-1) return true; // 注意是size-1
int direct[4][2] = {{0,-1},{0,1},{-1,0},{1,0}};
int m = board.size();
int n = board[0].size();
char c = board[i][j];
board[i][j] = '#'; // 标记成已访问
for(auto d : direct){
int x=i+d[0];
int y=j+d[1];
if(x>=0 && x<m && y>=0 && y<n && board[x][y]!='#'){
if(dfs(board, word, x, y, pos+1)) return true;
}
}
board[i][j] = c; // 退出前重置访问状态
return false;
}
public:
bool exist(vector<vector<char>>& board, string word) {
if(board.empty() || board[0].empty()) return false;
if(word.empty()) return true;
int m = board.size();
int n = board[0].size();
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(dfs(board, word, i, j, 0))
return true;
}
}
return false;
}
};
090. Subsets II
Description: 含重复元素的数组的子集
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
2
3
4
5
6
7
8
9
10Input: [1,2,2]
Output:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
解法一: 迭代
时间复杂度: $O(2^n)$, 时间复杂度为子集的个数
时间复杂度: $O(n)$, 空间复杂度为最长子集的长度
先排序, 然后对于一个元素, 如果这个元素与前一个元素相等, 那么在插入的时候, 就不能从第一个子集插入, 因为这样会重复, 因此要从不会造成重复的元素开始插入, 具体可看代码.
1 | class Solution { |
解法二: 回溯
时间复杂度: $O(2^n)$, 时间复杂度为子集的个数
时间复杂度: $O(n)$, 空间复杂度为递归的深度
先排序, 然后同样, 如果遇到相等元素, 则跳过, 以避免重复
1 | class Solution { |
091. Decode Ways
Description
A message containing letters from A-Z is being encoded to numbers using the following mapping:
‘A’ -> 1
‘B’ -> 2
…
‘Z’ -> 26
Given a non-empty string containing only digits, determine the total number of ways to decode it.
Example 1:
Input: “12”
Output: 2
Explanation: It could be decoded as “AB” (1 2) or “L” (12).
Example 2:
Input: “226”
Output: 3
Explanation: It could be decoded as “BZ” (2 26), “VF” (22 6), or “BBF” (2 2 6).
解法一(最优): DP constant space
时间复杂度: $O(n)$
空间复杂度: $O(1)$
存在问题: 下面的程序在面对测例:230001或230时, 输出的不是0. 但是仍然能通过OJ, 但实际上下面的解法在面对上面的样例时会返回错误答案, 因为没有对 0 进行特殊处理.
1 | class Solution { |
修复了上述的问题, 现在遇到 0 时会进行额外的判断, 0 不能单独编码, 必须与前面的字符组合, 如果无法组合, 则应该返回0, 如 230001, 就应该返回 0, 代码如下: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
27class Solution {
public:
int numDecodings(string s) {
int n = s.size();
if(n==0 || s[0] == '0') return 0;
//if(n==1) return 1;
vector<int> dp(n, 0);
dp[0] = 1;
int i = 1;
while(i<n){
if(s[i]=='0'){
if(s[i-1] =='2' || s[i-1] == '1') // 0 不能单独编码, 必须与前面的数字组合, 因此这里是 dp[i-2]
dp[i] = i>1 ? dp[i-2] : 1;
else // 如果 0 前面的值大于 2, 则无法组成编码, 应返回 0
return 0;
}
else if(s[i-1]=='1' ||(s[i-1]=='2' && s[i] <= '6')){
int prev_two = i>1 ? dp[i-2] : 1;
dp[i] = dp[i-1] + prev_two;
}else{
dp[i] = dp[i-1];
}
i++;
}
return dp[n-1];
}
};
上面的代码使用了 DP 数组, 空间复杂度为 $O(n)$, 实际上我们并不需要这么多空间, 只需要常数空间就可以完成数组, 即只需要当前 dp 值的前两个 dp 值即可. 代码如下: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
36class Solution {
public:
int numDecodings(string s) {
int n = s.size();
if(n==0 || s[0] == '0') return 0;
//if(n==1) return 1;
vector<int> dp(n, 0);
int f1 = 1; // 代表当前dp值之前一位的dp值
int f2 = 1; // 代表当前dp值之前两位的dp值
dp[0] = 1;
int i = 1;
while(i<n){
if(s[i]=='0'){
if(s[i-1] =='2' || s[i-1] == '1'){ // 0 不能单独编码, 必须与前面的数字组合, 因此这里是 dp[i-2]
int tmp = f1;
f1 = f2; // 令当前dp值为f2 (当前的dp值会成为下一个f1值)
f2 = tmp;
}
else // 如果 0 前面的值大于 2, 则无法组成编码, 应返回 0
return 0;
}
else if(s[i-1]=='1' ||(s[i-1]=='2' && s[i] <= '6')){
f1 = f1 + f2;
f2 = f1 - f2;
// 上面两个式子相当于:
// int tmp = f1; f1 = f1+f2; f2 = tmp;
//int prev_two = i>1 ? dp[i-2] : 1;
//dp[i] = dp[i-1] + prev_two;
}else{
f2 = f1; // 当前dp值不变, 所以只需要更新 f2 即可
}
i++;
}
return f1;
}
};
另一种写法, 更好理解: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
27class Solution {
public:
int numDecodings(string s) {
if (s.empty() || s[0] == '0') return 0;
int dp1 = 1; // 记录当前字符前一位的可能组合数
int dp2 = 1; // 记录当前字符前两位的可能组合数
long res = 1; // 记录当前字符的可能组合数
for (int i = 1; i < s.size(); i++) {
if (s[i] == '0') {
if (s[i-1] == '1' or s[i-1] == '2') { // d
res = dp2;
} else {
return 0;
}d
}
else if (s[i-1] == '1'
or (s[i-1] == '2' and s[i] < '7' and s[i] > '0')) {
res = dp1 + dp2;
} else {
res = dp1;
}
dp2 = dp1;
dp1 = res;
}
return res;
}
};
解法二: 递归
时间复杂度: $O(n^2)$
1 | class Solution { |
094. Binary Tree Inorder Traversal
中序遍历二叉树
Description
Given a binary tree, return the inorder traversal of its nodes’ values.
Example:1
2
3
4
5
6
7
8Input: [1,null,2,3]
1
\
2
/
3
Output: [1,3,2]
Follow up: Recursive solution is trivial, could you do it iteratively?
解法一: 递归
1 | /** |
解法二: 非递归
标准的中序非递归遍历算法
1 | class Solution { |
098. Validate Binary Search Tree
Description
Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
Both the left and right subtrees must also be binary search trees.
Example 1:
Input:
2
/ \
1 3
Output: true
Example 2:
5
/ \
1 4
/ \
3 6
Output: false
Explanation: The input is: [5,1,4,null,null,3,6]. The root node’s value
is 5 but its right child’s value is 4.
解法一: 递归
用一个指针来指向当前节点在顺序上的前一个节点, 判断是否为BST
1 | class Solution { |
下面的代码是典型错误解法: 因为, 我们不知只要考虑左子树节点值要小于当前节点值, 还要满足的另外一个条件是左子树本身也是一个二叉搜索树, 下面的代码没有进行该判断.
1 | /* |
解法二: 迭代(中序)
中序遍历二叉搜索树时, 返回的是一个有序的数组, 因此, 我们可以在遍历时, 一旦发现不有序, 就返回 false, 需要注意一点的是, 本题中二叉搜索树中的节点值是唯一的.
1 | class Solution { |
102. Binary Tree Level Order Traversal
按层次输出二叉树节点的值(每层的值要分开)
Description
解法一: 层次遍历
时间复杂度: $O(n)$ , 每个节点遍历一次
空间复杂度: $O(n)$ , 存储了n个节点的值
1 | /** |
103. Binary Tree Zigzag Level Order Traversal
按之字形打印二叉树
Description
Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]
解法一:利用reverse
时间复杂度为 $O(n^2)$ 空间复杂度为 $O(n)$
然后每次访问节点时, 都判断当前节点的层数, 如果为奇数层, 则将该层直接push back到结果向量中, 如果为偶数, 则将该层数据进行reverse后再push back到结果向量中. 通过while里面内置for循环, 来保证每次for循环都会将一整层的节点放进队列中, 无需额外的数组来存储depth信息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
29class Solution {
public:
vector<vector<int> > Print(TreeNode* pRoot) {
vector<vector<int>> res;
if(pRoot == NULL)
return res;
queue<TreeNode*> que;
que.push(pRoot);
bool even = false;
while(!que.empty()){
vector<int> vec; //将vec声明在内部, 省去每次的clear操作, clear操作需要对vector进行遍历, 并将每个元素置为null?
const int size = que.size(); //当前存的节点数目就是这一层所有的节点, 之前层的到已经被取出, 并且这一层的子节点还没有开始入队列
for(int i=0; i<size; ++i){ //将该层所有节点的子节点入队列, 同时当到达该层最后一个节点时终止
TreeNode* tmp = que.front();
que.pop();
vec.push_back(tmp->val);
if(tmp->left != NULL)
que.push(tmp->left);
if(tmp->right != NULL)
que.push(tmp->right);
}
if(even) //根据奇偶标识判断是否需要reverse
std::reverse(vec.begin(), vec.end());
res.push_back(vec);
even = !even;
}
return res;
}
};
解法二: 最优(不用reverse)
时间复杂度: $O(n)$
空间复杂度: $O(n)$
在解法二中, 复杂度高的原因是因每次遇到偶数层的时候都要进行 reverse, 实际上, 当我们知道了该层的节点个数以后, 我们可以直接开辟一个指定大小的 vector, 然后根据下标随机访问来填入该层的节点值, 这样一来就不用进行 reverse, 并且空间复杂度与解法二相同
1 | class Solution { |
解法三: 利用双端队列
时间复杂度: $O(n)$
空间复杂度: $O(n)$
1 | class Solution { |
105. Construct Binary Tree from Preorder and Inorder Traversal
Description: 根据先序和中序遍历构造二叉树
Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.(如果没有该条件则通常无法还原唯一的二叉树)
For example, given
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
Return the following binary tree:1
2
3
4
5 3
/ \
9 20
/ \
15 7
解法一: 递归
时间复杂度: $O(n^2)$, 在中序遍历中查找根节点的复杂度为 $O(n)$, 先序序列中总共有 $n$ 个根节点, 所以需要查找 $n$ 次
空间复杂度: 根据树的结构, 最坏情况下的递归深度为 $O(n)$.
先取先序遍历中的第一个节点为根节点, 然后在中序遍历冲查找该节点, 以该节点为界限将数组分成两边, 分别为左子树和右子树, 根据左子树和右子树的长度在先序遍历中也划分对应长度的两个数组, 然后将两个数组分别作为左子树的先序和中序, 以及右子树的先序和中序进行递归构建.
1 | /** |
解法二: 迭代
时间复杂度: $O(n)$
空间复杂度: $O(n)$
- 先将
preorder[i]
压入栈中, 如果当前 preorder 的元素与 inorder 中的元素不匹配, 则将 preorder 中的值构造成节点压入栈中, 并且新构造的节点一定是栈顶的左孩子. 重复该过程直到元素值匹配为止:preorder[i] = inorder[index]
- 当先序和中序的值匹配时, 则将节点出栈, 直到不再匹配为止.
- TODO: 该解法还没彻底搞清, 暂时搁置
1 | /** |
116. Populating Next Right Pointers in Each Node
令每个节点中的 next
指针指向它的右兄弟, 如果没有右兄弟, 那么就置为 nullptr
, 注意, 题目给定的树是满二叉树
Description
Given a binary tree
struct TreeLinkNode {
TreeLinkNode left;
TreeLinkNode right;
TreeLinkNode * next;
}
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:
Given the following perfect binary tree,
1
/ \
2 3
/ \ / \
4 5 6 7
After calling your function, the tree should look like:
1 -> NULL
/ \
2 -> 3 -> NULL
/ \ / \
4->5->6->7 -> NULL
解法一: 层次遍历
时间复杂度: $O(n)$
空间复杂度: $O(n)$
显而易见可以用层次遍历, 只需额外设置一个节点指针来维护当前节点的前一个节点(左兄弟节点).
但是, 题目中要求只能使用常数空间, 因此该解法不是最优解.
1 | /** |
解法二: 利用 next
指针的特性
时间复杂度: $O(n)$, 每个节点都要访问一次(仅访问一次)
空间复杂度: $O(1)$
由于是满二叉树, 因此我们可以轻易的利用next
指针自身的特性来实现层次遍历.
1 | class Solution { |
127. Word Ladder
实际上是图的BFS(广度优先搜索)
Description
Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence from beginWord to endWord, such that:
Only one letter can be changed at a time.
Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
Note:
Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.
You may assume no duplicates in the word list.
You may assume beginWord and endWord are non-empty and are not the same.
Example 1:1
2
3
4
5
6
7
8
9Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.
Example 2:1
2
3
4
5
6
7
8Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
Output: 0
Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.
解法一: BFS
时间复杂度: $O(nl)$, 其中, $l$ 为单词的长度, $n$ 是单词的数量, 因为广度优先遍历会对每个节点遍历一次, 而每个节点计算邻居时, 需要对 $l$ 个字母进行替换(替换26种, 常数级别), 另外, unordered_set 的 find 复杂度也为常数.
空间复杂度: $O(n)$ 需要额外借助队列进行广度优先遍历, 另外还使用了 unordered_set
来存储单词表
我们可以将此题看做是图的广度优先搜索, 首先, 以 beginWord 为图的起始节点, 然后, 那些所有与 beginWord 只有一个字母不相同的单词都可以看做是 beginWord 的邻居节点, 依次类推, 直到找到一个单词, 与 endWord 相同为止, 此时, 返回当前 endWord 与 beginWord 的距离. (距离的记录方式和二叉树层次遍历时的方式差不多, 都是利用当前队列中的元素大小来控制深度
的).
需要注意的地方有以下几点:
- 这里的图和树不太一样, 这里图没有链表指针来指示, 因此, 在每次将某一个单词入队列以后, 都需要在单词列表中删除掉这个单词(或者额外设置标记也行), 以防止重复搜索
- 题目给的是没有重复单词的单词表, 因此推荐使用 set 结构来进行删除 (erase) 操作, vector 结构的删除 (erase) 操作的时间复杂度较高.
1 | class Solution { |
130. Surrounded Regions
类似于围棋, 将被包裹住(4连通)的字符 O
全部转换成字符 X
.
Descriptioin
Given a 2D board containing ‘X’ and ‘O’ (the letter O), capture all regions surrounded by ‘X’.
A region is captured by flipping all ‘O’s into ‘X’s in that surrounded region.
Example:
X X X X
X O O X
X X O X
X O X X
After running your function, the board should be:
X X X X
X X X X
X X X X
X O X X
Explanation:
Surrounded regions shouldn’t be on the border, which means that any ‘O’ on the border of the board are not flipped to ‘X’. Any ‘O’ that is not on the border and it is not connected to an ‘O’ on the border will be flipped to ‘X’. Two cells are connected if they are adjacent cells connected horizontally or vertically.
解法一: 递归
时间复杂度: $O(n)$, n 为 board
中的元素个数
空间复杂度: $O(n)$, 递归深度优先遍历的递归次数最坏情况下为 n 次.
根据题目的要求, 我们可以从 board
的四个边界开始, 每遇到一次 O
就执行深度优先遍历, 将其相邻的所有 O
都变成另一个字符(如 #
). 然后, 在顺序遍历整个 board
, 将 board
中所有的 O
变成 X
, 将所有的 #
变成 O
, 即得解.
1 | class Solution { |
解法二: 迭代
时间复杂度: $O(n)$, n 为 board
中的元素个数
空间复杂度: $O(n)$, 额外申请队列的大小为 n
思想和解法一相同, 不过采用 BFS 迭代实现, 利用一个队列来实现
1 | class Solution { |
131. Palindrome Partitioning
划分回文子串
Description
解法一: 回溯+验证回文子串
时间复杂度: $O(n\times 2^n)$, 其中, 可能的 partition 情况最多有 $2^n$ 种, 而对于每一种都要进行复杂度为 $O(n)$ 的回文子串检查
空间复杂度: $O(n\times 2^n)$ ? 数组 res
的大小最坏情况下可达 $(n\times 2^n)$.
1 | class Solution { |
解法二: 回溯+DP
时间复杂度: $O(2^n)$, 利用 DP 建立一个 $n\times n$ 的 bool 数组, 其中 dp[i][j]
代表字符串从第 i 个字符开始, 到第 j 个字符组成的子串是否为回文串. 因此, 检查回文串时无需执行 $O(n)$ 的检查.
空间复杂度: $O(n\times 2^n + n^2)$, 需要额外的数组空间来实现 DP.
1 | class Solution { |
134. Gas Station
加油站问题, 根据油量和消耗量判断是否能走完一圈
Description
There are N gas stations along a circular route, where the amount of gas at station i is gas[i].
You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.
Return the starting gas station’s index if you can travel around the circuit once in the clockwise direction, otherwise return -1.
Note:
If there exists a solution, it is guaranteed to be unique.
Both input arrays are non-empty and have the same length.
Each element in the input arrays is a non-negative integer.
Example 1:
Input:
gas = [1,2,3,4,5]
cost = [3,4,5,1,2]
Output: 3
Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.
Example 2:
Input:
gas = [2,3,4]
cost = [3,4,3]
Output: -1
Explanation:
You can’t start at station 0 or 1, as there is not enough gas to travel to the next station.
Let’s start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 0. Your tank = 4 - 3 + 2 = 3
Travel to station 1. Your tank = 3 - 3 + 3 = 3
You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.
Therefore, you can’t travel around the circuit once no matter where you start.
解法: 最优
时间复杂度: $O(n)$
空间复杂度: $O(1)$
首先要知道, 如果总油量大于总消耗量, 那么就一定存在一个起始点, 使得可以走完全程. 因此, 设置两个变量 total_left
和 cur_left
, 前者存储从0点开始的总的剩余量, 后者存储从起点 start
开始的剩余量. 当 cur_left<=0
时, 说明从 start
开始一直到当前位置之间的任何一个加油站都不能够成为起点, 因此将 start
置为下一个位置, 重新开始, 并令 cur_left=0
. 在遍历完所有加油站以后, 如果总的剩余量不小于0, 则此时 start
所指的位置就一定是解.(由题意知, 该解是唯一解).
1 | class Solution { |
138. Copy List with Random Pointer
复杂链表的复制, 复制带有随机指针的链表
Description
A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
Return a deep copy of the list.
解法一: 复制+拆分
时间复杂度: $O(n)$, 遍历三次链表
空间复杂度: $O(1)$, 不包括复制链表占用的空间
先将每个节点复制到对应节点的后面, 然后给随机指针进行赋值
1 | /* |
解法二: 一次遍历
时间复杂度: $O(n)$, 一次遍历
空间复杂度: $O(n)$, 需要申请链表长度的哈希表
利用一个哈希表来存储已经访问过的节点, 哈希表的键值为: {cur_node, copy_node}
, 其中, cur_node
代表旧链表中的节点, copy_node
代表新链表中的节点. 顺序遍历旧链表, 对于旧链表中的每一个节点, 查看其 next
节点是否存在于哈希表 visit
中, 如果存在, 则将 copy_node
的 next
指针指向该节点(键)对应的复制节点(值). 对于 random
指针也是同理
1 | class Solution { |
解法三: 递归
时间复杂度: $O(n)$
空间复杂度: $O(n)$, 除了哈希表所占空间外, 递归还需额外空间, 但是可以近似看做是 $O(n)$
1 | class Solution { |
139. Word Break
判断字符串是否可以划分成字典里面的单词
Description
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
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 = “leetcode”, wordDict = [“leet”, “code”]
Output: true
Explanation: Return true because “leetcode” can be segmented as “leet code”.
Example 2:
Input: s = “applepenapple”, wordDict = [“apple”, “pen”]
Output: true
Explanation: Return true because “applepenapple” can be segmented as “apple pen apple”.
Note that you are allowed to reuse a dictionary word.
Example 3:
Input: s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]
Output: false
解法一: 回溯
时间复杂度: 超时
空间复杂度: $O(1)$
1 | class Solution { |
解法二: DP
时间复杂度: $O(n^2)$, $n$ 为字符串的长度
空间复杂度: $O(n)$, dp 数组额外空间, unordered_set 额外空间
1 | class Solution { |
解法三: DP
时间复杂度: $O(nm)$, $n$ 为字符串的长度, $m$ 为字典的 size
空间复杂度: $O(n)$, dp 数组额外空间
1 | class Solution { |
更简洁的写法:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
vector<bool> dp(s.size(), false);
for (int i = 0; i < s.size(); i++) {
for (auto const& word : wordDict) {
int lenW = word.size();
if (!dp[i] and i+1 >= lenW and word == s.substr(i-lenW+1, lenW)) {
dp[i] = (i-lenW+1 == 0) ? true : dp[i-lenW];
}
}
}
return dp[s.size() - 1];
}
};
142. Linked List Cycle II
Description: 求链表中环的开始节点
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Note: Do not modify the linked list.
Follow up:
Can you solve it without using extra space?
解法一: Floyd 的乌龟和兔子(Floyd 判环算法)
时间复杂度: $O(n)$
空间复杂度: $O(1)$
此题更多解析可以看剑指offer第55题
1 | /** |
144. Binary Tree Preorder Traversal
Description: 先根遍历
Given a binary tree, return the preorder traversal of its nodes’ values.
Example:1
2
3
4
5
6Input: [1,null,2,3]
1
\
2
/
3
Output: [1,2,3]
Follow up: Recursive solution is trivial, could you do it iteratively?
解法一: 递归
1 | class Solution { |
解法二: 迭代
1 | class Solution { |
148. Sort List
对链表进行排序, 要求时间复杂度为 $O(nlogn)$, 空间复杂度为常数
Description
Sort a linked list in O(n log n) time using constant space complexity.
Example 1:1
2Input: 4->2->1->3
Output: 1->2->3->4
Example 2:1
2Input: -1->5->3->4->0
Output: -1->0->3->4->5
解法一: 递归 自顶向下
时间复杂度: $O(nlogn)$
空间复杂度: $O(logn)$
首先对于链表的排序最先想到的就是归并排序, 因为题目的要求是空间复杂度为常数, 因为不能使用递归实现(递归会占用额外空间), 但是, 递归是一种很好理解的排序方法, 因此, 这里我们先给链表归并排序的递归实现.
1 | /** |
解法二: 迭代 自底向上
时间复杂度: $O(nlogn)$
空间复杂度: $O(1)$
先两两合并, 再四四合并, 逐渐向上, 直到完全合并. 注意这里之所以可以在 $O(1)$ 的空间复杂度内进行归并排序, 是因为采用了链表的底层结构, 使得 merge 操作可以在 $O(1)$ 的空间复杂度下进行. 但是对于一般的归并排序, 采用的是数组结构, 数组结构在进行 merge 时, 要么在 $O(n)$ 的空间复杂度下执行, 要么每次插入都需要移动其他元素, 增加时间复杂度.
接下来, 我们考虑如何实现归并排序的迭代算法, 代码如下:
1 | class Solution { |
150. Evaluate Reverse Polish Notation
计算逆波兰表达式
Description
Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +, -, *, /. Each operand may be an integer or another expression.
Note:
Division between two integers should truncate toward zero.
The given RPN expression is always valid. That means the expression would always evaluate to a result and there won’t be any divide by zero operation.
Example 1:
Input: [“2”, “1”, “+”, “3”, ““]
Output: 9
Explanation: ((2 + 1) 3) = 9
Example 2:
Input: [“4”, “13”, “5”, “/“, “+”]
Output: 6
Explanation: (4 + (13 / 5)) = 6
Example 3:
Input: [“10”, “6”, “9”, “3”, “+”, “-11”, ““, “/“, ““, “17”, “+”, “5”, “+”]
Output: 22
Explanation:
((10 (6 / ((9 + 3) -11))) + 17) + 5
= ((10 (6 / (12 -11))) + 17) + 5
= ((10 (6 / -132)) + 17) + 5
= ((10 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
解法一: 栈
时间复杂度: $O(n)$, 一次遍历
空间复杂度: $O(n)$, 需要一个额外的栈来存储中间结果
用栈来实现, 从到开始扫描字符串vector, 如果当前字符串不为运算符, 则直接入栈, 如果为运算符 , 则取栈顶两个元素进行运算然后将计算结果入栈. 最终, 栈中只剩一个结果值
需要注意的是: 首先要确保输入的逆波兰表达式是没有问题的, 其次还有要进行零除判断, 这几点本题没有考查, 但仍需注意
1 | class Solution { |
解法二: 栈+异常
解法与上面相同, 不同借助了异常, 显得更加简洁
1 | class Solution { |
解法三: 栈+lambda
思路与解法一一直, 另一种写法: 借助哈希表和lambda表达式, 使程序更加整洁
1 | class Solution { |
解法四: 栈+lambda+异常
1 | class Solution { |
152. Maximum Product Subarray
求连续子序列的最大乘积
Description
Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.
Example 1:
Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
Example 2:
Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
解法一: 递归
时间复杂度: $O(n)$, 遍历一次
空间复杂度: $O(n)$, 递归 $n$ 次
这道题和连续子序列的最大和比较相似, 但是更难一些, 我们需要考虑负负得正这种情况, 因此, 我们不仅仅要维护最大值, 还要维护最小值. 考虑利用递归的方法来实现, 假设我们现在已经知道了以第 i-1
个数为结尾的连续子序列的最大乘积值max
和最小乘积值min
, 那么如果数组中新来一个数 nums[i]
, 则以第 i
个数为结尾的连续子序列的最大乘积就一定是max * nums[i]
, min*nums[i]
, nums[i]
之中的最大者, 最小值为这三者的最小者. 由于我们还不知道最终的连续子序列是以第几个字符为结尾的, 因此我们利用一个变量res
来维护当前找到的最大的子序列乘积, 并且随着循环的进行不断更新这个值, 最终, res
的值就是我们要求的解, 代码如下:
1 | class Solution { |
解法二 迭代实现
时间复杂度: $O(n)$
空间复杂度: $O(1)$
思路和解法一相同, 只不过换成了迭代实现1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class Solution {
public:
int maxProduct(vector<int>& nums) {
if (nums.empty()) return 0;
int max_neg = nums[0];
int max_pos = nums[0];
int res = nums[0];
for (int i = 1; i < nums.size(); i++) {
int num = nums[i];
int a = num * max_neg;
int b = num * max_pos;
max_neg = std::min(num, std::min(a, b));
max_pos = std::max(num, std::max(a, b));
if (max_pos > res) res = max_pos;
}
return res;
}
};
解法三: DP 迭代
时间复杂度: $O(n)$
空间复杂度: $O(n)$, 该解法需要额外数组, 实际上这是不必要的, 详细可看解法二
上面的递归写法, 可以转换成DP迭代, 为此需要两个dp数组, 一个用来保存以第i个元素为结尾的连续子序列的最大值, 另一个保存最小值. 代码如下:
写法一: new数组1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22class Solution {
public:
int maxProduct(vector<int>& nums) {
if(nums.size() == 0 ) return 0;
int res=nums[0];
int *dp_max = new int[nums.size()]();
int *dp_min = new int[nums.size()]();
dp_max[0] = nums[0];
dp_min[0] = nums[0];
for(int i = 1; i<nums.size(); i++){
int a = dp_max[i-1]*nums[i];
int b = dp_min[i-1]*nums[i];
int c = nums[i];
dp_max[i] = max(a, max(b,c));
dp_min[i] = min(a, min(b,c));
res = max(res, dp_max[i]);
}
delete[] dp_max;
delete[] dp_min;
return res;
}
};
写法二: vector数组:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20CCclass Solution {
public:
int maxProduct(vector<int>& nums) {
if(nums.size() == 0 ) return 0;
int res=nums[0];
vector<int> dp_max(nums.size(), 0);
vector<int> dp_min(nums.size(), 0);
dp_max[0] = nums[0];
dp_min[0] = nums[0];
for(int i = 1; i<nums.size(); i++){
int a = dp_max[i-1]*nums[i];
int b = dp_min[i-1]*nums[i];
int c = nums[i];
dp_max[i] = max(a, max(b,c));
dp_min[i] = min(a, min(b,c));
res = max(res, dp_max[i]);
}
return res;
}
};
162. Find Peak Element
Description: 局部最大值
A peak element is an element that is greater than its neighbors.
Given an input array nums, where nums[i] ≠ nums[i+1], find a peak element and return its index.
The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.
You may imagine that nums[-1] = nums[n] = -∞.
Example 1:
Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.
Example 2:
Input: nums = [1,2,1,3,5,6,4]
Output: 1 or 5
Explanation: Your function can return either index number 1 where the peak element is 2,
or index number 5 where the peak element is 6.
解法一: $O(n)$ 复杂度
$O(n)$ 的时间复杂度, 不合符题目要求, 仅仅记录一下.
1 | class Solution { |
解法二: $O(logn)$ 复杂度
二分查找, 分为以下几种情况:
- If num[i-1] < num[i] > num[i+1], then num[i] is peak
- If num[i-1] < num[i] < num[i+1], then num[i+1…n-1] must contains a peak
- If num[i-1] > num[i] > num[i+1], then num[0…i-1] must contains a peak
- If num[i-1] > num[i] < num[i+1], then both sides have peak
1 | class Solution { |
1 | class Solution { |
递归实现:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class Solution {
public:
int helper(vector<int>& nums, int low, int high) {
if (low == high) {
return low;
}
int mid = (low + high) / 2;
if (nums[mid] > nums[mid+1]){
return helper(nums, low, mid);
} else {
return helper(nums, mid+1, high);
}
}
int findPeakElement(vector<int>& nums) {
return helper(nums, 0, nums.size()-1);
}
};
166. Fraction to Recurring Decimal
Description: 无限循环小数
Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.
If the fractional part is repeating, enclose the repeating part in parentheses.
Example 1:
Input: numerator = 1, denominator = 2
Output: “0.5”
Example 2:
Input: numerator = 2, denominator = 1
Output: “2”
Example 3:
Input: numerator = 2, denominator = 3
Output: “0.(6)”
解法一: 用余数作为哈希表的key
时间复杂度: $O(logn)$, 每次都会乘以10再取余数
空间复杂度: $O(logn)$, 余数的哈希表
首先, 获取最终浮点数的符号和整数部分, 此处由于可能出现分子为-2147483648
, 而分母为-1
的情况, 为此, 建议使用long
长整型来避免溢出.
在计算小数部分时, 将余数作为key
, 小数当前位置作为value
存入哈希表中, 然后将余数乘以10, 再计算当前小数位的值, 并将取余得到新的余数.
题目指明浮点数是无限循环小数, 则如果小数部分没有循环, 那么一定会出现余数为0的情况, 此时, 返回当前的res
即可. 如果小数存在循环, 那么循环一定出现在余数相同的时刻, 此时, 将添加后扩号, 并根据哈希表中的value
添加前括号.
1 | class Solution { |
179. Largest Number
Description: 排列数字使其字符串形式的数字为最大
Given a list of non negative integers, arrange them such that they form the largest number.
Example 1:
Input: [10,2]
Output: “210”
Example 2:
Input: [3,30,34,5,9]
Output: “9534330”
解法一: 构造比较函数, 快排排序
时间复杂度: $O(nlogn)$, 快排时间复杂度
空间复杂度: $O(logn)$, 快排空间复杂度, 如果使用其他排序算法, 可将空间复杂度降为 $O(1)$
我们可以构造一个新的比较函数来决定两个元素的先后关系, 对于任意两个元素 a
和 b
, 首先将其转换成字符串形式 s_a
和 s_b
, 我们知道, 若整形 a>b, 则一定有 s_a
> s_b
, 因此我们可以比较 s_a+s_b
和 s_b+s_a
的大小关系, 根据题目要求, 我们要进行递减排序. 得到比较函数以后, 利用快排排序即可.
1 | class Solution { |
解法二: 利用 STL sort() 函数
时间复杂度: $O(nlogn)$, 快排时间复杂度
空间复杂度: $O(logn)$, 快排空间复杂度, 如果使用其他排序算法, 可将空间复杂度降为 $O(1)$
思路与解法一一致, 只不过省略了排序算法的实现, 使用了 STL 的 sort
函数.
需要注意, 在 C++ STL 的 sort 函数中, bool 返回真的时候, 必须是绝对大于或者绝对小于, 对于等于的情况, 只能返回 false(因为当返回 true 时, 元素会继续下一个, 这样对于极端情况, 如所有元素都一样时, 会出现越界, 从而导致段错误)
1 | bool str_geq(int a, int b){ |
200. Number of Islands
Description: 区块的个数
Given a 2d grid map of ‘1’s (land) and ‘0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
Input:
11110
11010
11000
00000
Output: 1
Example 2:
Input:
11000
11000
00100
00011
Output: 3
解法一: DFS 遍历
时间复杂度: $O(n)$, 至多遍历两次 grid
空间复杂度: $O(1)$
遍历 grid 中的每一个元素, 如果为1, 则将与之相连的所有的1都置为0, 并且区块个数加1, 这样, 最坏的情况就是 grid 中的所有数字均为1, 此时, 需要遍历两边数组.
1 | class Solution { |
207. Course Schedule
Description: 课程表 / 判断有向图是否存在环
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?
Example 1:
Input: 2, [[1,0]]
Output: true
Explanation:
There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.
Example 2:
Input: 2, [[1,0],[0,1]]
Output: false
Explanation:
There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.
解法一: BFS / 拓扑排序
时间复杂度: $O(V+E)$, 统计入度时需要 $O(V)$, 处理队列需要 $O(E)$, 其中 $V$ 为节点个数, $E$ 为边的个数
空间复杂度: $O(V+E)$, 入度数组和队列分别需要 $(V)$, 邻接表需要 $O(V+E)$.
首先将图的边表示结构转换成邻接表形式(用vector
来实现邻接表, 使其支持随机访问). 然后再申请一个 $O(V)$ 大小的数组来存储每个节点的入度. 在拓扑排序时, 先将所有入度为0的节点添加都一个队列当中, 然后从队列顶端拿出一个节点, 将该节点的所有直接后序节点的入度都减1, 然后再将所有入度为0的节点入队列. 如此迭代下去, 直至所有队列为空. 此时, 如果还有某个节点的入度不为0, 则说明存在环, 应该返回 false, 否则, 返回 true.
1 | class Solution { |
解法二: DFS
时间复杂度: $O(V+E)$, 复杂度和 BFS 算法近似, 其中 $V$ 为节点个数, $E$ 为边的个数
空间复杂度: $O(V+E)$, visit
数组和递归栈分别需要 $(V)$, 邻接表需要 $O(V+E)$.
首先, 和 BFS 一样, 建立关于图的邻接表结构, 然后, 申请 $O(V)$ 大小的访问数组visit
, 初始值全部为0, 表示所有节点均为访问. 然后, 根据 DFS 算法的执行过程. 将当前正在访问的节点置为-1
, 将已经访问过且确认无环的节点置为1
. 则则DFS过程中, 如果访问到了一个已经被置为-1
的节点, 则说明该节点是当前循环内的正在访问的节点, 因此, 构成了一个环, 返回 false
. 如果遇到了一个被置为1
的节点, 因为已经确认该节点无环, 因此可以直接返回 true
.
1 | class Solution { |
208. Implement Trie (Prefix Tree)
Description: 实现字典树(前缀树)
Implement a trie with insert, search, and startsWith methods.
Example:1
2
3
4
5
6
7
8Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // returns true
trie.search("app"); // returns false
trie.startsWith("app"); // returns true
trie.insert("app");
trie.search("app"); // returns true
解法一
https://www.cnblogs.com/grandyang/p/4491665.html
时间复杂度: $O(k)$, 插入, 查找, 找前缀均只需要 $O(k)$复杂度, $k$ 为字符串长度
空间复杂度: 与字符串的公共部分的多少有关, 公共部分越多, 越节省空间, 反之, 空间复杂度较高. 最差情况下为 $O(wk)$, 其中, $w$ 为单词的个数, $k$ 为单词的最长长度.
字母字典树是一个26叉树, 树的根节点没有字符, 其他节点有且仅有一个字符, 我们模仿二叉树的定义, 构建一个26叉树的数据结构, 用子节点的编号代表字母(即0号节点代表字母a, 1号代表b,…,25号代表z), 另外需要定义一个布尔值来标识当前节点是否构成一个单词. 插入时, 根据字符串遍历树, 如果当前字符不存在, 则新建一个. 查找和找前缀时, 如果不存在则直接返回false
.
1 | class TrieNode{ |
210. Course Schedule II
Description: 判断有向图是否有环, 若无环, 则返回拓扑序列
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, return the ordering of courses you should take to finish all courses.
There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.
Example 1:
Input: 2, [[1,0]]
Output: [0,1]
Explanation:
There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1] .
Example 2:
Input: 4, [[1,0],[2,0],[3,1],[3,2]]
Output: [0,1,2,3] or [0,2,1,3]
Explanation:
There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3] .
解法一: BFS, 拓扑排序
时间复杂度: $O(V+E)$, 统计入度时需要 $O(V)$, 处理队列需要 $O(E)$, 其中 $V$ 为节点个数, $E$ 为边的个数
空间复杂度: $O(V+E)$, 入度数组和队列分别需要 $(V)$, 邻接表需要 $O(V+E)$, 相比于第207题, 多了一个拓扑序列的数组, 大小为 $O(V)$.
和第207题差不多, 不过在判断是否有环的同时, 还要记录正确的拓扑序列并返回.
1 | class Solution { |
解法二: DFS
时间复杂度: $O(V+E)$, 复杂度和 BFS 算法近似, 其中 $V$ 为节点个数, $E$ 为边的个数
空间复杂度: $O(V+E)$, visit
数组和递归栈分别需要 $(V)$, 邻接表需要 $O(V+E)$, 拓扑序列需要 $O(V)$.
1 | class Solution { |
215. Kth Largest Element in an Array
Description: 找出无序数组中第k大的数
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.
Example 1:
Input: [3,2,1,5,6,4] and k = 2
Output: 5
Example 2:
Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4
解法一: 小顶堆
时间复杂度: $O(nlogk)$, 堆的插入复杂度为 $O(logk)$, 最多需要进行 $n$ 次插入.
空间复杂度: $O(k)$, 堆的大小
构建一个大小为 $k$ 的小顶堆, 对于任意一个新来的元素, 如果该元素大于堆顶, 将则堆顶退出, 并将该元素插入. 最终, 堆内的元素就是数组的最大的前 $k$ 个元素, 而堆顶刚好为第 $k$ 大的元素.
1 | class Solution { |
解法二: 部分排序(nth_element)
http://www.voidcn.com/article/p-qyrpnkse-gx.html
最优解法
时间复杂度: 平均为 $O(n)$. nth_element 的时间复杂度为 $T(n) = T(n/2) + O(n) = O(n) + O(n/2) + O(n/4) + …$, 也就是 $O(n)$.
空间复杂度: $O(1)$, 不占用额外空间
直接调用 STL 的部分排序算法nth_element
.nth_element
算法将重新排列区间[first, last)的序列元素, 算法执行完毕后, 会使得
- 第 $k$ 个位置的元素在最终的算法执行完毕后, 和整个区间完全排序后该位置的元素相同.
- 这个新的
nth
元素之前的所有元素均 <= (>=)nth
元素之后的所有元素.
但是该算法并不保证位于第 $k$ 个元素两边区间的元素有序. 该算法和partial_sort
算法之间一个很大的区别在于:nth_element
对于除第 $k$ 位置的元素之外的区间元素的顺序不做保证, 而partial_sort
排序后会使得前 $m$ 个数的子区间是有序的. 正因为如此, 在需要无序的前top_k
个值时,nth_element
相对于partial_sort
要更快.(只需要找第 $k$ 个值, 其前面的元素即为 top_k, 时间复杂度为 $O(n)$). 如果需要有序, 也可以先使用nth_element
, 再对前 k 个数组排序, 总的复杂度为 $O(n+klogk)$
1 | class Solution { |
解法三: 基于 Partition
时间复杂度: $O(n)$
空间复杂度: $O(1)$
该解法和解法二思路相同, 只不过是我们自己手动实现 Partition 的算法逻辑, 而不是调用 STL 函数.
1 | class Solution { |
227. Basic Calculator II
Description: 基本计算器(二)
Implement a basic calculator to evaluate a simple expression string.
The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.
Example 1:
Input: “3+2*2”
Output: 7
Example 2:
Input: “ 3/2 “
Output: 1
Example 3:
Input: “ 3+5 / 2 “
Output: 5
解法一: 栈
时间复杂度: $O(n)$, 遍历字符串一遍, 遍历栈一遍
空间复杂度: $O(n)$, 栈的大小
因为本题没有带括号, 因此优先级关系比较明朗, 可以简单的用栈来实现. 对于任意一个符号, 如果是加号或者减号, 就直接将其后面的数字入栈, 其中减号的情况需要给入栈数字加负号. 如果是乘号或除号, 将先从栈顶取出一个数字, 然后将该数字与符号后的数字进行计算, 并将计算结果入栈. 如此遍历, 直到遍历完所有字符, 最终将栈中的所有数字相加.
此题需要注意两个地方, 一是对于第一个数字, 需要在特别的将该数字前的符号对应成加号. 二是需要处理字符串中出现的空格.
1 | class Solution { |
解法二: 字符串流
时间复杂度: $O(n)$, 遍历每个字符
空间复杂度: $O(1)$, 无需额外空间
字符串流可以自动的格式化读取字符串信息, 简化了代码编写量
1 | class Solution { |
230. Kth Smallest Element in a BST
Description: 找出二叉搜索树中的最小元素
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
2
3
4
5
6
7Input: root = [3,1,4,null,2], k = 1
3
/ \
1 4
\
2
Output: 1
Example 2:1
2
3
4
5
6
7
8
9Input: root = [5,3,6,2,4,null,null,1], k = 3
5
/ \
3 6
/ \
2 4
/
1
Output: 3
Follow up:
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?
解法一: 非递归中根遍历
时间复杂度: $O(k)$, 遍历到第 $k$ 个元素为止
空间复杂度: $O(k)$, 栈中最多存储 $k$ 个元素.
非递归中根遍历二叉搜索树, 当遍历到第k个元素时, 将其返回.
1 | /** |
解法二: 递归中根遍历
时间复杂度: $O(k)$
空间复杂度: $O(k)$
1 | class Solution { |
更简洁的写法:
1 | class Solution { |
解法三: 二叉搜索
时间复杂度: $O(logn)+ O(n)$, 搜索的复杂度为树的高度, 但是计算count的复杂度为 $O(n)$.
空间复杂度: $O(logn)$, 递归占用的空间, 若采用非递归实现, 则空间复杂度为 $O(1)$.
二叉搜索, 统计当前节点之前的元素个数, 如果大于 $k$, 则继续在左子树中搜索第 $k$ 小的元素, 如果 count 小于 $k$ , 则在右子树中搜索第 $k-count-1$ 小的元素.
1 | class Solution { |
解答Follow up
方法一:
根据解法三我们可以知道, 在计算子树节点个数的时候 int count = countNode(root->left);
, 有很多的重复计算, 因此, 我们可以修改树的结构定义, 使得每个节点都持有其左子树中的节点个数, 那么在查找第 $k$ 小的元素的时候, 就可以用 $O(1)$ 的时间复杂度获取到左子树的节点个数, 因此, 最终查询第 $k$ 小的时间复杂度变为 $O(logn)$.
方法二:
在中根遍历的同时, 用一个大小为 $k$ 的大顶堆(priority_queue
), 这些可以将二叉搜索树中最小的 $k$ 个数存储起来, 并且可以用 $O(1)$ 的时间复杂度获取到第 $k$ 小的元素. (二叉搜索树的中根遍历下, 未遍历到的都是较大的元素, 因此无需遍历整个树, 只需要遍历到第 $k$ 个元素即可). 在对树进行修改时, 同步更新大顶堆, 前者时间复杂度为 $O(logn)$, 后者为 $O(logk)$.
236. Lowest Common Ancestor of a Binary Tree
Description: 查找二叉树中任意两个节点的公共祖先
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
Given the following binary tree: root = [3,5,1,6,2,0,8,null,null,7,4]1
2
3
4
5
6
7 _______3______
/ \
__5__ __1__
/ \ / \
6 2 0 8
/ \
7 4
Example 1:1
2
3Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.
Example 2:1
2
3Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.
Note:
- All of the nodes values will be unique.
- p and q are different and both values will exist in the binary tree.
解法一: 递归
时间复杂度: $O(n)$, 需遍历 $n$ 个节点.(任何情况下都需遍历n个节点)
空间复杂度: $O(n)$, 需进行 $n$ 次递归调用.( $n$ 包含空节点)
对于最小公共祖先来说, 它相对于其他祖先有一个特点, 即节点 p
和 q
只可能是以下面三种情况分布在树中:
p
和q
分别处于当前节点的左子树 和 右子树之中.p
为当前节点,q
处于当前节点的左子树 或 右子树之中q
为当前节点,p
处于当前节点的左子树 或 右子树之中
而对于其他祖先来说, 绝对不可能出现上面三种情况, 因为 p
和q
一定处于其他祖先的同一侧子树之中., 即要么都处在右子树中, 要么都处在左子树中. 因此我们可以用p
和q
在当前节点构成的子树中的分布情况来判断是否为最小祖先.
**注意, 题目中说了p, q
一定存在, 并且树中节点都是唯一的, 因此, 下面的代码无需对p, q
进行存在性检查.
1 | /** |
上面用了是将res
作为成员函数进行赋值, 更好的做法是用指针引用.1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
TreeNode* res = nullptr;
lcaHelper(root, p, q, res);
return res;
}
bool lcaHelper(TreeNode* root, TreeNode* p, TreeNode* q, TreeNode*& res) {
if (root == nullptr) return false;
int left= lcaHelper(root->left, p, q, res) ? 1 : 0;
int right = lcaHelper(root->right, p, q, res) ? 1 : 0;
int mid = (root == p || root == q) ? 1 : 0;
if (left+right+mid >= 2) res = root;
return (left+right+mid) > 0;
}
};
解法二: 迭代(存储父节点)
时间复杂度: $O(n)$, 最坏需遍历 $n$ 个节点.
空间复杂度: $O(n+n+n) = O(n)$, 栈, 哈希表, 集合的空间复杂度在最坏情况下均为 $O(n)$
如果我们能够获取到父节点, 那么我们就可以反向遍历q
和p
来访问他们的祖先节点. 那么, 第一个公共的祖先节点就一定是 LCA node. 我们可以将节点的父节点指针保存在一个字典(hash)当中. 具体的算法流程如下所示:
- 从根节点开始遍历整个树(任意一种遍历算法都可以, 只要能找到
p
和q
即可); - 直到找到节点
p
和q
之前, 将所有节点的父节点都保存在字典(hash)中; - 一旦我们找到了
q
和q
, 我们就将所有p
的祖先节点放入了一个集合(set)当中; - 然后, 我们反向遍历
q
的祖先节点, 当找到一个存在时集合中的祖先节点时, 该节点就是第一个公共的租店节点, 也就是 LCA node, 将其返回.
1 | class Solution { |
解法三: 迭代(不存储父节点)
时间复杂度: $O(n)$, 最坏需遍历 $n$ 个节点.
空间复杂度: $O(n)$, 采用后序遍历, 只需维护一个栈, 空间复杂度在最坏情况下为 $O(n)$
在解法二中, 我们是通过反向遍历的方法来查找 LCA 的, 实际上我们可以省去这一步, 直接要一个指针时刻指向可能的 LCA, 当我们找到p
和q
两个节点时, 我们可以直接返回当前的 LCA. 具体算法步骤如下:
- 从根节点开始;
- 将
(root, root_state)
压入栈中,root_state
定义了根节点的剩余的子节点是否可以被遍历; - 当栈非空时, 查看栈顶元素
(parent_node, parent_state)
; - 在遍历
parent_node
的任何子节点之前, 首先确认parent_node
是否是节点p
或q
; - 当首次找到
p
或q
时, 将标志变量one_node_found
设置为True
. 同时根据栈中的节点跟踪 LCA (栈中的所有元素都是当前节点的祖先); - 当再次找到
p
或q
时, 说明我们已经将两个节点都找到了, 此时返回 LCA node. - 无论何时访问
parent_node
的子节点, 都需要将(parent_node, updated_parent_state)
更新到栈中. - A node finally gets popped off from the stack when the state becomes BOTH_DONE implying both left and right subtrees have been pushed onto the stack and processed. If one_node_found is True then we need to check if the top node being popped could be one of the ancestors of the found node. In that case we need to reduce LCA_index by one. Since one of the ancestors was popped off
Whenever both p and q are found, LCA_index would be pointing to an index in the stack which would contain all the common ancestors between p and q. And the LCA_index element has the lowest ancestor common between p and q.
1 | class Solution { |
238. Product of Array Except Self
Description: 计算数组内其他元素之积(不能使用除法)
Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].
Example:1
2Input: [1,2,3,4]
Output: [24,12,8,6]
Note: Please solve it without division and in O(n).
Follow up:
Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)
解法一: 借助辅助数组
时间复杂度: $O(n)$, 遍历两次数组
空间复杂度: $O(n)$, 额外申请 $n$ size 的数组(不计算 res 的空间占用)
1 | class Solution { |
解法二: 用一个变量代替数组
时间复杂度: $O(n)$, 两次遍历
空间复杂度: $O(1)$, 用变量代替数组
对解法一进行改写, 具体的做法是用一个变量来维护 from_begin 数组中的值(当然也可以选择代替 from_end)
1 | class Solution { |
解法三: 用两个变量代替数组
时间复杂度: $O(n)$, 一次遍历
空间复杂度: $O(1)$, 不计算结果数组的空间
观察到解法二的做法, 虽然将空间复杂度压缩到 $O(1)$, 但是仍然使用了两次for
循环, 实际上, 我们可以同时用变量from_begin
和变量from_end
替换掉对应的数组, 并且同一个for
循环中更新这两个变量, 如下所示.1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int n = nums.size();
int from_begin = 1;
int from_end = 1;
vector<int> res(n,1);
for(int i=0; i<n; i++){ // 同时从前后分别计算, from_begin记录i之前的元素之和, from_end记录i之后的元素之和
res[i] = from_begin * res[i];
from_begin = from_begin * nums[i];
res[n-i-1] = from_end * res[n-i-1];
from_end = from_end * nums[n-i-1];
}
return res;
}
};
240. Search a 2D Matrix II
Description: 矩阵搜索
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
2
3
4
5
6
7
8
9Consider the following matrix:
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
Given target = 5, return true.
Given target = 20, return false.
解法一: 从左下角开始
时间复杂度: $O(n+m)$, 最多走 $n+m$ 步, $n$ 和 $m$ 分别为矩阵的宽和高
空间复杂度: $O(1)$
1 | class Solution { |
279. Perfect Squares
Description: 找到最少的平方和个数
Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n.
Example 1:1
2
3Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.
Example 2:1
2
3Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.
解法一: 四平方和定理(最优)
时间复杂度: $O(\sqrt n)$, 最坏情况为 $O(\sqrt n)$, 最好情况为 $O(1)$.
空间复杂度: $O(1)$, 无需额外空间
四平方和定理: 任何一个正整数, 都可以表示成四个整数的平方和(如果不算 0 的话, 就是可以用小于等于 4 个整数的平方和来表示任意一个整数).
对于题目, 要求我们返回组合平方和的数字的 最少 个数(不算0), 因此, 这里还可以使用到两个特别的性质来加速计算:
- 如果 $n$ 可以被 4 整除, 那么 $n$ 和 $n/4$ 的最少平方和数字个数相同.
- 如果 $n \% 8=7$, 那么 $n$ 的最少平方和个数一定为 4.
因此, 本题的解法流程如下:
- 循环整除 4, 降低 $n$ 的大小;
- 判断是否有 $n \% 8 =7$, 如果有, 则直接返回 4;
- 查看 $n$ 是否能够拆分成两个数(其中一个可以为0), 如果可以, 则返回
!!i + !!j
, 即返回正整数的个数. 此处需要注意,i
需要从 0 开始遍历, 因为对于 $3^2+4^2 = 0^2 + 5^2 = 25$ 来说, 我们希望返回的是后者(即返回最少的平方和个数); - 如果上面都不行, 则只可能反正 3(因为 $n>0$).
1 | class Solution { |
解法二: DP
时间复杂度: $O(n\sqrt n)$, 外层循环约为 $n$ 次, 内层循环约为 $\sqrt n$ 次.
空间复杂度: $O(n)$, 需要额外申请 $n+1$ 大小的 DP 数组.
对于解法一来说, 虽然它的时间和空间复杂度最优, 但是其中使用到了很多不常用的定理和性质, 如果不知道这些定理和性质, 很难想到解法一的实现. 因此, 我们更容易想到的是使用动态规划来解决这道题, 具体解题步骤如下:
- 申请 $n+1$ 大小的 DP 数组, 并令
dp[0]=0
, 令其他元素为INT_MAX
,dp[i]
的值代表组成数字 $i$ 所需的最少的平方和数字个数; - 由于我们已经求得
dp[0]
的值, 因此, 对于j=1, 2, ...
来说, 我们可以顺势求得dp[0+j*j] = dp[0]+1=1
. - 对于已经求得的
dp[i]
, 我们可以求得dp[i+j*j] = min(dp[i+j*j], dp[i]+1)
, 这里的min
是为了保证组成数字的平方和个数最少. - 最终, 返回
dp.back()
即为组成 $n$ 的最少的平方和个数.
1 | class Solution { |
解法三: DP
时间复杂度: $O(n\sqrt n)$, 外层循环约为 $n$ 次, 内层循环约为 $\sqrt n$ 次.
空间复杂度: $O(n)$, 需要额外申请 $n+1$ 大小的 DP 数组.
复杂度和解法二没有区别, 但是我们可以从另一个角度来实现 DP 算法, 具体流程如下:
- 申请只含有一个元素的 DP 数组
dp[0]=0
; - 根据
dp[0]
的值计算dp[1]
.(计算方法和解法二类似, 具体请看代码) - 根据
dp[0]~dp[i-1]
的值计算dp[i]
. - 当
i==n
时, 返回dp[i]
.
1 | class Solution { |
解法四: 递归
http://www.cnblogs.com/grandyang/p/4800552.html
1 | // Recrusion |
287. Find the Duplicate Number
Description: 寻找重复元素
Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.
Example 1:1
2Input: [1,3,4,2,2]
Output: 2
Example 2:1
2Input: [3,1,3,4,2]
Output: 3
Note:
- You must not modify the array (assume the array is read only).
- You must use only constant, O(1) extra space.
- Your runtime complexity should be less than O(n2).
- There is only one duplicate number in the array, but it could be repeated more than once.
解法一: 哈希表
时间复杂度: $O(n)$, 一次遍历
空间复杂度: $O(n)$, 哈希表额外空间
这道题用哈希表很容易解, 但是这是最简单的解法之一(更简单的还有暴力法), 因此这里贴出来只用做参考.
1 | class Solution { |
另一种解法是不建立哈希表, 而是利用数组的元素值和元素下标建立对应关系, 即将所有的数字放置在数字对应的下标位置上, 这样, 最终重复的元素就会出现的下标为 0 的位置上, 当然, 期间如果已经发现重复, 则可以直接返回, 代码如下:
1 | class Solution { |
解法二: 排序
时间复杂度: $O(nlogn)$
空间复杂度: $O(1)$ 或者 $O(n)$
先对数组排序, 然后遍历查找重复元素, 但是这种解法会改变原有数组中的元素分布, 题目要是数组是只读的, 因此该解法也只作为参考贴出
1 | class Solution { |
解法三: Floyd 的乌龟和兔子(Floy 判圈算法)
Floyd’s Tortoise and Hare, 该算法是用来判断链表中是否含有环的. 对于此题, 我们换一个角度来解读, 数组中总共有 $n+1$ 个数, 这些数都是 $[1,n]$ 中的正整数, 因此, 至少会存在一个重复的数, 根据题目的假设, 有且仅有一个重复的数字, 那么, 我们假设该数字为 $k$, 于是, 我们可以将该数组表示成下面的形式(表中的 $x$ 代表该元素的值不为 $k$ ):
下标 | $0$ | $1$ | $2$ | … | $k$ | … | $n$ |
---|---|---|---|---|---|---|---|
元素 | $x$ | $k$ | … | $k$ | $x$ | … | $x$ |
如果我们将上面的 (下标, 元素)
看做是链表结构中的 (val, next)
, 那么可以看出, 当某一个节点(上面假设为节点 1)的 next
指向 k
以后, k
又会重新指向另一个元素, 但是, 经过一定步数以后, 一定 又会重新指向 k
(因为元素存在重复), 这在链表中称之为 “环”, 因此, 这道题就变成了求链表中环的开始节点, 该题正好是剑指offer第55题和 LeetCode第142题
这道题有一个很关键的条件就是, 元素的值是在1~n之间, 因此, 下标 0 位置上的元素值一定不为 0, 只有这样, 我们才可以将下标 0 选做起点, 如果选取其他的下标坐标起点, 那么有可能在第一步就死循环了.
1 | class Solution { |
更简洁的写法:
上面在求环的开始节点时, 是先求环长, 再让 fast
走环长距离, 然后 slow
和 fast
同步前进, 最终相遇点即为开始点, 这么写比较容易理解, 但难免有些繁琐. 实际上, 我们只需要令 slow
从头开始, 即 slow=0
, 接着令 fast
和 slow
同步前进, 那么相遇点就是开始节点. 原因是因为, 二者是从同一点出发的, fast 的步长较快, 当二者相遇时, 他们一定是在环中的某一点相遇, 这个时候再把slow重新放回起点, 那么fast领先slow的距离就等于: 环外的距离 + 若干圈 + 当前圈内已经走的距离. 而此时 fast 距离环入口还有一段距离, 因为第一次相遇点的位置, 因此, 我们如果此时从起点出发, 最终正好可以弥补这一部分距离, 因此, 最终会在环入口相遇.
一句话总结: 令fast和slow一起开始, fast步长是slow步长的二者, 找到二者相遇的点, 然后令slow重新回到起点, 此时步长一致, 再次相遇时即为环的入口点
1 | class Solution { |
289. Game of Life
Description: 游戏人生
According to the Wikipedia’s article: “The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970.”
Given a board with m by n cells, each cell has an initial state live (1) or dead (0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):
- Any live cell with fewer than two live neighbors dies, as if caused by under-population.
- Any live cell with two or three live neighbors lives on to the next generation.
- Any live cell with more than three live neighbors dies, as if by over-population..
- Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.
Write a function to compute the next state (after one update) of the board given its current state. The next state is created by applying the above rules simultaneously to every cell in the current state, where births and deaths occur simultaneously.
Example:1
2
3
4
5
6
7
8
9
10
11
12
13
14Input:
[
[0,1,0],
[0,0,1],
[1,1,1],
[0,0,0]
]
Output:
[
[0,0,0],
[1,0,1],
[0,1,1],
[0,1,0]
]
Follow up:
- Could you solve it in-place? Remember that the board needs to be updated at the same time: You cannot update some cells first and then use their updated values to update other cells.
- In this question, we represent the board using a 2D array. In principle, the board is infinite, which would cause problems when the active area encroaches the border of the array. How would you address these problems?
解法一: 状态机
时间复杂度: $O(mn)$, 遍历两次二维数组
空间复杂度: $O(1)$, 无需额外空间
根据细胞的更新规则, 我们可以设计出下面的状态转移:
0: 从 0 到 0;
1: 从 1 到 1:
2: 从 1 到 0;
3: 从 0 到 1;
因此, 本解法需要遍历两边 board
矩阵, 第一遍先计算每个 cell 的状态, 第二遍根据状态赋予 cell 不同的值, 具体来说就是如果当前状态 board[i][j]%2==0
, 那么就令 board[i][j]=0
, 反之, 令 board[i][j]=1
.
1 | class Solution { |
Follow up
- 常数空间复杂度: 正如解法一
- 无边界限制: 修改边界空间条件, 使其变成 “循环” 二维矩阵.
300. Longest Increasing Subsequence
Description: 求最长递增序列(可以不连续)的长度
Given an unsorted array of integers, find the length of longest increasing subsequence.
Example:1
2
3Input: [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
Note:
- There may be more than one LIS combination, it is only necessary for you to return the length.
- Your algorithm should run in O(n2) complexity.
Follow up:
Could you improve it to O(n log n) time complexity?
解法一: 暴力
时间复杂度: $O(2^n)$
空间复杂度: $O(n^2)$
对于任意一个数字, 只有两种情况, 即处于最长递增数组内, 或者不处于最长递增数组内, 需要同时将这两种情况考虑, 然后选择最长的情况. 该方法时间超限.
解法二: Recursion with memorization [Memory Limit Exceeded]
解法三: DP
分析题目可以得出, 第 $i$ 个下标对应的数字是否存在于递增序列中, 与该下标之后的元素是无关的, 因此, 很自然的想到利用 DP 的方法来解决这道题. 我们令 dp[i]
代表 包含第 $i$ 个下标对应元素的递增序列的长度. 在求取 dp[i+1]
时, 我们需要遍历前面 dp[0~i]
个数组元素才能决定 dp[i+1]
的值, 因此, 时间复杂度为 $O(n^2)$, 空间复杂度为 $O(n)$. (比递归方法好很多).
1 | class Solution { |
解法四: DP+二分搜索(最优)
时间复杂度: $O(nlogn)$, 每次搜索的复杂度为 $O(logn)$, 总共需要搜索 $n$ 次
空间复杂度: $O(m)$, $m$ 为最长递增序列的长度.
同样还是 DP 解法, 但是我们重新赋予 dp[]
数组另一个含义, 我们令 dp[]
数组内储存的元素的数量刚好等于当前最长递增序列的数量, 注意, dp[]
数组内的值不一定是递增序列的值. 核心算过过程如下所示:
- 初始时, 令
dp[]
数组为空, 即dp=[]
; - 对于每一个元素
num
, 我们查找num
在dp
数组中的upper_bound
迭代器(首个大于num
的元素的迭代器), 假设取名为upper
;(注意,dp
数组是有序的, 所以这里的查询复杂度为 $O(logn)$) - 查看
upper-1
指向的元素是否和num
相等, 如果相等, 则说明该元素已经存在, 那么就跳过该元素, 重新回到步骤2; - 如果
num
大于dp
数组内的所有元素, 则将num
添加进dp
数组; 否则, 就将dp
数组中大于num
的第一个元素的值赋为num
. - 重复步骤2,3,4, 直到遍历完数组为止.
为了更好的解释这种解法, 我们通过举例进行说明, 假定输入的数字序列为: [4,10,3,4,10,3,2]
, 那么我们的 dp[]
数组的变化情况如下:
dp=[]
,初始时, 数组为空;dp=[4]
, 遍历元素4, 加入到数组中;dp=[4,10]
, 遍历元素10, 10大于所有元素, 将其添加到数组中;dp=[3,10]
, 遍历元素3, 发现第一个大于3的值为4, 将其赋值为3;dp=[3,4]
, 遍历元素4, 发现第一个大于4的的值为10, 将其赋值为4;dp=[3,4,10]
, 遍历元素10, 10大于所有元素, 将其添加到数组中;dp=[3,4,10]
, 遍历元素3, 3在数组中已经存在, 跳过该元素;dp=[2,4,10]
, 遍历元素2, 发现第一个大于2个值为3, 将其赋值为2.
综上, 我们可以看到, dp
数组的长度始终等于当前数组的最长子序列的长度, 故而, 直接返回 dp.size()
即为最终的结果. 注意, dp
内的值不一定为递增子序列的值.
1 | class Solution { |
322. Coin Change
Description: 硬币凑面额
You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
Example 1:1
2
3Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
Example 2:1
2Input: coins = [2], amount = 3
Output: -1
解法一: DP
时间复杂度: $O(nm)$, $n$ 为总面额的大小, $m$ 为硬币的数量.
空间复杂度: $O(n)$, DP 数组的大小为总面额的大小.
当我们求组成面额 $i$ 时所需的最少硬币数时, 我们可以用面额 $j$ 和面额 $i-j$ ($j\in[0,i]$)所需的硬币数之和来代替, 因此, 也就是说只与 $i$ 之前的面额数有关, 所以我们可以考虑使用 DP 算法来求解. 我们令 dp[i]
代表组成面额 $i$ 时所需的最少的硬币数, 要求 dp[i]
, 我们可以根据硬币的面额来求解, 假设硬币的面额是 $j$, 那么就有 dp[i] = min(dp[j] + dp[i-j])
, 其中 dp[j]=1
, 因为组成这种面额只需要一个硬币就可以了, 我们根据此公式就可以写出相应的 DP 代码, 如下所示.
1 | class Solution { |
你可能会觉得我们进行了一些无用计算, 例如如果 $i$ 为 11, 而 coins
为 [1,5], 那么我们是否只需要计算 dp[6] 就可以了呢? 实际上, 如果有面额为 1 的硬币存在, 那么我们就必须计算所有的小于 $i$ 的dp值, 因为这些都是解, 至于是否为最小数量, 则需要利用 min 来不断筛选.
解法二: DP 递归实现
时间复杂度: $O(nm)$, $n$ 为总面额的大小, $m$ 为硬币的数量.
空间复杂度: $O(n+n)=O(n)$, DP 数组的大小为总面额的大小, 另外, 递归还需额外占用一定空间.
1 | class Solution { |
解法三: 对暴力解法剪枝
时间复杂度: $O(logn+mlogm)$, 每次都用当前面额除以硬币面额, 故时间复杂度为 $O(logn)$, $O(mlogm)$ 为对硬币面额的排序复杂度, 当 $m<<n$ 时, 可忽略不计.
空间复杂度: $O(logn)$, 无需申请额外空间, 仅仅是递归过程需要占用空间.
下面的方法利用余数对暴力解法进行剪枝, 剪枝后的程序运行速度十分快, 远远快于前两个算法.
1 | class Solution { |
关于此算法的更详细解释(http://www.cnblogs.com/grandyang/p/5138186.html):
难道这题一定要DP来做吗, 我们来看网友hello_world00提供的一种解法, 这其实是对暴力搜索的解法做了很好的优化, 不仅不会TLE, 而且击败率相当的高!对比Brute Force的方法, 这里在递归函数中做了很好的优化. 首先是判断start是否小于0, 因为我们需要从coin中取硬币, 不能越界. 下面就是优化的核心了, 看target是否能整除coins[start], 这是相当叼的一步, 比如假如我们的目标值是15, 如果我们当前取出了大小为5的硬币, 我们做除法, 可以立马知道只用大小为5的硬币就可以组成目标值target, 那么我们用cur + target/coins[start] 来更新结果res. 之后的for循环也相当叼, 不像暴力搜索中的那样从start位置开始往前遍历coins中的硬币, 而是遍历 target/coins[start] 的次数, 由于不能整除, 我们只需要对余数调用递归函数, 而且我们要把次数每次减1, 并且再次求余数. 举个例子, 比如coins=[1,2,3], amount=11, 那么 11除以3, 得3余2, 那么我们的i从3开始遍历, 这里有一步非常有用的剪枝操作, 没有这一步, 还是会TLE, 而加上了这一步, 直接击败百分之九十九以上, 可以说是天壤之别. 那就是判断若 cur + i >= res - 1 成立, 直接break, 不调用递归. 这里解释一下, cur + i 自不必说, 是当前硬币个数cur 加上新加的i个硬币, 我们都是知道cur+i如果大于等于res的话, 那么res是不会被更新的, 那么为啥这里是大于等于res-1呢?因为能运行到这一步, 说明之前是无法整除的, 那么余数一定存在, 所以再次调用递归函数的target不为0, 那么如果整除的话, cur至少会加上1, 所以又跟res相等了, 还是不会使得res变得更小.
324. Wiggle Sort II
Description: “驼峰” 排序
Given an unsorted array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]….
Example 1:1
2Input: nums = [1, 5, 1, 1, 6, 4]
Output: One possible answer is [1, 4, 1, 5, 1, 6].
Example 2:1
2Input: nums = [1, 3, 2, 2, 3, 1]
Output: One possible answer is [2, 3, 1, 3, 1, 2].
Note:
You may assume all input has valid answer.
Follow Up:
Can you do it in O(n) time and/or in-place with O(1) extra space?
解法一: 排序
时间复杂度: $O(nlogn + n)$, 排序的时间复杂度为 $O(nlogn)$, 构造 “驼峰” 数组的复杂度为 $O(n)$
空间复杂度: $O(n)$, 额外数组需要占用 $O(n)$ 空间
该问题的解法可能有多个, 我们只需要找到其中一个即可, 核心思路是将一个数组分成两半, 其中前一半的元素都小于后一半的元素, 然后我们只需要依次从两个数组中取值组成新数组, 就可以满足 “驼峰” 排序.
首先, 对数组中的元素排序, 这样, 任意的相邻元素, 都满足 nums[i] <= nums[i+1]
, 我们将数组分成两半, 这样, 前半段的元素都小于等于后半段的元素, 注意, 题目中已经指明数组是合法的有效数组, 所以一定可以组成驼峰, 因此, 我们先取前半段的最后一个元素, 再取后半段的最后一个元素, 这两个元素一定满足绝对小于关系(否则无法形成 “驼峰”), 然后我们再取倒数第二个, 依次类推, 直至取完. 注意, 我们不能从前往后取, 因为不能保证前半段的第二个元素绝对小于后半段的第一个元素, 例如[4,5,5,6], 从前往后取就会变成[4,5,5,6], 不符合驼峰, 从后往前取为[5,6,4,5], 符合驼峰.
1 | class Solution { |
解法二: partition
时间复杂度: $O(n+n)= O(n)$, 查找中位数需要 $O(n)$, 填充数组需要 $O(n)$.
空间复杂度: $O(n)$, 填充时使用了额外的数组空间来辅助.
如果当数组中的元素不含有重复时, 此题很容易就用基于 partition 的方法解决, 因为, 我们可以找到将数组分成两个具有绝对小于关系的数组, 然后依次用两个数组填充即可, 但是, 此题的元素是可重复的, 所以必须考虑重复元素的影响.
首先我们利用 nth_element()
找到中位数, 虽然 nth_element()
的时间复杂度已经不是 $O(n)$, 但是这里我们为了简化代码, 仍然使用 nth_element()
来查找中位数 mid
(后面也会更多稍复杂一点的 partition 算法, 面试时建议使用 nth_element
, 注意要向面试官说明复杂度问题), 之后, 对于其他的任意一个数组元素, 都有三种不同的情况:
- 大于
mid
, 将大于mid
的元素放在数组开始的奇数位上面; - 小于
mid
, 将小于mid
的元素放在数组的偶数位上面; - 等于
mid
, 用所有等于mid
的元素填充剩下的位置.
由于题目指明输入的数组一定是有效的, 因此当我们进行了上面遍历后, 数组一定会变成 “驼峰” 数组, 因为当和 mid
相等的元素处于 “驼峰” 底部时, 它一定位于偶数位(奇数位都是大于 mid
的元素), 同理, 当 mid
处于 “驼峰” 顶部时, 它一定位于奇数位, 因为偶数位都被小于 mid
的元素填充. 故最终的数组是 “驼峰” 数组.
nth_element()(该函数在 C++17 后不是 $O(n)$, 而是 $O(nlogn)$, 但是在 C++11 中仍然是 $O(n)$):1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22class Solution {
public:
void wiggleSort(vector<int>& nums) {
int n = nums.size();
std::nth_element(nums.begin(), nums.begin()+n/2, nums.end());
int mid = nums[n/2]; // 找到中位数
vector<int> res(n, mid); // 先将所有元素置为中位数
int even_i = (n-1)/2*2; // 令 even_i 指向数组的最后一个偶数位
int odd_i = 1;
for(int i=0; i<n; i++){
if(nums[i] > mid){ // 将大于中位数的放到前面的奇数位上
res[odd_i] = nums[i];
odd_i += 2;
}else if(nums[i] < mid){ //将小于中位数的放到后面的偶数位上
res[even_i] = nums[i];
even_i -= 2;
}
} // 剩下的位置都是中位数
nums = res;
}
};
自己利用partition实现 $O(n)$ 的中位数查找:
1 | class Solution { |
Follow up: three-way partition
时间复杂度: $O(n+n) = O(n)$, 找中位数时的复杂度为 $O(n)$, 调整数组的复杂度为 $O(n)$.
空间复杂度: $O(1)$, 无需占用额外空间
解法二的时间复杂度满足要求, 问题在于我们如何能够在 $O(1)$ 的空间复杂度限制下, 完成数组的填充工作, 很自然的我们可以想到利用 swap
来实现, 具体流程如下所示:
- 先令
even_i
指向数组的最后一个偶数位(从0位开始, 0算作偶数位), 令odd_i
指向第一个奇数位(下标为1). 我们从最后一个偶数位元素(用下标i
指示)开始进行判断; - 如果
nums[i]<mid
, 则将nums[i]
与nums[even_i]
交换, 交换后,even_i
不可再被访问, 令even_i -= 2
, 同时注意, 由于刚开始的时候i
与even_i
是相等的, 故也要令i -= 2
, 当i<0
以后, 要令i
指向最后一个奇数位. - 如果
nums[i]>mid
, 则将nums[i]
与nums[odd_i]
交换, 同时令odd_i += 2
, 注意, 此时,i
指向的数字是交换后的原来odd_i
指向的数字, 因此, 我们需要对该数字进行判断, 故不能改变i
的值. - 如果和
mid
相等, 则无需进行交换填充, 令其保存原值即可, 判断下一个元素, 令i -=2
, 同时还要判断i
是否小于 0, 若小于, 则需令i
指向最后的奇数位.
nth_element():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
28class Solution {
public:
void wiggleSort(vector<int>& nums) {
int n = nums.size();
std::nth_element(nums.begin(), nums.begin()+n/2, nums.end());
int mid = nums[n/2]; // 找到中位数
// O(1) 空间复杂度填充数组
int even_i = (n-1)/2*2;
int odd_i = 1;
int i = even_i; // 令i指向最后一个偶数位
int count = n;
while(count--){ //每次都会判断一个元素
if(nums[i] < mid){
std::swap(nums[i], nums[even_i]);
even_i -= 2;
i -= 2;
if(i<0) i = n/2*2 - 1; // 令 i 指向最后一个奇数位
}else if(nums[i] > mid){
std::swap(nums[i], nums[odd_i]);
odd_i += 2; // 奇数位增加
}else{ // 保持原值不变, 判断下一个值
i -= 2;
if(i<0) i = n/2*2 - 1; // 令 i 指向最后一个奇数位
}
}
}
};
partition:
1 | class Solution { |
328. Odd Even Linked List
Description: 奇偶链表
Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.
You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.
Example 1:1
2Input: 1->2->3->4->5->NULL
Output: 1->3->5->2->4->NULL
Example 2:1
2Input: 2->1->3->5->6->4->7->NULL
Output: 2->3->6->7->1->5->4->NULL
Note:
The relative order inside both the even and odd groups should remain as it was in the input.
The first node is considered odd, the second node even and so on …
解法一: 一次遍历
时间复杂度: $O(n)$, 遍历每个节点一次
空间复杂度: $O(1)$, 未使用任何额外空间
我们利用两个变量分别来维护奇数链表和偶数链表, 最后令奇数链表的最后一个节点的 next
指针指向偶数链表的头结点, 代码如下:
1 | /** |
更简洁的写法:1
2
3
4
5
6
7
8
9
10
11
12
13
14public class Solution {
public ListNode oddEvenList(ListNode head) {
if (head == null) return null;
ListNode odd = head, even = head.next, evenHead = even;
while (even != null && even.next != null) {
odd.next = even.next;
odd = odd.next;
even.next = odd.next;
even = even.next;
}
odd.next = evenHead;
return head;
}
}
334. Increasing Triplet Subsequence
Description: 递增的三元子序列
Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.
Formally the function should:
Return true if there exists i, j, k
such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false.
Note: Your algorithm should run in O(n) time complexity and O(1) space complexity.
Example 1:1
2Input: [1,2,3,4,5]
Output: true
Example 2:1
2Input: [5,4,3,2,1]
Output: false
解法一: 用辅助变量指向 min 和 mid
时间复杂度: $O(n)$, 每个元素之遍历一次
空间复杂度: $O(1)$, 无需额外空间
我们利用两个变量 min
和 mid
分别指向三元子序列中的最小元素和中间元素, 最开始时, 二者赋初值为 INT_MAX
, 然后遍历数组, 对于数组中的每一个数 num
, 进行如下判断:
- 是否小于等于
min
, 若满足, 则令min=num
; - 若不满足(1), 则说明
num > min
, 判断num
是否小于等于mid
, 若满足, 责令mid=num
;(此时mid
一定大于min
, 且下标也大于min
下标) - 若不满足(1)(2), 则说明
num
不仅大于min
, 而且大于mid
, 同时num
的下标也大于前两者, 由此, 我们找到了一个满足条件的递增三元组子序列, 可直接返回true
. 否则, 重复以上步骤直至遍历完数组 - 如果遍历完整个数组后, 仍然找不到符合条件的序列, 则说明不存在这样的序列, 返回 false.
1 | class Solution { |
341. Flatten Nested List Iterator
Description: 将嵌套的多维列表展开成一维
Given a nested list of integers, implement an iterator to flatten it.
Each element is either an integer, or a list — whose elements may also be integers or other lists.
Example 1:1
2
3Input: [[1,1],2,[1,1]]
Output: [1,1,2,1,1]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].
Example 2:1
2
3Input: [1,[4,[6]]]
Output: [1,4,6]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].
解法一: 栈
PS: 这道题可以在初始化时将列表全部展开并存储, 这样 hasNext()
就可以达到 $O(1)$ 的时间复杂度, 但是, 这是很不好的! 因为实际实现迭代器时, 我们往往只在需要的时候才会对元素进行展开, 这样可以获得最大的平均效率
时间复杂度: $O(n)$, 每个节点至多遍历一次, 其中, next()
复杂度为 $O(1)$, 初始化和 hasNext()
的复杂度均为 $O(n)$
空间复杂度: $O(n)$, 栈所需空间
先将数组中的所有元素从后往前的放进栈中, 这样栈顶元素即为数组中的第一个元素, 然后对栈顶元素进行判断, 如果 isInteger()
为真, 则直接返回 true
, 否则, 就获取栈顶对应的 vector<NestedInteger>
数组, 并将栈顶 pop()
, 然后将数组从后往前再放到栈中, 重复以上操作直至栈为空, 代码如下:
1 | /** |
解法二: deque
时间复杂度: $O(n)$, 每个节点至多遍历一次, 其中, next()
复杂度为 $O(1)$, 初始化和 hasNext()
的复杂度均为 $O(n)$
空间复杂度: $O(n)$, 双端队列所需空间
同样的思路, 也可以用双端队列解决.(栈有的功能双端队列也有)
347. Top K Frequent Elements
Description: 寻找频率最高的 k 个数字
Given a non-empty array of integers, return the k most frequent elements.
Example 1:1
2Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
Example 2:1
2Input: nums = [1], k = 1
Output: [1]
Note:
You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.
解法一: 哈希+大顶堆
时间复杂度: $O(n+nlogn)=O(nlogn)$, 遍历复杂度为 $O(n)$, 堆排序复杂度为 $O(nlogn)$
空间复杂度: $O(n+n) = O(n)$, unordered_map
和 priority_queue
各占 $O(n)$ 大小的空间
1 | class Solution { |
解法二: 哈希+小顶堆
时间复杂度: $O(n+nlogk)=O(nlogk)$, 遍历复杂度为 $O(n)$, 堆排序时, 用小顶堆, 只保存最大的 k 个元素即可.
空间复杂度: $O(n+n) = O(n)$, unordered_map
和 priority_queue
各占 $O(n)$ 大小的空间
整体思路和解法一相同, 只不过我们需要得到最大的 $k$ 个元素即可, 因此无需维护 $n$ 大小的大顶堆. 相反, 我们选择维护 $k$ 大小的小顶堆, 对于任意一个新来的元素, 如果它大于堆顶, 则将堆顶退出, 然后将新来元素加入堆中. 因为小顶堆的堆顶是最小的元素, 因此堆中用于 $k-1$ 个比堆顶大的元素, 故这 $k$ 个元素就是最大的 $k$ 个元素, 最终我们只需要将堆中数据依次取出, 然后执行一次 reverse()
即可.
1 | class Solution { |
解法三: 哈希+桶
时间复杂度: $O(n+n+k)=O(n)$, 构建哈希表, 构建桶, 从桶找到 $k$ 个最大数字的复杂度分别为: $O(n)$, $O(n)$, 和 $O(k)$.
空间复杂度: $O(n+n) = O(n)$, 哈希表和桶各占 $O(n)$
当我们拥有关于元素频率的哈希表以后, 我们可以利用此表构建桶结构, 桶的 “关键字” 为元素频率, 之后, 我们可以用 $O(n)$ 的复杂度对桶进行遍历, 当找到 $k$ 个最大元素时, 跳出遍历循环, 代码如下:
1 | class Solution { |
378. Kth Smallest Element in a Sorted Matrix
Description: 找到半有序数组中的第 k 小的元素
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
2
3
4
5
6
7
8matrix = [
[ 1, 5, 9],
[10, 11, 13],
[12, 13, 15]
],
k = 8,
return 13.
Note:
You may assume k is always valid, 1 ≤ k ≤ n2.
解法一: 堆
基于堆的 baseline 解法:
最简单的堆解法就是不使用矩阵的有序性质, 直接当成无序数组来做, 我们申请一个 $k$ 大小的大顶堆, 然后遍历矩阵中的所有元素, 如果某元素小于堆顶就将堆顶弹出, 并压入该元素, 最终, 大顶堆的堆顶就是整个矩阵中第 $k$ 小的元素. 该解法的时间复杂度为 $O(nmlogk)$, 空间复杂度为 $O(k)$, 由于没有使用到有序矩阵的性质, 故不做讨论.
更优的基于堆的解法(超屌的解法!):
时间复杂度: $O(klogn)$, $k$ 代表 kth, $n$ 代表矩阵的行数
空间复杂度: $O(n)$, 堆的大小, $n$ 代表矩阵的行数
我们需要利用矩阵行列分别有序的性质, 首先, 具体思路如下:
- 利用将矩阵中每一行的首元素(也就是第一列元素, 同理, 这里也可以用第一行元素)构造一个最小堆(这一步的复杂度小于 $O(nlogn)$), 堆中的元素是一个
pair
, 其中first
为元素的值,second
又是一个pair
, 存储着值的行列坐标(i, j)
- 将最小堆中的一个元素弹出(弹出的是当前堆最小的元素), 然后再将弹出元素的同一行的下一个元素(通过元素坐标获取)压入堆, 压入后, 堆会自动排序, 使得最小的元素位于堆顶.
- 重复步骤(2) k-1 次以后. 我们已经弹出了整个矩阵的最小的 k-1 个元素, 那么现在堆顶中的元素就是第 k 小的元素, 将其返回即可
1 | class Solution { |
解法二: 二分查找
时间复杂度: $O(nlogm\times logD$, $n$ 为矩阵的行数, $m$ 为矩阵的列数, $D$ 为矩阵中最大元素与最小元素之间的差值.
空间复杂度: $O(1)$, 没有利用额外空间
算法利用了每一行中, 元素都是有序的这个性质(但是没有用到列有序的性质), 步骤如下:
- 获取矩阵中元素的最小值
low
和最大值high
- 令
mid = (high+low)/2
, 然后我们利用upper_bound()
函数来查找矩阵中第一个大于mid
的元素(耗时 $O(logn)$), 接着计算这个元素之前的元素数量. 对矩阵的每一行重复这个步骤, 并将所有的元素数量累加起来 - 如果累加元素数
count < k
, 说明,mid
的值较小, 我们令low=mid+1
, 否则, 说明count>=k
, 我们令high=mid
, 注意, 这里的赋值关系最好不要改动, 并且要知道为什么令high=mid
, 而不是mid-1
. - 重复上述过程直至
low=high
, 此时,low
或high
的值就是矩阵中第 k 小的值
1 | class Solution { |
解法三: 二分查找
时间复杂度: $O((n+m)logD)$, $n$ 为矩阵行数, $m$ 为矩阵列数, $D$ 为矩阵中元素的最大差值
空间复杂度: $O(1)$
解法二中并没有完全使用到矩阵所有的性质, 考虑到矩阵在列上也是有序的, 我们可以进一步优化算法. 我们应该还记得在剑指offer的第一题中, 考察了这种行列有序数组的元素查找算法, 我们可以在 $O(n+m)$ 的时间里找到指定的元素, 因此, 我们可以利用该算法替换解法二中对每一行执行二分查找的算法, 故而时间复杂度就变成了 $O((n+m)logD)$, 其中, $n$ 为矩阵行数, $m$ 为矩阵列数, $D$ 为矩阵中元素的最大差值, 代码如下.
1 | class Solution { |
380. Insert Delete GetRandom O(1)
Description: 常数时间复杂度的插入,删除,和随机获取
Design a data structure that supports all following operations in average O(1) time.
- insert(val): Inserts an item val to the set if not already present.
- remove(val): Removes an item val from the set if present.
- getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.
Example:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23// Init an empty set.
RandomizedSet randomSet = new RandomizedSet();
// Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomSet.insert(1);
// Returns false as 2 does not exist in the set.
randomSet.remove(2);
// Inserts 2 to the set, returns true. Set now contains [1,2].
randomSet.insert(2);
// getRandom should return either 1 or 2 randomly.
randomSet.getRandom();
// Removes 1 from the set, returns true. Set now contains [2].
randomSet.remove(1);
// 2 was already in the set, so return false.
randomSet.insert(2);
// Since 2 is the only number in the set, getRandom always return 2.
randomSet.getRandom();
解法一: 哈希表+数组
时间复杂度: $O(1)$, 符合题意
空间复杂度: $O(n)$, 数组和哈希表的大小各为 $O(n)$.
解题思路:
- 插入: 用数组的
push_back()
存储新来的元素, 同时存入哈希表,key
为元素值,val
为元素在数组中的下标; - 删除: 先用哈希表获取元素的下标, 然后将数组中的该元素和数组的最后一个元素交换, 接着用
pop_back()
删除该元素, 然后用erase()
从哈希表中删除该元素, 最后在哈希表中更新被交换元素的下标; - 获取随机元素: 利用 C++ 的内置随机函数
rand()
来获取随机数. 但是注意, rand() 对生成的随机数质量无法保证, 在 C++11 中, 已经建议使用随机数生成设施来替换 rand(). 另外注意: 如果想要使用srand()
来播种, 那么不能将该语句放在getRandom()
函数中, 因为重复播种会使得每次生成的随机数都一样, 正确的做法是将其放在构造函数中, 只进行一次播种.
1 | class RandomizedSet { |
384. Shuffle an Array
Description: 打乱数组
Shuffle a set of numbers without duplicates.
Example:1
2
3
4
5
6
7
8
9
10
11
12// Init an array with set 1, 2, and 3.
int[] nums = {1,2,3};
Solution solution = new Solution(nums);
// Shuffle the array [1,2,3] and return its result. Any permutation of [1,2,3] must equally likely to be returned.
solution.shuffle();
// Resets the array back to its original configuration [1,2,3].
solution.reset();
// Returns the random shuffling of array [1,2,3].
solution.shuffle();
解法一: 随机交换
时间复杂度: $O(n)$, 打乱需要 $O(n)$, reset
为 $O(1)$
空间复杂度: $O(n)$
- shuffle: 打乱时, 遍历数组的下标, 然后随机生成一个下标, 令二者指向的元素交换. 更多分析请看Knuth shuffle算法
- reset: 直接返回缓存的原始数组
1 | class Solution { |
395. Longest Substring with At Least K Repeating Characters
Description
Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.
Example 1:1
2
3
4
5
6
7Input:
s = "aaabb", k = 3
Output:
3
The longest substring is "aaa", as 'a' is repeated 3 times.
Example 2:1
2
3
4
5
6
7Input:
s = "ababbc", k = 2
Output:
5
The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.
解法一: 哈希表+位标志
时间复杂度: 平均情况下为 $O(n)$, 最坏情况(待查找子串不存在)下为 $O(n^2)$
空间复杂度: $O(26 + 1)$, 26 为哈希表的大小, 1 为 mask
的大小.
对于字母集, 可以利用哈希表来实现 $O(n)$ 复杂度的字符数量统计, 我们设置一个变量 mask
, 该变量每一个比特位上的值有两种含义: 当某比特位为 1 时, 代表该比特位对应的字母在当前字符子串中的数量小于 k, 反之, 则该比特位为 0. 那么, 只要当 mask=0
, 就说明此时的子串符合题目的要求, 我们计算当前子串的长度, 并更新最长长度值, 由于子串必须是连续的, 所以下一个子串的开始字符一定不会在当前子串的结束字符之前, 因为如果这样的话, 就一定会在当前子串的结束字符处终止, 故判断下一个子串时, 我们可以从当前子串结束字符的下一位开始判断. 代码如下:
1 | class Solution { |
解法二: 分而治之, 递归
时间复杂度: $O(n)$, 最坏情况下为 $O(n)$, 因为递归调用的深度最多为 26, 而每一层的复杂度约为 $O(n)$. (这种说法是网上的说法, 但是这里我个人觉得最坏情况是 $O(n^2), 只不过有的递归调用很快退出, 是的程序运行时间很短)
空间复杂度: $O(26+log_{26}n)$, 哈希表空间为, 递归占用空间为 $O(log_{26}n)$.
对于任意的字符串, 我们都执行下面的算法步骤:
- 根据当前的字符串, 构建相应的哈希表, 表内数据为没一个字符的出现次数, 所以哈希表的大小为 26(或 256);
- 如果哈希表内所有字符的出现次数都满足条件(出现 0 次出现 k 次以上), 那么当前字符串满足条件, 可直接输出长度
- 如果字符串中存在不满足条件的字符, 那么就以这些字符
1 | class Solution { |
解法三: 更简洁的递归
时间复杂度: $O(n)$, 最差情况下为 $O(kn)$, 详细见下面的分析
空间复杂度: $O(n)$, 哈希+递归
真正的 $O(n)$ 复杂度的实现: 和上面的思路一致, 也是利用不满足条件的字符作为分隔(因为只有符合条件的字符组成的字符串从 有可能 具有正确的长度), 但是不同于上面程序的是, 此次我们只对满足条件的子串进行递归, 故而那些重复的不满足条件的字符不会被重复用于递归(上面的代码就是重复调用了, 因为是在发现 <k 时就进行调用), 下面的代码更加精炼易懂, 我们首先会跳过所有不满足条件的字符, 然后从满足条件的字符开始, 找到连续的满足条件的子串的最后一个字符, 然后对这个子串进行递归调用, 也就是说, 我们最多会进行不超过 k 次递归调用, 因为最坏的情况是 26 个字符中, 只有一个字符不满足条件, 而这个字符最多将字符串分割成 k 段, 如果分割成 k+1 段, 那么就必须用 k 个字符, 此时与假设矛盾.
1 | class Solution { |
上面的边界控制比较麻烦, 下面我们用超尾的方式来进行边界控制, 会使程序更加简洁, 如下所示:
1 | class Solution { |
454. 4Sum II
Description: 4 数之和为零的可能组合数
Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is zero.
To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of -228 to 228 - 1 and the result is guaranteed to be at most 231 - 1.
Example:1
2
3
4
5
6
7
8
9
10
11
12
13Input:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]
Output:
2
Explanation:
The two tuples are:
1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0
解法一: 先求两两之和
时间复杂度: $O(n^2+n^2)=O(n^2)$, 前者为 A, B 两两和的复杂度, 后者为 C, D 两两和的复杂度.
空间复杂度: $O(n^2)$, 哈希表占用的空间
先求 A 与 B 的两两之和, 并将和作为键存于哈希表中, 哈希表中的值为和的出现次数, 然后再求 C, D 的两两之和, 同时查询哈希表中是否存在 C, D 和的负数, 若存在, 则说明可以组成零. 代码如下:
1 | class Solution { |