没有合适的资源？快使用搜索试试~ 我知道了~

首页二维查找与替换技巧：剑指Offer算法详解

二维查找与替换技巧：剑指Offer算法详解

剑指offe

需积分: 9 0 下载量 101 浏览量更新于2024-07-17 收藏 545KB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

试读

76页

"剑指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"。首先，遍历整个字符串直到结尾，统计空格数量和字符串总长度。如果没有空格，直接返回。如果有空格，根据空格数量计算新的字符串长度，并在原字符串中进行替换操作。这个任务不涉及复杂的逻辑，但体现了对基本字符串操作的理解。通过这两个问题，求职者可以锻炼在实际场景下解决数组搜索和字符串操作的能力，同时也能了解到如何在面试中展示自己的编程思维和优化技巧。在实际面试过程中，解决这类问题不仅能展现编程基础，还能体现算法优化和空间复杂度控制的意识。"

资源详情

资源推荐

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;

}

};

分析：考查链表的归并。

思路：为了不单独选出头结点，特定义了一个节点

，方便处理。指针

是为了记住申请空

间的位置，便于之后释放。



树的子结构

输入两颗二叉树 A，B，判断 B 是不是 A 的子结构。

代码：

struct TreeNode {

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);//如果节点值相同，继续匹配左子树和右子树

}

};

分析：这题主要是搞清楚子结构的定义。

思路：先序遍历每一个节点，从

树根节点开始判断：

）当前节点的值与

树根节点的值是否一样，若一样，执行

）；否则，执行

）；

）继续判断

树左子树和

树左子树，以及

树右子树和

树右子树；

）说明此节点一定不是子结构的根节点，则：

2.1

）递归：令当前节点的左孩子为当前节点，执行

）；

2.2

）递归：令当前节点的右孩子为当前节点，执行

）；

函数

isSubtree

中有很多

return

语句，主要是为了在找到子结构时能够立即返回，避免不必

要的递归。

本题的“子结构”需要注意以下几点：

1）节点值可以重复；

2）树 B 只是树 A 的一部分，不一定非要到叶子节点，即下面的情况是满足子结构的：

2 2

2 3 4 5

4 5 B 树

6 7

A 树

3）当树 A 不空、B 树空时，B 树也是 A 树的子结构。

 二叉树的镜像

操作给定的二叉树，将其变换为源二叉树的镜像。

二叉树的镜像定义：源二叉树

/ \

6 10

/ \ / \

5 7 9 11

镜像二叉树

/ \

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) {

}

};*/

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

多加了

；

i++

走向下一行

while(i<row-k) vec.push_back(matrix[i++][j]);//

从“右上角向右下角”输出

i--;j--;//i—

因为上面

while

多加了

；

j—

走向左一列

while(j>=k) vec.push_back(matrix[i][j--]);//

从“右下角向左下角”输出

j++;i--;//j++

因为上面

while

多减了

；

i—

走向上一行

while(i>=k+1) vec.push_back(matrix[i--][j]);//

从“左下角向左上角”输出

k++;//

准备进行下一轮

}

return vec;

}

};

分析：一圈可以分成四步：

剩余75页未读，继续阅读

粉丝: 439
资源: 2

上传资源快速赚钱

我的内容管理展开

我的资源快来上传第一个资源

我的收益

登录查看自己的收益

我的积分登录查看自己的积分

我的C币登录后查看C币余额

我的收藏

我的下载

下载帮助

二维查找与替换技巧：剑指Offer算法详解

剑指offer答案全集解析

剑指offer源代码解析

剑指offer笔试及源程序

剑指offer前端需要刷吗

剑指offer代码下载c++

剑指offer java

剑指offer java pdf

剑指offerjava版pdf

剑指offer pdf

剑指offer电子版

剑指offer与华为机试练哪个比较好

剑指offer c++

剑指offer python

剑指offer+java

剑指offer 40python

剑指offerc语言

剑指offer第二版java

牛客网剑指offer j

剑指offer c语言

javascript剑指offer17

最新资源