没有合适的资源?快使用搜索试试~ 我知道了~
首页二维查找与替换技巧:剑指Offer算法详解
二维查找与替换技巧:剑指Offer算法详解
需积分: 9 0 下载量 101 浏览量
更新于2024-07-17
收藏 545KB PDF 举报
"剑指Offer是面向求职者的一系列算法题目集,旨在帮助应聘者提升技术能力和面试技巧。本文主要解析了两个经典问题: 1. 二维数组中的查找 题目要求设计一个函数,输入一个二维数组,其中每一行按从左到右递增排序,每一列按从上到下递增排序。目标是判断给定的整数`target`是否在数组中存在。函数`Find`的实现采用从右上角(`i=0`, `j=col-1`)开始的二分查找策略,每次比较`target`与当前元素,如果相等则返回`true`,如果`target`大于当前元素,则向下方移动`i`,小于则向左方移动`j`。当遍历完整个二维数组的某行或列后,仍未找到`target`,则返回`false`。这种算法的时间复杂度是O(m+n),其中m和n分别为行数和列数,空间复杂度为O(1)。 2. 替换空格 这个问题是关于字符串处理的,需要编写一个名为`replaceSpace`的函数,将输入字符串中的每个空格替换成"%20"。首先,遍历整个字符串直到结尾,统计空格数量和字符串总长度。如果没有空格,直接返回。如果有空格,根据空格数量计算新的字符串长度,并在原字符串中进行替换操作。这个任务不涉及复杂的逻辑,但体现了对基本字符串操作的理解。 通过这两个问题,求职者可以锻炼在实际场景下解决数组搜索和字符串操作的能力,同时也能了解到如何在面试中展示自己的编程思维和优化技巧。在实际面试过程中,解决这类问题不仅能展现编程基础,还能体现算法优化和空间复杂度控制的意识。"
资源详情
资源推荐
![](https://csdnimg.cn/release/download_crawler_static/11074388/bgd.jpg)
class Solution {
public:
ListNode* Merge(ListNode* pHead1, ListNode* pHead2){
if(NULL==pHead1) return pHead2;
if(NULL==pHead2) return pHead1;
if(NULL==pHead1 && NULL==pHead2) return NULL;
ListNode *p1 = pHead1, *p2 = pHead2, *pHead = NULL;//pHead 为归并后的头节点
ListNode *p = new ListNode(-1);//申请一个节点,为了操作方便
ListNode *q = p;//记住此申请节点,在最后要释放空间
while(p1 && p2){
if(p1->val<p2->val){
p->next = p1;
p1 = p1->next;
}else{
p->next = p2;
p2 = p2->next;
}
p = p->next;
if(NULL==pHead) pHead = p;//记住头节点
}
while(p1){
p->next = p1;
p1 = p1->next;
}
while(p2){
p->next = p2;
p2 = p2->next;
}
delete q;//释放申请的动态空间
return pHead;
}
};
分析:考查链表的归并。
思路:为了不单独选出头结点,特定义了一个节点
p
,方便处理。指针
q
是为了记住申请空
间的位置,便于之后释放。
树的子结构
输入两颗二叉树 A,B,判断 B 是不是 A 的子结构。
代码:
/*
struct TreeNode {
![](https://csdnimg.cn/release/download_crawler_static/11074388/bge.jpg)
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
public:
bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2){
if(pRoot1==NULL || pRoot2==NULL) return false;
return isSubtree(pRoot1,pRoot2);
}
bool isSubtree(TreeNode *pa, TreeNode *pb){
if(pa==NULL) return false;//递归结束条件
bool ret = false;//返回值
if(pa->val==pb->val) ret = isSubtreeTmp(pa,pb);//节点值相同,继续判断左右子树
if(ret) return true;//如果左右子树都相同,表示已找到,立即返回
ret = isSubtree(pa->left,pb);//节点值不相同,在 A 树的左子树中寻找
if(ret) return true;//如果找到,立即返回
ret = isSubtree(pa->right,pb);//节点值不相同,在 B 树的右子树中寻找
if(ret) return true;//如果找到,立即返回
else return false;//上述都找不到时,返回 false
}
bool isSubtreeTmp(TreeNode *pa, TreeNode *pb){
if(pb==NULL) return true;//为空,说明此子树已完全匹配
if(pa==NULL && pb!=NULL) return false;//如果 A 树先空,而 B 树还没空,匹配失败
return pa->val==pb->val && isSubtreeTmp(pa->left,pb->left) &&
isSubtreeTmp(pa->right,pb->right);//如果节点值相同,继续匹配左子树和右子树
}
};
分析:这题主要是搞清楚子结构的定义。
思路:先序遍历每一个节点,从
A
树根节点开始判断:
1
)当前节点的值与
B
树根节点的值是否一样,若一样,执行
2
);否则,执行
3
);
2
)继续判断
A
树左子树和
B
树左子树,以及
A
树右子树和
B
树右子树;
3
)说明此节点一定不是子结构的根节点,则:
2.1
)递归:令当前节点的左孩子为当前节点,执行
1
);
2.2
)递归:令当前节点的右孩子为当前节点,执行
1
);
函数
isSubtree
中有很多
return
语句,主要是为了在找到子结构时能够立即返回,避免不必
要的递归。
![](https://csdnimg.cn/release/download_crawler_static/11074388/bgf.jpg)
本题的“子结构”需要注意以下几点:
1)节点值可以重复;
2)树 B 只是树 A 的一部分,不一定非要到叶子节点,即下面的情况是满足子结构的:
2 2
2 3 4 5
4 5 B 树
6 7
A 树
3)当树 A 不空、B 树空时,B 树也是 A 树的子结构。
二叉树的镜像
操作给定的二叉树,将其变换为源二叉树的镜像。
二叉树的镜像定义:源二叉树
8
/ \
6 10
/ \ / \
5 7 9 11
镜像二叉树
8
/ \
10 6
/ \ / \
11 9 7 5
代码:
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
![](https://csdnimg.cn/release/download_crawler_static/11074388/bg10.jpg)
class Solution {
public:
void Mirror(TreeNode *pRoot) {
if(pRoot==NULL) return;
TreeNode *node = pRoot->left;
pRoot->left = pRoot->right;
pRoot->right = node;
Mirror(pRoot->left);
Mirror(pRoot->right);
}
};
分析:递归地交换左右子树即可。
顺时针打印矩阵
输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字,例如,如果输入如下
矩 阵 : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则 依 次 打 印 出 数 字
1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
本题代码分成两步来说:
第一步:
class Solution {
public:
vector<int> printMatrix(vector<vector<int> > matrix) {
vector<int> vec;
int row = matrix.size();//
行数
int col = matrix[0].size();//
列数
int k = 0;//
控制循环输出的次数
while(k<=row/2 && k<=col/2){
int i = k, j = k;//
每一次循环输出从
matrix[k][k]
开始
while(j<col-k) vec.push_back(matrix[i][j++]);//
从“左上角向右上角”输出
j--;i++;//j—
因为上面
while
多加了
1
;
i++
走向下一行
while(i<row-k) vec.push_back(matrix[i++][j]);//
从“右上角向右下角”输出
i--;j--;//i—
因为上面
while
多加了
1
;
j—
走向左一列
while(j>=k) vec.push_back(matrix[i][j--]);//
从“右下角向左下角”输出
j++;i--;//j++
因为上面
while
多减了
1
;
i—
走向上一行
while(i>=k+1) vec.push_back(matrix[i--][j]);//
从“左下角向左上角”输出
k++;//
准备进行下一轮
}
return vec;
}
};
分析:一圈可以分成四步:
剩余75页未读,继续阅读
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/8b38388c0ebf4f33b9173d06b7241c56_hansionz.jpg!1)
Hansionz
- 粉丝: 439
- 资源: 2
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
最新资源
- Vue实现iOS原生Picker组件:详细解析与实现思路
- Arduino蓝牙小车:参数调试与功能控制
- 百度Java面试精华:200页精选资源涵盖核心知识点
- Swift使用CoreData填坑指南:CoreData在Swift 3.0的变化
- 微距离无线充电器创新设计及其实验探索
- MTK Android平台开发全攻略:44步详解流程
- RecyclerView全面解析:替代ListView的新选择
- Android开发:自动适配中英文键盘解决方案
- Android调用WebService接口教程
- Android开发:BitmapUtil图片处理全解析与实例
- Android多线程断点续传实现详解
- PCA算法在人脸识别会议签到系统中的应用
- EventBus 3.0:Android事件总线详解与实战应用
- Android FileUtil:全面解析文件操作实用技巧与实例
- RecyclerView添加头部和尾部实战教程
- Android实现微博滑动固定顶部栏实战与优化
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)