剑指Offer

  1. 剑指 Offer 03. 数组中重复的数字
    1. Solution
  2. 剑指 Offer 04. 二维数组中的查找
    1. 菜鸡第一印象-暴力法
    2. 大神点拨-站在右上角看,这个矩阵其实就像是一个BST
    3. 总结
  3. 剑指 Offer 05. 替换空格
    1. Solution - 额外字符串reserve版本
    2. Solution - 精打细算 resize原地
  4. 剑指 Offer 06. 从尾到头打印链表
    1. Solution - 两次遍历
    2. Solution - 递归
    3. Solution - 栈
  5. 剑指 Offer 07. 重建二叉树
    1. Solution
  6. 剑指 Offer 09. 用两个栈实现队列
    1. Solution - 版本1 拷贝多
    2. Solution - 版本2 减少了拷贝
  7. 剑指 Offer 10- I. 斐波那契数列
    1. Solution
  8. 剑指 Offer 10- II. 青蛙跳台阶问题
    1. Solution
  9. 剑指 Offer 11. 旋转数组的最小数字
    1. Solution - 暴力法
    2. Solution - 二分 (一个排序好的数组, 虽然打乱一次 但仍应该首先考虑二分)
  10. 剑指 Offer 12. 矩阵中的路径
    1. Solution - dfs
  11. 剑指 Offer 13. 机器人的运动范围
    1. Solution - dfs
  12. 剑指 Offer 14- I. 剪绳子
    1. Solution - dp
  13. 剑指 Offer 15. 二进制中1的个数
    1. Solution - 右移运算符 循环M次 M为二进制位数和 负数会出错导致死循环
    2. Solution - 解决负数的一种方法
    3. Solution - 更加高效的 循环M次 M为二进制1的位数
  14. 剑指 Offer 16. 数值的整数次方
    1. Solution - 快速幂
    2. Solution - 快速幂 减少空间 去除vector
  15. 剑指 Offer 18. 删除链表的节点
    1. Solution 爆栈Warning
    2. Solution - 保存last
  16. 剑指 Offer 20. 表示数值的字符串
    1. Solution if else - 我愿称其为最强题目 尝试了N遍才过
    2. Solution - 自动状态机
  17. 剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
    1. Solution - 代码不简洁版本 双指针
    2. Solution - 使用continue简化边界判断 双指针
    3. Solution - 快慢指针
  18. 剑指 Offer 22. 链表中倒数第k个节点
    1. Solution - 依旧是解决链表问题的通用方法 快慢指针
  19. 剑指 Offer 24. 反转链表
    1. Solution1 - 代码过长的递归
    2. Solution2 - 代码简洁的递归
    3. Solution - 双指针 又双叒叕
  20. 剑指 Offer 25. 合并两个排序的链表
    1. Solution - 未使用虚拟头结点 代码较长且重复
    2. Solution - 使用虚拟头结点 代码大幅简洁 去除了重复片段
  21. 剑指 Offer 26. 树的子结构
    1. Solution - 先序遍历
    2. Solution - 简洁了一些 但我认为一个ifelse比一个函数调用更加高效
  22. 剑指 Offer 27. 二叉树的镜像
    1. Solution - 递归
    2. Solution - 迭代
  23. 剑指 Offer 28. 对称的二叉树
    1. Solution - 递归
    2. Solution - 迭代
  24. 剑指 Offer 29. 顺时针打印矩阵
    1. Solution - 额外MN空间
    2. Solution - 边界控制 不使用额外空间
  25. 剑指 Offer 31. 栈的压入、弹出序列
    1. Solution1 - X一样长的代码
    2. Solution2 - 大佬精简的代码
  26. 剑指 Offer 32 - I. 从上到下打印二叉树
    1. Solution - deque
  27. 剑指 Offer 32 - II. 从上到下打印二叉树 II
    1. Solution - 使用nullptr标记
    2. - 使用for循环 提前保存变量解决size会改变的问题
  28. 剑指 Offer 32 - III. 从上到下打印二叉树 III
    1. Solution - 设置标志位
    2. Solution - 使用reverse
  29. 剑指 Offer 33. 二叉搜索树的后序遍历序列
    1. Solution - 递归
    2. Solution - 迭代 栈
  30. 剑指 Offer 34. 二叉树中和为某一值的路径
    1. Solution - 回溯法
  31. 剑指 Offer 37. 序列化二叉树
    1. Solution
  32. 剑指 Offer 38. 字符串的排列 - 30MIN
    1. Solution
    2. Solution - 改进版 - 源字符串上swap
  33. 剑指 Offer 39. 数组中出现次数超过一半的数字 - 20MIN
    1. Solution - Map统计次数
    2. Solution - sort排序 中间位置元素为结果
    3. Solution - 摩尔投票法
  34. 剑指 Offer 40. 最小的k个数
    1. Solution - 维护最大堆 O(nlogk) O(k)
    2. Solution - 基于快排分区思想 O(n) O(logn)
  35. 剑指 Offer 41. 数据流中的中位数 - 30MIN
    1. Solution 最大堆 + 最小堆 求中位数
  36. 剑指 Offer 42. 连续子数组的最大和 - 5MIN
    1. Solution
  37. 剑指 Offer 45. 把数组排成最小的数
    1. Solution - 遇事不决dfs 超时..
    2. Solution - 特殊的排序(另类的comp函数)
  38. 剑指 Offer 46. 把数字翻译成字符串
    1. Solution - 遇事不决dfs
    2. Solution - DP
  39. 剑指 Offer 47. 礼物的最大价值
    1. Solution - 备忘录 接近超时
    2. Solution - dp table 接近100%
  40. 剑指 Offer 48. 最长不含重复字符的子字符串
    1. Solution - 双指针 + hash表
    2. Solution - Dp + hash表
  41. 剑指 Offer 49. 丑数
    1. Solution - 逐个计算 超时
    2. Solution - 生成丑数
  42. 剑指 Offer 50. 第一个只出现一次的字符
    1. Solution
  43. 剑指 Offer 51. 数组中的逆序对
    1. Solution - 归并排序 求逆序对
  44. 剑指 Offer 52. 两个链表的第一个公共节点
    1. Solution - 相遇
  45. 剑指 Offer 53 - II. 0~n-1中缺失的数字
    1. Solution - 二分法
  46. 剑指 Offer 54. 二叉搜索树的第k大节点
    1. Solution - 中序遍历得到递增序列
    2. Solution - 先右再左的中序遍历 得到的是递减序列!!
  47. 剑指 Offer 55 - I. 二叉树的深度
    1. Solution - bfs + nullptr
    2. dfs 第一个想出来的竟然不是这个…
  48. 剑指 Offer 55 - II. 平衡二叉树
    1. Solution
  49. 剑指 Offer 56 - I. 数组中数字出现的次数
    1. Solution - xor 以及xor分组
  50. 剑指 Offer 56 - II. 数组中数字出现的次数 II
    1. Solution - 二进制位出现次数 % 3
    2. Solution - 状态机
  51. 剑指 Offer 57. 和为s的两个数字
    1. Solution - 双指针 O(n) O(1)
    2. Solution - 如果题目是无序数组 用Hash表 O(n) O(n)
  52. 剑指 Offer 57 - II. 和为s的连续正数序列
    1. Solution - 滑动窗口
  53. 剑指 Offer 58 - I. 翻转单词顺序
    1. Solution
  54. 剑指 Offer 59 - I. 滑动窗口的最大值
    1. Solution
  55. 剑指 Offer 59 - II. 队列的最大值
    1. Solution
  56. 剑指 Offer 60. n个骰子的点数
    1. Solution - 暴力法
    2. Solution - 动态规划
  57. 剑指 Offer 61. 扑克牌中的顺子
    1. Solution
  58. 剑指 Offer 63. 股票的最大利润
    1. Solution - 动态规划
  59. 剑指 Offer 64. 求1+2+…+n
    1. Solution - sizeof代替乘法 + 短路运算控制返回
  60. 剑指 Offer 65. 不用加减乘除做加法
    1. Solution a + b = x(进位信息 使用 & << 1) + y(本位信息 使用 xor)
  61. 剑指 Offer 68 - I. 二叉搜索树的最近公共祖先
    1. Solution - 读题 利用好每一个条件

剑指 Offer 03. 数组中重复的数字

Difficulty: 简单

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例 1:

输入:
[2, 3, 1, 0, 2, 5, 3]
输出:2 或 3

限制:

2 <= n <= 100000

Solution

Language: ****


剑指 Offer 04. 二维数组中的查找

Difficulty: 中等

在一个 n * m 的二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个高效的函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。

示例:

现有矩阵 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]
]

给定 target = 5,返回 true

给定 target = 20,返回 false

限制:

0 <= n <= 1000

0 <= m <= 1000

注意:本题与主站 240 题相同:

菜鸡第一印象-暴力法

O(nm)

class Solution {
public:
bool findNumberIn2DArray(vector<vector<int>>& matrix, int target)
{
if (matrix.empty() || matrix[0].empty())
{
return false;
}

for (const auto& vec : matrix)
{
if (vec[0] > target)
{
return false;
}
for (const auto& num : vec)
{
if (num == target)
{
return true;
}
if (num > target)
{
break;
}
}
}
return false;
}
};

大神点拨-站在右上角看,这个矩阵其实就像是一个BST

class Solution {
public:
bool findNumberIn2DArray(vector<vector<int>>& matrix, int target)
{
if (matrix.empty() || matrix[0].empty())
{
return false;
}

int row_max = matrix.size();

int column = matrix[0].size() - 1;
int row = 0;

while (row < row_max && column >= 0)
{
if (matrix[row][column] == target)
{
return true;
}
else if (matrix[row][column] > target)
{
column--;
}
else
{
row++;
}
}
return false;
}
};

总结

初看题目, 还是没有详细审题漏掉了每一列都按照从上到下递增的顺序排序. 然后按照暴力法做了出来, 看了眼评论第一上面那句话让我翻回去看了下绝了.

剑指 Offer 05. 替换空格

Difficulty: 简单

请实现一个函数,把字符串 s 中的每个空格替换成”%20”。

示例 1:

输入:s = "We are happy."
输出:"We%20are%20happy."

限制:

0 <= s 的长度 <= 10000

Solution - 额外字符串reserve版本

class Solution {
public:
string replaceSpace(string s)
{
string result;
result.reserve(s.size() * 3);

for (char c : s)
{
if (c == ' ')
{
result.append("%20");
}
else
{
result += c;
}
}

return result;
}
};

Solution - 精打细算 resize原地

class Solution {
public:
string replaceSpace(string s)
{
int num = 0;
for (int i = 0; i < s.size(); ++i)
{
if (s[i] == ' ')
{
num++;
}
}

s.resize(num * 2 + s.size());

int sub = num * 2 + s.size();
for (int i = s.size() - 1; i >= 0; --i)
{
if (s[i] != ' ')
{
sub--;
s[sub] = s[i];
}
else
{
sub -= 3;
s[sub] = '%';
s[sub + 1] = '2';
s[sub + 2] = '0';
}
}
return s;
}
};

剑指 Offer 06. 从尾到头打印链表

Difficulty: 简单

输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回)。

示例 1:

输入:head = [1,3,2]
输出:[2,3,1]

限制:

0 <= 链表长度 <= 10000

Solution - 两次遍历

class Solution {
public:
vector<int> reversePrint(ListNode* head)
{
if (!head)
{
return vector<int>();
}

int length = 0;
ListNode* temp = head;
while (temp)
{
length++;
temp = temp->next;
}

vector<int> result;
result.resize(length);
for (int i = length - 1; i >= 0; --i)
{
result[i] = head->val;
head = head->next;
}
return result;
}
};

Solution - 递归

class Solution {
public:
vector<int> reversePrint(ListNode* head)
{
vector<int> result;
reversePrint(head, &result);
return result;
}

void reversePrint(ListNode* head, vector<int>* result)
{
if (!head)
{
return;
}

reversePrint(head->next, result);
result->push_back(head->val);
}
};

Solution - 栈

class Solution {
public:
vector<int> reversePrint(ListNode* head)
{
stack<ListNode*> sta;

ListNode* temp = head;
while (temp)
{
sta.push(temp);
temp = temp->next;
}

vector<int> result(sta.size());
int sub = 0;
while (!sta.empty())
{
result[sub++] = sta.top()->val;
sta.pop();
}
return result;
}
};

剑指 Offer 07. 重建二叉树

Difficulty: 中等

输入某二叉树的前序遍历和中序遍历的结果,请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如,给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树:

  3
/ \
9 20
/ \
15 7

限制:

0 <= 节点个数 <= 5000

注意:本题与主站 105 题重复:

Solution

class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder)
{
return buildTree(preorder, inorder, 0, 0, inorder.size());
}

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder, int pre_l, int in_l, int in_r)
{
if (in_l == in_r)
{
return nullptr;
}

TreeNode* node = new TreeNode(preorder[pre_l]);

for (int i = in_l; i < in_r; ++i)
{
if (inorder[i] == preorder[pre_l])
{
node->left = buildTree(preorder, inorder, pre_l + 1, in_l, i);
node->right = buildTree(preorder, inorder, pre_l + 1 + i - in_l, i + 1, in_r);
}
}

return node;
}
};

剑指 Offer 09. 用两个栈实现队列

Difficulty: 简单

用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTaildeleteHead ,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,deleteHead 操作返回 -1 )

示例 1:

输入:
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
输出:[null,null,3,-1]

示例 2:

输入:
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
输出:[null,-1,null,null,5,2]

提示:

  • 1 <= values <= 10000
  • 最多会对 appendTail、deleteHead 进行 10000 次调用

Solution - 版本1 拷贝多

class CQueue {
public:
CQueue() {

}

void appendTail(int value)
{
while (!core_stack.empty())
{
int temp = core_stack.top();
core_stack.pop();
temp_stack.push(temp);
}

temp_stack.push(value);
}

int deleteHead()
{
while (!temp_stack.empty())
{
int temp = temp_stack.top();
temp_stack.pop();
core_stack.push(temp);
}

int result = -1;
if (!core_stack.empty())
{
result = core_stack.top();
core_stack.pop();
}
return result;
}

stack<int> temp_stack;
stack<int> core_stack;
};

Solution - 版本2 减少了拷贝

class CQueue {
public:
CQueue() {

}

void appendTail(int value)
{
temp_stack.push(value);
}

int deleteHead()
{
int result = -1;

if (!core_stack.empty())
{
result = core_stack.top();
core_stack.pop();
}
else
{
while (!temp_stack.empty())
{
int temp = temp_stack.top();
temp_stack.pop();
core_stack.push(temp);
}

if (!core_stack.empty())
{
result = core_stack.top();
core_stack.pop();
}
}

return result;
}

stack<int> temp_stack;
stack<int> core_stack;
};

剑指 Offer 10- I. 斐波那契数列

Difficulty: 简单

写一个函数,输入 n ,求斐波那契(Fibonacci)数列的第 n 项(即 F(N))。斐波那契数列的定义如下:

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

斐波那契数列由 0 和 1 开始,之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。

示例 1:

输入:n = 2
输出:1

示例 2:

输入:n = 5
输出:5

提示:

  • 0 <= n <= 100

Solution

class Solution {
public:
int fib(int n)
{
int arr[max(n + 1, 2)];
arr[0] = 0;
arr[1] = 1;

for (int i = 2; i <= n; ++i)
{
arr[i] = (arr[i - 1] + arr[i - 2]) % 1000000007;
}

return arr[n];
}
};

剑指 Offer 10- II. 青蛙跳台阶问题

Difficulty: 简单

一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。

示例 1:

输入:n = 2
输出:2

示例 2:

输入:n = 7
输出:21

示例 3:

输入:n = 0
输出:1

提示:

  • 0 <= n <= 100

注意:本题与主站 70 题相同:

Solution

class Solution {
public:
int numWays(int n)
{
int dp[max(n + 1, 2)];
dp[0] = 1;
dp[1] = 1;

for (int i = 2; i <= n; ++i)
{
dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007;
}

return dp[n];
}
};

剑指 Offer 11. 旋转数组的最小数字

Difficulty: 简单

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如,数组 [3,4,5,1,2][1,2,3,4,5] 的一个旋转,该数组的最小值为1。  

示例 1:

输入:[3,4,5,1,2]
输出:1

示例 2:

输入:[2,2,2,0,1]
输出:0

注意:本题与主站 154 题相同:

Solution - 暴力法

class Solution {
public:
int minArray(vector<int>& numbers)
{
int result = numbers[0];
for (int i = 0; i < numbers.size() - 1; ++i)
{
if (numbers[i] > numbers[i + 1])
{
result = numbers[i + 1];
break;
}
}

return result;
}
};​

Solution - 二分 (一个排序好的数组, 虽然打乱一次 但仍应该首先考虑二分)

class Solution {
public:
int minArray(vector<int>& numbers)
{
int low = 0;
int high = numbers.size() - 1;

while (low < high)
{
int mid = (low + high) / 2;

if (numbers[mid] > numbers[high])
{
low = mid + 1;
}
else if (numbers[mid] < numbers[high])
{
high = mid;
}
else
{
high--;
}
}
return numbers[low];
}
};

剑指 Offer 12. 矩阵中的路径

Difficulty: 中等

请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始,每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格,那么该路径不能再次进入该格子。例如,在下面的3×4的矩阵中包含一条字符串“bfce”的路径(路径中的字母用加粗标出)。

[[“a”,”b“,”c”,”e”],
[“s”,”f“,”c“,”s”],
[“a”,”d”,”e“,”e”]]

但矩阵中不包含字符串“abfb”的路径,因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后,路径不能再次进入这个格子。

示例 1:

输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出:true

示例 2:

输入:board = [["a","b"],["c","d"]], word = "abcd"
输出:false

提示:

  • 1 <= board.length <= 200
  • 1 <= board[i].length <= 200

注意:本题与主站 79 题相同:

Solution - dfs

Language: ****

class Solution {
public:
bool exist(vector<vector<char>>& board, string word)
{
for (int i = 0; i < board.size(); ++i)
{
for (int j = 0; j < board[0].size(); ++j)
{
if (word[0] == board[i][j])
{
if (exist(board, word, i, j, 0))
{
return true;
}
}
}
}
return false;
}

bool exist(vector<vector<char>>& board, const string& word, int x, int y, int sub)
{
if (sub >= word.size())
{
return true;
}

if (x < 0 || y < 0 || x >= board.size() || y >= board[0].size())
{
return false;
}

if (board[x][y] == ' ')
{
return false;
}

if (board[x][y] != word[sub])
{
return false;
}

char back = board[x][y];
board[x][y] = ' ';

if (exist(board, word, x + 1, y, sub + 1) ||
exist(board, word, x, y + 1, sub + 1) ||
exist(board, word, x - 1, y, sub + 1) ||
exist(board, word, x, y - 1, sub + 1))
{
return true;
}

board[x][y] = back;

return false;
}
};

剑指 Offer 13. 机器人的运动范围

Difficulty: 中等

地上有一个m行n列的方格,从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动,它每次可以向左、右、上、下移动一格(不能移动到方格外),也不能进入行坐标和列坐标的数位之和大于k的格子。例如,当k为18时,机器人能够进入方格 [35, 37] ,因为3+5+3+7=18。但它不能进入方格 [35, 38],因为3+5+3+8=19。请问该机器人能够到达多少个格子?

示例 1:

输入:m = 2, n = 3, k = 1
输出:3

示例 2:

输入:m = 3, n = 1, k = 0
输出:1

提示:

  • 1 <= n,m <= 100
  • 0 <= k <= 20

Solution - dfs

class Solution {
public:
bool Check(int x, int y, int k)
{
int temp = 0;

while (x != 0)
{
temp += x % 10;
x /= 10;
}
while (y != 0)
{
temp += y % 10;
y /= 10;
}
return temp <= k;
}

int movingCount(int m, int n, int k)
{
vector<vector<int>> vec(m, vector<int>(n, 0));
return movingCount(vec, 0, 0, k);
}

constexpr static int SS = 4;
int xx[SS] = {1, -1, 0, 0};
int yy[SS] = {0, 0, 1, -1};

int movingCount(vector<vector<int>>& vec, int x, int y, int k)
{
if (!Check(x, y, k))
{
return 0;
}

if (x < 0 || y < 0 || x >= vec.size() || y >= vec[0].size())
{
return 0;
}

if (vec[x][y] == 1)
{
return 0;
}
vec[x][y] = 1;
int result = 1;

for (int i = 0; i < SS; ++i)
{
result += movingCount(vec, x + xx[i], y + yy[i], k);
}

return result;
}
};

剑指 Offer 14- I. 剪绳子

Difficulty: 中等

给你一根长度为 n 的绳子,请把绳子剪成整数长度的 m 段(m、n都是整数,n>1并且m>1),每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0]*k[1]*...*k[m-1] 可能的最大乘积是多少?例如,当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到的最大乘积是18。

示例 1:

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1

示例 2:

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

提示:

  • 2 <= n <= 58

注意:本题与主站 343 题相同:

Solution - dp

class Solution
{
public:
int cuttingRope(int n)
{
int* dp = new int[n + 1]{};
// 初始状态
dp[2] = 1;
// 状态转移方程
for(int i = 3; i < n + 1; i++)
{
for(int j = 2; j < i; j++)
{
dp[i] = max(dp[i], max(j * dp[i-j], j * (i - j)));
}
}
// 返回值
return dp[n];
}
};

剑指 Offer 15. 二进制中1的个数

Difficulty: 简单

请实现一个函数,输入一个整数(以二进制串形式),输出该数二进制表示中 1 的个数。例如,把 9 表示成二进制是 1001,有 2 位是 1。因此,如果输入 9,则该函数输出 2。

示例 1:

输入:00000000000000000000000000001011
输出:3
解释:输入的二进制串 00000000000000000000000000001011 中,共有三位为 '1'。

示例 2:

输入:00000000000000000000000010000000
输出:1
解释:输入的二进制串 00000000000000000000000010000000 中,共有一位为 '1'。

示例 3:

输入:11111111111111111111111111111101
输出:31
解释:输入的二进制串 11111111111111111111111111111101 中,共有 31 位为 '1'。

提示:

  • 输入必须是长度为 32二进制串

注意:本题与主站 191 题相同:

Solution - 右移运算符 循环M次 M为二进制位数和 负数会出错导致死循环

class Solution {
public:
int hammingWeight(uint32_t n)
{
int result = 0;

while (n != 0)
{
result += n & 1;
n = n >> 1;
}
return result;
}
};

Solution - 解决负数的一种方法

class Solution
{
public:
int hammingWeight(uint32_t n)
{

}
}

Solution - 更加高效的 循环M次 M为二进制1的位数

class Solution {
public:
int hammingWeight(uint32_t n)
{
int result = 0;

while (n != 0)
{
result++;
n &= n - 1;
}
return result;
}
};

把一个整数减去1之后再和原来的整数作&运算, 得到的结果相当于将二进制表示中的最右边一个1变成0

剑指 Offer 16. 数值的整数次方

Difficulty: 中等

实现函数double Power(double base, int exponent),求base的exponent次方。不得使用库函数,同时不需要考虑大数问题。

示例 1:

输入: 2.00000, 10
输出: 1024.00000

示例 2:

输入: 2.10000, 3
输出: 9.26100

示例 3:

输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25

说明:

  • -100.0 < x < 100.0
  • n 是 32 位有符号整数,其数值范围是 [−231, 231 − 1] 。

注意:本题与主站 50 题相同:

Solution - 快速幂

class Solution {
public:
double myPow(double x, int n)
{
if (n == 0)
{
return 1;
}

bool flag = true;
if (n > 0)
{
flag = false;
n = -n;
}

double result = x;
vector<double> ex;
while (n < -1)
{
if (n % 2 == -1)
{
ex.push_back(result);
}
result *= result;
n = n / 2;
}

while (!ex.empty())
{
result *= ex.back();
ex.pop_back();
}

if (flag)
{
result = 1 / result;
}

return result;
}
};

Solution - 快速幂 减少空间 去除vector

class Solution {
public:
double myPow(double x, int n)
{
if (n == 0)
{
return 1;
}

bool flag = true;
if (n > 0)
{
flag = false;
n = -n;
}

double result = x;
double ex = 1.0;
while (n < -1)
{
if (n % 2 == -1)
{
ex *= result;
}
result *= result;
n = n / 2;
}

result *= ex;

if (flag)
{
result = 1 / result;
}

return result;
}
};

剑指 Offer 18. 删除链表的节点

Difficulty: 简单

给定单向链表的头指针和一个要删除的节点的值,定义一个函数删除该节点。

返回删除后的链表的头节点。

注意:此题对比原题有改动

示例 1:

输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点,那么在调用了你的函数之后,该链表应变为 4 -> 1 -> 9.

示例 2:

输入: head = [4,5,1,9], val = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点,那么在调用了你的函数之后,该链表应变为 4 -> 5 -> 9.

说明:

  • 题目保证链表中节点的值互不相同
  • 若使用 C 或 C++ 语言,你不需要 freedelete 被删除的节点

Solution 爆栈Warning

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* deleteNode(ListNode* head, int val)
{
if (!head)
{
return nullptr;
}

if (head->val == val)
{
return head->next;
}

head->next = deleteNode(head->next, val);
return head;
}
};

Solution - 保存last

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* deleteNode(ListNode* head, int val)
{
if (!head)
{
return nullptr;
}

if (head->val == val)
{
return head->next;
}

ListNode* last = head;
ListNode* temp = head->next;

while (temp)
{
if (temp->val == val)
{
last->next = temp->next;
}
last = temp;
temp = temp->next;
}

return head;
}
};

剑指 Offer 20. 表示数值的字符串

Difficulty: 中等

请实现一个函数用来判断字符串是否表示数值(包括整数和小数)。例如,字符串”+100”、”5e2”、”-123”、”3.1416”、”-1E-16”、”0123”都表示数值,但”12e”、”1a3.14”、”1.2.3”、”+-5”及”12e+5.4”都不是。

Solution if else - 我愿称其为最强题目 尝试了N遍才过

class Solution {
public:
bool isNumber(string s)
{
int begin = 0;
int end = s.size();
bool num = false;

// 去除开头结尾空格
while (begin < end && s[begin] == ' ')
{
begin++;
}
while (end > begin && s[end - 1] == ' ')
{
end--;
}
int sub = begin;

// + - 打头直接去掉
if (s[sub] == '+' || s[sub] == '-')
{
sub++;
}

// 判断+-之后是否有小数点
bool has_point = false;
if (s[sub] == '.')
{
has_point = true;
sub++;
}

// 正常数字判断
while (sub < end)
{
if (s[sub] == '.')
{
if (has_point)
{
return false; // 小数点只能出现一次
}
has_point = true;
}
else if (s[sub] >= '0' && s[sub] <= '9')
{
num = true; // 是一个数字
}
else
{
break;
}
sub++;
}

// 科学计数法判断 E或e 不作为第一个或者最后一个字符
if (sub > begin && sub < end - 1 && (s[sub] == 'e' || s[sub] == 'E'))
{
sub++;

// 去掉E e之后紧接着的 +- 必须 +-只有还有数字
if ((s[sub] == '+' || s[sub] == '-') && sub < end - 1)
{
sub++;
}

while (sub < end && s[sub] >= '0' && s[sub] <= '9')
{
sub++;
}
}
return num && sub == end; // 含数字且已经遍历完毕
}
};

Solution - 自动状态机


剑指 Offer 21. 调整数组顺序使奇数位于偶数前面

Difficulty: 简单

输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶数位于数组的后半部分。

示例:

输入:nums = [1,2,3,4]
输出:[1,3,2,4]
注:[3,1,2,4] 也是正确的答案之一。

提示:

  1. 0 <= nums.length <= 50000
  2. 1 <= nums[i] <= 10000

Solution - 代码不简洁版本 双指针

class Solution {
public:
vector<int> exchange(vector<int>& nums)
{
if (nums.empty())
{
return nums;
}

int begin = 0;
int end = nums.size() - 1;

while (begin < end)
{
while (nums[end] % 2 == 0)
{
end--;
if (begin > end)
{
return nums;
}
}

if (nums[begin] % 2 == 0)
{
swap(nums[begin], nums[end--]);
}
else
{
begin++;
}
}
return nums;
}
};

Solution - 使用continue简化边界判断 双指针

class Solution {
public:
vector<int> exchange(vector<int>& nums)
{
int left = 0;
int right = nums.size() - 1;

while (left < right)
{
if ((nums[left] & 1) != 0)
{
left ++;
continue;
}
if ((nums[right] & 1) != 1)
{
right --;
continue;
}
swap(nums[left++], nums[right--]);
}
return nums;
}
};

Solution - 快慢指针

class Solution {
public:
vector<int> exchange(vector<int>& nums)
{
int slow = 0;
int fast = 0;

while (fast < nums.size())
{
if ((nums[fast] & 1) == 0)
{
fast++;
continue;
}
swap(nums[slow++], nums[fast++]);
}
return nums;
}
};

慢指针负责指向偶数, 当快指针寻找到奇数时 进行替换 然后两者都向前移动

不过这个代码存在原地tp的问题 极端情况下如果全是奇数则会替换size次

剑指 Offer 22. 链表中倒数第k个节点

Difficulty: 简单

输入一个链表,输出该链表中倒数第k个节点。为了符合大多数人的习惯,本题从1开始计数,即链表的尾节点是倒数第1个节点。

例如,一个链表有 6 个节点,从头节点开始,它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

示例:

给定一个链表: 1->2->3->4->5, 和 k = 2.

返回链表 4->5.

Solution - 依旧是解决链表问题的通用方法 快慢指针

class Solution {
public:
ListNode* getKthFromEnd(ListNode* head, int k)
{
if (!head)
{
return nullptr;
}

ListNode* fast = head;
for (int i = 0; i < k; ++i)
{
fast = fast->next;
}

ListNode* slow = head;
while (fast)
{
slow = slow->next;
fast = fast->next;
}
return slow;
}
};

判断链表环依然采用快慢指针, 快指针一次走两步 注意判断两次fast不为nullptr 当fast==low的时候说明有环

判断环长度, 第一次相遇后 到 第二次相遇 慢指针走的次数即为长度. 快指针在相遇后正好比慢指针多走一圈

1->2->3->4

1->2->3->4->5

取中间节点 快指针走两步 慢指针走一步 当快指针无法走两步的时候 慢指针所指为中间

剑指 Offer 24. 反转链表

Difficulty: 简单

定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

限制:

0 <= 节点个数 <= 5000

注意:本题与主站 206 题相同:

Solution1 - 代码过长的递归

/**
* 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)
{
return nullptr;
}

ListNode* new_head = nullptr;
ListNode* front = reverse(head, &new_head);
front->next = nullptr;

return new_head;
}

ListNode* reverse(ListNode* node, ListNode** head)
{
if (!node)
{
return nullptr;
}

ListNode* front = reverse(node->next, head);
if (front)
{
front->next = node;
}
else
{
*head = node;
}
return node;
}
};

Solution2 - 代码简洁的递归

class Solution {
public:
ListNode* reverseList(ListNode* head)
{
if (!head || !head->next)
{
return head;
}

ListNode* ret = reverseList(head->next);

head->next->next = head;
head->next = nullptr;
return ret;
}
};

首先S2开头的!head->next的判断减少了一次了递归 同时也简化了S1中的front的判断 不会有空指针.

然后S1使用的返回值 返回的下一个节点. 然而实际上下一个节点已经可以通过本节点的next访问 通过next->next来倒转指向

这样将返回值省了出来 返回原链表的尾结点 作为新的头结点

Solution - 双指针 又双叒叕

class Solution {
public:
ListNode* reverseList(ListNode* head)
{
if (!head)
{
return nullptr;
}

ListNode* node2 = head->next;
ListNode* node1 = head;

node1->next = nullptr;

ListNode* back = nullptr;
while (node2)
{
back = node2->next;

node2->next = node1;
node1 = node2;

node2 = back;
}
return node1;
}
};

剑指 Offer 25. 合并两个排序的链表

Difficulty: 简单

输入两个递增排序的链表,合并这两个链表并使新链表中的节点仍然是递增排序的。

示例1:

输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4

限制:

0 <= 链表长度 <= 1000

注意:本题与主站 21 题相同:

Solution - 未使用虚拟头结点 代码较长且重复

class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2)
{
if (!l1)
{
return l2;
}

if (!l2)
{
return l1;
}

ListNode* ret = nullptr;
if (l1->val < l2->val)
{
ret = l1;
l1 = l1->next;
}
else
{
ret = l2;
l2 = l2->next;
}

ListNode* node = ret;
while (l1 || l2)
{
if (!l1)
{
node->next = l2;
break;
}
if (!l2)
{
node->next = l1;
break;
}

if (l1->val < l2->val)
{
node->next = l1;
l1 = l1->next;
}
else
{
node->next = l2;
l2 = l2->next;
}
node = node->next;
}
return ret;
}
};

Solution - 使用虚拟头结点 代码大幅简洁 去除了重复片段

class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2)
{
ListNode* dumy = new ListNode(0);

ListNode* node = dumy;
while (l1 || l2)
{
if (!l1)
{
node->next = l2;
break;
}
if (!l2)
{
node->next = l1;
break;
}

if (l1->val < l2->val)
{
node->next = l1;
l1 = l1->next;
}
else
{
node->next = l2;
l2 = l2->next;
}
node = node->next;
}
return dumy->next;
}
};

使用了虚拟头结点 直接简化了重复片段 tql

剑指 Offer 26. 树的子结构

Difficulty: 中等

输入两棵二叉树A和B,判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构, 即 A中有出现和B相同的结构和节点值。

例如:
给定的树 A:

     3     / \    4   5   / \  1   2
给定的树 B:

   4    /  1
返回 true,因为 B 与 A 的一个子树拥有相同的结构和节点值。

示例 1:

输入:A = [1,2,3], B = [3,1]
输出:false

示例 2:

输入:A = [3,4,5,1,2], B = [4,1]
输出:true

限制:

0 <= 节点个数 <= 10000

Solution - 先序遍历

class Solution {
public:
bool isSubStructure(TreeNode* A, TreeNode* B)
{
if (!A || !B)
{
return false;
}

if (A->val == B->val)
{
if (cmpTree(A, B))
{
return true;
}
}

return isSubStructure(A->left, B) ||
isSubStructure(A->right, B);
}

bool cmpTree(TreeNode* A, TreeNode* B)
{
if (!B)
{
return true;
}
if (!A)
{
return false;
}

if (A->val == B->val)
{
return cmpTree(A->left, B->left) && cmpTree(A->right, B->right);
}
return false;
}
};

Solution - 简洁了一些 但我认为一个ifelse比一个函数调用更加高效

class Solution {
public:
bool isSubStructure(TreeNode* A, TreeNode* B)
{
if (!A || !B)
{
return false;
}

return cmpTree(A, B) || isSubStructure(A->left, B) ||
isSubStructure(A->right, B);
}

bool cmpTree(TreeNode* A, TreeNode* B)
{
if (!B)
{
return true;
}
if (!A)
{
return false;
}

return (A->val == B->val) && cmpTree(A->left, B->left) && cmpTree(A->right, B->right);
}
};

剑指 Offer 27. 二叉树的镜像

Difficulty: 简单

请完成一个函数,输入一个二叉树,该函数输出它的镜像。

例如输入:

     4    /   \   2     7  / \   / \ 1   3 6   9
镜像输出:

     4    /   \   7     2  / \   / \ 9   6 3   1

示例 1:

输入:root = [4,2,7,1,3,6,9]
输出:[4,7,2,9,6,3,1]

限制:

0 <= 节点个数 <= 1000

注意:本题与主站 226 题相同:

Solution - 递归

class Solution {
public:
TreeNode* mirrorTree(TreeNode* root)
{
if (!root)
{
return nullptr;
}

swap(root->left, root->right);

mirrorTree(root->left);
mirrorTree(root->right);

return root;
}
};

Solution - 迭代

class Solution {
public:
TreeNode* mirrorTree(TreeNode* root)
{
if (!root)
{
return nullptr;
}

deque<TreeNode*> nodes;
nodes.push_back(root);

while (!nodes.empty())
{
TreeNode* node = nodes.front();
nodes.pop_front();
swap(node->left, node->right);

if (node->left)
{
nodes.push_back(node->left);
}
if (node->right)
{
nodes.push_back(node->right);
}
}

return root;
}
};

剑指 Offer 28. 对称的二叉树

Difficulty: 简单

请实现一个函数,用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样,那么它是对称的。

例如,二叉树 [1,2,2,3,4,4,3] 是对称的。

    1    / \   2   2  / \ / \ 3  4 4  3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

    1    / \   2   2    \   \    3    3

示例 1:

输入:root = [1,2,2,3,4,4,3]
输出:true

示例 2:

输入:root = [1,2,2,null,3,null,3]
输出:false

限制:

0 <= 节点个数 <= 1000

注意:本题与主站 101 题相同:

Solution - 递归

class Solution {
public:
bool isSymmetric(TreeNode* root)
{
if (!root)
{
return true;
}

return solve(root->left, root->right);
}

bool solve(TreeNode* lhs, TreeNode* rhs)
{
if (!lhs && !rhs)
{
return true;
}
if (!lhs || !rhs)
{
return false;
}

if (lhs->val == rhs->val)
{
return solve(lhs->left, rhs->right) && solve(lhs->right, rhs->left);
}
return false;
}
};

Solution - 迭代

class Solution {
public:
bool isSymmetric(TreeNode* root)
{
if (!root)
{
return true;
}

list<TreeNode*> nodes;
nodes.push_back(root->left);
nodes.push_back(root->right);

while (!nodes.empty())
{
TreeNode* node1 = nodes.front();
nodes.pop_front();
TreeNode* node2 = nodes.front();
nodes.pop_front();

if (!node1 && !node2)
{
continue;
}
else if (node1 && node2)
{
if (node1->val != node2->val)
{
return false;
}
nodes.push_back(node1->left);
nodes.push_back(node2->right);
nodes.push_back(node1->right);
nodes.push_back(node2->left);
}
else
{
return false;
}
}
return true;
}
};

剑指 Offer 29. 顺时针打印矩阵

Difficulty: 简单

输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字。

示例 1:

输入:matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出:[1,2,3,6,9,8,7,4,5]

示例 2:

输入:matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出:[1,2,3,4,8,12,11,10,9,5,6,7]

限制:

  • 0 <= matrix.length <= 100
  • 0 <= matrix[i].length <= 100

注意:本题与主站 54 题相同:

Solution - 额外MN空间

class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix)
{
if (matrix.empty() || matrix[0].empty())
{
return vector<int>();
}

const int MX = matrix.size();
const int MY = matrix[0].size();
vector<vector<int>> flags(MX, vector<int>(MY, 0));

int x = 0, y = 0;

vector<int> result;
result.reserve(MX * MY);

int xx[] = {0, 1, 0, -1};
int yy[] = {1, 0, -1, 0};

int i = 0;

while (x >= 0 && y >= 0 && x < MX && y < MY && flags[x][y] != 1)
{
for (;x >= 0 && y >= 0 && x < MX && y < MY && flags[x][y] != 1;
x += xx[i], y += yy[i])
{
flags[x][y] = 1;
result.push_back(matrix[x][y]);
}

x -= xx[i];
y -= yy[i];

i = (i + 1) % 4;

x += xx[i];
y += yy[i];
}
return result;
}
};

Solution - 边界控制 不使用额外空间

class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix)
{
if (matrix.empty() || matrix[0].empty())
{
return vector<int>();
}

const int MX = matrix.size();
const int MY = matrix[0].size();

vector<int> result;
result.reserve(MX * MY);

int xx[] = {0, 1, 0, -1};
int yy[] = {1, 0, -1, 0};

// int nn[] = {1, 0, 0, 0};
// int ee[] = {0, -1, 0, 0};
// int ss[] = {0, 0, -1, 0};
// int ww[] = {0, 0, 0, 1};

int i = 0;
int x = 0, y = 0;

int e = MY, s = MX, w = 0, n = 0;

while (x >= n && y >= w && x < s && y < e)
{
for (;x >= n && y >= w && x < s && y < e;
x += xx[i], y += yy[i])
{
result.push_back(matrix[x][y]);
}

x -= xx[i];
y -= yy[i];


// n += nn[i];
// e += ee[i];
// s += ss[i]; 更短的写法
// w += ww[i];

if (i == 0)
{
n++;
}
else if (i == 1)
{
e--;
}
else if (i == 2)
{
s--;
}
else
{
w++;
}

i = (i + 1) % 4;
x += xx[i];
y += yy[i];
}
return result;
}
};

剑指 Offer 31. 栈的压入、弹出序列

Difficulty: 中等

输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如,序列 {1,2,3,4,5} 是某栈的压栈序列,序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列,但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。

示例 1:

输入:pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出:true
解释:我们可以按以下顺序执行:
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

示例 2:

输入:pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出:false
解释:1 不能在 2 之前弹出。

提示:

  1. 0 <= pushed.length == popped.length <= 1000
  2. 0 <= pushed[i], popped[i] < 1000
  3. pushed 是 popped 的排列。

注意:本题与主站 946 题相同:

Solution1 - X一样长的代码

class Solution {
public:
bool validateStackSequences(vector<int>& pushed, vector<int>& popped)
{
stack<int> lstack;

int i = 0, j = 0;

while (i < pushed.size() && j < popped.size())
{
while (!lstack.empty())
{
if (lstack.top() == popped[j])
{
lstack.pop();
j++;
}
else
{
break;
}
}
if (pushed[i] == popped[j])
{
i++;
j++;
}
else
{
lstack.push(pushed[i]);
i++;
}
}

while (!lstack.empty())
{
if (lstack.top() == popped[j])
{
lstack.pop();
j++;
}
else
{
return false;
}
}
return true;
}
};

Solution2 - 大佬精简的代码

class Solution {
public:
bool validateStackSequences(vector<int>& pushed, vector<int>& popped)
{
stack<int> lstack;

int j = 0;
for (int num : pushed)
{
lstack.push(num);

while (!lstack.empty() && lstack.top() == popped[j])
{
lstack.pop();
j++;
}
}
return j == popped.size();
}
};

精简思路

源代码是栈不为空的时候 比较栈顶和popped[i]

如果相等则出栈

如果不相等 转去判断pushed当前元素popped[i]

如果两者相等则后移

如果两者不相等则入栈当前元素.

实际上这里就可以直接入栈元素然后再判断,如果相等了就出栈 如果不相等也恰好入栈了

剑指 Offer 32 - I. 从上到下打印二叉树

Difficulty: 中等

从上到下打印出二叉树的每个节点,同一层的节点按照从左到右的顺序打印。

例如:
给定二叉树: [3,9,20,null,null,15,7],

  3
/ \
9 20
/ \
15 7

返回:

[3,9,20,15,7]

提示:

  1. 节点总数 <= 1000

Solution - deque

class Solution {
public:
vector<int> levelOrder(TreeNode* root)
{
if (!root)
{
return {};
}
deque<TreeNode*> nodes;

nodes.push_back(root);

vector<int> result;
while (!nodes.empty())
{
TreeNode* node = nodes.front();
nodes.pop_front();

result.push_back(node->val);

if (node->left)
{
nodes.push_back(node->left);
}
if (node->right)
{
nodes.push_back(node->right);
}
}
return result;
}
};

剑指 Offer 32 - II. 从上到下打印二叉树 II

Difficulty: 简单

从上到下按层打印二叉树,同一层的节点按从左到右的顺序打印,每一层打印到一行。

例如:
给定二叉树: [3,9,20,null,null,15,7],

  3
/ \
9 20
/ \
15 7

返回其层次遍历结果:

[
[3],
[9,20],
[15,7]
]

提示:

  1. 节点总数 <= 1000

注意:本题与主站 102 题相同:

Solution - 使用nullptr标记

class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root)
{
if (!root)
{
return {};
}

deque<TreeNode*> nodes;

nodes.push_back(root);
nodes.push_back(nullptr);

vector<vector<int>> result;
result.push_back(vector<int>());

while (!nodes.empty())
{
TreeNode* node = nodes.front();
nodes.pop_front();

if (node)
{
result.back().push_back(node->val);
if (node->left)
{
nodes.push_back(node->left);
}
if (node->right)
{
nodes.push_back(node->right);
}
}
else
{
if (!nodes.empty())
{
result.push_back(vector<int>());
nodes.push_back(nullptr);
}
}
}

return result;
}
};

首先想出的就是这个方法

- 使用for循环 提前保存变量解决size会改变的问题

class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root)
{
if (!root)
{
return {};
}

deque<TreeNode*> nodes;

nodes.push_back(root);

vector<vector<int>> result;

while (!nodes.empty())
{
result.push_back(vector<int>());

int ss = nodes.size();
for (int i = 0; i < ss; ++i)
{
TreeNode* node = nodes.front();
nodes.pop_front();

result.back().push_back(node->val);
if (node->left)
{
nodes.push_back(node->left);
}
if (node->right)
{
nodes.push_back(node->right);
}
}
}

return result;
}
};

写完S1就去看了看题解 没想到还有这种方法, 妙蛙种子在米奇妙妙屋吃妙脆角

剑指 Offer 32 - III. 从上到下打印二叉树 III

Difficulty: 中等

请实现一个函数按照之字形顺序打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右到左的顺序打印,第三行再按照从左到右的顺序打印,其他行以此类推。

例如:
给定二叉树: [3,9,20,null,null,15,7],

  3
/ \
9 20
/ \
15 7

返回其层次遍历结果:

[
[3],
[20,9],
[15,7]
]

提示:

  1. 节点总数 <= 1000

Solution - 设置标志位

class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root)
{
if (!root)
{
return {};
}

deque<TreeNode*> nodes;
nodes.push_back(root);

bool right = true;

vector<vector<int>> result;

while (!nodes.empty())
{
result.emplace_back();

int SS = nodes.size();

if (right)
{
right = false;
for (int i = 0; i < SS; ++i)
{
TreeNode* node = nodes.front();
nodes.pop_front();
result.back().push_back(node->val);

if (node->left)
{
nodes.push_back(node->left);
}
if (node->right)
{
nodes.push_back(node->right);
}
}
}
else
{
right = true;
for (int i = SS - 1; i >= 0; --i)
{
TreeNode* node = nodes.back();
nodes.pop_back();
result.back().push_back(node->val);

if (node->right)
{
nodes.push_front(node->right);
}
if (node->left)
{
nodes.push_front(node->left);
}
}
}
}
return result;
}
};​

Solution - 使用reverse

class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root)
{
if (!root)
{
return {};
}

deque<TreeNode*> nodes;
nodes.push_back(root);

vector<vector<int>> result;
bool even = false;

while (!nodes.empty())
{
result.emplace_back();

int SS = nodes.size();

vector<int>& tmp = result.back();
for (int i = 0; i < SS; ++i)
{
TreeNode* node = nodes.front();
nodes.pop_front();
tmp.push_back(node->val);

if (node->left)
{
nodes.push_back(node->left);
}
if (node->right)
{
nodes.push_back(node->right);
}
}

if (even)
{
std::reverse(tmp.begin(), tmp.end());
}
even = !even;
}
return result;
}
};

剑指 Offer 33. 二叉搜索树的后序遍历序列

Difficulty: 中等

输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true,否则返回 false。假设输入的数组的任意两个数字都互不相同。

参考以下这颗二叉搜索树:

    5
/ \
2 6
/ \
1 3

示例 1:

输入: [1,6,3,2,5]
输出: false

示例 2:

输入: [1,3,2,6,5]
输出: true

提示:

  1. 数组长度 <= 1000

Solution - 递归

class Solution {
public:
bool verifyPostorder(vector<int>& postorder)
{
return verifyPostorder(postorder, 0, postorder.size());
}

bool verifyPostorder(vector<int>& postorder, int begin, int end)
{
if (end - begin <= 2)
{
return true;
}

int root_sub = end - 1;
int r_begin = begin;
for (int i = begin; i < root_sub; ++i)
{
if (postorder[i] < postorder[root_sub])
{
r_begin++;
}
else
{
break;
}
}

for (int i = r_begin; i < root_sub; ++i)
{
if (postorder[i] < postorder[root_sub])
{
return false;
}
}
return verifyPostorder(postorder, begin, r_begin) &&
verifyPostorder(postorder, r_begin, root_sub);
}
};

睡前来一道, 这是我第一次 一次通过的剑指里面的中等题目-_- 睡了睡了

Solution - 迭代 栈

剑指 Offer 34. 二叉树中和为某一值的路径

Difficulty: 中等

输入一棵二叉树和一个整数,打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

示例:
给定如下二叉树,以及目标和 sum = 22

      5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1

返回:

[
[5,4,11,2],
[5,8,4,5]
]

提示:

  1. 节点总数 <= 10000

注意:本题与主站 113 题相同:

Solution - 回溯法

class Solution {
public:

vector<int> path;
vector<vector<int>> result;

vector<vector<int>> pathSum(TreeNode* root, int sum)
{
dfs(root, sum);

return result;
}

void dfs(TreeNode* root, int sum)
{
if (!root)
{
return;
}

path.push_back(root->val);
if (sum == root->val && !root->left && !root->right)
{
result.push_back(path);
}
else
{
dfs(root->left, sum - root->val);
dfs(root->right, sum - root->val);
}
path.pop_back();
}
};

剑指 Offer 37. 序列化二叉树

Difficulty: 困难

请实现两个函数,分别用来序列化和反序列化二叉树。

**示例: **

你可以将以下二叉树:

1
/ \
2 3
/ \
4 5

序列化为 "[1,2,3,null,null,4,5]"

注意:本题与主站 297 题相同:

Solution

class Codec {
public:

// Encodes a tree to a single string.
string serialize(TreeNode* root)
{
if (!root)
{
return "[null]";
}

deque<TreeNode*> nodes;
nodes.push_back(root);

string result;
while (!nodes.empty())
{
TreeNode* node = nodes.front();
nodes.pop_front();
if (node)
{
result += "," + to_string(node->val);
nodes.push_back(node->left);
nodes.push_back(node->right);
}
else
{
result += ",null";
}
}

result[0] = '[';
result += ']';
return result;
}

// Decodes your encoded data to tree.
TreeNode* deserialize(string data)
{
deque<TreeNode*> nodes;
ParseData(data, nodes);

TreeNode* ret = nodes.front();
nodes.pop_front();

if (nodes.size() == 0)
{
return ret;
}

deque<TreeNode*> temp_nodes;
temp_nodes.push_back(ret);

while (!temp_nodes.empty())
{
const int SS = temp_nodes.size();

if (nodes.size() < SS * 2)
{
break;
}

for (int i = 0; i < SS; ++i)
{
TreeNode* node = temp_nodes.front();
temp_nodes.pop_front();

node->left = nodes.front();
nodes.pop_front();
node->right = nodes.front();
nodes.pop_front();

if (node->left)
{
temp_nodes.push_back(node->left);
}
if (node->right)
{
temp_nodes.push_back(node->right);
}
}
}

return ret;
}

void ParseData(const string& data, deque<TreeNode*>& nodes)
{
int i = 1;

int num = 0;
bool empty = false;
int flag = 1; // -

while (i < data.size())
{
char c = data[i++];

if (c >= '0' && c <= '9')
{
num = num * 10 + c - '0';
}
else if (c == ',' || c == ']')
{
if (empty)
{
nodes.push_back(nullptr);
empty = false;
}
else
{
nodes.push_back(new TreeNode(num * flag));
num = 0;
flag = 1;
}
}
else if (c == 'n')
{
empty = true;
}
else if (c == '-')
{
flag = -1;
}
}
}
};​

剑指 Offer 38. 字符串的排列 - 30MIN

Difficulty: 中等

输入一个字符串,打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组,但里面不能有重复元素。

示例:

输入:s = "abc"
输出:["abc","acb","bac","bca","cab","cba"]

限制:

1 <= s 的长度 <= 8

Solution

class Solution {
public:

vector<string> result;

vector<string> permutation(string s)
{
std::string temp;
temp.resize(s.size());

permutation(s, 0, temp);
return result;
}

void permutation(string& s, int sub, std::string& temp)
{
if (sub == s.size())
{
result.push_back(temp);
return;
}

char flag['z' - 'A' + 1]{};
for (int i = 0; i < s.size(); ++i)
{
char back = s[i];
if (back != '#')
{
if (flag[back - 'A'] == 0)
{
flag[back - 'A'] = 1;
temp[sub] = s[i];

s[i] = '#';
permutation(s, sub + 1, temp);
s[i] = back;
}
}
}
}
};

代码中防止重复的代码太巧了, 自己一开始使用的set去重. 然后看到了题解的剪枝方法 在每一层中一个字母仅能出现一次, 时间消耗大幅下降了

Solution - 改进版 - 源字符串上swap

class Solution {
public:

vector<string> result;

vector<string> permutation(string s)
{
permutation(s, 0);
return result;
}

void permutation(string& s, int sub)
{
if (sub == s.size() - 1) // 仅剩一个字符 该字符正好位于末尾 直接保存
{
result.push_back(s);
return;
}

char flag['z' - 'A' + 1]{};
for (int i = sub; i < s.size(); ++i) // 从本层开始 sub之前的字符已经被使用了
{
char back = s[i];

if (flag[back - 'A'] == 0)
{
flag[back - 'A'] = 1;

swap(s[i], s[sub]); // 交换未使用元素到本层位置
permutation(s, sub + 1);
swap(s[i], s[sub]);
}
}
}
};

由于是全排列, 其实可以将未使用元素挨个的交换到本层位置 这样本层位置之前的字符是使用过的.

剑指 Offer 39. 数组中出现次数超过一半的数字 - 20MIN

Difficulty: 简单

数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。

你可以假设数组是非空的,并且给定的数组总是存在多数元素。

示例 1:

输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2

限制:

1 <= 数组长度 <= 50000

注意:本题与主站 169 题相同:

Solution - Map统计次数

int majorityElement(vector<int>& nums)
{
map<int, int> times;

int end_time = nums.size() / 2;

for (auto& num : nums)
{
times[num]++;
if (times[num] > end_time)
{
return num;
}
}
return 0;
}

Solution - sort排序 中间位置元素为结果

int majorityElement(vector<int>& nums)
{
sort(nums.begin(), nums.end());

return nums[nums.size() / 2];
}

Solution - 摩尔投票法

int majorityElement(vector<int>& nums)
{
int vote = nums[0];
int sum = 0;

for (auto& num : nums)
{
sum += vote == num ? 1 : -1;
if (sum < 0)
{
vote = num;
sum = 1;
}
}

// int times = 0;
// for (auto& num : nums)
// {
// times += num == vote ? 1 : 0;
// }
// 如果可能不存在结果 则需要进行验证
return vote;
}

剑指 Offer 40. 最小的k个数

Difficulty: 简单

输入整数数组 arr ,找出其中最小的 k 个数。例如,输入4、5、1、6、2、7、3、8这8个数字,则最小的4个数字是1、2、3、4。

示例 1:

输入:arr = [3,2,1], k = 2
输出:[1,2] 或者 [2,1]

示例 2:

输入:arr = [0,1,2,1], k = 1
输出:[0]

限制:

  • 0 <= k <= arr.length <= 10000
  • 0 <= arr[i] <= 10000

Solution - 维护最大堆 O(nlogk) O(k)

class Solution {
public:

priority_queue<int> min_heap;

void TryToAdd(int num, int k)
{
if (min_heap.size() < k)
{
min_heap.push(num);
}
else
{
if (num < min_heap.top())
{
min_heap.pop();
min_heap.push(num);
}
}
}

vector<int> getLeastNumbers(vector<int>& arr, int k)
{
if (k <= 0)
{
return {};
}

for (auto num : arr)
{
TryToAdd(num, k);
}

vector<int> result(k);
for (int i = 0; i < k; ++i)
{
result[i] = min_heap.top();
min_heap.pop();
}
return result;
}
};

Solution - 基于快排分区思想 O(n) O(logn)

class Solution {
public:

vector<int> getLeastNumbers(vector<int>& arr, int k)
{
if (k == 0)
{
return {};
}
Partition(arr, 0, arr.size() - 1, k);

return vector<int>(arr.begin(), arr.begin() + k);
}

int Partition(vector<int>& arr, int left , int right, int k)
{
if (right - left <= 0)
{
return left;
}
int ret = left;

int index = ret + 1;

for (int i = index; i <= right; ++i)
{
if (arr[i] < arr[ret])
{
swap(arr[index], arr[i]);
index++;
}
}
swap(arr[index - 1], arr[ret]);
int part = index - 1;

if (part == k)
{
return part;
}
else if (part < k)
{
return Partition(arr, part + 1, right, k);
}
else
{
return Partition(arr, left, part - 1, k);
}
}
};

剑指 Offer 41. 数据流中的中位数 - 30MIN

Difficulty: 困难

如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。

例如,

[2,3,4] 的中位数是 3

[2,3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构:

  • void addNum(int num) - 从数据流中添加一个整数到数据结构中。
  • double findMedian() - 返回目前所有元素的中位数。

示例 1:

输入:
["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
[[],[1],[2],[],[3],[]]
输出:[null,null,null,1.50000,null,2.00000]

示例 2:

输入:
["MedianFinder","addNum","findMedian","addNum","findMedian"]
[[],[2],[],[3],[]]
输出:[null,null,2.00000,null,2.50000]

限制:

  • 最多会对 addNum、findMedian 进行 50000 次调用。

注意:本题与主站 295 题相同:

Solution 最大堆 + 最小堆 求中位数

class MedianFinder {
public:

priority_queue<int, vector<int>, greater<int>> min_heap;
priority_queue<int> max_heap;
int size = 0;

/** initialize your data structure here. */
MedianFinder() {

}

void addNum(int num)
{
if (size == 0)
{
min_heap.push(num);
}
else
{
if (size % 2 == 0)
{
if (num > max_heap.top())
{
min_heap.push(num);
}
else
{
max_heap.push(num);
min_heap.push(max_heap.top());
max_heap.pop();
}
}
else
{
if (num < min_heap.top())
{
max_heap.push(num);
}
else
{
min_heap.push(num);
max_heap.push(min_heap.top());
min_heap.pop();
}
}
}
size++;
}

double findMedian()
{
if (size % 2 == 0)
{
return (max_heap.top() + min_heap.top()) / 2.0;
}
else
{
return min_heap.top();
}
}
};

最开始写的时候堆的调整写在了findMedian里面, 实际应该写在addNum这样函数的功能才分工明确 而且由于两个堆大小基本平衡效率更高

剑指 Offer 42. 连续子数组的最大和 - 5MIN

Difficulty: 简单

输入一个整型数组,数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

示例1:

输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。

提示:

  • 1 <= arr.length <= 10^5
  • -100 <= arr[i] <= 100

注意:本题与主站 53 题相同:

Solution

class Solution {
public:
int maxSubArray(vector<int>& nums)
{
int sum = 0;
int ret = nums[0];
for (auto& num : nums)
{
if (sum >= 0)
{
sum += num;
}
else
{
sum = num;
}
ret = max(sum, ret);
}
return ret;
}
};

剑指 Offer 45. 把数组排成最小的数

Difficulty: 中等

输入一个非负整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。

示例 1:

输入: [10,2]
输出: "102"

示例 2:

输入: [3,30,34,5,9]
输出: "3033459"

提示:

  • 0 < nums.length <= 100

说明:

  • 输出结果可能非常大,所以你需要返回一个字符串而不是整数
  • 拼接起来的数字可能会有前导 0,最后结果不需要去掉前导 0

Solution - 遇事不决dfs 超时..

class Solution {
public:

string minNumber(vector<int>& nums)
{
string result;
string temp;
dfs(nums, 0, result, temp);
return result;
}

void dfs(vector<int>& nums, int sub, string& result, string& temp)
{
if (!result.empty() && result.compare(temp) < 0) // 剪枝
{
return;
}

if (sub == nums.size())
{
if (result.empty() || result.compare(temp) > 0)
{
result = temp;
}
return;
}

set<int> exist;
for (int i = sub; i < nums.size(); ++i)
{
auto iter = exist.lower_bound(nums[i]); // 剪枝
if (iter == exist.end() || *iter != nums[i])
{
exist.insert(iter, nums[i]);

swap(nums[i], nums[sub]);

string num = to_string(nums[sub]);
temp += num;

dfs(nums, sub + 1, result, temp);

temp.erase(temp.end() - num.size(), temp.end());

swap(nums[i], nums[sub]);
}
}
}
};

Solution - 特殊的排序(另类的comp函数)

class Solution {
public:

void QuickSort(vector<string>& strs, int left, int right)
{
if (right - left <= 0)
{
return;
}

auto comp =
[](const string& lhs, const string& rhs)
{
return lhs + rhs < rhs + lhs;
};

int pivot = left;

int index = left + 1;
for (int i = index; i <= right; ++i)
{
if (comp(strs[i], strs[pivot]))
{
swap(strs[i], strs[index]);
index++;
}
}
swap(strs[pivot], strs[index - 1]);

// int le = left;
// int ri = right;

// while (le < ri)
// {
// while (le < ri && !comp(strs[ri], strs[pivot]))
// {
// ri--;
// }
// while (le < ri && comp(strs[le], strs[pivot]))
// {
// le++;
// }
// swap(strs[le], strs[ri]);
// }
// swap(strs[le], strs[pivot]);

QuickSort(strs, left, index - 2);
QuickSort(strs, index, right);
}

string minNumber(vector<int>& nums)
{
vector<string> strs;
strs.reserve(nums.size());

for (int num : nums)
{
strs.push_back(to_string(num));
}

QuickSort(strs, 0, strs.size() - 1);

string result;
for (const auto& str : strs)
{
result += str;
}
return result;
}
};

剑指 Offer 46. 把数字翻译成字符串

Difficulty: 中等

给定一个数字,我们按照如下规则把它翻译为字符串:0 翻译成 “a” ,1 翻译成 “b”,……,11 翻译成 “l”,……,25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数,用来计算一个数字有多少种不同的翻译方法。

示例 1:

输入: 12258
输出: 5
解释: 12258有5种不同的翻译,分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"

提示:

  • 0 <= num < 2<sup>31</sup>

Solution - 遇事不决dfs

class Solution {
public:
int translateNum(int num)
{
string num_str = to_string(num);

return dfs(num_str, 0);
}

int dfs(const string& str, int sub)
{
if (sub > str.size())
{
return 0;
}
else if (sub >= str.size() - 1)
{
return 1;
}

int time = 0;
if (sub < str.size() - 1 && str[sub] == '1')
{
time += dfs(str, sub + 2);
}
else if (sub < str.size() - 1 && str[sub] == '2' &&
str[sub + 1] >= '0' && str[sub + 1] <= '5')
{
time += dfs(str, sub + 2);
}

time += dfs(str, sub + 1);

return time;
}
};

Solution - DP

class Solution {
public:
int translateNum(int num)
{
string num_str = to_string(num);

vector<int> dp(num_str.size() + 1);
dp[0] = 1;
dp[1] = 1;

for (int i = 2; i <= num_str.size(); ++i)
{
dp[i] = dp[i - 1];

if (num_str[i - 2] == '1')
{
dp[i] += dp[i - 2];
}
else if (num_str[i - 2] == '2' && num_str[i - 1] >= '0' && num_str[i - 1] <= '5')
{
dp[i] += dp[i - 2];
}
}
return dp[num_str.size()];
}
};

可以对dp数组进行降维打击 易读性也被降维打击了

class Solution {
public:
int translateNum(int num)
{
string num_str = to_string(num);

int a = 1; // i - 2
int b = 1; // i - 1
int dp = b; // i

for (int i = 2; i <= num_str.size(); ++i)
{
dp = b;

if (num_str[i - 2] == '1')
{
dp += a;
}
else if (num_str[i - 2] == '2' && num_str[i - 1] >= '0' && num_str[i - 1] <= '5')
{
dp += a;
}
a = b;
b = dp;
}
return dp;
}
};

dp[0]=1这点没有考虑到, 本来设置的为0.

然而当num为25的时候dp[2]应该为2, 所以必须把dp[0]设置为1

状态转移方程dp[i] = dp[i - 1] + dp[i - 2](i-1和i-2字符需要能连接) 是因为如果把i-1和i-2连接有dp[i-2]

如果不连接则有dp[i - 1]种 所以最终是二者之和

可以对str字符串进行降维打击 易读性又双被降维打击了

class Solution {
public:
int translateNum(int num)
{
int a = 1; // i - 2
int b = 1; // i - 1
int dp = b; // i

int last_s = num % 10;
int now_s;
num /= 10;

while (num != 0)
{
now_s = num % 10;
num /= 10;

dp = b;

int temp = now_s * 10 + last_s;
if (temp >= 10 && temp <= 25)
{
dp += a;
}

a = b;
b = dp;

last_s = now_s;
}
return dp;
}
};

剑指 Offer 47. 礼物的最大价值

Difficulty: 中等

在一个 m*n 的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于 0)。你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值,请计算你最多能拿到多少价值的礼物?

示例 1:

输入: 
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物

提示:

  • 0 < grid.length <= 200
  • 0 < grid[0].length <= 200

Solution - 备忘录 接近超时

class Solution {
public:
int maxValue(vector<vector<int>>& grid)
{
return dfs(grid, 0, 0);
}

std::map<std::string, int> bwl;
int dfs(const vector<vector<int>>& grid, int x, int y)
{
if (x == grid.size() - 1 && y == grid[0].size() - 1)
{
return grid[x][y];
}

std::string key = to_string(x) + "," + to_string(y);
auto iter = bwl.find(key);
if (iter != bwl.end())
{
return iter->second;
}

int r = 0;
int d = 0;
if (x < grid.size() - 1 && y < grid[0].size())
{
r = dfs(grid, x + 1, y);
}
if (y < grid[0].size() - 1 && x < grid.size())
{
d = dfs(grid, x, y + 1);
}

int result = max(r, d) + grid[x][y];
bwl[key] = result;
return result;
}
};

Solution - dp table 接近100%

class Solution {
public:
int maxValue(vector<vector<int>>& grid)
{
const int XS = grid.size();
const int YS = grid[0].size();

vector<vector<int>> dp(XS + 1, vector<int>(YS + 1, 0));

for (int x = 1; x <= XS; ++x)
{
for (int y = 1; y <= YS; ++y)
{
dp[x][y] = max(dp[x - 1][y], dp[x][y - 1]) + grid[x - 1][y - 1];
}
}
return dp[XS][YS];
}
};

剑指 Offer 48. 最长不含重复字符的子字符串

Difficulty: 中等

请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。

示例 1:

输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。

示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
  请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。

提示:

  • s.length <= 40000

注意:本题与主站 3 题相同:

Solution - 双指针 + hash表

class Solution {
public:
int lengthOfLongestSubstring(string s)
{
if (s.empty())
{
return 0;
}

int begin = 0;
int end = 0;
int hash[128]{};
for (int i = 0; i < 128; ++i)
{
hash[i] = -1;
}

int ret = 1;
for (;end < s.size(); ++end)
{
char c = s[end];
if (hash[c] >= begin)
{
int len = end - begin;
ret = max(len, ret);
begin = hash[c] + 1;
}
hash[c] = end;
}
ret = max(end - begin, ret);
return ret;
}
};
class Solution {
public:
int lengthOfLongestSubstring(string s)
{
int begin = 0;
int end = 0;
int hash[128]{};
for (int i = 0; i < 128; ++i)
{
hash[i] = -1;
}

int ret = 0;
for (;end < s.size(); ++end)
{
char c = s[end];
if (hash[c] >= begin)
{
begin = hash[c] + 1;
}
ret = max(end - begin + 1, ret);
hash[c] = end;
}
return ret;
}
};

简化版, hash[c] >= begin主要是更细begin指针, 而更新ret的可以放一起. 原版是end在重复的字符上进行取长度, 新版则是end未在重复字符上 所以需要长度 + 1

Solution - Dp + hash表

class Solution {
public:
int lengthOfLongestSubstring(string s)
{
int hash[128]{};
vector<int> dp(s.size() + 1);
dp[0] = 0;
int begin = 1;
int ret = 0;
for(int i = 1; i <= s.size(); ++i)
{
char c = s[i - 1];
if (hash[c] >= begin)
{
dp[i] = i - hash[c];
begin = hash[c] + 1;
}
else
{
dp[i] = dp[i - 1] + 1;
}
hash[c] = i;
ret = max(ret, dp[i]);
}
return ret;
}
};

剑指 Offer 49. 丑数

Difficulty: 中等

我们把只包含质因子 2、3 和 5 的数称作丑数(Ugly Number)。求按从小到大的顺序的第 n 个丑数。

示例:

输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

**说明: ** 

  1. 1 是丑数。
  2. n 不超过1690。

注意:本题与主站 264 题相同:

Solution - 逐个计算 超时

class Solution {
public:
int nthUglyNumber(int n)
{
if (n <= 1)
{
return 1;
}

unordered_set<int> ugly_num;
vector<int> bases = {2, 3, 5};
ugly_num.insert(1);

int k = 1;
int num = 1;
while (k < n)
{
num++;
for (int base : bases)
{
if (num % base == 0 && ugly_num.find(num / base) != ugly_num.end())
{
ugly_num.insert(num);
k++;
break;
}
}
}
return num;
}
};

Solution - 生成丑数

class Solution {
public:
int nthUglyNumber(int n)
{
int dp[n];
dp[0] = 1;
int a = 0, b = 0, c = 0;
for (int i = 1; i < n; ++i)
{
int numa = dp[a] * 2;
int numb = dp[b] * 3;
int numc = dp[c] * 5;

int min_abc = min(numa, min(numb, numc));
dp[i] = min_abc;
if (min_abc == numa)
{
a++;
}
if (min_abc == numb)
{
b++;
}
if (min_abc == numc)
{
c++;
}
}
return dp[n - 1];
}
};

每个新的丑数都是已有丑数的2 3 5倍, 需要按循序将这些丑数排好. 如果一个数字已经提供过了新的丑数, 那么就应该有这个新的丑数尝试去提供, 否则一定是重复的 对应了

代码中的a++ b++ c++, 每次取出最小的丑数添加到结果中

剑指 Offer 50. 第一个只出现一次的字符

Difficulty: 简单

在字符串 s 中找出第一个只出现一次的字符。如果没有,返回一个单空格。 s 只包含小写字母。

示例:

s = "abaccdeff"
返回 "b"

s = ""
返回 " "

限制:

0 <= s 的长度 <= 50000

Solution

class Solution {
public:
char firstUniqChar(string s)
{
if (s.empty())
{
return ' ';
}

int hash2[26]{};
for (int i = 0; i < 26; ++i)
{
hash2[i] = -1;
}

for (int i = 0; i < s.size(); ++i)
{
int c = s[i] - 'a';

if (hash2[c] == -1)
{
hash2[c] = i; // 标记第一次出现的位置
}
else
{
hash2[c] = -2;
}
}

int min_sub = -1;
int min = INT_MAX;
for (int i = 0; i < 26; ++i)
{
if (hash2[i] >= 0 && hash2[i] < min)
{
min = hash2[i];
min_sub = i;
}
}
if (min_sub == -1)
{
return ' ';
}

char result = 'a' + min_sub;
return result;
}
};

剑指 Offer 51. 数组中的逆序对

Difficulty: 困难

在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。

示例 1:

输入: [7,5,6,4]
输出: 5

限制:

0 <= 数组长度 <= 50000

Solution - 归并排序 求逆序对

class Solution {
public:
int reversePairs(vector<int>& nums)
{
vector<int> temp(nums.size());
return MergeSort(nums, temp, 0, nums.size() - 1);
}

int MergeSort(vector<int>& nums, vector<int>& temp, int left, int right)
{
if (left >= right)
{
return 0;
}

int mid = (left + right) / 2;

int result = 0;

result += MergeSort(nums, temp, left, mid);
result += MergeSort(nums, temp, mid + 1, right);

int temp_i = left;
int i = left;
int j = mid + 1;
int begin_j = j;
while (i <= mid && j <= right)
{
if (nums[i] <= nums[j])
{
temp[temp_i++] = nums[i];
i++;
result += (j - begin_j);

}
else
{
temp[temp_i++] = nums[j];
j++;
}
}
for (;i <= mid; ++i)
{
temp[temp_i++] = nums[i];
result += (j - begin_j);
}
for (; j <= right; ++j)
{
temp[temp_i++] = nums[j];
}
std::copy(temp.begin() + left, temp.begin() + right + 1, nums.begin() + left);

return result;
}
};

剑指 Offer 52. 两个链表的第一个公共节点

Difficulty: 简单

输入两个链表,找出它们的第一个公共节点。

如下面的两个链表

在节点 c1 开始相交。

示例 1:

输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出:Reference of the node with value = 8
输入解释:相交节点的值为 8 (注意,如果两个列表相交则不能为 0)。从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为 [5,0,1,8,4,5]。在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。

示例 2:

输入:intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出:Reference of the node with value = 2
输入解释:相交节点的值为 2 (注意,如果两个列表相交则不能为 0)。从各自的表头开始算起,链表 A 为 [0,9,1,2,4],链表 B 为 [3,2,4]。在 A 中,相交节点前有 3 个节点;在 B 中,相交节点前有 1 个节点。

示例 3:

输入:intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出:null
输入解释:从各自的表头开始算起,链表 A 为 [2,6,4],链表 B 为 [1,5]。由于这两个链表不相交,所以 intersectVal 必须为 0,而 skipA 和 skipB 可以是任意值。
解释:这两个链表不相交,因此返回 null。

注意:

  • 如果两个链表没有交点,返回 null.
  • 在返回结果后,两个链表仍须保持原有的结构。
  • 可假定整个链表结构中没有循环。
  • 程序尽量满足 O(n) 时间复杂度,且仅用 O(1) 内存。
  • 本题与主站 160 题相同:

Solution - 相遇

class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
{
if (!headA || !headB)
{
return nullptr;
}
ListNode* temp_a = headA;
ListNode* temp_b = headB;

while (temp_a->next || temp_b->next)
{
if (temp_a == temp_b)
{
return temp_a;
}
temp_a = temp_a->next ? temp_a->next : headB;

temp_b = temp_b->next ? temp_b->next : headA;
}
return temp_a == temp_b ? temp_a : nullptr;
}
};

这里踩了一个坑, 我开始是修改了next指针 首先题目不允许修改 其次修改之后会影响另一个指针的判断, 因为修改的这个node很可能是共享的node

class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
{
ListNode* temp_a = headA;
ListNode* temp_b = headB;

while (temp_a != temp_b)
{
temp_a = temp_a ? temp_a->next : headB;
temp_b = temp_b ? temp_b->next : headA;
}
return temp_a;
}
};

退出条件优化了, 两种可能一种是二者相遇了 一种是二者都为空指针 这样代码能简化很多

剑指 Offer 53 - II. 0~n-1中缺失的数字

Difficulty: 简单

一个长度为n-1的递增排序数组中的所有数字都是唯一的,并且每个数字都在范围0~n-1之内。在范围0~n-1内的n个数字中有且只有一个数字不在该数组中,请找出这个数字。

示例 1:

输入: [0,1,3]
输出: 2

示例 2:

输入: [0,1,2,3,4,5,6,7,9]
输出: 8

限制:

1 <= 数组长度 <= 10000

Solution - 二分法

class Solution {
public:
int missingNumber(vector<int>& nums)
{
if (nums[0] != 0)
{
return 0;
}

int ret = find(nums, 0, nums.size() - 1);
if (ret == -1)
{
return nums[nums.size() - 1] + 1;
}
return ret;
}

int find(vector<int>& nums, int left, int right)
{
if (left >= right)
{
return -1;
}

int mid = (left + right) / 2;
if (mid + 1 <= right && nums[mid] == nums[mid + 1] - 2)
{
return nums[mid] + 1;
}
else if (mid - 1 >= left && nums[mid] == nums[mid - 1] + 2)
{
return nums[mid] - 1;
}
else
{
int ret = find(nums, left, mid - 1);
if (ret == -1)
{
ret = find(nums, mid + 1, right);
}
return ret;
}
}
};

没错写了这么长的二分…. 第一印象没有想到迭代版本 如何收缩区间. 索性就两侧都搜索. 实际看了题解才发现

漏掉了一个条件, 当num[i] > i的时候就说明了缺失的数字在左边 反过来就是在右边

class Solution {
public:
int missingNumber(vector<int>& nums)
{
int left = 0;
int right = nums.size() - 1;

while (left <= right)
{
int mid = (left + right) / 2;
if (nums[mid] > mid)
{
right = mid - 1;
}
else if (nums[mid] == mid)
{
left = mid + 1;
}
}
return left;
}
};

题解上面还多了一个判断点 循环结束的时候left位于右子数组的开始 right位于左子数组的结束

结果为右子数组开始元素的下标

0 1 2 3 4 5

0 1 2 3 5 6 // 右子数组 56 左子数组 0 1 2 3 5对应的下标4位答案

剑指 Offer 54. 二叉搜索树的第k大节点

Difficulty: 简单

给定一棵二叉搜索树,请找出其中第k大的节点。

示例 1:

输入: root = [3,1,4,null,2], k = 1
3
/ \
1 4
\
  2
输出: 4

示例 2:

输入: root = [5,3,6,2,4,null,null,1], k = 3
5
/ \
3 6
/ \
2 4
/
1
输出: 4

限制:

1 ≤ k ≤ 二叉搜索树元素个数

Solution - 中序遍历得到递增序列

class Solution {
public:
int kthLargest(TreeNode* root, int k)
{
vector<int> temp;
dfs(root, k, temp);
return temp[temp.size() - k];
}

void dfs(TreeNode* root, int k, vector<int>& temp)
{
if (!root)
{
return 0;
}
dfs(root->left, k, temp);
temp.push_back(root->val);
dfs(root->right, k, temp);
}
};

Solution - 先右再左的中序遍历 得到的是递减序列!!

class Solution {
public:
int result;
int kthLargest(TreeNode* root, int k)
{
dfs(root, k);
return result;
}

void dfs(TreeNode* root, int& k)
{
if (!root)
{
return;
}
dfs(root->right, k);
if (k == 0)
{
return; // 提前返回这里也非常妙啊
}
if (--k == 0)
{
result = root->val;
}
dfs(root->left, k);
}
};

看到题解这句话直接惊呆我了先右再左的中序遍历 得到的是递减序列

还有提前返回的判断

剑指 Offer 55 - I. 二叉树的深度

Difficulty: 简单

输入一棵二叉树的根节点,求该树的深度。从根节点到叶节点依次经过的节点(含根、叶节点)形成树的一条路径,最长路径的长度为树的深度。

例如:

给定二叉树 [3,9,20,null,null,15,7]

  3
/ \
9 20
/ \
15 7

返回它的最大深度 3 。

提示:

  1. 节点总数 <= 10000

注意:本题与主站 104 题相同:

Solution - bfs + nullptr

class Solution {
public:
int maxDepth(TreeNode* root)
{
if (!root)
{
return 0;
}

deque<TreeNode*> nodes;
nodes.push_back(root);
nodes.push_back(nullptr);
int result = 0;

while (!nodes.empty())
{
TreeNode* node = nodes.front();
nodes.pop_front();

if (node == nullptr)
{
if (!nodes.empty())
{
nodes.push_back(nullptr);
}
result++;
continue;
}
if (node->left)
{
nodes.push_back(node->left);
}
if (node->right)
{
nodes.push_back(node->right);
}
}
return result;
}
};

第一印象还是使用了nullptr作为层之间的区分, 前面做过类似的第一印象也是nullptr实际上应该用

for循环更加好 提前取出循环次数, 这样就算更改deque的size也不影响循环次数了

class Solution {
public:
int maxDepth(TreeNode* root)
{
if (!root)
{
return 0;
}

deque<TreeNode*> nodes;
nodes.push_back(root);
int result = 0;

while (!nodes.empty())
{
result++;
const int SS = nodes.size();
for (int i = 0; i < SS; ++i)
{
TreeNode* node = nodes.front();
nodes.pop_front();
if (node->left)
{
nodes.push_back(node->left);
}
if (node->right)
{
nodes.push_back(node->right);
}
}
}
return result;
}
};

dfs 第一个想出来的竟然不是这个…

class Solution {
public:
int maxDepth(TreeNode* root)
{
if (!root)
{
return 0;
}
return max(maxDepth(root->left), maxDepth(root->right)) + 1;
}
};

剑指 Offer 55 - II. 平衡二叉树

Difficulty: 简单

输入一棵二叉树的根节点,判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1,那么它就是一棵平衡二叉树。

示例 1:

给定二叉树 [3,9,20,null,null,15,7]

  3
/ \
9 20
/ \
15 7

返回 true

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]

      1
/ \
2 2
/ \
3 3
/ \
4 4

返回 false

限制:

  • 0 <= 树的结点个数 <= 10000

注意:本题与主站 110 题相同:

Solution

class Solution {
public:
bool isBalanced(TreeNode* root)
{
return depth(root) != -1;
}

int depth(TreeNode* node)
{
if (!node)
{
return 0;
}
int left = depth(node->left);
if (left == -1)
{
return -1;
}

int right = depth(node->right);
if (right == -1)
{
return -1;
}
if (abs(left - right) > 1)
{
return -1;
}
return max(left, right) + 1;
}
};

剑指 Offer 56 - I. 数组中数字出现的次数

Difficulty: 中等

一个整型数组 nums 里除两个数字之外,其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。

示例 1:

输入:nums = [4,1,4,6]
输出:[1,6] 或 [6,1]

示例 2:

输入:nums = [1,2,10,4,1,4,3,3]
输出:[2,10] 或 [10,2]

限制:

  • 2 <= nums.length <= 10000

Solution - xor 以及xor分组

class Solution {
public:
vector<int> singleNumbers(vector<int>& nums)
{
int xor_result = 0;
for (int num : nums)
{
xor_result ^= num;
}

int bit_1 = 1;
while ((xor_result & 1) == 0)
{
xor_result = xor_result >> 1;
bit_1++;
}

int xor_1 = 0;
int xor_2 = 0;
bit_1--;
for (int num : nums)
{
int bit_1_temp = (num >> bit_1) & 1;

if (bit_1_temp == 1)
{
xor_1 ^= num;
}
else
{
xor_2 ^= num;
}
}
return {xor_1, xor_2};
}
};

第一印象看到这个题目想到了用xor运算, 然而却没有想到如何将两个不同的数字分开.

看了题解发现 第一次xor出来的xor_result 如果是11101则说明两个不同的数字的右数第一位不同. 这样通过

其他数字的最后一位是1还是0就能分成两个数组 然后分别xor

class Solution {
public:
vector<int> singleNumbers(vector<int>& nums)
{
int xor_result = 0;
for (int num : nums)
{
xor_result ^= num;
}

int bit_1 = 1;
while ((xor_result & bit_1) == 0)
{
bit_1 = bit_1 << 1; // 通过逻辑左移取位
}

int xor_1 = 0;
int xor_2 = 0;
for (int num : nums)
{
if (num & bit_1) // 这里也变了
{
xor_1 ^= num;
}
else
{
xor_2 ^= num;
}
}
return {xor_1, xor_2};
}
};

剑指 Offer 56 - II. 数组中数字出现的次数 II

Difficulty: 中等

在一个数组 nums 中除一个数字只出现一次之外,其他数字都出现了三次。请找出那个只出现一次的数字。

示例 1:

输入:nums = [3,4,3,3]
输出:4

示例 2:

输入:nums = [9,1,7,9,7,9,7]
输出:1

限制:

  • 1 <= nums.length <= 10000
  • 1 <= nums[i] < 2^31

Solution - 二进制位出现次数 % 3

class Solution {
public:
int singleNumber(vector<int>& nums)
{
int bits[32]{};

for (int num : nums)
{
int index = 0;
while (num != 0)
{
bits[index] += num & 1;
num = num >> 1;
index++;
}
}

int result = 0;
for (int i = 0; i < 32; ++i)
{
result = result << 1;
result |= bits[31 - i] % 3;
}
return result;
}
};

Solution - 状态机

剑指 Offer 57. 和为s的两个数字

Difficulty: 简单

输入一个递增排序的数组和一个数字s,在数组中查找两个数,使得它们的和正好是s。如果有多对数字的和等于s,则输出任意一对即可。

示例 1:

输入:nums = [2,7,11,15], target = 9
输出:[2,7] 或者 [7,2]

示例 2:

输入:nums = [10,26,30,31,47,60], target = 40
输出:[10,30] 或者 [30,10]

限制:

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^6

Solution - 双指针 O(n) O(1)

class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target)
{
int le = 0;
int ri = nums.size() - 1;

while (le < ri)
{
int sum = nums[le] + nums[ri];
if (sum == target)
{
return {nums[le], nums[ri]};
}
else if (sum > target)
{
ri--;
}
else
{
le++;
}
}
return {0, 0};
}
};

Solution - 如果题目是无序数组 用Hash表 O(n) O(n)

class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target)
{
unordered_set<int> set;

for (int num : nums)
{
int need = target - num;

auto iter = set.find(need);
if (iter == set.end())
{
set.insert(num);
}
else
{
return {num, *iter};
}
}
return {0, 0};
}
};

剑指 Offer 57 - II. 和为s的连续正数序列

Difficulty: 简单

输入一个正整数 target ,输出所有和为 target 的连续正整数序列(至少含有两个数)。

序列内的数字由小到大排列,不同序列按照首个数字从小到大排列。

示例 1:

输入:target = 9
输出:[[2,3,4],[4,5]]

示例 2:

输入:target = 15
输出:[[1,2,3,4,5],[4,5,6],[7,8]]

限制:

  • 1 <= target <= 10^5

Solution - 滑动窗口

class Solution {
public:
vector<vector<int>> findContinuousSequence(int target)
{
vector<vector<int>> result;
int begin = 1;
int end = 2;
int sum = 3;

while (end < target && begin != end)
{
if (sum == target)
{
result.emplace_back();
vector<int>& vec = result.back();
vec.reserve(end - begin + 1);
for (int i = begin; i <= end; ++i)
{
vec.push_back(i);
}
end++;
sum += end;
}
else if (sum < target)
{
end++;
sum += end;
}
else
{
sum -= begin;
begin++;
}
}
return result;
}
};

剑指 Offer 58 - I. 翻转单词顺序

Difficulty: 简单

输入一个英文句子,翻转句子中单词的顺序,但单词内字符的顺序不变。为简单起见,标点符号和普通字母一样处理。例如输入字符串”I am a student. “,则输出”student. a am I”。

示例 1:

输入: "the sky is blue"
输出: "blue is sky the"

示例 2:

输入: "  hello world!  "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格,但是反转后的字符不能包括。

示例 3:

输入: "a good   example"
输出: "example good a"
解释: 如果两个单词间有多余的空格,将反转后单词间的空格减少到只含一个。

说明:

  • 无空格字符构成一个单词。
  • 输入字符串可以在前面或者后面包含多余的空格,但是反转后的字符不能包括。
  • 如果两个单词间有多余的空格,将反转后单词间的空格减少到只含一个。

注意:本题与主站 151 题相同:

注意:此题对比原题有改动

Solution

class Solution {
public:
string reverseWords(string s)
{
if (s.empty())
{
return "";
}

int begin = 0;
int end = s.size();
while (begin < s.size() && s[begin] == ' ')
{
begin++;
}
while (end >= 1 && s[end - 1] == ' ')
{
end--;
}
if (begin >= end)
{
return "";
}
reverse(s.begin() + begin, s.begin() + end);

int word_begin = begin;
for (int i = begin; i < end; ++i)
{
if (s[i] == ' ')
{
int word_end = i;
reverse(s.begin() + word_begin, s.begin() + word_end);
word_begin = i + 1;
}
}
reverse(s.begin() + word_begin, s.begin() + end);

string result;
result.reserve(end - begin);
for (int i = begin; i < end; ++i)
{
if (s[i] == ' ')
{
if (result[result.size() - 1] != ' ')
{
result.append(1, ' ');
}
}
else
{
result.append(1, s[i]);
}
}
return result;
}
};

我用的解法是先翻转整个字符串 然后再把单词翻转过来 这样组成结果

实际上可以直接从尾部遍历, 然后一个单词一个单词的拼接出结果

class Solution {
public:
string reverseWords(string s)
{
int begin = 0;
int end = s.size();
while (begin < s.size() && s[begin] == ' ')
{
begin++;
}
while (end >= 1 && s[end - 1] == ' ')
{
end--;
}
if (begin >= end)
{
return "";
}
string result;
result.reserve(end - begin);

int i = end - 1;
int j = end;
while (i >= begin)
{
while (i >= begin && s[i] != ' ')
{
i--;
}
result.append(s.begin() + i + 1, s.begin() + j);
result.append(1, ' '); // 注意这里 第一个参数数量 第二个是字符 反过来也能运行 但是结果出错
while (i >= begin && s[i] == ' ')
{
i--;
}
j = i + 1;
}
return result.substr(0, result.size() - 1);
}
};

剑指 Offer 59 - I. 滑动窗口的最大值

Difficulty: 简单

给定一个数组 nums 和滑动窗口的大小 k,请找出所有滑动窗口里的最大值。

示例:

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:

滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7

提示:

你可以假设 k 总是有效的,在输入数组不为空的情况下,1 ≤ k ≤ 输入数组的大小。

注意:本题与主站 239 题相同:

Solution

class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k)
{
if (nums.empty())
{
return {};
}
vector<int> result;
result.reserve(nums.size() - k + 1);

int temp_i = 0;
for (int i = 1; i < k; ++i)
{
if (nums[i] > nums[temp_i])
{
temp_i = i;
}
}
result.push_back(nums[temp_i]);

int left = 1;
int right = k;
while (right < nums.size())
{
if (left > temp_i)
{
temp_i = left;
for (int j = left + 1; j <= right; ++j)
{
if (nums[j] > nums[temp_i])
{
temp_i = j;
}
}
}
else
{
if (nums[right] > nums[temp_i])
{
temp_i = right;
}
}
result.push_back(nums[temp_i]);
left++;
right++;
}
return result;
}
};

实际不用在将最大元素移出时进行遍历, 可以采用如下方式, 添加一个deque来解决. 这样能保证获取最大元素为O(1)

class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k)
{
if (nums.empty())
{
return {};
}
vector<int> result;
result.reserve(nums.size() - k + 1);

deque<int> window;
for (int i = 0; i < k; ++i)
{
while (!window.empty() && nums[window.back()] < nums[i])
{
window.pop_back();
}
window.push_back(i);
}
result.push_back(nums[window.front()]);

for (int i = k; i < nums.size(); ++i)
{
if (i - k + 1 > window.front()) // 移除已经滑动出去的值
{
window.pop_front();
}

while (!window.empty() && nums[window.back()] < nums[i]) // 每次添加元素前将小于其的元素移除 保证队列内有序
{
window.pop_back();
}
window.push_back(i);
result.push_back(nums[window.front()]);
}
return result;
}
};

剑指 Offer 59 - II. 队列的最大值

Difficulty: 中等

请定义一个队列并实现函数 max_value 得到队列里的最大值,要求函数max_valuepush_backpop_front均摊时间复杂度都是O(1)。

若队列为空,pop_frontmax_value 需要返回 -1

示例 1:

输入: 
["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
[[],[1],[2],[],[],[]]
输出: [null,null,null,2,1,2]

示例 2:

输入: 
["MaxQueue","pop_front","max_value"]
[[],[],[]]
输出: [null,-1,-1]

限制:

  • 1 <= push_back,pop_front,max_value的总操作数 <= 10000
  • 1 <= value <= 10^5

Solution

鉴于上一题所以这一题一开始就想的这种方法, 结果有个地方开始没转过来

如果压入123 那么maxs里面只会保留3 不管是否pop_front掉1和2 最大值只会是3, pop_front掉于最大值前面压入的数不会影响最大值

class MaxQueue {
public:
MaxQueue()
{

}

int max_value()
{
return maxs.empty() ? -1 : maxs.front();
}

void push_back(int value)
{
nums.push(value);

while (!maxs.empty() && maxs.back() < value)
{
maxs.pop_back();
}
maxs.push_back(value);
}

int pop_front()
{
if (nums.empty())
{
return -1;
}
int ret = nums.front();
nums.pop();
if (maxs.front() == ret)
{
maxs.pop_front();
}

return ret;
}

queue<int> nums;
deque<int> maxs;
};

剑指 Offer 60. n个骰子的点数

Difficulty: 中等

把n个骰子扔在地上,所有骰子朝上一面的点数之和为s。输入n,打印出s的所有可能的值出现的概率。

你需要用一个浮点数数组返回答案,其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。

示例 1:

输入: 1
输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]

示例 2:

输入: 2
输出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778]

限制:

1 <= n <= 11

Solution - 暴力法

class Solution {
public:

vector<int> counter;

int n_back;

void dfs(int n, int sum)
{
if (n == 0)
{
counter[sum - n_back]++;
return;
}
for (int i = 1; i <= 6; ++i)
{
dfs(n - 1, sum + i);
}
}

vector<double> dicesProbability(int n)
{
n_back = n;
counter.resize(n * 6 - n + 1);
dfs(n, 0);

double sum_count = pow(6, n);
vector<double> result;
result.resize(n * 6 - n + 1);
for (int i = 0; i < n * 6 - n + 1; ++i)
{
result[i] = counter[i] / sum_count;
}
return result;
}
};

每个骰子都可能是1-6 将骰子掷完就能得到结果

Solution - 动态规划

class Solution {
public:

vector<double> dicesProbability(int n)
{
vector<int> vec1(n * 6 + 1, 0);
vector<int> vec2(n * 6 + 1, 0);

for (int i = 1; i <= 6; ++i) // n == 1时 是 1 1 1 1 1 1
{
vec1[i] = 1;
}

for (int i = 2; i <= n; ++i)
{
for (int j = 0; j < i; ++j)
{
vec2[j] = 0;
}

for (int j = i; j <= i * 6; ++j)
{
vec2[j] = 0;
for (int k = 1; j >= k && k <= 6; ++k)
{
vec2[j] += vec1[j - k];
}
}
vec1.swap(vec2);
}

double sum = pow(6, n);
vector<double> ret;
ret.reserve(n * 6 - n + 1);
for (int i = n; i <= n * 6; ++i)
{
ret.push_back(vec1[i] / sum);
}
return ret;
}
};

当投掷n个骰子的时候出现总和为m 那么 x[n][m] = x[n-1][m-1] + x[n-1][m-2] + x[n-1][m-3] + x[n-1][m-4] + x[n-1][m-5] + x[n-1][m-6]

这样每计算n个骰子的时候只需要第n-1轮的结果 可以使用两个数组, 计算完第n轮后将这个数组swap到”上一轮数组”用于计算n+1轮

剑指 Offer 61. 扑克牌中的顺子

Difficulty: 简单

从扑克牌中随机抽5张牌,判断是不是一个顺子,即这5张牌是不是连续的。2~10为数字本身,A为1,J为11,Q为12,K为13,而大、小王为 0 ,可以看成任意数字。A 不能视为 14。

示例 1:

输入: [1,2,3,4,5]
输出: True

示例 2:

输入: [0,0,1,2,5]
输出: True

限制:

数组长度为 5 

数组的数取值为 [0, 13] .

Solution

class Solution {
public:
bool isStraight(vector<int>& nums)
{
vector<int> vec(13, 0);
int left_sub = vec.size();
int zero_count = 0;
for (int num : nums)
{
if (num == 0)
{
zero_count++; // 统计0的数量
}
else if (vec[num - 1] == 0)
{
vec[num - 1] = 1; // 标记出现的非0卡牌
left_sub = min(left_sub, num - 1); // 更新第一张非0卡牌的开始位置
}
else
{
return false; // 存在重复的卡牌
}
}

int right_sub = left_sub;
while (right_sub < vec.size() && (vec[right_sub] == 1 || zero_count > 0))
{
if (vec[right_sub] == 0) // 为0表示没有这张卡 需要消耗一张0来补齐
{
zero_count--;
}
right_sub++;
}

return right_sub - left_sub + zero_count == nums.size(); // 输入数据的长度 = 顺子的长度(含补齐) + 剩余下的0
}
};

剑指 Offer 63. 股票的最大利润

Difficulty: 中等

假设把某股票的价格按照时间先后顺序存储在数组中,请问买卖该股票一次可能获得的最大利润是多少?

示例 1:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

示例 2:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

限制:

0 <= 数组长度 <= 10^5

注意:本题与主站 121 题相同:

Solution - 动态规划

class Solution {
public:
int maxProfit(vector<int>& prices)
{
int buy_price = INT_MAX;
int ans = 0;

for (int curr_price : prices)
{
if (curr_price > buy_price)
{
// try sell
ans = max(ans, curr_price - buy_price); // 当前价格大于卖出价格尝试卖出
}
else if (curr_price < buy_price)
{
// buy this
buy_price = curr_price; // 当前价格小于买入价格 尝试改为当前价格买入
}
}
return ans;
}
};

剑指 Offer 64. 求1+2+…+n

Difficulty: 中等

1+2+...+n ,要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句(A?B:C)。

示例 1:

输入: n = 3
输出: 6

示例 2:

输入: n = 9
输出: 45

限制:

  • 1 <= n <= 10000

Solution - sizeof代替乘法 + 短路运算控制返回

class Solution {
public:
// int sumNums(int n)
// {
// char a[n][n + 1];
// return (sizeof a) >> 1;
// }

int sumNums(int n)
{
n > 1 && (n += sumNums(n - 1)); // 短路运算右边对n进行赋值
return n;
}
};

剑指 Offer 65. 不用加减乘除做加法

Difficulty: 简单

写一个函数,求两个整数之和,要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。

示例:

输入: a = 1, b = 1
输出: 2

提示:

  • ab 均可能是负数或 0
  • 结果不会溢出 32 位整数

Solution a + b = x(进位信息 使用 & << 1) + y(本位信息 使用 xor)

class Solution {
public:
int add(int a, int b)
{
while (b != 0)
{
int c = (a & b) << 1; // 进位信息 1 + 1 = 10 由于1&1=1所以需要 <<
a ^= b; // 本位信息 0 + 0 = 0 1 + 0 = 1 0 + 1 = 0 1 + 1 = 0
b = c; // a + b = x1(进位) + y1(本位) = x2(进位) + y2(本位) .... + 到进位为0 这样就是结果了 0 + x = x;
} // 已知a+b = 进位+本位 而进位+本位也是两个数字相加 所以可以连续调用公式 直到进位为0 本位就是结果
return a;
}
};

剑指 Offer 68 - I. 二叉搜索树的最近公共祖先

Difficulty: 简单

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”

例如,给定如下二叉搜索树:  root = [6,2,8,0,4,7,9,null,null,3,5]

示例 1:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。

示例 2:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

说明:

  • 所有节点的值都是唯一的。
  • p、q 为不同节点且均存在于给定的二叉搜索树中。

注意:本题与主站 235 题相同:

Solution - 读题 利用好每一个条件

/**
* 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 nullptr;
}
if (p->val > q->val)
{
swap(p, q);
}
while (true)
{
if (root->val < p->val)
{
root = root->right;
}
else if (root->val > q->val)
{
root = root->left;
}
else
{
break;
}
}
return root;
}
};

我第一次写这个题目没有用上二叉搜索树这个条件, 把下一个题目二叉树给写出来了….

没利用好题目, 没读好题 我有罪

这个题目利用的是二叉搜索树 如果两个数都小于根节点 则位于根节点的左子树 两个都大于则位于根节点的右子树

如果一个大于一个小于说明位于左右子树则当前节点即为答案. 通过保证p的值小于q可以简化以上的判断. 如果最小的p都大于根节点则较大的q也一定大于


转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。