小陈君
小陈君
全部文章
分类
题解(10)
归档
标签
去牛客网
登录
/
注册
小陈君的博客
全部文章
(共10篇)
题解 | #数组中的逆序对#
思路1递归,dp(n) = dp(n-1)+[n到n-1]之间比n小的和,例如,遍历数组,第一个数是5,则判断4是否在右侧,如果有,则统计IDX5到IDX4之间比5小的值的个数,并获得4的索引IDX4,递归计算4右侧逆序数量。用HashMap可以加快递归过程,递归获得4右侧的逆序数量时,先从hash...
排序
分治
2021-07-06
0
374
整数中1出现的次数
思路1将n按照位数分段进行计算。例如,对41133的求解划分成:40000,5位数1000,4位数100,3位数30,2位数3,1位数五个段来求解,每个段需要求两个部分Tk_1、O(curValue): 1.Tk_1,当前位数k的下一级位数k_1中1的个数Tk_1。例如40000,当前为k=5位数...
分段
归纳
2021-06-25
0
365
题解 | #最小的K个数#
思路1 冒泡排序思路 冒泡出k个最小的值即ok import java.util.ArrayList; public class Solution { public ArrayList<integer> GetLeastNumbers_Solution(int [] i...
排序
查找
堆
2021-05-31
0
345
题解 | #二叉搜索树与双向链表#
描述输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向 思路1思考点1. 遍历二叉树,对每个节点,将其左节点的右指针指向当前节点,将其右节点的左指针指向当前节点;返回当前节点,为上一级节点的左/右侧子节点。思考点2. 返回的节点如果是左...
二叉树
链表
2021-05-30
0
301
题解 | #栈的压入、弹出序列#
思路1对于出栈数组中的每个元素:考虑该元素出栈时,或者从栈顶弹出,或者在压入一些元素后,再从栈顶弹出。因此,遍历出栈数组中的每个元素,先判断栈顶是否是该元素,如果是,则弹出,遍历下一个出栈元素;如果不是,则将入栈数组压入栈中,直到遇见该元素,再遍历下一个(下一个元素的入栈元素应接着上次入栈结束的位置...
2021-05-17
0
344
题解 | #反转链表#
思路1三个指针,一个指向pre,一个指向cur,一个指向next。对每一个节点,调整其next指针指向前一个节点。 public class Solution { public ListNode ReverseList(ListNode head) { ListNode preNod...
2021-05-16
0
385
题解 | #链表中倒数第k个结点#
思路1 第一遍遍历计算链表的长度,计算出倒数第k个节点的索引值idx = length-k,再从头寻找第idx个节点。 public ListNode FindKthToTail (ListNode pHead, int k) { // write code here if...
2021-05-16
0
417
题解 | #数值的整数次方#
题目描述给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。 保证base和exponent不同时为0。不得使用库函数,同时不需要考虑大数问题,也不用考虑小数点后面0的位数。 思路一个数末尾为0时,右移一位相当于除以2,一个数末尾为1时,...
2021-05-12
0
325
题解 | #矩形覆盖#
核心思想每个大矩形都由上一个大矩形添加一个小矩形而得到,在添加小矩形的过程中有两种方法。 竖向添加:小矩形直接追加在大矩形的尾部 横向添加:小矩形要扭转一个已有的小矩形,组成一个正方形追加在大矩形尾部当前矩形形态数f(n) = 竖向添加矩形+横向添加矩形如果上一个大矩形是由横向两个小矩形结尾,则...
2021-05-11
0
384
题解 | #重建二叉树#
<非递归实现>看题解里千篇一律的递归实现,与大家分享新的非递归方法,仅为扩展思路。 主要思路: 遍历前序序列pre的每一个值,对每个值,创建节点,查找其在中序序列in中的索引位置,判断该位置为前方节点中序序列in的左子树还是右子树(见详解),将该节点接到前方节点对应的left或ri...
二叉树
2021-05-10
0
361