JinFei's Blog

Thinking will not overcome fear but action will.

[剑指Offer]数组中出现次数超过一半的数字

STL，mmap使用

题目描述 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。 解题思路 可以使用键值对映射，key为对应的numbers里的元素，value则为这个元素出现的次数 其实这道题判断的更多的是，存不存在，如果题目说了...

Posted by JinFei on December 14, 2019

[剑指Offer]包含min函数的栈

栈操作

题目描述 定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。 解题思路 使用辅助栈 push元素时，首先插入S1，然后判断插入的元素是否比S2栈要小于等于，如果是的话，就还要入S2栈 pop的时候，先pop栈S1,然后判断pop的元素是否是S2栈的top元素，如果是的话，还要从S2栈里进行pop操作 常规版本 ...

Posted by JinFei on December 13, 2019

[剑指Offer]合并两个排序的链表

链表操作

题目描述 输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。 解题思路 生成一个新的头节点 最后返回头节点的next指针 常规版本 /* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) ...

Posted by JinFei on December 13, 2019

[剑指Offer]反转链表

链表操作

题目描述 输入一个链表，反转链表后，输出新链表的表头。 解题思路 需要三个指针，当更改cur->next指向前一个指针的时候，要保存next，否则链表就会段 定义 prev（最初赋值为NULL即可），cur（指向头节点），reverserHead(反转后的头指针) 循环的时候，再定义一个next，保存cur->next指针 /* struct Lis...

Posted by JinFei on December 13, 2019

[剑指Offer]斐波那契数列

斐波那契

题目描述 大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。n<=39 解题思路 按照f(n) = f(n - 1) + f(n - 2) class Solution { public: int Fibonacci(int n) { if(n < 0){ r...

Posted by JinFei on December 13, 2019

[剑指Offer]栈的压入、弹出序列

栈

题目描述 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的） 解题思路 借助辅助栈 遍历A序列 如果辅助栈的头元素与p...

Posted by JinFei on December 13, 2019

[剑指Offer]二维数组中的查找

有序查找

题目描述 在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。 解题思路 从右上角开始查找 如果比target大的话，只能是在下一行（因为这一行的这个元素是最大的） 类似的，比target小的话，只能是左边一列 class ...

Posted by JinFei on December 12, 2019

[iTools]MathType7+Word2016工具使用

MathType7嵌套Word

描述 这两天一直在捣弄MathType7怎么嵌入Word2016环境的问题，捣弄了一晚上+一上午。。。。贼气。。。 环境+failed尝试方法 环境 windows10 + Office2016 专业版 + Mathtype7.2 （上一个版本过期了 sad…） 知乎上讨论了MathType+Word2016兼容问题 需要 将路径被office信任，打开word→...

Posted by JinFei on December 11, 2019

[剑指Offer]把数组排成最小的数

C++ cmp函数重载

题目描述 输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。 解题思路 对vector容器内的数据进行排序，按照 将a和b转为string后 若 a＋b<b+a a排在在前 的规则排序 如 a = 2, b = 21 因为 212 &...

Posted by JinFei on December 9, 2019

[剑指Offer]矩形覆盖

斐波那契数列

题目描述 我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？ 解题思路 以2x8的矩形为例。示意图如下： 我们先把2x8的覆盖方法记为f(8)。用第一个1x2小矩阵覆盖大矩形的最左边时有两个选择，竖着放或者横着放。当竖着放的时候，右边还剩下2x7的区域，这种情况下的覆盖方法记为f(7)。接下...

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