JinFei's Blog

Thinking will not overcome fear but action will.

[剑指Offer]求第n个丑数

丑数

题目描述 把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。 解题思路 2^x, 3^y, 5^z res[num_2] * 2, res[num_3] * 3, res[num_5] * 5 三个数取最小即为当前第i个丑数 class...

Posted by JinFei on February 29, 2020

[剑指Offer]n个骰子的点数

dp

题目描述 把n个骰子扔在地上，所有骰子朝上的一面的点数之和为s.输入n，打印出s的所有可能的值出现的概率。 解题思路 我们设立数组dp[i][j]，用数组中的第n个数表示骰子点数和为j的次数 第k次投掷骰子的数可能为1~6中的任意一个数，如果我们假设第k次投掷骰子最终所有的和为n，那么和为n的次数就为前一次投掷（第k-1次投掷）和为n-1、n-2、n-3、n-4、n-5、...

Posted by JinFei on February 26, 2020

[剑指Offer]数组中的逆序对

归并排序

题目描述 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007 输入描述 题目保证输入的数组中没有的相同的数字 数据范围： 对于%50的数据,size<=10^4 \ 对于%75的数据,size<=10^5 ...

Posted by JinFei on February 24, 2020

[剑指Offer]调整数组顺序使奇数位于偶数前面

使用冒泡排序

题目描述 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。 解题思路 使用冒泡排序的思想 如果arr[i]是偶数，arr[i + 1]是奇数，那么我们就将其换位 利用第二重循环来做 class Solution { public: voi...

Posted by JinFei on February 24, 2020

[剑指Offer]数据流中的中位数

C++最大最小堆模拟，优先级队列

题目描述 如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。 解题思路 为要求的是中位数，那么这两个堆，大顶堆用来存较小的数，从大到小排列； ...

Posted by JinFei on February 24, 2020

[剑指Offer]数组中只出现一次的数字

异或，反码，补码使用

题目描述 一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。 解题思路 全部异或得一个结果 根据这个结果得到末尾1的位置 按照这个位置进行分组 每组分别进行异或 即可得最后结果 class Solution { public: vector<int> singleNumbers(vector<...

Posted by JinFei on February 23, 2020

[剑指Offer]序列化二叉树

序列化，反序列化，二叉树

题目描述 请实现两个函数，分别用来序列化和反序列化二叉树 二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#），以 ！ 表示一个结点值的结束（value!）。 二叉树的反序列化是指：根据某种...

Posted by JinFei on February 23, 2020

[LeetCode]105. Construct Binary Tree from Preorder and Inorder Traversal

先序，中序建树，重建二叉树

题目描述 Given preorder and inorder traversal of a tree, construct the binary tree. NOTE You may assume that duplicates do not exist in the tree. Example: preorder = [3,9,20,15,7] inorder = [...

Posted by JinFei on February 23, 2020

[剑指Offer]二叉树中和为某一值的路径

DFS查找路径

题目描述 输入一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前) 解题思路 递归先序遍历树， 把结点加入路径。 若该结点是叶子结点则比较当前路径和是否等于期待和。 弹出结点，每一轮递归返回到父结点时，当前路径也应该回退一个...

Posted by JinFei on February 23, 2020

[剑指Offer]二叉树的深度

递归，非递归求深度

题目描述 输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。 解题思路 递归求树的深度 /* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x...

Posted by JinFei on February 23, 2020

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