- 剑指offer刷题笔记
- 前言
- 重复数字I
- 重复数字II
- 二维数组中的查找
- 替换空格
- 打印链表
- *重建二叉树
- 二叉树的下一个结点
- 两个栈实现队列
- 斐波那契数列
- 旋转数组
- 矩阵中的路径
- *机器人的运动范围
主要刷题平台为 牛客网，部分题目使用 LeetCode 和 ACwing 作为辅助。每题均包含主要思路、详细注释、时间复杂度和空间复杂度分析，每题均是尽可能最佳的解决办法。
重复数字I链接：
acwing：重复数字
newcode：重复数字
题目：
给定一个长度为 n 的整数数组 nums，数组中所有的数字都在 0∼n−1 的范围内。
数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。
请找出数组中任意一个重复的数字。
注意：如果某些数字不在 0∼n−1 的范围内，或数组中不包含重复数字，则返回 -1；
思路：
先将每个数字都放到对应的位置上，然后如果在放的过程中，发现该位置已经有数字了，那么就说明这个数字是多余的了
class Solution {
public:
int duplicateInArray(vector& nums) {
//每个数放到对应的位置上,如 时间复杂度 O(1)
int n=nums.size();
for(int i=0;i
//如果超出数据范围
if(nums[i]<0||nums[i]>=n)
{
return -1;
}
}
for(int i=0;i
//将每个数字都放到对应的位置上
while(i!=nums[i]&&nums[nums[i]]!=nums[i])
{
//如果该位置已经无法交换，就是 该位置上的数字已经是 对应的数字了
swap(nums[i],nums[nums[i]]);
}
//当前位置已经有对应数字了
if(nums[i]!=i)
{
return nums[i];
}
}
return -1;
}
};
时间复杂度 O ( n ) O(n) O(n)，额外空间复杂度 O ( 1 ) O(1) O(1)
重复数字IIACwing重复数字II
LeetCode 寻找重复数字
题目：
给定一个长度为 n+1的数组nums，数组中所有的数均在 1∼n 的范围内，其中 n≥1。
请找出数组中任意一个重复的数，但不能修改输入的数组。
思路：
有n+1个数字，但是数字范围在1~n，所以一定会有一个重复的数字，我们要 做的工作就是找到这个重复数字，
我们采用分治的思想，将每个数的取值的区间[1, n]划分成[1, n/2]和[n/2+1, n]两个子区间，然后分别统计两个区间中数的个数。
注意这里的区间是指 数的取值范围，而不是 数组下标。
划分之后，左右两个区间里一定至少存在一个区间，区间中数的个数大于区间长度。
class Solution {
public:
int duplicateInArray(vector& nums) {
//[l,mid] 和 [mid+1,r]
int l=1,r=nums.size()-1;
//整数二分
while(l
int mid=l+r>>1;
int s=0;
//统计左边数字数量
for(auto x:nums)
{
//s += x >= l && x <= mid;
if (x >= l && x <= mid)
s ++ ;
}
if(s>mid-l+1)
{
//重复数字在左半边
r=mid;
}
else
{
l=mid+1;
}
}
return r;
}
};
时间复杂度：每次会将区间长度缩小一半，一共会缩小
O
(
l
o
g
n
)
O(logn)
O(logn) 次。每次统计两个子区间中的数时需要遍历整个数组，时间复杂度是
O
(
n
)
O(n)
O(n)。所以总时间复杂度是
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)
空间复杂度：代码中没有用到额外的数组，所以额外的空间复杂度是
O
(
1
)
O(1)
O(1)
acwing二维数组中的查找
leetcode:二维数组中的查找
newcode：二维数组中的查找
题目：
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
数据范围:二维数组中元素个数范围 [0,1000]
思路：
暴力搜索的时间复杂度是 O ( n 2 ) O(n^2) O(n2), 由于数据不是很高，所以可以通过：
class Solution {
public:
bool searchArray(vector> array, int target) {
for(int i=0;i
for(int j=0;j
if(array[i][j]==target)
{
return true;
}
}
}
return false;
}
};
这里是有时间复杂度可以达到 O ( n ) O(n) O(n),因为题目中的二维数组 是有单调性的，所以我们可以从 右上角 的那个元素入手，如果 target 比右上角的元素大，则说明 target 不在该行，如果target比右上角元素小，则说明target不在该列，就可以实现要么排除掉 一行，要么排除掉一列
class Solution {
public:
bool searchArray(vector> array, int target) {
if(array.empty()||array[0].empty())
{
return false;
}
int i=0,j=array[0].size()-1;
while(j>=0&&i
if(array[i][j]>target)
{
j--;
}
else if(array[i][j]
i++;
}
else
{
return true;
}
}
return false;
}
};
替换空格
newcode: 替换空格
leetcode: 替换空格
题目：
请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
思路：
比较简单，使用额外空间：
class Solution {
public:
string replaceSpace(string s) {
// write code here
string result;
for(auto x:s)
{
if(x==' ')
{
result+="%20";
}
else
{
result+=x;
}
}
return result;
}
};
用时间换空间，在原数组上操作，不使用额外的内存空间
class Solution {
public:
string replaceSpace(string s) {
//使用从后向前填充，不用申请新的数组
//避免了从前向后填充元素 需要每次将添加元素之后的所有元素 向后移动
//统计空格个数
int count=0;
int sOldSize=s.size();
for (int i=0;i
if(s[i]==' ')
{
count++;
}
}
//扩容字符串大小,替换后的大小
//因为本来就有一个空格，所以只要再多增加两个空格的大小，就可以放下这个字符了
s.resize(s.size()+count*2);
int sNewSize=s.size();
//从后向前替换为 “%20”
for (int i=sNewSize-1,j=sOldSize-1;j
//i 是新字符串（扩容后，后面全部都是空格）的最后一个位置， j 是旧字符串（扩容前）的最后一个位置，现在就是把就字符串依次后移，如果遇到空格，就替换为 %20
if (s[j]!=' ')
{
//将字符串中的字符后移
s[i]=s[j];
}
else
{
s[i]='0';
s[i-1]='2';
s[i-2]='%';
i-=2;
}
}
return s;
}
};
打印链表
链接：
newcode打印链表
acwing打印链表
题目：
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
思路：
如果要使用 容器的性质，可以很轻易的实现
class Solution {
public:
vector reversePrint(ListNode* head) {
vector result;
ListNode* cur=head;
while(cur!=nullptr)
{
result.push_back(cur->val);
cur=cur->next;
}
//反转容器中的数据
return vector(result.rbegin(),result.rend());
}
};
*重建二叉树
链接：重建二叉树
题目：
给定节点数为 n 的二叉树的前序遍历和中序遍历结果，请重建出该二叉树并返回它的头结点。
例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建出如下图所示。
class Solution {
public:
TreeNode* traversal(vector& vin,int vinBegin,int vinEnd,vector& pre,int preBegin,int preEnd)
{
if(preBegin==preEnd)
{
return nullptr;
}
TreeNode* root=new TreeNode(pre[preBegin]);
//在 中序数组中寻找 根节点
int delimeterIndex=0;
for(delimeterIndex=vinBegin;delimeterIndex
if(vin[delimeterIndex]==pre[preBegin])
{
break;
}
}
//切割中序数组，因为要使用递归，所以一定要使用函数内的变量
int leftVinBegin=vinBegin; //左闭右开
int leftVinEnd=delimeterIndex;
int rightVinBegin=delimeterIndex+1;
int rightVinEnd=vinEnd;
//切割前序数组
int leftPreBegin=preBegin+1; //左闭右开
int leftPreEnd=preBegin+1+(delimeterIndex-vinBegin); //终止位置为 起始位置+中序左区间大小
int rightPreBegin=preBegin+1+(delimeterIndex-vinBegin);
int rightPreEnd=preEnd;
root->left=traversal(vin, leftVinBegin, leftVinEnd,pre,leftPreBegin,leftPreEnd);
root->right=traversal(vin, rightVinBegin, rightVinEnd,pre,rightPreBegin,rightPreEnd);
return root;
}
TreeNode* reConstructBinaryTree(vector pre,vector vin) {
if(pre.size()==0||vin.size()==0)
{
return nullptr;
}
return traversal(vin,0,vin.size(),pre,0,pre.size());
}
};
二叉树的下一个结点
下一个结点
题目：
给定一个二叉树其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的next指针。下图为一棵有9个节点的二叉树。树中从父节点指向子节点的指针用实线表示，从子节点指向父节点的用虚线表示
最重要的就是要分开讨论不同的情况，实现所有要求，一定要记清 中序遍历的顺序：左-中-右
如果该节点有右子树，那么下一个结点就是右子树中的 最左边的 左孩子
如果该节点没有右子树，那么下一个节点就要看父节点了，如果当前节点是父节点的左孩子，那么下一个结点就是 当前节点的 父节点（不一定是直接父节点）
class Solution {
public:
TreeLinkNode* GetNext(TreeLinkNode* pNode) {
//根据中序遍历，如果有右子树，那么右子树的左孩子(最左边的左孩子)J就是下一额节点
if(pNode->right)
{
pNode=pNode->right;
//右子树的最左边的孩子
while(pNode->left)
{
pNode=pNode->left;
}
return pNode;
}
//直到找到当前节点 是 父节点 的左孩子
// while(pNode->next&&pNode==pNode->next->right)
// {
// //第一个当前节点是父节点左孩子的节点
// pNode=pNode->next;
// }
// return pNode->next;
//没有右子树,只有左子树
while(pNode->next)
{
//是父节点的左子树，那么下一个结点就是 父节点
if(pNode==pNode->next->left)
{
return pNode->next;
}
//不是父节点的左子树就继续找父节点
pNode=pNode->next;
}
//没有父节点
return nullptr;
}
};
两个栈实现队列
两个栈实现队列
题目：
用两个栈来实现一个队列，使用n个元素来完成 n 次在队列尾部插入整数(push)和n次在队列头部删除整数(pop)的功能。 队列中的元素为int类型。保证操作合法，即保证pop操作时队列内已有元素。
数据范围： n≤1000
要求：存储n个元素的空间复杂度为 O(n) ，插入与删除的时间复杂度都是 O(1)
思路：
一定要先想清楚再下手，我们要用栈(先进后出)实现队列（先进先出），一个 栈 肯定是完不成的，必须要使用两个栈来实现，我们可选择将所有的 入队 都放在stack1 中，然后如果要 出队，就可以将 stack1 中的内容 再放到 stack2 中，这样放入stack2 中的 从顶到底的顺序，就是 队列 出队的顺序了，只要 stack2不是空的，就可以确保 stack2的顺序是出队顺序，如果stack2空了，就继续将 stack1 中的元素放入 stack2
class Solution
{
public:
void push(int node) {
//新数据都放入 stack1 中
stack1.push(node);
}
int pop() {
//由于数据都是放在 stack1 中的，我们要进行出队，就是stack1 中的栈底元素，我们将 stack1 中的元素全部发放到
//stack2 中之后，stack2的遍历顺序就是 队列的出列顺序了
if(stack2.empty())
{
while(!stack1.empty())
{
stack2.push(stack1.top());
stack1.pop();
}
}
//元素出栈之后，要在栈中弹出
int ret=stack2.top();
stack2.pop();
return ret;
}
private:
stack stack1;
stack stack2;
};
斐波那契数列
斐波那契数列
题目：
大家都知道斐波那契数列，现在要求输入一个正整数 n ，请你输出斐波那契数列的第 n 项。
斐波那契数列是一个满足 f i b ( x ) = { 1 x = 1 , 2 f i b ( x − 1 ) + f i b ( x − 2 ) x > 2 fib(x)=left{ begin{array}{rcl} 1 & {x=1,2}\ fib(x-1)+fib(x-2) &{x>2}\ end{array} right. fib(x)={1fib(x−1)+fib(x−2)x=1,2x>2的数列
数据范围： 1 ≤ n ≤ 40 1leq nleq 40 1≤n≤40
要求：空间复杂度 O ( 1 ) O(1) O(1)，时间复杂度 O ( n ) O(n) O(n) ，本题也有时间复杂度 O ( l o g n ) O(logn) O(logn) 的解法
思路：
这个做法是我目前看到的最优的做法了，时间复杂度为
O
(
n
)
O(n)
O(n), 空间复杂度为
O
(
1
)
O(1)
O(1), 因为每一个 斐波那契数字都 只与前面的两个数字有关，所以可以只记录前面的两个，实现降低 空间复杂度（空间复杂度为
O
(
n
)
O(n)
O(n)的做法就是使用 动态规划的做法了）
递归的写法就不再演示了，递归法：时间复杂度：
O
(
2
n
)
O(2^n)
O(2n) 空间复杂度：递归栈的空间
class Solution {
public:
int Fibonacci(int n) {
//因为求解只涉及到三个变量，所以使用三个变量来实现
int a=0,b=1;
//对于每一个斐波那契数，只和他前面的两个有关，所以可以进一步压缩空间
while(n--)
{
//a b 交替更新
int c=a+b;
a=b;
b=c;
}
return a;
}
};
空间复杂度 O ( 1 ) O(1) O(1)，时间复杂度 O ( n ) O(n) O(n)
动态规划做法：可以根据数据范围开辟对应大小的 dp数组，虽然时间复杂度可以达到要求，但是 空间复杂度明显没有上一个更小
class Solution {
public:
int Fibonacci(int n) {
//根据数据范围确定 dp数组的大小
int dp[40]={0};
dp[0]=0;
dp[1]=1;
dp[2]=1;
//从第3项开始，要包含最后一项
for(int i=3;i<=n;i++)
{
dp[i]=dp[i-1]+dp[i-2];
}
return dp[n];
}
};
旋转数组
acwing题解
newcode：旋转数组
题目：
有一个长度为 n 的非降序数组，比如[1,2,3,4,5]，将它进行旋转，即把一个数组最开始的若干个元素搬到数组的末尾，变成一个旋转数组，比如变成了[3,4,5,1,2]，或者[4,5,1,2,3]这样的。请问，给定这样一个旋转数组，求数组中的最小值。
数据范围： 1 ≤ n ≤ 10000 1 le n le 10000 1≤n≤10000，数组中任意元素的值: 0 ≤ v a l ≤ 100000 0 le val le 100000 0≤val≤100000
要求：空间复杂度： O ( 1 ) O(1) O(1) ，时间复杂度： O ( l o g n ) O(logn) O(logn)
思路：
直接使用二分查找
class Solution {
public:
int minNumberInRotateArray(vector rotateArray) {
//二分查找
if(rotateArray.size()==0)
{
return 0;
}
int left=0,right=rotateArray.size()-1;
while(left
if(rotateArray[left]
return rotateArray[left];
}
int mid=left+right>>1;
//int mid=left+((right-left))>>1;
if(rotateArray[right]
left=mid+1;
}
else if(rotateArray[right]>rotateArray[mid])
{
right=mid;
}
else
{
//不能确定答案在左边还是右边，那么就让last = last - 1;慢慢缩少区间，同时也不会错过答案
--right;
}
}
return rotateArray[left];
}
};
空间复杂度： O ( 1 ) O(1) O(1) ，时间复杂度： O ( l o g n ) O(logn) O(logn)
矩阵中的路径矩阵中的路径
题目：
请设计一个函数，用来判断在一个n乘m的矩阵中是否存在一条包含某长度为 len 的字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如 [ a b c e s f c s a d e e ] begin{bmatrix} a & b & c &e \ s & f & c & s \ a & d & e& e\ end{bmatrix}quad ⎣⎡asabfdcceese⎦⎤矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
数据范围： 0 ≤ n , m ≤ 20 , 1 ≤ l e n ≤ 25 0 le n,m le 20 ,1le len le 25 0≤n,m≤20 ,1≤len≤25
进阶：时间复杂度 O ( n 2 ) O(n^2) O(n2)，空间复杂度 O ( n 2 ) O(n^2 ) O(n2)
思路：
深度优先遍历的经典题目
枚举单词的起点，然后依次枚举单词的每个字母。
过程中需要将已经使用过的字母改成一个特殊字母，以避免重复使用字符。
class Solution {
public:
bool dfs(vector>& matrix,string &word,char u,int x,int y)
{
//该路径上的字符不一致
if(matrix[x][y]!=word[u])
{
return false;
}
//这两个判断的先后顺序不能颠倒
//找到该字符串，当前字符匹配且当前为最后一个字符时，直接返回true
if(u==word.size()-1)
{
return true;
}
//上右下左 横为y，纵为x
int idx[4]={-1,0,1,0};
int idy[4]={0,1,0,-1};
//记录当前值
char t=matrix[x][y];
//修改当前坐标的值，防止重复使用
matrix[x][y]='*';
for(int i=0;i<4;i++)
{
//尝试四个方向
int a=x+idx[i];
int b=y+idy[i];
if(a>=0&&a=0&&b
if(dfs(matrix, word, u+1, a, b))
{
return true;
}
}
}
//恢复现场
matrix[x][y]=t;
return false;
}
bool hasPath(vector >& matrix, string word) {
// write code here
for(int i=0;i
for(int j=0;j
if(dfs(matrix,word,0,i,j))
{
return true;
}
}
}
return false;
}
};
时间复杂度分析：单词起点一共有 n 2 n^2 n2 个，单词的每个字母一共有上下左右四个方向可以选择，但由于不能走回头路，所以除了单词首字母外，仅有三种选择。所以总时间复杂度是 O ( n 2 3 k ) O(n^23^k) O(n23k)。
*机器人的运动范围机器人的运动范围
题目：
地上有一个 rows 行和 cols 列的方格。坐标从 [0,0] 到 [rows-1,cols-1] 。一个机器人从坐标 [0,0] 的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于 threshold 的格子。 例如，当 threshold 为 18 时，机器人能够进入方格 [35,37] ，因为 3+5+3+7 = 18。但是，它不能进入方格 [35,38] ，因为 3+5+3+8 = 19 。请问该机器人能够达到多少个格子？
思路：
宽度优先遍历的经典题目
要注意判断障碍物，有些格子是不能走的
class Solution {
public:
int get_signal_sum(int x)
{
int s=0;
while(x)
{
s+=x%10;
x/=10;
}
return s;
}
int get_sum(pair p)
{
return get_signal_sum(p.first)+get_signal_sum(p.second);
}
int movingCount(int threshold, int rows, int cols) {
int res=0;
if(rows==0||cols==0)
{
return 0;
}
//默认所有格子都是没有走过的
vector> st(rows,vector(cols));
queue> q; //宽度优先搜索使用的队列
//也可以使用 make_pair
q.push({0,0});
//走的方向: 纵为x 横为y 上右下左
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
//循环放入
while(q.size())
{
auto t=q.front();
q.pop();
//如果不符合条件, 就不走这条路
if(get_sum(t)>threshold||st[t.first][t.second]==true)
{
continue;
}
res++;
st[t.first][t.second]=true; //表示走过了
//走的方向
for(int i=0;i<4;i++)
{
int x=t.first+dx[i];
int y=t.second+dy[i];
//判断是否合法的坐标
if(x>=0&&x=0&&y
q.push({x,y});
}
}
}
return res;
}
};
每个节点最多只会入队一次，所以时间复杂度不会超过方格中的节点个数。
最坏情况下会遍历方格中的所有点，所以时间复杂度就是 O(nm)
