pozhenzi
pozhenzi
全部文章
题解
归档
标签
去牛客网
登录
/
注册
pozhenzi的博客
苟有恒,又何必三更眠五更起;最无益,莫过于一日曝十日寒。
全部文章
/ 题解
(共9篇)
题解 | #跳台阶#
算法思路 由于青蛙在每一层台阶都只存在两种跳法:选择跳一级还是两级。那么假设跳上n级台阶有F(n)中跳法,很容易就可以写出递推公式 F(n) = F(n - 1) + F(n - 2);这不就是动态规划中的状态转移方程么,因此代码就很容易写出来了。 算法实现一 首先用递归方式实现: public c...
算法题
动态规划
斐波那契
2021-08-15
0
290
题解 | #两数之和#
算法思路 题目要求计算数组中两数之和等于特定值的组合,首先很容易想到的一种算法是把该数组每一个值及其下标存到一个Map里面;然后再次遍历数组,看Map中是否有补数(特定值与当前值之差)存在,有的话说明找到了,否则继续找;事实上,我们只需要遍历一遍数组就可以了:在遍历数组的过程中如果没有找到补数,就把...
算法题
2021-08-15
0
272
题解 | #寻找第K大#
算法思路 要找数组中第K大的数,很简单的就是将数组从大到小进行排序,然后输出数组第K个数即可;排序的话我们选择快速排序,简单高效,而且因为是原地排序空间复杂度也低;不同于#排序#中从小到大排序,只要修改partition()方法交换判定条件,即可实现从大到小排序; 算法实现 public class...
算法题
快速排序
2021-08-15
0
279
题解 | #最小的K个数#
算法思路 题目要求数组中最小的K个数,很明显我们可以先对数组进行从小到大排序,然后输出前K个数即可;排序算法介绍参考#排序#,这里我们选择快速排序来实现。 算法实现 public class Solution { public ArrayList<Integer> GetLeas...
算法题
快速排序
2021-08-15
0
227
题解 | #求二叉树的层序遍历#
算法思路 要对二叉树做层序遍历,那么要先能够知道当前层有哪些元素,然后按顺序从左往右遍历,这里最容易想到的就是用队列来存储了,队列的FIFO特性保证遍历顺序;遍历过程中保存好当前层遍历结果以及下一层的元素,然后递归直到二叉树遍历完; 算法实现 public class Solution { ...
算法题
二叉树遍历
2021-08-15
0
267
题解 | #实现二叉树先序,中序和后序遍历#
算法思路 二叉树遍历最简单的实现方法就是使用递归的写法了,比如先序遍历:先打印根节点,然后是左子树,接着右子树;题目要求将二叉树的三种遍历结果以数组形式返回,那么我们先可以创建三个链表分别保存先序、中序和后续的遍历结果,然后将结果合并成二位数组返回即可; 算法实现 public class Solu...
算法题
二叉树遍历
2021-08-14
0
303
题解 | #设计LRU缓存结构#
算法思路 题目要求设计一个LRU(Least Recent Used)缓存结构,即优先淘汰最久没有使用到的数据。最常规做法就是使用一个List将缓存索引保存起来:当缓存中每插入一条数据,就往List头插入该数据索引;而每次缓存被命中时,则将该数据索引挪到List头部;此外再用一个Map来保存缓存索引...
算法题
LRU缓存
2021-08-14
0
252
题解 | #排序#
解题思路 题目要求解题时间在1s内,那么就限定了排序算法范围在快排、堆排和归并排序之间,下面依次实现之; 快排 算法原理 快排采用了分治的思想:要对数组A进行排序,可以先将A分成两个子数组A1和A2,并同时保证A1中任一元素值小于A2中任一元素,然后对两子数组在重复此操作直到数组无法再进行分割,最后...
快速排序
算法题
归并排序
2021-08-14
0
312
题解 | #反转链表#
解题思路 对于链表来说,我们知道头插和尾插的结果一个是逆序,一个是顺序排列;那么便可以遍历原链表,通过头插到新链表,从而实现链表反转; 代码 public class Solution { public ListNode ReverseList(ListNode head) { ...
算法题
链表
2021-08-11
0
234