JinFei's Blog

Thinking will not overcome fear but action will.

[剑指Offer]树的子结构

判断B是不是A的子树，两个递归的使用

题目描述 输入一棵二叉树，判断该二叉树是否是平衡二叉树。 解题思路 可以用递归的思路，先写一个helper函数，递归求树的高度 然后递归求，当前root节点的左右子树，看绝对值是否大于1 如果大于1，肯定不是 如果是的话，则递归判断root的左子树，root右子树是否满足平衡二叉树的性质。 注意一下递归的结束的条件，当root节点为NULL时，是返回true...

Posted by JinFei on January 17, 2020

[剑指Offer]数字在排序数组中出现的次数

二分查找，递归，循环两种

题目描述 统计一个数字在排序数组中出现的次数。 解题思路 考验二分查找的细节 首先第一种解码 使用STL中的map<int, int>数据结构，遍历一遍整个数组，这样做的时间复杂度为O(n) 第二种，二分查找，可以把时间复杂度降为O(log(n)) 二分查找的细节，获得最后一个k的index，获得第一个k的index，然后相减+1即为出现的次数 ...

Posted by JinFei on January 16, 2020

[剑指Offer]判断二叉搜索树的后序遍历

二叉搜索树的遍历

题目描述 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。 解题思路 二叉搜索树最后一个节点即为根节点 根节点的左节点都要比根节点要小 右节点都要比大节点大 利用这个性质，可以利用递归的思想，非别判断数组序列是否满足左右搜索子树的性质 注意结束的条件 class S...

Posted by JinFei on January 16, 2020

[剑指Offer]二叉树的镜像

递归的使用

题目描述 操作给定的二叉树，将其变换为源二叉树的镜像。 解题思路 这道题一直有个坑 判断如果当前节点的left，right节点都为空，则直接返回就行 如果有一个不为空，就使用一个临时变量，进行替换操作 然后再继续递归左右子树 class Solution { public: void Mirror(TreeNode *pRoot) { ...

Posted by JinFei on January 16, 2020

[剑指Offer]树的子结构

判断B是不是A的子树，两个递归的使用

题目描述 输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构） 解题思路 递归的使用，判断B是不是A的子结构 需要用两个递归函数，第一个递归的意思是，如果当前节点pRoot1 == pRoot2,则需要从该节点往下递归查找 第二个递归，表示如果不等，需要判断pRoot1的左子树，右子树 注意第二个递归的结束的条件，需要先判断...

Posted by JinFei on January 16, 2020

[LeetCode]560. Subarray Sum Equals K

暴力，哈希

题目描述 Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k. Example 1: Input:nums = [1,1,1], k = 2 Output: 2 Note: Th...

Posted by JinFei on December 31, 2019

[LeetCode]34. Find First and Last Position of Element in Sorted Array

二分查找的扩展

题目描述 Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value. Your algorithm’s runtime complexity must be in the order of O(log ...

Posted by JinFei on December 30, 2019

[LeetCode]322. Coin Change

dp状态方程

题目描述 You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amoun...

Posted by JinFei on December 29, 2019

[LeetCode]138. Copy List with Random Pointer

复杂链表的复制

题目描述 A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null. Return a deep copy of the list. The Linked List is re...

Posted by JinFei on December 29, 2019

[LeetCode]19. Remove Nth Node From End of List

链表的删除

题目描述 Given a linked list, remove the n-th node from the end of list and return its head. Note: Given n will always be valid. Follow up: Could you do this in one pass? Example: Given link...

Posted by JinFei on December 28, 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