剑指Offer刷题
第一天
1. 找出数组中重复的数
给定一个长度为 n 的整数数组 nums，数组中所有的数字都在 0∼n−1 的范围内。
数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。
请找出数组中任意一个重复的数字。
注意：如果某些数字不在 0∼n−1 的范围内，或数组中不包含重复数字，则返回 -1；
样例：
给定 nums = [2, 3, 5, 4, 3, 2, 6, 7]。 返回 2 或 3。
思路
首先判断是否某些数字不在 0∼n−1 的范围内，或数组中不包含重复数字，然后返回-1。然后再判断数字是否重复，重复则返回该数，否则返回-1。
时间复杂度
$O(n)$
class Solution {
public:
int duplicateInArray(vector<int>& nums) {
int n = nums.size();
vector<int> cnt(nums.size());
for (int i = 0; i < nums.size(); i++){
if (nums[i] < 0 || nums[i] >= n) return -1;
}
for (int i = 0; i < nums.size(); i++){
cnt[nums[i]]++;
if (cnt[nums[i]] > 1) return nums[i];
}
return -1;
}
};2. 不修改数组找出重复的数字
给定一个长度为 n+1 的数组 nums，数组中所有的数均在 1∼n 的范围内，其中 n≥1。
请找出数组中任意一个重复的数，但不能修改输入的数组。
样例
给定 nums = [2, 3, 5, 4, 3, 2, 6, 7]。 返回 2 或 3。
思考题
如果只能使用 O(1)的额外空间，该怎么做呢？
思路
不修改原数组思路很简单，直接遍历一遍然后使用一个标记数组来记录每个数出现的次数，但是这样多使用了O(n)的空间，下面考虑使用O(1)的额外空间。
我们发现有n+1个数，但是这些数据在1-n的范围内，所以一定会有一个数重复。因此我们可以使用分治的思想，将数字的取值划分为两个子区间，统计两个子区间的数字的个数，当某个子区间的数字的个数超过了该区间的大小，那么我们要找的这个数字一定是属于这个区间了。当我们不断缩小区间，直到区间大小为1，这个数字我们就找到了。
时间复杂度
$O(lg n)$
class Solution {
public:
int duplicateInArray(vector<int>& nums) {
int l = 1, r = nums.size() - 1;
while (l < r){
int mid = l + r >> 1;
int cnt = 0;
for (auto x : nums) cnt += (x <= mid) && (x >= l);
if (cnt > mid - l + 1) r = mid;
else l = mid + 1;
}
return l;
}
};3. 二维数组中的查找
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
样例
输入数组： [ [1,2,8,9]， [2,4,9,12]， [4,7,10,13]， [6,8,11,15] ] 如果输入查找数值为7，则返回true， 如果输入查找数值为5，则返回false。
思路1
二分里面使用二分。因为它们是单调的，所以可以使用嵌套二分来查找。不过不知道为什么在AcWing上有一个数据会无法通过。
时间复杂度1
$O(log n \times log m)$
class Solution {
public:
bool searchArray(vector<vector<int>> array, int target) {
if (array.empty()) return false;
int l = 0, r = array[0].size() - 1, u = 0, d = array.size() - 1;
while (l < r){
int mid1 = l + r >> 1;
while (u < d){
int mid2 = u + d >> 1;
if (array[mid2][mid1] >= target) d = mid2;
else u = mid2 + 1;
}
if (array[u][mid1] >= target) r = mid1;
else l = mid1 + 1;
}
if (array[d][r] == target) return true;
return false;
}
};思路2
如下图所示，x左边的数都小于等于x，x下边的数都大于等于x。
我们可以利用这个性质，来解决这道题目。对于当前x，有如下性质：
- $x = target$，返回true
- $x \geq target$，往左移
- $x \leq target$，往下移
时间复杂度2
$O(n + m)$
class Solution {
public:
bool searchArray(vector<vector<int>> array, int target) {
if (array.empty()) return false;
int j = array[0].size() - 1, i = 0;
while (i < array.size() && j >= 0){
if (array[i][j] == target) return true;
if (array[i][j] > target) j --;
else i ++;
}
return false;
}
};4. 替换空格
请实现一个函数，把字符串中的每个空格替换成"%20"。
你可以假定输入字符串的长度最大是 1000。
注意输出字符串的长度可能大于 1000。
样例
输入："We are happy." 输出："We%20are%20happy."
思路1
遍历字符串，替代空格即可。
时间复杂度1
$O(n)$
class Solution {
public:
string replaceSpaces(string &str) {
string temp = "";
for (int i = 0; i < str.size(); i++){
if (str[i] == ' '){
temp += "%20";
} else {
temp.push_back(str[i]);
}
}
return temp;
}
};思路2
为了节省空间，我们可以先遍历一次字符串，将原字符串长度动态扩展，然后使用双指针算法来修改字符串。
时间复杂度2
$O(n)$
class Solution {
public:
string replaceSpaces(string &str) {
int j = str.length() - 1, i = str.length() - 1;
for (int i = 0; i < str.length(); i++){
if (str[i] == ' '){
j += 2;
}
}
str.resize(j + 1);
while (i >= 0){
if (str[i] == ' '){
str[j--] = '0';
str[j--] = '2';
str[j--] = '%';
} else {
str[j--] = str[i];
}
i--;
}
return str;
}
};5. 从尾到头打印链表
思路
从头到尾遍历链表，将其存储在数组中，然后将数组翻转即可。
时间复杂度
$O(n)$
class Solution {
public:
vector<int> printListReversingly(ListNode* head) {
vector<int> v;
while (head != NULL){
v.push_back(head->val);
head = head->next;
}
reverse(v.begin(), v.end());
return v;
}
};6. 重建二叉树
输入一棵二叉树前序遍历和中序遍历的结果，请重建该二叉树。
注意:
- 二叉树中每个节点的值都互不相同；
- 输入的前序遍历和中序遍历一定合法；
样例
给定： 前序遍历是：[3, 9, 20, 15, 7] 中序遍历是：[9, 3, 15, 20, 7] 返回：[3, 9, 20, null, null, 15, 7, null, null, null, null]
返回的二叉树如下所示： 3 / \ 9 20 / \ 15 7
思路
- 根据前序遍历我们可以得到根的值
- 根据根的值就可以查找到中序遍历中根的位置k，k的左右侧分别是左右子树
- 我们只需要传入根在前序遍历的位置，以及中序遍历的左右子树即可递归重建二叉树
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
unordered_map<int, int> pos;
TreeNode* dfs(vector<int>& pre, vector<int>& in, int root, int l, int r)
{
if (l > r) return NULL;
TreeNode* node = new TreeNode(pre[root]);
int k = pos[pre[root]];
node->left = dfs(pre, in, root + 1, l, k - 1);
node->right = dfs(pre, in, root + k - l + 1, k + 1, r);
return node;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
for (int i = 0; i < inorder.size(); i++){
pos[inorder[i]] = i;
}
return dfs(preorder, inorder, 0, 0, inorder.size() - 1);
}
};第二天
7. 二叉树的下一个节点
给定一棵二叉树的其中一个节点，请找出中序遍历序列的下一个节点。
注意：
- 如果给定的节点是中序遍历序列的最后一个，则返回空节点;
- 二叉树一定不为空，且给定的节点一定不是空节点；
样例
假定二叉树是：[2, 1, 3, null, null, null, null]， 给出的是值等于2的节点。 则应返回值等于3的节点。 解释：该二叉树的结构如下，2的后继节点是3。 2 / \ 1 3
思路
分两种情况，如下图：
- 如果当前节点p有右子树，那么当前节点右子树的最左边的节点就是p的后继节点
- 如果当前节点p无右子树，那么找到当前节点p的father节点（因为它的左儿子节点是中序遍历的前一个节点），如果该节点的右儿子节点与当前节点p是同一个节点，就继续往上找father节点，直到找到一个不满足该条件的节点，该节点的father节点就是我们要找的后继节点
时间复杂度
$O(h)$
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode *father;
* TreeNode(int x) : val(x), left(NULL), right(NULL), father(NULL) {}
* };
*/
class Solution {
public:
TreeNode* inorderSuccessor(TreeNode* p) {
if (p->right)
{
p = p->right;
while (p->left)
{
p = p->left;
}
return p;
}
while (p->father && p->father->right == p) p = p->father;
return p->father;
}
};8. 用两个栈实现队列
请用栈实现一个队列，支持如下四种操作：
push(x) – 将元素x插到队尾；
pop() – 将队首的元素弹出，并返回该元素；
peek() – 返回队首元素；
empty() – 返回队列是否为空；
注意：
- 你只能使用栈的标准操作：push to top，peek/pop from top, size 和 is empty；
- 果你选择的编程语言没有栈的标准库，你可以使用list或者deque等模拟栈的操作；
- 输入数据保证合法，例如，在队列为空时，不会进行pop或者peek等操作；
样例
MyQueue queue = new MyQueue(); queue.push(1); queue.push(2); queue.peek(); // returns 1 queue.pop(); // returns 1 queue.empty(); // returns false
思路
创建两个栈stk1，stk2，由于栈是先进后出，当把stk1中的数据弹出放入stk2时，再从stk2弹出就是队列的性质先进先出了。
时间复杂度
- push()：$O(1)$；
- pop(): 每次需要将主栈元素全部弹出，再压入，所以需要 $O(n)$的时间；
- peek()：类似于$pop()$，需要 $O(n)$的时间；
- empty()：$O(1)$；
class MyQueue {
private:
stack<int> stk1, stk2;
public:
/** Initialize your data structure here. */
MyQueue() {
}
/** Push element x to the back of queue. */
void push(int x) {
while (!stk2.empty())
{
int t = stk2.top();
stk2.pop();
stk1.push(t);
}
stk1.push(x);
}
/** Removes the element from in front of queue and returns that element. */
int pop() {
while (!stk1.empty())
{
int t = stk1.top();
stk1.pop();
stk2.push(t);
}
int t = stk2.top();
stk2.pop();
return t;
}
/** Get the front element. */
int peek() {
while (!stk1.empty())
{
int t = stk1.top();
stk1.pop();
stk2.push(t);
}
return stk2.top();
}
/** Returns whether the queue is empty. */
bool empty() {
return stk1.empty() && stk2.empty();
}
};
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue obj = MyQueue();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.peek();
* bool param_4 = obj.empty();
*/9. 斐波那契数列
输入一个整数 n ，求斐波那契数列的第 n 项。
假定从 0 开始，第 0 项为 00。(n≤39)
样例
输入整数 n=5 返回 5
思路
由于这题数据量小，同时我们为了节省空间，使用两个变量滚动往后计算。
时间复杂度
$O(n)$
class Solution {
public:
int Fibonacci(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
int a = 0, b = 1, c = 0;
int cnt = n - 1;
while (cnt--)
{
c = a + b;
a = b;
b = c;
}
return c;
}
};10. 旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个升序的数组的一个旋转，输出旋转数组的最小元素。
例如数组 {3,4,5,1,2} 为 {1,2,3,4,5} 的一个旋转，该数组的最小值为 1。
数组可能包含重复项。
注意：数组内所含元素非负，若数组大小为 0，请返回 −1。
样例
输入：nums=[2,2,2,0,1] 输出：0
思路
如下图是数组的下标与值的坐标，我们发现分界线处的值是我们要求的最小值。当我们去掉旋转数组最后相同的数据时，这个数组满足如下性质：
竖线左边的都大于等于第一个值，竖线右边的都小于第一个值。
我们可以利用这个性质二分
时间复杂度
最坏情况是所有数字相同时，时间复杂度为$O(n)$，平均时间复杂度$O(log n)$
class Solution {
public:
int findMin(vector<int>& nums) {
if (nums.empty()) return -1;
int l = 0, r = nums.size() - 1;
while (r > 0 && nums[r] == nums[0]) r--;
if (nums[r] >= nums[0]) return nums[0];
while (l < r)
{
int mid = l + r >> 1;
if (nums[mid] < nums[0]) r = mid;
else l = mid + 1;
}
return nums[l];
}
};11. 矩阵中的路径
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。
路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。
如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。
注意：
输入的路径不为空；
所有出现的字符均为大写英文字母；
样例
matrix= [ ["A","B","C","E"], ["S","F","C","S"], ["A","D","E","E"] ] str="BCCE" , return "true" str="ASAE" , return "false"
思路
先枚举单词的起点，然后依次枚举单词的每个字母。在搜索中要注意将已经遍历过的字符修改成特殊字符，避免再次遍历。
时间复杂度
总共有$n^2$个字母，对于每个单词，有k个字母，由于不能走回头路，故有3个方向可选，因此时间复杂度为$O(n^2 \times k)$
class Solution {
public:
bool dfs(vector<vector<char>>& matrix, string &str, int u, int x, int y)
{
// cout << str[u] << " " << matrix[x][y] << endl;
if (str[u] != matrix[x][y]) return false;
if (u == str.length() - 1) return true;
char c = matrix[x][y];
matrix[x][y] = ' ';
int dx[] = {0, 1, -1, 0}, dy[] = {-1, 0, 0, 1};
for (int i = 0; i < 4; i++)
{
int m = matrix.size(), n = matrix[0].size();
int tx = x + dx[i], ty = y + dy[i];
if (tx < 0 || tx >= m || ty < 0 || ty >= n) continue;
if (dfs(matrix, str, u + 1, tx, ty)) return true;
}
matrix[x][y] = c;
return false;
}
bool hasPath(vector<vector<char>>& matrix, string &str) {
for (int i = 0; i < matrix.size(); i ++ )
for (int j = 0; j < matrix[i].size(); j ++ )
if (dfs(matrix, str, 0, i, j))
return true;
return false;
}
};12. 机器人的运动范围
地上有一个 m 行和 n 列的方格，横纵坐标范围分别是 0∼m−1 和 0∼n−1。
一个机器人从坐标 (0,0) 的格子开始移动，每一次只能向左，右，上，下四个方向移动一格。
但是不能进入行坐标和列坐标的数位之和大于 k 的格子。
请问该机器人能够达到多少个格子？
样例1
输入：k=7, m=4, n=5 输出：20
样例2
输入：k=18, m=40, n=40 输出：1484 解释：当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。 但是，它不能进入方格（35,38），因为3+5+3+8 = 19。
注意:
$0<=m<=50$
$0<=n<=50$
$0<=k<=100$
思路
从(0,0)开始遍历，每次进入一个新格子判断一次是否走过以及是否满足条件行坐标和列坐标的数位之和大于 k ，如果满足则返回1，否则返回0。
时间复杂度
由于我们不需要回溯，我们只需要遍历所有格子即可，所有时间复杂度为$O(nm)$。
bool st[55][55];
class Solution {
public:
int sum(int x)
{
int t = 0;
while (x)
{
t += x % 10;
x /= 10;
}
return t;
}
int dfs(int k, int m, int n, int x, int y)
{
int cnt = 0;
if (sum(x) + sum(y) > k || st[x][y]) return 0;
st[x][y] = true;
cnt++;
int dx[] = {0, 1, -1, 0}, dy[] = {1, 0, 0, -1};
for (int i = 0; i < 4; i++)
{
int tx = x + dx[i], ty = y + dy[i];
if (tx < 0 || tx >= m || ty < 0 || ty >= n) continue;
cnt += dfs(k, m, n, tx, ty);
}
return cnt;
}
int movingCount(int threshold, int rows, int cols)
{
if (rows == 0 || cols == 0) return 0;
return dfs(threshold, rows, cols, 0, 0);
}
};13. 剪绳子
给你一根长度为 n 绳子，请把绳子剪成 m 段（m、n 都是整数，2≤n≤58并且 m≥2）。
每段的绳子的长度记为 k[1]、k[2]、……、k[m]。
k[1]k[2]…k[m] 可能的最大乘积是多少？
例如当绳子的长度是 8 时，我们把它剪成长度分别为 2、3、3 的三段，此时得到最大的乘积 18。
样例
输入：8 输出：18
思路
总所周知，当所有数字为平均值时，其和最大。我们不妨看以下问题：
已知：$\sum_{i}^{k}n_i$，求：$max(\prod_{i}^{k}n_i)$
要解决这个问题，很简单，我们令$y=max(\prod_{i}^{k}n_i)$
那么$y_{max}=x^{\tfrac{N}{x}}$，将常数N去掉得：
$y_{max}=x^{\tfrac{1}{x}}$
因此$y_{max} ∝ x^{\tfrac{1}{x}}=e^{\tfrac{ln x}{x}}$
而$\tfrac{ln x}{x}$在$x=e$处取得极大值，也是最大值
由于 $y(2) < y(3)$，因此$x=3$时y取得最大值
同时，很显然因子不包括1。要使得乘积最大，全都取3，但是对于余数为1，我们不能取1，这时候我们要取4；对于余数为2，我们取2。
时间复杂度
$O(n)$
class Solution {
public:
int maxProductAfterCutting(int length) {
if (length == 2) return 1;
int res = 1;
if (length % 3 == 1) res = 4, length -= 4;
if (length % 3 == 2) res = 2, length -= 2;
while (length) res *= 3, length -= 3;
return res;
}
};第三天
14. 二进制中1的个数
输入一个 32 位整数，输出该数二进制表示中 1 的个数。
注意：
负数在计算机中用其绝对值的补码来表示。
样例1
输入：9 输出：2 解释：9的二进制表示是1001，一共有2个1。
样例2
输入：-2 输出：31 解释：-2在计算机里会被表示成11111111111111111111111111111110， 一共有31个1。
思路
使用lowbit得到最后一个数字1。
时间复杂度
$O(log n)$
class Solution {
public:
int lowbit(int x)
{
return x & -x;
}
int NumberOf1(int n) {
int cnt = 0;
for (int i = n; i; i -= lowbit(i)) cnt++;
return cnt;
}
};15. 删除链表中重复的节点
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留。
样例1
输入：1->2->3->3->4->4->5 输出：1->2->5
样例2
输入：1->1->1->2->3 输出：2->3
思路
由于头结点可能会被删掉，所以我们需要再前面加一个虚拟结点，防止冗余的判断。在进行删除的时候，我们用两个指针，一个指针存当前最后一个不用删除的节点，另一个指针存第一个指针之后重复的一段数字的最后一个节点（当然也能可能不重复，那么这段只有一个节点）。
时间复杂度
$O(n)$
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* deleteDuplication(ListNode* head) {
auto dummy = new ListNode(-1);
dummy->next = head;
auto p = dummy;
while(p->next)
{
auto q = p->next;
while(q && q->val == p->next->val) q = q->next;
if (p->next->next == q) p = p->next;
else p->next = q;
}
return dummy->next;
}
};第四天
16. 正则表达式匹配
请实现一个函数用来匹配包括'.'和'*'的正则表达式。
模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次）。
在本题中，匹配是指字符串的所有字符匹配整个模式。
例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配。
样例
输入： s="aa" p="a*" 输出:true
思路
记忆化搜索
时间复杂度
$O(n + m)$
class Solution {
public:
vector<vector<int>>f;
int n, m;
bool isMatch(string s, string p) {
n = s.size();
m = p.size();
f = vector<vector<int>>(n + 1, vector<int>(m + 1, -1));
f[n][m] = 1;
dp(0, 0, s, p);
return dp(0, 0, s, p);
}
int dp(int x, int y, string &s, string &p)
{
if (f[x][y] != -1) return f[x][y];
if (y == m)
return f[x][y] = x == n;
bool first_match = x < n && (s[x] == p[y] || p[y] == '.');
bool ans;
if (y + 1 < m && p[y + 1] == '*')
{
return dp(x, y + 2, s, p) || first_match && dp(x + 1, y, s, p);
}
else
return first_match && dp(x + 1, y + 1, s, p);
}
};17. 表示数值的字符串
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。
例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。
但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。
注意:
- 小数可以没有整数部分，例如
.123等于0.123； - 小数点后面可以没有数字，例如
233.等于233.0； - 小数点前面和后面可以有数字，例如
233.666; - 当e或E前面没有数字时，整个字符串不能表示数字，例如
.e1、e1； - 当e或E后面没有整数时，整个字符串不能表示数字，例如
12e、12e+5.4;
样例：
输入: "0" 输出: true
思路
数字构成格式为：[+|-][数字][.][数字][e|E][数字]，我们可以根据这个格式来进行模拟。
时间复杂度
$O(n)$
class Solution {
public:
bool isNumber(string s) {
bool success = false;
int i = 0;
if (s[i] == '+' || s[i] == '-') i++;
while (isdigit(s[i])) success = true, i++;
if (s[i] == '.') i++;
while (isdigit(s[i])) success = true, i++;
if (!success) return false;
if (s[i] == 'e' || s[i] == 'E')
{
success = false, i++;
if (s[i] == '+' || s[i] == '-') i++;
while (isdigit(s[i])) success = true, i++;
}
return success && (i == s.length());
}
};18. 调整数组顺序使奇数位于偶数前面
输入一个整数数组，实现一个函数来调整该数组中数字的顺序。
使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分。
样例
输入：[1,2,3,4,5] 输出: [1,3,5,2,4]
思路
交换左边的偶数与右边的奇数。
时间复杂度
$O(n)$
class Solution {
public:
void reOrderArray(vector<int> &array) {
for (int i = 0, j = array.size() - 1; i < j;)
{
while (array[i] % 2) i++;
while (array[j] % 2 == 0) j--;
if (i < j) swap(array[i], array[j]);
}
}
};19. 链表中倒数第k个节点
输入一个链表，输出该链表中倒数第 k 个结点。
注意：
k >= 0;
如果 k 大于链表长度，则返回 NULL;
样例
输入：链表：1->2->3->4->5 ，k=2 输出：4
思路
遍历一遍链表得到链表长度cnt，然后将倒数第k个换算成第cnt-k+1个。
时间复杂度
$O(n)$
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* findKthToTail(ListNode* pListHead, int k) {
auto p = pListHead;
int cnt = 0;
while (p) p = p->next, cnt++;
if (k > cnt) return NULL;
p = pListHead;
int i = 0;
while (p)
{
i++;
if (cnt - k + 1 == i) return p;
p = p->next;
}
}
};20. 链表中环的入口结点
给定一个链表，若其中包含环，则输出环的入口节点。
若其中不包含环，则输出null。
样例
给定如上所示的链表： [1, 2, 3, 4, 5, 6] 2 注意，这里的2表示编号是2的节点，节点编号从0开始。所以编号是2的节点就是val等于3的节点。 则输出环的入口节点3.
思路
我们只需要遍历一遍节点即可，在遍历的时候使用hash表标记，然后如果再次遍历到了它说明它是入口节点。
时间复杂度
$O(n)$
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
unordered_map<ListNode*, bool> st;
ListNode *entryNodeOfLoop(ListNode *head) {
ListNode *p = head;
while(p)
{
if (st[p]) return p;
st[p] = true;
p = p->next;
}
return NULL;
}
};21. 反转链表
定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。
思考题：
请同时实现迭代版本和递归版本。
样例
输入:1->2->3->4->5->NULL 输出:5->4->3->2->1->NULL
思路1——迭代版本
由于是单链表，无法直接获取当前节点的前驱结点，所以我们需要用一个变量存起来，同时由于后继节点会被修改，也需要用一个变量存储，最后还需要一个变量表示当前节点，用来扫描链表。这里有一个图可以形象的展示这个题目的做法：
时间复杂度1
$O(n)$
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* p = head;
ListNode* pre = NULL;
while (p)
{
ListNode* temp_next = p->next;
p->next = pre;
pre = p;
p = temp_next;
}
return pre;
}
};思路2——递归版本
由于是单链表，无法直接获取当前节点的前驱结点，所以我们需要用一个变量存起来，同时由于后继节点会被修改，也需要用一个变量存储，最后还需要一个变量表示当前节点，用来扫描链表。
时间复杂度2
首先我们先考虑 reverseList 函数能做什么，它可以翻转一个链表，并返回新链表的头节点，也就是原链表的尾节点。所以我们可以先递归处理 reverseList(head->next)，这样我们可以将以head->next为头节点的链表翻转，并得到原链表的尾节点tail，此时head->next是新链表的尾节点，我们令它的next指针指向head，并将head->next指向空即可将整个链表翻转，且新链表的头节点是tail。
$O(n)$
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(!head || !head->next) return head;
auto p = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return p;
}
};第五天
22. 合并两个排序的链表
输入两个递增排序的链表，合并这两个链表并使新链表中的结点仍然是按照递增排序的。
样例
输入：1->3->5 , 2->4->5 输出：1->2->3->4->5->5
思路
从前往后扫描l1,和l2，判断l1和l2节点的值，将其加入到新链表当中即可。
时间复杂度
$O(n)$
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* merge(ListNode* l1, ListNode* l2) {
ListNode* dummy = new ListNode(-1);
dummy->next = NULL;
auto p = dummy;
while (l1 && l2)
{
while (l1 && l2 && l1->val < l2->val)
{
p->next = l1;
p = p->next;
l1 = l1->next;
}
while (l2 && l1 && l1->val >= l2->val)
{
p->next = l2;
p = p->next;
l2 = l2->next;
}
}
while (l1)
{
p->next = l1;
l1 = l1->next;
p = p->next;
}
while (l2)
{
p->next = l2;
l2 = l2->next;
p = p->next;
}
p->next = NULL;
return dummy->next;
}
};23. 树的子结构
输入两棵二叉树 A，B，判断 B 是不是 A 的子结构。
我们规定空树不是任何树的子结构。
样例
树 AA：
8
/ \
8 7
/ \
9 2
/ \
4 7
树 BB：
8
/ \
9 2
返回 true，因为 B 是 A 的子结构。
思路
对于A的每个节点，我们同时遍历B和A，判断是否匹配。
时间复杂度
$O(nm)$
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool hasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
if (!pRoot1 || !pRoot2) return false;
if (isPart(pRoot1, pRoot2)) return true;
return hasSubtree(pRoot1->left, pRoot2) || hasSubtree(pRoot1->right, pRoot2);
}
bool isPart(TreeNode* p1, TreeNode* p2)
{
if (!p2) return true;
if (!p1 || p1->val != p2->val) return false;
return isPart(p1->left, p2->left) && isPart(p1->right, p2->right);
}
};24. 二叉树的镜像
输入一个二叉树，将它变换为它的镜像。
样例
输入树：
8
/ \
6 10
/ \ / \
5 7 9 11
[8,6,10,5,7,9,11,null,null,null,null,null,null,null,null]
输出树：
8
/ \
10 6
/ \ / \
11 9 7 5
[8,10,6,11,9,7,5,null,null,null,null,null,null,null,null]
思路
遍历二叉树，交换左右儿子即可。
时间复杂度
$O(n)$
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void mirror(TreeNode* root) {
if (!root) return;
mirror(root->left);
mirror(root->right);
swap(root->left, root->right);
}
};25. 对称的二叉树
请实现一个函数，用来判断一棵二叉树是不是对称的。
如果一棵二叉树和它的镜像一样，那么它是对称的。
样例
如下图所示二叉树[1,2,2,3,4,4,3,null,null,null,null,null,null,null,null]为对称二叉树：
1
/ \
2 2
/ \ / \
3 4 4 3
如下图所示二叉树[1,2,2,null,4,4,3,null,null,null,null,null,null]不是对称二叉树：
1
/ \
2 2
\ / \
4 4 3
思路
对于当前节点的左右子树，我们只需要判断左子树的右儿子与右子树的左儿子以及左子树的左儿子与右子树的右儿子是否相同即可。
时间复杂度
$O(n)$
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if (!root) return true;
return dfs(root->left, root->right);
}
bool dfs(TreeNode* p, TreeNode* q)
{
if (!p || !q) return !p && !q;
if (p->val != q->val) return false;
return dfs(p->left, q->right) && dfs(p->right, q->left);
}
};第六天
26. 顺时针打印矩阵
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
样例
输入： [ [1, 2, 3, 4], [5, 6, 7, 8], [9,10,11,12] ] 输出：[1,2,3,4,8,12,11,10,9,5,6,7]
思路
按照顺序右下上左直到走完。
时间复杂度
$O(nm)$
class Solution {
public:
vector<int> printMatrix(vector<vector<int> > matrix) {
vector<int> ans;
if (matrix.empty()) return ans;
int n = matrix.size();
int m = matrix[0].size();
int x = 0, y = 0, k = 1;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
bool vis[n][m];
memset(vis, 0, sizeof vis);
for (int i = 0; i < n * m; i++)
{
ans.push_back(matrix[x][y]);
vis[x][y] = true;
int tx = x + dx[k], ty = y + dy[k];
if (tx < 0 || tx >= n || ty < 0 || ty >= m || vis[tx][ty])
{
k = (k + 1) % 4;
tx = x + dx[k], ty = y + dy[k];
}
x = tx, y = ty;
}
return ans;
}
};27. 包含min函数的栈
设计一个支持push，pop，top等操作并且可以在O(1)时间内检索出最小元素的堆栈。
push(x)–将元素x插入栈中
pop()–移除栈顶元素
top()–得到栈顶元素
getMin()–得到栈中最小元
样例
MinStack minStack = new MinStack(); minStack.push(-1); minStack.push(3); minStack.push(-4); minStack.getMin(); --> Returns -4. minStack.pop(); minStack.top(); --> Returns 3. minStack.getMin(); --> Returns -1.
思路
经典问题——单调栈。
时间复杂度
$O(1)$
class MinStack {
public:
/** initialize your data structure here. */
stack<int> stk, min_stk;
MinStack() {
}
void push(int x) {
stk.push(x);
if (min_stk.empty() || min_stk.top() >= x) min_stk.push(x);
}
void pop() {
if (stk.top() == min_stk.top()) min_stk.pop();
stk.pop();
}
int top() {
return stk.top();
}
int getMin() {
return min_stk.top();
}
};
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(x);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/28. 栈的压入、弹出序列
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。
假设压入栈的所有数字均不相等。
例如序列 1,2,3,4,5 是某栈的压入顺序，序列 4,5,3,2,1 是该压栈序列对应的一个弹出序列，但 4,3,5,1,2 就不可能是该压栈序列的弹出序列。
注意：若两个序列长度不等则视为并不是一个栈的压入、弹出序列。若两个序列都为空，则视为是一个栈的压入、弹出序列。
样例
输入：[1,2,3,4,5] [4,5,3,2,1] 输出：true
思路
模拟站，当栈为空时，压入数据；当不空时，判断栈顶和当前弹出序列的元素是否相等，相等则弹出，不相等则继续压入，直到操作完成。这里最后在判断时候有三个条件，第一个所有入栈数的用过了，第二个是所有出栈数都用了，第三个是栈为空。
时间复杂度
class Solution {
public:
bool isPopOrder(vector<int> pushV,vector<int> popV) {
int i = 0, j = 0;
stack<int> stk;
while (i < pushV.size())
{
if (stk.empty()) stk.push(pushV[i]), i++;
while (stk.top() != popV[j])
{
stk.push(pushV[i]);
i++;
}
while (!stk.empty() && stk.top() == popV[j])
{
stk.pop();
j++;
}
}
if (i == pushV.size() && j == popV.size() && stk.empty()) return true;
return false;
}
};29. 不分行从上往下打印二叉树
从上往下打印出二叉树的每个结点，同一层的结点按照从左到右的顺序打印。
样例
输入如下图所示二叉树[8, 12, 2, null, null, 6, null, 4, null, null, null]
8
/ \
12 2
/
6
/
4
输出：[8, 12, 2, 6, 4]
思路
BFS遍历树。
时间复杂度
$O(n)$
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> printFromTopToBottom(TreeNode* root) {
return bfs(root);
}
vector<int> bfs(TreeNode* root)
{
vector<int> res;
if(!root) return res;
queue<TreeNode*> q;
q.push(root);
while (!q.empty())
{
TreeNode* t = q.front();
q.pop();
res.push_back(t->val);
if (t->left) q.push(t->left);
if (t->right) q.push(t->right);
}
return res;
}
};30. 分行从上往下打印二叉树
从上到下按层打印二叉树，同一层的结点按从左到右的顺序打印，每一层打印到一行。
样例
输入如下图所示二叉树[8, 12, 2, null, null, 6, null, 4, null, null, null]
8
/ \
12 2
/
6
/
4
输出：[[8], [12, 2], [6], [4]]
思路
使用NULL来标记每一层的结尾。
时间复杂度
$O(n)$
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> printFromTopToBottom(TreeNode* root) {
return bfs(root);
}
vector<vector<int>> bfs(TreeNode* root)
{
vector<vector<int>> res;
if(!root) return res;
vector<int> level;
queue<TreeNode*> q;
q.push(root);
q.push(NULL);
while (!q.empty())
{
TreeNode* t = q.front();
q.pop();
if (!t)
{
if (level.empty()) break;
res.push_back(level);
level.clear();
q.push(NULL);
continue;
}
level.push_back(t->val);
if (t->left) q.push(t->left);
if (t->right) q.push(t->right);
}
return res;
}
};31. 之字形打印二叉树
请实现一个函数按照之字形顺序从上向下打印二叉树。
即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
样例
输入如下图所示二叉树[8, 12, 2, null, null, 6, 4, null, null, null, null]
8
/ \
12 2
/ \
6 4
输出：[[8], [2, 12], [6, 4]]
思路
对于每一层，使用变量标记，奇数层不翻转，偶数层翻转。
时间复杂度
$O(n)$
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> printFromTopToBottom(TreeNode* root) {
return bfs(root);
}
vector<vector<int>> bfs(TreeNode* root)
{
vector<vector<int>> res;
if(!root) return res;
vector<int> level;
queue<TreeNode*> q;
q.push(root);
q.push(NULL);
int flag = 1;
while (!q.empty())
{
TreeNode* t = q.front();
q.pop();
if (!t)
{
if (level.empty()) break;
flag ^= 1;
if (flag)
{
reverse(level.begin(), level.end());
}
res.push_back(level);
level.clear();
q.push(NULL);
continue;
}
level.push_back(t->val);
if (t->left) q.push(t->left);
if (t->right) q.push(t->right);
}
return res;
}
};32. 二叉搜索树的后序遍历序列
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。
如果是则返回true，否则返回false。
假设输入的数组的任意两个数字都互不相同。
样例
输入：[4, 8, 6, 12, 16, 14, 10] 输出：true
思路
由于是BST的后序遍历，所以最后一个数是根节点，从左往右扫描到最后一个小于根节点的地方，这一段都是左子树，另外一段是右子树，那么我们只需要去判断右子树是否都大于根节点即可。
时间复杂度
$O(nn^2)$
class Solution {
public:
vector<int> seq;
bool verifySequenceOfBST(vector<int> sequence) {
seq = sequence;
return dfs(0, seq.size() - 1);
}
bool dfs(int l, int r)
{
if (l >= r) return true;
int root = seq[r];
int k = l;
while (k < r && seq[k] < root) k++;
for (int i = k; i < r; i++)
if (seq[i] < root)
return false;
return dfs(l, k - 1) && dfs(k, r - 1);
}
};33. 二叉树中和为某一值的路径
输入一棵二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。
从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
样例
给出二叉树如下所示，并给出num=22。
5
/ \
4 6
/ / \
12 13 6
/ \ / \
9 1 5 1
输出：[[5,4,12,1],[5,6,6,5]]
思路
每次将当前节点加入总和和，然后判断是否与给定sum相等。
时间复杂度
$O(n)$
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> path;
vector<int> p;
int sum;
vector<vector<int>> findPath(TreeNode* root, int sum) {
this->sum = sum;
dfs(root, sum);
return this->path;
}
void dfs(TreeNode* t, int sum)
{
if (!t) return;
sum -= t->val;
p.push_back(t->val);
if (!t->left && !t->right && !sum) {
path.push_back(p);
}
if (t->left) dfs(t->left, sum);
if (t->right) dfs(t->right, sum);
p.pop_back();
}
};34. 复杂链表的复刻
请实现一个函数可以复制一个复杂链表。
在复杂链表中，每个结点除了有一个指针指向下一个结点外，还有一个额外的指针指向链表中的任意结点或者null。
注意：函数结束后原链表要与输入时保持一致。
思路
使用hash存储 key = 源链表节点，value = 目标链表节点，遍历源链表，判断每个节点和random节点是否在hash表中，如果不存在则创建
时间复杂度
$O(n)$
/**
* Definition for singly-linked list with a random pointer.
* struct ListNode {
* int val;
* ListNode *next, *random;
* ListNode(int x) : val(x), next(NULL), random(NULL) {}
* };
*/
class Solution {
public:
ListNode *copyRandomList(ListNode *head) {
unordered_map<ListNode*, ListNode*> hash;
hash[nullptr] = nullptr;
auto dup = new ListNode(-1), tail = dup;
while(head)
{
if(!hash.count(head)) hash[head] = new ListNode(head->val);
if(!hash.count(head->random)) hash[head->random] = new ListNode(head->random->val);
tail->next = hash[head];
tail->next->random = hash[head->random];
tail = tail->next;
head = head->next;
}
return dup->next;
}
};
35. 二叉搜索树与双向链表
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。
要求不能创建任何新的结点，只能调整树中结点指针的指向。
注意：
需要返回双向链表最左侧的节点。
例如，输入下图中左边的二叉搜索树，则输出右边的排序双向链表。
思路
这里双向链表的构建过程其实就是BST的中序遍历，我们只需要稍微改一下中序遍历即可。遍历时候我们使用一个pre遍历来存储当前节点的前一个节点。
时间复杂度
$O(n)$
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* pre = NULL;
TreeNode* convert(TreeNode* root) {
dfs(root);
while(root && root->left) root = root->left;
return root;
}
void dfs(TreeNode* t){
if (!t) return;
dfs(t->left);
t->left = pre;
if (pre) pre->right = t;
pre = t;
dfs(t->right);
}
};36. 序列化二叉树
请实现两个函数，分别用来序列化和反序列化二叉树。
您需要确保二叉树可以序列化为字符串，并且可以将此字符串反序列化为原始树结构。
样例
你可以序列化如下的二叉树
8
/ \
12 2
/ \
6 4
为："[8, 12, 2, null, null, 6, 4, null, null, null, null]"
思路
使用前序遍历序列化二叉树，再使用前序遍历处理二叉树。
时间复杂度
$O(n)$
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
string res;
dfs_s(root, res);
return res;
}
void dfs_s(TreeNode* t, string& res)
{
if (!t)
{
res += "null ";
return;
}
res += to_string(t->val) + ' ';
dfs_s(t->left, res);
dfs_s(t->right, res);
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
int u = 0;
return dfs_d(data, u);
}
TreeNode* dfs_d(string data, int& u)
{
if (u == data.size()) NULL;
int k = u;
while (data[k] != ' ') k++;
if (data[u] == 'n')
{
u = k + 1;
return NULL;
}
int sign = 1;
if (data[u] == '-') u++, sign = -1;
int val = 0;
for (int i = u; i < k; i++) val = val * 10 + data[i] - '0';
u = k + 1;
auto root = new TreeNode(val * sign);
root->left = dfs_d(data, u);
root->right = dfs_d(data, u);
return root;
}
};37. 数字排列
输入一组数字（可能包含重复数字），输出其所有的排列方式。
样例
输入：[1,2,3] 输出： [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
思路
由于这里数字可以重复，我们可以先将所有数字排序，然后假定相同数字的一个相对位置，即对于一段相同的数字，后面数字只能在前面数字的后面，然后通过正常的枚举即可。对于这题的状态表示，我们可以用一个数组标记，也可用一个二进制数字表示。
时间复杂度
$O(n \times n!)$
class Solution {
public:
vector<int> v;
vector<vector<int>> vs;
vector<bool> vis;
vector<vector<int>> permutation(vector<int>& nums) {
vis.resize(nums.size());
v.resize(nums.size());
sort(nums.begin(), nums.end());
dfs(0, 0, 0, nums, vs);
return vs;
}
void dfs(int u, int s, int status, vector<int>& nums, vector<vector<int>>& vs)
{
if (u == nums.size())
{
vs.push_back(v);
return;
}
if (!u || nums[u] != nums[u - 1]) s = 0;
for (int i = s; i < nums.size(); i++)
{
if (!(status >> i & 1))
{
v[i] = nums[u];
dfs(u + 1, i + 1, status + (1 << i), nums, vs);
}
}
}
};38. 数组中出现次数超过一半的数字
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
假设数组非空，并且一定存在满足条件的数字。
思考题：
假设要求只能使用 O(n) 的时间和额外 O(1) 的空间，该怎么做呢？
样例
输入：[1,2,1,1,3] 输出：1
思路
正常的做法，如果没有思考题中的要求，我们只需要开一个数组标记出现次数即可。但是有了题目的思考的要求，我们这里有一个巧妙的做法：使用一个计数变量cnt，从前往后遍历数组，如果当前数与前一个数不同则cnt--，如果cnt变为0，则当前数变为前一个数，直到遍历完，当前数即为所求。
时间复杂度
$O(n)$
class Solution {
public:
int moreThanHalfNum_Solution(vector<int>& nums) {
int cnt = 0, cur = nums[0];
for (int i = 0; i < nums.size(); i++)
{
if (cnt == 0) cur = nums[i];
if (nums[i] == cur) cnt++;
else cnt--;
}
return cur;
}
};39. 最小的k个数
输入 n 个整数，找出其中最小的 k 个数。
注意：
数据保证 k 一定小于等于输入数组的长度;
输出数组内元素请按从小到大顺序排序;
样例
输入：[1,2,3,4,5,6,7,8] , k=4 输出：[1,2,3,4]
思路
优先队列，维护一个大小为k的大根堆。
时间复杂度
class Solution {
public:
vector<int> getLeastNumbers_Solution(vector<int> input, int k) {
priority_queue<int> q;
for (int i = 0; i < input.size(); i++)
{
q.push(input[i]);
if (q.size() > k) q.pop();
}
vector<int> res;
for (int i = 0; i < k; i++)
{
res.push_back(q.top());
q.pop();
}
reverse(res.begin(), res.end());
return res;
}
};第七天
40.
如何得到一个数据流中的中位数？
如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。
如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
样例
输入：1, 2, 3, 4 输出：1,1.5,2,2.5 解释：每当数据流读入一个数据，就进行一次判断并输出当前的中位数。
思路
维护一个小根堆和大根堆，小根堆存放小于中位数的数，大根堆存放大于中位数的数。
时间复杂度
$O(log n)$
class Solution {
public:
priority_queue<int> max_heap;
priority_queue<int, vector<int>, greater<int>> min_heap;
void insert(int num){
max_heap.push(num);
if (min_heap.size() && max_heap.top() > min_heap.top())
{
int minv = max_heap.top(), maxv = min_heap.top();
max_heap.pop(), min_heap.pop();
max_heap.push(maxv), min_heap.push(minv);
}
if (max_heap.size() > min_heap.size() + 1)
{
min_heap.push(max_heap.top());
max_heap.pop();
}
}
double getMedian(){
if (min_heap.size() + max_heap.size() & 1) return max_heap.top();
return (min_heap.top() + max_heap.top()) / 2.0;
}
};41. 连续子数组的最大和
输入一个 非空 整型数组，数组里的数可能为正，也可能为负。
数组中一个或连续的多个整数组成一个子数组。
求所有子数组的和的最大值。
要求时间复杂度为 O(n)。
样例
输入：[1, -2, 3, 10, -4, 7, 2, -5] 输出：18
思路
维护以前一个数结束的数组的最大和。
时间复杂度
$O(n)$
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int res = -0x3f3f3f3f;
int sum = 0;
for (int i = 0; i < nums.size(); i++)
{
if (sum < 0) sum = 0;
sum += nums[i];
res = max(sum, res);
}
return res;
}
};42. 从1到n整数中1出现的次数
输入一个整数 n，求从 1 到 n 这 n 个整数的十进制表示中 11 出现的次数。
例如输入 12，从 1 到 12 这些整数中包含 “1” 的数字有 1，10，11 和 12，其中 “1” 一共出现了 5 次。
样例
输入： 12 输出： 5
思路
对于每一位的1，分类讨论。
时间复杂度
$O(log^2 n)$
class Solution {
public:
int numberOf1Between1AndN_Solution(int n) {
vector<int> nums;
while (n) nums.push_back(n % 10), n /= 10;
int res = 0;
for (int i = nums.size() - 1; i >= 0; i--)
{
int l = 0, r = 0, t = 1;
for (int j = nums.size() - 1; j > i; j--) l = l * 10 + nums[j];
for (int j = i - 1; j >= 0; j--) r = r * 10 + nums[j], t *= 10;
res += l * t;
if (nums[i] == 1) res += r + 1;
if (nums[i] > 1) res += t;
}
return res;
}
};43. 数字序列中某一位的数字
数字以 0123456789101112131415…0123456789101112131415… 的格式序列化到一个字符序列中。
在这个序列中，第 55 位（从 00 开始计数）是 55，第 1313 位是 11，第 1919 位是 44，等等。
请写一个函数求任意位对应的数字。
样例
输入：13 输出：1
思路
找规律，每个位数的数字分别有9，90，900......
时间复杂度
$O(log n)$
class Solution {
public:
int digitAtIndex(int n) {
if (n < 9) return n;
long long k = 1, t = 9;
while (true)
{
if (n - k * t < 0) break;
n -= k * t;
k++, t *= 10;
}
long long s = pow(10, k - 1) + n / k - !(n % k);
n %= k;
string res = to_string(s);
return res[(n - 1 + k) % k] - '0';
}
};44. 把数组排成最小的数
输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
例如输入数组 [3,32,321]，则打印出这 3 个数字能排成的最小数字 321323。
样例
输入：[3, 32, 321] 输出：321323 注意：输出数字的格式为字符串。
思路
贪心。
时间复杂度
$O(nlog n)$
class Solution {
public:
static bool cmp(string a, string b)
{
return a + b < b + a;
}
string printMinNumber(vector<int>& nums) {
vector<string> nums_strs;
for (auto num : nums) nums_strs.push_back(to_string(num));
sort(nums_strs.begin(), nums_strs.end(), cmp);
string res = "";
for (auto num : nums_strs) res += num;
return res;
}
};45. 把数字翻译成字符串
给定一个数字，我们按照如下规则把它翻译为字符串：
0 翻译成 a，1 翻译成 b，……，11 翻译成 l，……，25 翻译成 z。
一个数字可能有多个翻译。
例如 12258 有 5 种不同的翻译，它们分别是 bccfi、bwfi、bczi、mcfi 和 mzi。
请编程实现一个函数用来计算一个数字有多少种不同的翻译方法。
样例
输入："12258" 输出：5
思路
动态规划，我们使用f[i]来表示前i个数字的方案，然后状态转移。
时间复杂度
$O(n)$
class Solution {
public:
int getTranslationCount(string s) {
int len = s.size();
int f[len + 1] = { 0 };
s = " " + s;
f[0] = 1;
for (int i = 1; i <= len; i++)
{
f[i] += f[i - 1];
int val = (s[i - 1] - '0') * 10 + s[i] - '0';
if (val >= 10 && val <= 25) f[i] += f[i - 2];
}
return f[len];
}
};第八天
46. 礼物的最大价值
在一个 m×n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。
你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格直到到达棋盘的右下角。
给定一个棋盘及其上面的礼物，请计算你最多能拿到多少价值的礼物？
注意：m,n>0
样例
输入： [ [2,3,1], [1,7,1], [4,6,1] ] 输出：19 解释：沿着路径 2→3→7→6→1 可以得到拿到最大价值礼物。
思路
简单动态规划。
时间复杂度
$O(nm)$
class Solution {
public:
int getMaxValue(vector<vector<int>>& grid) {
int n = grid.size(), m = grid[0].size();
vector<vector<int>> f(n, vector<int>(m));
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
{
if (!i && !j)
{
f[i][j] = grid[i][j];
continue;
}
f[i][j] = -0x3f3f3f3f;
if (i) f[i][j] = max(f[i][j], f[i - 1][j] + grid[i][j]);
if (j) f[i][j] = max(f[i][j], f[i][j - 1] + grid[i][j]);
}
return f[n - 1][m - 1];
}
};47. 最长不含重复字符的子字符串
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
假设字符串中只包含从 a 到 z 的字符。
样例
输入："abcabc" 输出：3
思路
双指针。
时间复杂度
$O(n)$
class Solution {
public:
int longestSubstringWithoutDuplication(string s) {
int f[26] = { 0 };
int ans = 0;
for (int r = 0, l = 0; r < s.length(); r++)
{
int v = s[r] - 'a';
f[v]++;
if (f[v] > 1)
{
while (l < r)
{
if (f[v] == 1) break;
int nv = s[l] - 'a';
f[nv]--, l++;
}
}
ans = max(r - l + 1, ans);
}
return ans;
}
};48. 丑数
我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。
例如 6、8 都是丑数，但 14 不是，因为它包含质因子 7。
求第 n 个丑数的值。
样例
输入：5 输出：5
注意：习惯上我们把 1 当做第一个丑数。
思路
三路合并，每次找到接下来三个可能的最小丑数，然后判断。
时间复杂度
$O(n)$
class Solution {
public:
int getUglyNumber(int n) {
vector<int> f(1, 1);
int i = 0, j = 0, k = 0;
while (--n)
{
int t = min(f[i] * 2, min(f[j] * 3, f[k] * 5));
if (t == f[i] * 2) i++;
if (t == f[j] * 3) j++;
if (t == f[k] * 5) k++;
f.push_back(t);
}
return f.back();
}
};49. 字符串中第一个只出现一次的字符
在字符串中找出第一个只出现一次的字符。
如输入"abaccdeff"，则输出b。
如果字符串中不存在只出现一次的字符，返回 # 字符。
样例：
输入："abaccdeff" 输出：'b'
思路
字符串哈希。
时间复杂度
class Solution {
public:
char firstNotRepeatingChar(string s) {
vector<int> f(256);
for (int i = 0; i < s.size(); i++) f[s[i]]++;
for (int i = 0; i < s.size(); i++)
if (f[s[i]] == 1)
return s[i];
return '#';
}
};50. 字符流中第一个只出现一次的字符
请实现一个函数用来找出字符流中第一个只出现一次的字符。
例如，当从字符流中只读出前两个字符 go 时，第一个只出现一次的字符是 g。
当从该字符流中读出前六个字符 google 时，第一个只出现一次的字符是 l。
如果当前字符流没有存在出现一次的字符，返回 # 字符。
样例
输入："google" 输出："ggg#ll" 解释：每当字符流读入一个字符，就进行一次判断并输出当前的第一个只出现一次的字符。
思路
双指针。
时间复杂度
class Solution{
public:
//Insert one char from stringstream
int f[256] = { 0 };
queue<char> q;
void insert(char ch){
if (++f[ch] > 1)
{
while (q.size() && f[q.front()] > 1) q.pop();
}
else q.push(ch);
}
//return the first appearence once char in current stringstream
char firstAppearingOnce(){
if (q.size()) return q.front();
return '#';
}
};第九天
51. 数组中的逆序对
在数组中的两个数字如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。
输入一个数组，求出这个数组中的逆序对的总数。
样例
输入：[1,2,3,4,5,6,0] 输出：6
思路
正常的办法我们可以用暴力做法求，但是我们可以使用归并排序求逆序对来优化时间复杂度。
时间复杂度
$n(log n)$
class Solution {
public:
int merge(vector<int>& nums, int l, int r)
{
if (l >= r) return 0;
int mid = l + r >> 1;
int i = l, j = mid + 1;
vector<int> temp;
int res = merge(nums, l, mid) + merge(nums, mid + 1, r);
while (i <= mid && j <= r)
{
if (nums[i] <= nums[j]) temp.push_back(nums[i++]);
else
{
temp.push_back(nums[j++]);
res += mid - i + 1;
}
}
while (i <= mid) temp.push_back(nums[i++]);
while (j <= r) temp.push_back(nums[j++]);
for (int i = l, j = 0; j < temp.size(); i++, j++) nums[i] = temp[j];
return res;
}
int inversePairs(vector<int>& nums) {
return merge(nums, 0, nums.size() - 1);
}
};52. 两个链表的第一个公共结点
输入两个链表，找出它们的第一个公共结点。
当不存在公共节点时，返回空节点。
样例
给出两个链表如下所示：
A： a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3
输出第一个公共节点c1
思路
不同部分长度分别为a， 和b，公共部分为c；a + c + b = b + c + a;让两个一起走，a走到头就转向b， b走到头转向a，则在公共部分相遇。
时间复杂度
$O(n)$
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *findFirstCommonNode(ListNode *headA, ListNode *headB) {
auto p = headA, q = headB;
while (p != q)
{
if (p) p = p->next;
else p = headB;
if (q) q = q->next;
else q = headA;
}
return p;
}
};53. 数字在排序数组中出现的次数
统计一个数字在排序数组中出现的次数。
例如输入排序数组 [1,2,3,3,3,3,4,5] 和数字 3，由于 3 在这个数组中出现了 4 次，因此输出 4。
样例
输入：[1, 2, 3, 3, 3, 3, 4, 5] , 3 输出：4
思路
二分找到第一个等于k的数和最后一个等于k的数。
时间复杂度
$O(log n)$
class Solution {
public:
int getNumberOfK(vector<int>& nums , int k) {
if (nums.empty()) return 0;
int l = -1, r = nums.size();
while (l < r)
{
int mid = l + r + 1 >> 1;
if (nums[mid] < k) l = mid;
else r = mid - 1;
}
int t = l;
l = -1, r = nums.size();
while (l < r)
{
int mid = l + r >> 1;
if (nums[mid] > k) r = mid;
else l = mid + 1;
}
return l - t - 1;
}
};54. 0到n-1中缺失的数字
一个长度为 n−1 的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围 0 到 n−1 之内。
在范围 0 到 n−1 的 n 个数字中有且只有一个数字不在该数组中，请找出这个数字。
样例
输入：[0,1,2,4] 输出：3
思路
二分。
时间复杂度
$O(log n)$
class Solution {
public:
int getMissingNumber(vector<int>& nums) {
if (nums.empty()) return 0;
int l = 0, r = nums.size() - 1;
while (l < r)
{
int mid = l + r >> 1;
if (nums[mid] > mid) r = mid;
else l = mid + 1;
}
if (nums[l] == l) l++;
return l;
}
};55. 数组中数值和下标相等的元素
假设一个单调递增的数组里的每个元素都是整数并且是唯一的。
请编程实现一个函数找出数组中任意一个数值等于其下标的元素。
例如，在数组 [−3,−1,1,3,5] 中，数字 3 和它的下标相等。
样例
输入：[-3, -1, 1, 3, 5] 输出：3 注意:如果不存在，则返回-1。
思路
二分。
时间复杂度
class Solution {
public:
int getNumberSameAsIndex(vector<int>& nums) {
int l = 0, r = nums.size() - 1;
while (l < r)
{
int mid = l + r >> 1;
if (nums[mid] < mid) l = mid + 1;
else r = mid;
}
if (nums[r] == r) return r;
return -1;
}
};56. 二叉搜索树的第k个结点
给定一棵二叉搜索树，请找出其中的第 k 小的结点。
你可以假设树和 k 都存在，并且 1≤k≤ 树的总结点数。
样例
输入：root = [2, 1, 3, null, null, null, null] ，k = 3 2 / \ 1 3 输出：3
思路
二叉树遍历。
时间复杂度
$O(n)$
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* ans;
void dfs(TreeNode* t, int& k)
{
if (!t) return;
dfs(t->left, k);
k--;
if (k == 0) ans = t;
if (k > 0) dfs(t->right, k);
}
TreeNode* kthNode(TreeNode* root, int k) {
dfs(root, k);
return ans;
}
};57. 二叉树的深度
输入一棵二叉树的根结点，求该树的深度。
从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
样例
输入：二叉树[8, 12, 2, null, null, 6, 4, null, null, null, null]如下图所示：
8
/ \
12 2
/ \
6 4
输出：3
思路
二叉树遍历。
时间复杂度
$O(n)$
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int treeDepth(TreeNode* root) {
if (!root) return 0;
return max(treeDepth(root->left), treeDepth(root->right)) + 1;
}
};58. 平衡二叉树
输入一棵二叉树的根结点，判断该树是不是平衡二叉树。
如果某二叉树中任意结点的左右子树的深度相差不超过 1，那么它就是一棵平衡二叉树。
注意：
规定空树也是一棵平衡二叉树。
样例
输入：二叉树[5,7,11,null,null,12,9,null,null,null,null]如下所示， 5 / \ 7 11 / \ 12 9 输出：true
思路
递归求高度，判断是否相差超过1。
时间复杂度
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool ans = true;
bool isBalanced(TreeNode* root) {
dfs(root);
return ans;
}
int dfs(TreeNode* u)
{
if (!u) return 0;
int l = dfs(u->left), r = dfs(u->right);
if (abs(l - r) > 1) ans = false;
return max(l, r) + 1;
}
};59. 数组中只出现一次的两个数字
一个整型数组里除了两个数字之外，其他的数字都出现了两次。
请写程序找出这两个只出现一次的数字。
你可以假设这两个数字一定存在。
样例
输入：[1,2,3,3,4,4] 输出：[1,2]
思路
将数分为两个集合，第k位为1的集合和第k位不是1的集合，其中x y分别在这两个集合，且相同的元素是在同一个集合里面，于是将其转化成了求重复数字中的单个数值的问题。
时间复杂度
$O(n)$
class Solution {
public:
vector<int> findNumsAppearOnce(vector<int>& nums) {
int t = 0;
for (auto x : nums ) t ^= x;
int k = 0;
while ((t >> k & 1) == 0) k++;
int res = 0;
for (auto x : nums)
if (x >> k & 1)
res ^= x;
return vector<int>{res, t ^ res};
}
};60. 数组中唯一只出现一次的数字
在一个数组中除了一个数字只出现一次之外，其他数字都出现了三次。
请找出那个只出现一次的数字。
你可以假设满足条件的数字一定存在。
思考题：
如果要求只使用 O(n) 的时间和额外 O(1) 的空间，该怎么做呢？
样例
输入：[1,1,1,2,2,2,3,4,4,4] 输出：3
思路
本题与前一题思路类似，前一题中，其他数都出现了两次，因此需要的状态转移方式是，如果出现两个1就抵消为0，用一个变量和异或运算即可实现，而本题是需要1出现三次时才会抵消，因此有三种状态，即1出现的次数为3k, 3k + 1, 3k + 2次
逐个位来看，要设计一个两位的状态转移，出现三个1时，循环抵消，出现0时不变，一个变量只能记录两种状态，因此要用两个变量来记录状态，用one和two两个变量来记录1出现次数
00表示1出现3k次，01表示1出现3k + 1次，10表示1出现3k + 2次
真值表
two one x two one 0 0 1 0 1 0 1 1 1 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 1 0
先看one的状态转移方程
one = (~one & ~two & x) | (one & ~two & ~x)
= ~two & ((~one & x) | (one & ~x))
= ~two & (one ^ x)
同理，再用转移后的one来求two的状态转移方程
这里，one为当且仅当1出现次数为3k + 1, tow为当且仅当1出现次数为3k + 2
因此如果题目改为，有一个数出现了两次，则返回two即可
时间复杂度
$O(n)$
class Solution {
public:
int findNumberAppearingOnce(vector<int>& nums) {
int one = 0, two = 0;
for(auto x : nums)
{
one = (one ^ x) & ~two;
two = (two ^ x) & ~one;
}
return one;
}
};61. 和为S的两个数字
输入一个数组和一个数字 s，在数组中查找两个数，使得它们的和正好是 s。
如果有多对数字的和等于 s，输出任意一对即可。
你可以认为每组输入中都至少含有一组满足条件的输出。
样例
输入：[1,2,3,4] , sum=7 输出：[3,4]
思路
暴力法的时间复杂度较高的原因是寻找 target - x 的时间复杂度过高。需要一种更优秀的方法，能够快速寻找数组中是否存在目标元素。如果存在，[x, target - x] 即为答案。
使用哈希表，可以将寻找 target - x 的时间复杂度降低到从O(N) 降低到 O(1)。
创建一个哈希表，对于每一个 x，我们首先查询哈希表中是否存在target - x，如果有返回[x, target - x]如果没有，将 x 插入到哈希表中。
时间复杂度
$O(n)$
class Solution {
public:
vector<int> findNumbersWithSum(vector<int>& nums, int target) {
unordered_set<int> us;
for (int x : nums)
{
if (us.count(target - x))
return vector<int>{x, target - x};
us.insert(x);
}
}
};62. 和为S的连续正数序列
输入一个正数 S，打印出所有和为 S 的连续正数序列（至少含有两个数）。
例如输入 15，由于 1+2+3+4+5=4+5+6=7+8=15，所以结果打印出 3 个连续序列 1∼5、4∼6 和 7∼8。
样例
输入：15 输出：[[1,2,3,4,5],[4,5,6],[7,8]]
思路
双指针。
时间复杂度
$O(n)$
class Solution {
public:
vector<vector<int> > findContinuousSequence(int sum) {
vector<vector<int> > res;
for (int l = 1, r = 1, s = 0; l < sum; l++)
{
while (s < sum) s += r++;
if (s == sum && r - l + 1 > 1)
{
vector<int> v;
for (int i = l; i < r; i++) v.push_back(i);
res.push_back(v);
}
s -= l;
}
return res;
}
};63. 翻转单词顺序
输入一个英文句子，单词之间用一个空格隔开，且句首和句尾没有多余空格。
翻转句子中单词的顺序，但单词内字符的顺序不变。
为简单起见，标点符号和普通字母一样处理。
例如输入字符串"I am a student."，则输出"student. a am I"。
样例
输入："I am a student." 输出："student. a am I"
思路
模拟。
时间复杂度
$O(n)$
class Solution {
public:
string reverseWords(string s) {
vector<string> v;
for (int l = 0, r = 0; r < s.length(); r++)
{
while (r < s.length() && s[r] != ' ') r++;
v.push_back(s.substr(l, r - l));
l = r + 1;
}
string res = "";
for (int i = v.size() - 1; i >= 0; i--)
{
res += v[i];
if (i) res += ' ';
}
return res;
}
};64. 左旋转字符串
字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。
请定义一个函数实现字符串左旋转操作的功能。
比如输入字符串"abcdefg"和数字 2，该函数将返回左旋转 2 位得到的结果"cdefgab"。
注意：
数据保证 n 小于等于输入字符串的长度。
样例
输入："abcdefg" , n=2 输出："cdefgab"
思路
技巧。
时间复杂度
class Solution {
public:
string leftRotateString(string str, int n) {
reverse(str.begin(), str.end());
reverse(str.begin(), str.begin() + str.length() - n);
reverse(str.begin() + str.length() - n, str.end());
return str;
}
};第十天
65. 滑动窗口的最大值
给定一个数组和滑动窗口的大小，请找出所有滑动窗口里的最大值。
例如，如果输入数组 [2,3,4,2,6,2,5,1] 及滑动窗口的大小 3，那么一共存在 6 个滑动窗口，它们的最大值分别为 [4,4,6,6,6,5]。
注意：
数据保证 k 大于 0，且 k 小于等于数组长度。
样例
输入：[2, 3, 4, 2, 6, 2, 5, 1] , k=3 输出: [4, 4, 6, 6, 6, 5]
思路
首先，最直接的做法当然是模拟滑动窗口的过程，每向右滑动一次都遍历一遍窗口内的数字找最大的输出，这样的复杂度是O(kn)，我们可以考虑优化一下。窗口向右滑动的过程实际上就是将处于窗口的第一个数字删除，同时在窗口的末尾添加一个新的数字，这就可以用双向队列来模拟，每次把尾部的数字弹出，再把新的数字压入到头部，然后找队列中最大的元素即可。
为了更快地找到最大的元素，我们可以在队列中只保留那些可能成为窗口最大元素的数字，去掉那些不可能成为窗口中最大元素的数字。考虑这样一个情况，如果队列中进来一个较大的数字，那么队列中比这个数更小的数字就不可能再成为窗口中最大的元素了，因为这个大的数字是后进来的，一定会比之前早进入窗口的小的数字要晚离开窗口，那么那些早进入且比较小的数字就“永无出头之日”，所以就可以弹出队列。
于是我们维护一个双向单调队列，队列放的是元素的下标。我们假设该双端队列的队头是整个队列的最大元素所在下标，至队尾下标代表的元素值依次降低。初始时单调队列为空。随着对数组的遍历过程中，每次插入元素前，首先需要看队头是否还能留在队列中，如果队头下标距离i超过了k，则应该出队。同时需要维护队列的单调性，如果nums[i]大于或等于队尾元素下标所对应的值，则当前队尾再也不可能充当某个滑动窗口的最大值了，故需要队尾出队。始终保持队中元素从队头到队尾单调递减。依次遍历一遍数组，每次队头就是每个滑动窗口的最大值所在下标。
时间复杂度
$O(n)$
class Solution {
public:
vector<int> maxInWindows(vector<int>& nums, int k) {
deque<int> q;
vector<int> res;
for (int i = 0; i < nums.size(); i++)
{
if (q.size() && q.front() + k <= i) q.pop_front();
while (q.size() && nums[q.back()] <= nums[i]) q.pop_back();
q.push_back(i);
if (i >= k - 1) res.push_back(nums[q.front()]);
}
return res;
}
};66. 骰子的点数
将一个骰子投掷 n 次，获得的总点数为 s，s 的可能范围为 n∼6n。
掷出某一点数，可能有多种掷法，例如投掷 2 次，掷出 3 点，共有 [1,2],[2,1] 两种掷法。
请求出投掷 n 次，掷出 n∼6n 点分别有多少种掷法。
样例1 输入：n=1 输出：[1, 1, 1, 1, 1, 1] 解释：投掷1次，可能出现的点数为1-6，共计6种。每种点数都只有1种掷法。所以输出[1, 1, 1, 1, 1, 1]。 样例2 输入：n=2 输出：[1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1] 解释：投掷2次，可能出现的点数为2-12，共计11种。每种点数可能掷法数目分别为1,2,3,4,5,6,5,4,3,2,1。 所以输出[1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1]。
思路
dp[i][j]表示用i个骰子扔出和为j的可能数，因为第i个骰子可能扔出1-6的点数，则dp[i][j]=dp[i-1][j-1]+dp[i-1][j-2]+dp[i-1][j-3]+dp[i-1][j-4]+dp[i-1][j-5]+dp[i-1][j-6]。
时间复杂度
$O(n^2)$
class Solution {
public:
vector<int> numberOfDice(int n) {
vector<vector<int>> f(n + 1, vector<int>(n * 6 + 1));
f[0][0] = 1;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= i * 6; j++)
for (int k = 1; k <= min(6, j); k++)
f[i][j] += f[i - 1][j - k];
vector<int> res;
for (int i = n; i <= n * 6; i++) res.push_back(f[n][i]);
return res;
}
};67. 扑克牌的顺子
从扑克牌中随机抽 5 张牌，判断是不是一个顺子，即这 5 张牌是不是连续的。
2∼10 为数字本身，A 为 11，J 为 11，Q 为 12，K 为 13，大小王可以看做任意数字。
为了方便，大小王均以 0 来表示，并且假设这副牌中大小王均有两张。
样例1 输入：[8,9,10,11,12] 输出：true 样例2 输入：[0,8,9,11,12] 输出：true
思路
- 除了0以外不能出现两个相同的数字；
- 排序后两个相邻数字的差值不能大于0的个数。
时间复杂度
$O(n)$
class Solution {
public:
bool isContinuous( vector<int> numbers ) {
if (numbers.empty()) return false;
sort(numbers.begin(), numbers.end());
int k = 0;
while (numbers[k] == 0) numbers[k++];
for (int i = k + 1; i < numbers.size(); i++)
{
if (numbers[i] == numbers[i - 1]) return false;
}
if (numbers.back() - numbers[k] + 1 <= numbers.size()) return true;
return false;
}
};68. 圆圈中最后剩下的数字
0,1,…,n−1 这 n 个数字 (n>0) 排成一个圆圈，从数字 0 开始每次从这个圆圈里删除第 m 个数字。
求出这个圆圈里剩下的最后一个数字。
样例
输入：n=5 , m=3 输出：3
思路
递推 f(n,m)=[f(n-1,m)+m]%n
时间复杂度
$O(n)$
class Solution {
public:
int lastRemaining(int n, int m){
if (n == 1) return 0;
return (lastRemaining(n - 1, m) + m) % n;
}
};69. 股票的最大利润
假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖 一次 该股票可能获得的利润是多少？
例如一只股票在某些时间节点的价格为 [9,11,8,5,7,12,16,14]。
如果我们能在价格为 5 的时候买入并在价格为 16 时卖出，则能收获最大的利润 11。
样例
输入：[9, 11, 8, 5, 7, 12, 16, 14] 输出：11
思路
由于只允许做一次股票买卖交易，枚举每一天作为卖出的日子，买入日子一定在卖出日子之前，为了获利最多，希望买入的日子的股票价格尽可能低。
时间复杂度
$O(n)$
class Solution {
public:
int maxDiff(vector<int>& nums) {
int minv = 0x3f3f3f3f, ans = 0;
for (int x : nums)
{
minv = min(x, minv);
if (x > minv) ans = max(ans, x - minv);
}
return ans;
}
};70. 求1+2+…+n
求 1+2+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句 (A?B:C)。
样例
输入：10 输出：55
思路1
递归。
时间复杂度1
$O(n)$
class Solution {
public:
int getSum(int n) {
int res = n;
if (n == 0) return 0;
(n > 0) && (res += getSum(n - 1));
return res;
}
};思路2
变相等差求和。
时间复杂度2
$O(1)$
class Solution {
public:
int getSum(int n) {
char a[n][n+1];
return sizeof(a)>>1;
}
};71. 不用加减乘除做加法
写一个函数，求两个整数之和，要求在函数体内不得使用 ＋、－、×、÷＋、－、×、÷ 四则运算符号。
样例
输入：num1 = 1 , num2 = 2 输出：3
思路
以15 + 7为例，在十进制加法中：
- 只做各位相加不进位运算，即得到12,；
- 做进位运算，即得到10,；3、把前面两个结果先相加，即得到22；
同样二进制加法也一样：
- 两个整数做异或^，得到各位相加不进位的运算结果；
- 两个整数做与&，然后再左移一位，即得到进位的运算结果；
- 将上面两个结果相加，即重复步骤1,2，直至进位的运算结果为0；
时间复杂度
$O(1)$
class Solution {
public:
int add(int num1, int num2){
while (num2)
{
int sum = num1 ^ num2;
int c = (num1 & num2) << 1;
num1 = sum;
num2 = c;
}
return num1;
}
};72. 构建乘积数组
给定一个数组A[0, 1, …, n-1]，请构建一个数组B[0, 1, …, n-1]，其中B中的元素B[i]=A[0]×A[1]×… ×A[i-1]×A[i+1]×…×A[n-1]。
不能使用除法。
样例
输入：[1, 2, 3, 4, 5] 输出：[120, 60, 40, 30, 24]
思考题：
能不能只使用常数空间？（除了输出的数组之外）
思路
用两个数组left和right，left[i]=A[0]*A[1]*…*A[i-1], left[i]=A[i-1]*left[i-1]; right[i] = A[i+1]*A[i+2]*…*A[n-1]，则right[i]=A[i+1]*right[i+1]。但是这里我们并不需要额外开，因为我们可以使用一个滚动变量实现。
最后结果B[i]=left[i]*right[i]。
时间复杂度
$O(n)$
class Solution {
public:
vector<int> multiply(const vector<int>& A) {
if (A.empty()) return vector<int>();
int n = A.size();
vector<int> B(n);
for (int i = 0, p = 1; i < n; i++) B[i] = p, p *= A[i];
for (int i = n - 1, p = 1; i >= 0; i--) B[i] *= p, p *= A[i];
return B;
}
};73. 把字符串转换成整数
请你写一个函数 StrToInt，实现把字符串转换成整数这个功能。
当然，不能使用 atoi 或者其他类似的库函数。
样例
输入："123" 输出：123
注意:
你的函数应满足下列条件：
- 忽略所有行首空格，找到第一个非空格字符，可以是 ‘+/−’ 表示是正数或者负数，紧随其后找到最长的一串连续数字，将其解析成一个整数；
- 整数后可能有任意非数字字符，请将其忽略；
- 如果整数长度为 00，则返回 00；
- 如果整数大于 INT_MAX(231−1231−1)，请返回 INT_MAX；如果整数小于INT_MIN(−231−231) ，请返回 INT_MIN；
思路
模拟操作即可。
时间复杂度
class Solution {
public:
int strToInt(string str) {
int k = 0, sign = 1;
while (k < str.size() && str[k] == ' ') k++;
if (!isdigit(str[k]) && str[k] != '-' && str[k] != '+') return 0;
if (str[k] == '-') sign = -1, k++;
else if (str[k] == '+') k++;
long long v = 0;
while (isdigit(str[k])) v = v * 10 + str[k] - '0', k++;;
v *= sign;
if (v > (1ll << 31 - 1)) return INT_MAX;
if (v < -(1 << 31)) return INT_MIN;
return v;
}
};73. 树中两个结点的最低公共祖先
给出一个二叉树，输入两个树节点，求它们的最低公共祖先。
一个树节点的祖先节点包括它本身。
注意：
输入的二叉树不为空；
输入的两个节点一定不为空，且是二叉树中的节点；
样例
二叉树[8, 12, 2, null, null, 6, 4, null, null, null, null]如下图所示：
8
/ \
12 2
/ \
6 4
- 如果输入的树节点为2和12，则输出的最低公共祖先为树节点8。
- 如果输入的树节点为2和6，则输出的最低公共祖先为树节点2。
思路
考虑在左子树和右子树中查找这两个节点，如果两个节点分别位于左子树和右子树，则最低公共祖先为自己(root)，若左子树中两个节点都找不到，说明最低公共祖先一定在右子树中，反之在左子树。考虑到二叉树的递归特性，因此可以通过递归来求得。
时间复杂度
$O(n)$
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root) return NULL;
if (root == p || root == q) return root;
TreeNode* l = lowestCommonAncestor(root->left, p, q);
TreeNode* r = lowestCommonAncestor(root->right, p, q);
if (l && r) return root;
if (l) return l;
return r;
}
};
