《剑指offer》题目 C++详细题解

JZ15 二进制中1的个数

核心考点:二进制计算

思路一:使用一个循环,因为我们知道整型变量只有32位,所以循环结束的条件就是到32,从最低位开始,逐位检查数字 n 的二进制表示,利用位运算中的与运算,将当前位移到最低位,然后与 1 进行按位与运算,判断结果是否为 1,如果当前位为 1,则计数器 count 加 1,循环结束后,计数器 count 中保存的就是数字 n 的二进制表示中 1 的个数。

class Solution {
public:int NumberOf1(int n) {int count = 0;int i = 0;while(i < 32){if((n >> i) & 1 == 1) // 使用按位与进行比较count++;i++;}return count;}
};

但是上面的算法的时间复杂度是O(N)的,有没有更简单更便捷的算法呢?

思路二:使用 while 循环,只要 n 不为 0,就继续循环。循环中,执行 n &= (n - 1) 操作。该操作利用了二进制数中 1 的性质:将一个数减 1,然后与原数进行按位与运算,可以将最右边的一个 1 变成 0,每次执行 n &= (n - 1) 操作后,n 中的 1 的个数减少 1,因此代码将计数器 count 加 1,循环结束后,计数器 count 中保存的就是 n 的二进制表示中 1 的个数,代码返回 count。

class Solution {
public:int NumberOf1(int n) {int count = 0;while(n){n &= (n - 1);count++;}return count;}
};

这种方法比直接遍历二进制位效率更高,因为每次循环都只进行一次位运算,可以更快地将 n 中的 1 个数进行统计。

JZ22 链表中倒数最后k个结点

核心考点:链表,前后指针的使用,边界条件的检查

由于题目中明确了这是一个单链表,所以我们不可以从后向前遍历找到最后k个节点,所以此时我们可以使用前后双指针的思路,前指针先走k步,随后前后两个指针同时向后走,当前指针到达结尾的时候,后指针所在的位置就是倒数最后k个节点 。

/*** struct ListNode {*	int val;*	struct ListNode *next;*	ListNode(int x) : val(x), next(nullptr) {}* };*/
class Solution {
public:ListNode* FindKthToTail(ListNode* pHead, int k) {ListNode* fast = pHead;ListNode* slow = pHead;// 前指针先走k步while(k--){if(fast == nullptr)return nullptr;fast = fast->next;} // 前后指针同时走while(fast){fast = fast->next;slow = slow->next;}return slow;}
};

JZ24 反转链表

核心考点:链表操作,思维缜密程度

这个题目的做法有很多种,我们依次来写一下。

思路一:定义三个指针,整体右移,边移动边翻转,保证不会断链

/*** struct ListNode {*	int val;*	struct ListNode *next;*	ListNode(int x) : val(x), next(nullptr) {}* };*/
class Solution {
public:ListNode* ReverseList(ListNode* head) {if(!head || !head->next)return head;// 至少两个节点ListNode* n1, *n2, *n3;n1 = head;n2 = head->next;n3 = head->next->next; // 可能为空while(n3 != nullptr){n2->next = n1; // 翻转// 向后移动n1 = n2;n2 = n3;n3 = n3->next; // 不断链}// 走到这里n3为空n2->next = n1;head->next = nullptr;return n2;}
};

思路二:采用头插的方法进行翻转,此时拿原始链表的时候注意不要断链

/*** struct ListNode {*	int val;*	struct ListNode *next;*	ListNode(int x) : val(x), next(nullptr) {}* };*/
class Solution {
public:ListNode* ReverseList(ListNode* head) {if(!head || !head->next)return head;// 至少两个节点ListNode* newhead = nullptr;ListNode* cur = head;while(cur){// 把原链表的第一个节点拿下来ListNode* tmp = cur;cur = cur->next;// 头插tmp->next = newhead;newhead = tmp;}return newhead;}
};

思路三:使用递归来解决,过程中出现重复子问题

如果我们先逆序前两个节点,会出现什么问题呢?

我们会发现此时会出现断链的情况,会把节点值为3的节点丢失,从而找不到后面的节点,会造成内存泄漏的问题,所以先直接修改前两个是不合理的,所以我们需要换一种思路,以一种宏观的思路,相信dfs一定可以能帮我们完成的逆序的任务,给dfs一个头节点,dfs帮我完成逆序,返回逆序之后的头节点,那么此时就有:

此时刚好就完成了我们的逆序工作,如果上面的思路不好理解,我们可以把链表当作一棵树,只不过此时是一个单边树,此时我们对这棵树仅需进行以此后序遍历即可

/*** struct ListNode {*	int val;*	struct ListNode *next;*	ListNode(int x) : val(x), next(nullptr) {}* };*/
class Solution {
public:ListNode* ReverseList(ListNode* head) {if (head == nullptr || head->next == nullptr) return head;ListNode* newhead = ReverseList(head->next);head->next->next = head;head->next = nullptr;// 返回逆序之后的头节点return newhead;}
};

JZ25 合并两个排序的链表

核心考点:链表合并

对于这道题,解题的思路有很多种,我们可以一个一个节点的归并,当然,也可以采用递归完成。

思路一:通过循环遍历两个有序链表,每次选择较小的节点插入到新的链表,最终得到一个合并后的有序链表。

/*** struct ListNode {*	int val;*	struct ListNode *next;*	ListNode(int x) : val(x), next(nullptr) {}* };*/
class Solution {
public:ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {if(pHead1 == nullptr)return pHead2;if(pHead2 == nullptr)return pHead1;ListNode* cur1 = pHead1;ListNode* cur2 = pHead2;// 标明新链表的头尾节点,闭区间ListNode* newhead = nullptr;ListNode* tail = nullptr;while(cur1 && cur2){// 选出较小的节点ListNode* tmp = nullptr;if(cur1->val >= cur2->val){tmp = cur2;cur2 = cur2->next;}else{tmp = cur1;cur1 = cur1->next;}// 尾插到新链表if(newhead == nullptr){newhead = tail = tmp;}else{tail->next = tmp;tail = tail->next;}}// 合并后,cur1或者cur2可能不为空,此时直接链接即可if(cur1)tail->next = cur1;if(cur2)tail->next = cur2;return newhead;}
};

思路二:通过递归调用 Merge 函数,每次将两个链表首节点进行比较,并将较小的节点作为合并后的新链表的头节点,并将较小的节点的 next 指针指向递归调用 Merge 函数的结果,最终得到一个合并后的有序链表。

/*** struct ListNode {*	int val;*	struct ListNode *next;*	ListNode(int x) : val(x), next(nullptr) {}* };*/
class Solution {
public:ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {if(pHead1 == nullptr)return pHead2;if(pHead2 == nullptr)return pHead1;ListNode* head = nullptr;// 1.找到较小的节点,head// 并从原链表中删除该节点if(pHead1->val < pHead2->val){head = pHead1;pHead1 = pHead1->next;}else{head = pHead2;pHead2 = pHead2->next;}//2.出现子问题,此时变少了一个节点// 但是此时依然是合并链表head->next = Merge(pHead1, pHead2);return head;}
};

想清楚上面的方法,此时我们的代码就能更优化一点。

/*** struct ListNode {*	int val;*	struct ListNode *next;*	ListNode(int x) : val(x), next(nullptr) {}* };*/
class Solution {
public:ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {if(pHead1 == nullptr)return pHead2;if(pHead2 == nullptr)return pHead1;if(pHead1->val < pHead2->val){pHead1->next = Merge(pHead1->next, pHead2);return pHead1;}else{pHead2->next = Merge(pHead1, pHead2->next);return pHead2;}}
};

JZ26 树的子结构

核心考点:二叉树理解,二叉树遍历

解题思路:二叉树都是递归定义的,所以递归操作是比较常见的做法,首先明白子结构怎么理解,可以理解成子结构是原树的子树(或者一部分),也就是说,B要是A的子结构,B的根节点+左子树+右子树,都在A中存在且构成树形结构,所以我们比较的过程要分为两步

  • 1.先确定起始位置
  • 2.在确定从该位置开始,后续的左右子树的内容是否一致
/*
struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int x) :val(x), left(NULL), right(NULL) {}
};*/
class Solution {private:bool IsSameTree(TreeNode* root1, TreeNode* root2) {if (!root2) // 子树已经遍历完毕return true;if (!root1) // 母树已经遍历完毕return false;if (root1->val != root2->val)return false;// 此位置处根节点值相等bool left = IsSameTree(root1->left, root2->left);bool right = IsSameTree(root1->right, root2->right);return left && right;}public:bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {if (pRoot1 == nullptr || pRoot2 == nullptr)return false;bool result = false;// 先寻找起始位置if (pRoot1->val == pRoot2->val) {// 判断两棵树是否相同result = IsSameTree(pRoot1, pRoot2);}// 左子树和pRoot2比较if (result == false) {result = HasSubtree(pRoot1->left, pRoot2);}// 右子树和pRoot2比较if (result == false) {result = HasSubtree(pRoot1->right, pRoot2);}return result;}
};

JZ27 二叉树的镜像

核心考点:二叉树操作

这个题目我们仔细观察可以发现,所谓的二叉树镜像本质是自底向上进行左右左右子树交换的过程,既然是自底向上,那就说明这个题目的思想是后序遍历,这样这个题目就比较好写啦

class Solution {
public:TreeNode* Mirror(TreeNode* pRoot) {if(!pRoot)return pRoot;if(!pRoot->left && !pRoot->right)return pRoot;if(pRoot->left)Mirror(pRoot->left);if(pRoot->right)Mirror(pRoot->right);TreeNode* tmp = pRoot->left;pRoot->left = pRoot->right;pRoot->right = tmp;return pRoot;}
};

JZ76 删除链表中重复的结点

核心操作:链表操作,临界条件检查,特殊情况处理

解题思路:通过快慢指针的方式限定范围,从而达到去重的效果,这里需要注意处理全部相同,全部不同和部分相同的三种情况的方式。

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {}
};
*/
class Solution {
public:ListNode* deleteDuplication(ListNode* pHead) {if(pHead == nullptr)return pHead;// 申请带头结点ListNode* head = new ListNode(0);head->next = pHead;// 定义重复区域的区间,左开右闭ListNode* prev = head;ListNode* tail = head->next;while(tail != nullptr){// 1.先确定重复区域的起始位置while(tail->next != nullptr && tail->val != tail->next->val){prev = tail;tail = tail->next;}// 2.确定重复区域的结束位置while(tail->next != nullptr && tail->val == tail->next->val){tail = tail->next;}// 走到这里有三种情况// 1.tail->next为空, 有重复区间// 2.tail->next不为空, 有重复区间// 3.链表没有重复结点,没有重复区间if (prev->next != tail){prev->next = tail->next;  }tail = tail->next;}ListNode* next = head->next;delete head;return next;}
};

JZ30 包含min函数的栈

核心考点:栈的规则性设计

解题思路:很容易想到,在栈内部保存min变量,每次更新的时候,都对min变量进行更新。//但是,面试官很容易就会问到:如果想拿出第二小,第三小的值怎么拿?用上面的办法就不行了,为了满足通用,我们使用一个辅助栈,内部保存元素的个数和数据栈完全一样,不过,辅助栈内部永远保存本次入栈的数为所有数据的最小值(注意:辅助栈内部元素可能会出现“必要性”重复),我们这里是为了实现算法,所以就不从0开始实现stack了,我们直接使用c++库里面实现的栈就好,题面说了,保证测试中不会当栈为空的时候,对栈调用pop()或者min()或者top()方法,所以,后面的代码对空的检验可有可无。

注意:最小栈的元素个数和数据栈的个数相同,最小栈的栈顶永远保存着当前个数的数据栈中的最小值,其中,最小栈可能出现重复的数组。

class Solution {
public:void push(int value) {st.push(value);if(minst.empty() || value < minst.top())minst.push(value); // 插入小值elseminst.push(minst.top());  // 插入栈顶的值}void pop() {st.pop();minst.pop();}int top() {return st.top();}int min() {return minst.top();}stack<int> st;  // 数据栈stack<int> minst; // 最小栈
};

JZ31 栈的压入、弹出序列

核心考点:栈的理解

思路:将入栈序列的元素压入辅助栈。检查辅助栈的栈顶元素是否等于出栈序列的元素,如果相等,则执行出栈操作,继续检查直到栈顶元素不再等于出栈序列的元素或者栈为空。当入栈序列中的所有元素都被处理完后,检查出栈序列是否也到达了末尾。如果出栈序列也到达了末尾,说明所有元素都按照正确的顺序弹出了栈,因此此时是一个有效的弹出序列;反之则不是。

class Solution {
public:bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {stack<int> st;int curpush = 0, curpop = 0;while(curpush < pushV.size()){// 入栈序列直接入栈st.push(pushV[curpush++]);// 出栈序列和栈顶元素相同,就一直出栈while(!st.empty() && st.top() == popV[curpop]){st.pop();curpop++;}}return curpop == pushV.size() ? true : false;}
};

JZ32 从上往下打印二叉树

核心考点:二叉树层序遍历

这个题目本质是二叉树的层序遍历,我们可以直接借助一个队列来完成这个题目,首先我们创建一个队列用来暂存待处理的节点,并创建一个用来存储层序遍历的结果的vector容器。将根节点压入队列,当队列不为空时,循环执行以下操作:从队列头部取出一个节点,将节点的值添加到结果中。如果节点有左子树,则将左子树节点加入队列。如果节点有右子树,则将右子树节点加入队列。当队列变为空时,所有节点都已经处理完毕,返回结果即可。

/*
struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int x) :val(x), left(NULL), right(NULL) {}
};*/
class Solution {
public:vector<int> PrintFromTopToBottom(TreeNode* root) {vector<int> ret; // 返回层序遍历的结果queue<TreeNode*> q;if(root == nullptr)return ret;// 根节点先入队列q.push(root);while(q.size()){// 访问当前结点并出队列TreeNode* t = q.front();q.pop();ret.push_back(t->val);// 左子树入队列if(t->left)q.push(t->left);// 右子树入队列if(t->right)q.push(t->right);}return ret;}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/399832.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

如何检查端口占用:netstat和lsof指令

在网络故障排查和系统管理中&#xff0c;检查端口占用情况是一项常见且重要的任务。本文将详细介绍如何使用 netstat 和 lsof 这两个强大的工具来检查端口占用和相关服务。 1. 使用 netstat 查看端口占用 netstat (network statistics) 是一个用于显示网络连接、路由表、接口…

前端react集成OIDC

文章目录 OpenID Connect (OIDC)3种 授权模式 【服务端】express 集成OIDC【前端】react 集成OIDCoidc-client-js库 原生集成react-oidc-context 库非组件获取user信息 OAuth 2.0 协议主要用于资源授权。 OpenID Connect (OIDC) https://openid.net/specs/openid-connect-core…

【案例44】Oracle启用“_optimizer_skip_scan_enabled” 参数导致NC系统卡死问题

问题现象 客户反映系统卡顿&#xff0c;很多操作耗时都比较长&#xff0c;通过nmc监控&#xff0c;线程耗时主要集中在数据库上。 问题分析 首先监控数据库服务器资源使用情况&#xff0c;CPU、内存使用正常&#xff0c;没有达到峰值。 监控磁盘IO情况&#xff0c;发现磁盘最…

WPF篇(11)-ToolTip控件(提示工具)+Popup弹出窗口

ToolTip控件 ToolTip控件继承于ContentControl&#xff0c;它不能有逻辑或视觉父级&#xff0c;意思是说它不能以控件的形式实例化&#xff0c;它必须依附于某个控件。因为它的功能被设计成提示信息&#xff0c;当鼠标移动到某个控件上方时&#xff0c;悬停一会儿&#xff0c;…

【C++ 面试 - 基础题】每日 3 题(十一)

✍个人博客&#xff1a;Pandaconda-CSDN博客 &#x1f4e3;专栏地址&#xff1a;http://t.csdnimg.cn/fYaBd &#x1f4da;专栏简介&#xff1a;在这个专栏中&#xff0c;我将会分享 C 面试中常见的面试题给大家~ ❤️如果有收获的话&#xff0c;欢迎点赞&#x1f44d;收藏&…

解决浏览器书签同步问题,极空间部署开源免费的跨平台书签同步工具『xBrowserSync』

解决浏览器书签同步问题&#xff0c;极空间部署开源免费的跨平台书签同步工具『xBrowserSync』 哈喽小伙伴们好&#xff0c;我是Stark-C~ 作为一个喜欢折腾的数码党&#xff0c;我平时上网冲浪使用的浏览器绝不会只限于一种&#xff0c;就比如说我在上班的地方只会用到Edge浏…

安科瑞Acrel-2000ES储能能量管理系统在新型电力系统下分布式储能的研究

摘要&#xff1a;传统电力系统的结构和运行模式在以新能源为主体的新型电力系统中发生了巨大的变化&#xff0c;分布式储能作为电力系统中重要的能量调节器&#xff0c;也迎来了新的发展机遇。立足于储能技术发展现状&#xff0c;分析了分布式储能技术特点及在清洁可再生能源方…

priority_queue的介绍 仿函数

1.priority_queue的介绍 1.优先队列是⼀种容器适配器&#xff0c;根据严格的弱排序标准&#xff0c;它的第⼀个元素总是它所包含的元素中最⼤的。 2.此上下⽂类似于堆&#xff0c;在堆中可以随时插⼊元素&#xff0c;并且只能检索最⼤堆元素&#xff08;优先队列中位于顶部的元…

接口自动化--Postman(1)

Postman介绍 介绍&#xff1a;Postman是一款接口调试工具特点&#xff1a;支持Mac、Windows和Linux下载&#xff1a;Postman官网下载 【黑马客达天下-登录接口调试】 1、获取验证码 需求&#xff1a;使用Postman访问验证码接口&#xff0c;并查看响应结果地址&#xff1a;h…

北斗三号5G遥测终端机系统在水库大坝安全监测应用

一、概述 我国现有水库大坝9.8万余座&#xff0c;是世界上拥有水库大坝最多的国家。这些水库大坝在防洪、发电、供水、灌溉等方面发挥巨大效益的同时&#xff0c;所存在的安全风险不容忽视。大坝安全监测是大坝安全管理的重要内容&#xff0c;是控制大坝风险的重要措施。大坝安…

Spring入门讲解

这里写目录标题 Spring基础概念关键重点主要特性主要优势Spring与Java EE的对比Spring生态系统概述总结 Spring 基础概念 Spring是一个开源的轻量级Java开发框架&#xff0c;它提供了全面的基础设施支持&#xff0c;简化了企业级应用的开发和部署。Spring的核心理念是依赖注入…

Stable Diffusion 必备插件推荐,菜鸟轻松成高手!

前言 一个刚学AI绘画的小菜鸟如何快速成为Stable Diffusion高手&#xff1f;答案就是SD插件。 只要学会使用SD的各种插件&#xff0c;帮你写正向和负向提示词&#xff0c;修复人脸/身体/手指&#xff0c;高清放大图片&#xff0c;指定人物pose&#xff0c;图片微调等等都可以…

合合信息OCR支持30类国内常见票据一站式分类识别,支持医疗发票、数电票识别

合合信息TextIn平台明星产品——国内通用票据识别&#xff0c;重磅更新&#xff01; 产品支持票据类型扩展到23大类、30小类&#xff0c;覆盖场景更全面&#xff0c;同时升级优化了多款票据识别模型&#xff0c;平均识别率较前版本提升11.5%&#xff0c;整体识别速度提升21.9%…

手写mybatis拦截器自动填充数据

文章目录 &#x1f31e; Sun Frame&#xff1a;SpringBoot 的轻量级开发框架&#xff08;个人开源项目推荐&#xff09;&#x1f31f; 亮点功能&#x1f4e6; spring cloud模块概览常用工具 &#x1f517; 更多信息1.将sun-club-subject模块的登录拦截器放到sun-club-common包中…

Prometheus+Grafana保姆笔记(1)——Prometheus+Grafana的安装

Prometheus Grafana 的组合在微服务项目中可以完成许多DevOps任务&#xff0c;它们共同提供了强大的监控和可视化功能。 我们陆续介绍Prometheus Grafana 的相关用法。 首先介绍PrometheusGrafana的安装。 安装 Prometheus Prometheus 是GO写的&#xff0c;并不依赖于 Ja…

HIT CSAPP——程序人生-Hello’s P2P

本文链接&#xff1a;https://blog.csdn.net/QingFeng_0813/article/details/139468749?spm1001.2014.3001.5502 计算机系统 大作业 题 目 程序人生-Hello’s P2P 专 业 医学与健康学院 学   号 2022110762 班 级 2252003 …

(回溯) LeetCode 47. 全排列||

原题链接 建议先练习&#xff1a;全排列| 一. 题目描述 给定一个可包含重复数字的序列 nums &#xff0c;按任意顺序 返回所有不重复的全排列。 示例 1&#xff1a; 输入&#xff1a;nums [1,1,2] 输出&#xff1a; [[1,1,2],[1,2,1],[2,1,1]]示例 2&#xff1a; 输入&a…

Java流程控制01:用户交互Scanner

本节教学视频链接&#xff1a;https://www.bilibili.com/video/BV12J41137hu?p33&vd_sourceb5775c3a4ea16a5306db9c7c1c1486b5https://www.bilibili.com/video/BV12J41137hu?p33&vd_sourceb5775c3a4ea16a5306db9c7c1c1486b5 Scanner 类用于扫描输入文本从字符串中提…

Bug 解决 | 组件库报错、或样式丢失不生效

目录 一、前言 二、版本问题 1、使用 VantUI 的 toast 组件报错&#xff1f; 2、引入 VantUI 组件库后&#xff0c;toast 组件样式丢失了&#xff1f; 3、使用 Ant Design Vue 组件库&#xff0c;启动后显示 antd.css 不存在&#xff1f; 4、Vant UI 组件库引入的 tabs 组…

数据中心安全建设整体解决方案(DOC原件22页)

数据中心的安全体系建设并非安全产品的堆砌&#xff0c;它是一个根据用户具体业务环境、使用习惯、安全策略要求等多个方面构建的一套生态体系&#xff0c;涉及众多的安全技术&#xff0c;实施过程需要涉及大量的调研、咨询等工作&#xff0c;还会涉及到众多的安全厂家之间的协…