牛客_fengziggg

题解

/ 注册

全部文章 / 题解（共25篇）

[slide_window]包含min函数的栈

思路：一开始只是简单的模拟有min的栈，最直白的就是用一个指针或者变量维持最小值，每次插入删除都更新一次，在调用min的时候就是O(1)，但是这个就是每次都要sort的复杂度（不是find，找不到对比的对象，这里小混），基础的就是这么做了。看了别人的发现是滑动窗口，只不过活动窗口的时候，当前最值的...

2020-04-29

1 769

[basic_recursion]树的子结构

思路： 1.一开始马上想到的是KMP的思路关注点在加速匹配上，但树形结构好像很麻烦于是考证转化为数组存储是否可以匹配，因为数组的二叉树靠下表的2倍关系确定前后节点，所以这个思路好像是可行的，但想了一下要是稀疏树那数组的长度是指数级想想可怕就转去其他思路（但不代表这是不可行的，后来输出样例也是数组输出...

2020-04-26

0 589

[base_recursion]合并链表

思路：合并链表最基本的两个思路：1.吧表头最小的一个抽出，然后比较被抽后的剩下的链表继续操作2.比较表头链表然后选择最小的一个（抽出）插入到没被选中的链表的合适的位置（并不是表头的下一个，而是那种一边<=另一边>的中间点插入，这里思路混乱了废了一些时间）,这个版本繁琐远不如上个版本好，...

2020-04-25

0 673

[water]反转链表

思路： 1.链表反转遍历版和递归版，递归版可以在前馈过程反转，结尾处回递结果，也可在结尾处反转然后回递，这里做了第一种 struct ListNode { int val; struct ListNode *next; ListNode(int x) : ...

2020-04-25

0 570

[water_rearTopNode]链表中倒数第k个结点

思路：用两种方法：1.设一个pre在p跑了k个单位后再一起移动到结尾2.直接把整个list给反转过来，三指针，练手，这里会输出node[k]之后所有所以不能用（这种跟递归差不多，但直接递归无法处理返回ind和返回node，封装个专门回传的对象应该可以，还有就是存入栈那空间换时间） struct L...

2020-04-25

0 682

[water_dp_fibnaci]矩形覆盖

题目：我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2n的大矩形，总共有多少种方法？比如n=3时，23的矩形块有3种覆盖方法：思路：其实在列举前几个的时候就知道是fibnaci（除了0的情况不符合，而且样例还真带0真是无聊），但是不知道为什么是fi...

2020-04-25

3 771

[water_doubleRapidPow]数值的整数次方

题目：给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。保证base和exponent不同时为0 思路：还是矩阵快速幂，只是要细分double幂的为0情况为负情况：base==0和！=0， r>0/r<0/r=0;1.bas...

2020-04-25

0 722

[water_moveOp]二进制中1的个数

题目：输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。思路： 1.c和java底层是补码二进制，直接用位运算计数，就是负数的补码右移是补1，左移补0，所以右移无穷1，所以得限制int 32个位。2.题解区里的巧妙思路，既然底层是二进制了，可不可以直接统计出1的个数而不是遍历，当为...

2020-04-25

0 577

[rapid_pow]斐波那契数列

思路：练习矩阵的快速幂，就是将幂乘的指数累加过程变成变底数后指数的累乘缩小，然后在fibnaci加速就是将累次的计算（递推式的）用矩阵乘法来表示，然后就可以用乘法中的数学规律加速实现快速幂。代码也很巧妙，就是在每一次扩大底数缩小指数的时候，若指数为奇数，这原底数肯定会被抽出一个单独乘在结果里，偶数...

2020-04-24

0 604

[binary_search]旋转数组的最小数字

题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。思路：这道题花费...

2020-04-24

5 801