JinFei's Blog

Thinking will not overcome fear but action will.

[剑指Offer]对称的二叉树

拆分，递归的使用

题目描述 请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。 解题思路 可以用递归的思路，写一个helper函数，注意这个helper函数是两个参数，就像二叉树的当前节点的左右子节点一样 递归结束条件，如果当前两个节点都为空则返回true 如果两个节点其中有一个为空，则返回false，肯定不相等 如果两...

Posted by JinFei on December 18, 2019

[剑指Offer]从上往下打印二叉树

STL队列的使用

题目描述 从上往下打印出二叉树的每个节点，同层节点从左至右打印。 解题思路 考察STL中的队列 写法，queue q,一些基本操作和stack类似，都是push，pop操作，有特殊的front 注意每个入队push的是，当前队列的首元素的左右节点，所以会有一个temp变量来指示。 /* struct TreeNode { int val; struct Tr...

Posted by JinFei on December 17, 2019

[剑指Offer]替换空格

原地更新字符串

题目描述 请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。 解题思路 本体考察的是原地更新字符串 首先统计出空格的次数 新字符串的索引长度为 原来的长度+空格的次数*2-1 旧字符串的索引长度为 长度-1 从最后开始处理，如果对应的是空格，则这个先对...

Posted by JinFei on December 17, 2019

[剑指Offer]变态跳台阶

跳台阶问题

题目描述 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。 解题思路 动态规划 多项式的推导 当n = 1 时， 只有一种跳法，即1阶跳：Fib(1) = 1; 当n = 2 时， 有两种跳的方式，一阶跳和二阶跳：Fib(2)  = 2; 到这里为止，和普通跳台阶是一样的。 当n = 3 时，有三种跳的...

Posted by JinFei on December 16, 2019

[剑指Offer]链表中环的入口结点

链表操作，快慢指针使用

题目描述 给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。 解题思路 快慢指针的应用 链表中有环的条件为，快慢指针一定会在环中相遇 求环的入口节点，当快慢指针相遇的位置，然后初始化一个指针指向头结点，这次以每次只走一步的步伐，最终会在环的入口节点相遇 第二遍注意的点 注意指针的移动 指针的初始化位置，开始的时候，快慢指针都指...

Posted by JinFei on December 15, 2019

[剑指Offer]求1+2+3+...+n

构造函数使用

题目描述 求1+2+3+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。 解题思路 使用构造函数 设置两个静态变量，当前num，当前sum 每次初始化这个类的一个对象时，当前num自增，然后将sum += num 这样肯定生成的是这个类的对象数组（生成过程可以用指针替代,如Test* t...

Posted by JinFei on December 15, 2019

[剑指Offer]矩阵中的路径

dfs模拟

题目描述 请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如 a b c e s f c s a d e e 矩阵中包含一条字符串”bcced”的路径，但是矩阵中不包含”abcb”路径，因为字符串的第...

Posted by JinFei on December 15, 2019

[剑指Offer]和为S的两个数字

快慢指针的应用

题目描述 输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。 输出描述: 对应每个测试案例，输出两个数，小的先输出。 解题思路 快慢指针的使用 慢指针指向开头，快指针指向最后 如果结果大于指定的，快指针往前移 如果结果小于指定的，慢指针往后移 记得要有break条件，不然...

Posted by JinFei on December 14, 2019

[剑指Offer]两个链表的第一个公共结点

快慢指针的应用

题目描述 输入两个链表，找出它们的第一个公共结点。 解题思路 快慢指针的使用 先求出两个链表的长度 长的链表，快指针，先走，具体步数为 长链表减去短链表的长度 然后同时走，直至相等 使用函数模板 greater模板，从大到小排序 /* struct ListNode { int val; struct ListNode *next; ListNod...

Posted by JinFei on December 14, 2019

[剑指Offer]连续子数组的最大和

dp

题目描述 HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最...

Posted by JinFei on December 14, 2019

FEATURED TAGS
iTools 剑指Offer dfs 排序 数据结构 栈 链表 dp 字符串 树 LeetCode 最大堆 STL使用 查找 二叉树 图 转载 STL backtracking BFS stack 分治 DFS 异或 冒泡排序 归并排序 回溯 递归 C C++基础 腾讯面试 递减栈 递增栈 贪心 位操作 双指针 math 前缀树 prefix tree 力扣 位运算 数学 双向链表 快排 多线程 二分搜索 旋转数组 优先级队列 直方图 BST 字符串操作 DP 异或运算
ABOUT ME

Goals determine what you going to be!

✉️ luojf@nbjl.nankai.edu.cn

FRIENDS