3 zfr143816

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 25w+

动态规划——硬币问题

动态规划——硬币问题/*题目描述:给定不同面额的硬币 coins 和一个总金额 amount,可以凑成总金额所需的最少的硬币个数。 *解体思路: * 动态规划: * coins={1、2、5} amount=11; * 确定状态:dp[i] 当前金额i需要dp[i]枚硬币组成 * 状态转移方程:dp[i]=min(dp[i-1],dp[i-2],dp[i-5]) 当前状态的前一个状态有三种可能选择最优解 * 记忆化递归: * 声明记忆哈希表 * 枚举当前金额的前一个状态的所有

2020-08-10 18:03:37

LeetCode-236 二叉树最近公共祖先

LeetCode-236 二叉树最近公共祖先/* 236. 二叉树的最近公共祖先 * 题目描述:给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 * 解体思路:分两部分解决 * 第一部分:实现判断两个结点包含于某根节点的子树内 * 第二部分:先序遍历二叉树,如果根节点的子树包含qp目标结点 * 传入左孩子,进行递归。传入右孩子,进行递归。 * 如果孩子的递归返回值为null,则返回根节点,如果孩子的递归结

2020-08-10 17:59:40

二叉树第K层结点个数

二叉树第K层结点个数public class ErChaShuKCengJieDianGeShu { public static void main(String[] args) { TreeNode root = new TreeNode(1); root.left = new TreeNode(2); root.right = new TreeNode(3); root.left.left = new TreeNode(4); root.left.right = new Tr

2020-08-10 17:57:43

重建二叉树

重建二叉树/* 题目描述:输入某二叉树的前序遍历和中序遍历的结果,请重建该二叉树。 * 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 * 例如:前序遍历为12473568、中序遍历为47215386 * 前序遍历的第一个元素为数的根节点、中序遍历中根节点左边的为左子树右边的为右子树 * 前序:根节点(1)左子树(247)右子树(3568) * 中序:左子树(472)根节点(1)右子树(5368) * * 前序247、中序472

2020-08-10 17:34:37

归并排序

归并排序/* 归并排序:将一个数组切分、切分,,,分到不可再分,然后两两合并,,,合并直到合并会大数组 * 合并的过程即合并俩个有序序列。 * 归并排序与快速排序的不同指出在于,快排的有序发生在切分过程,归并的有序发生在合并的过程。 * * */public class MergeSort { public static void main(String[] args) { int[] array = {5,8,10,12,7,13,15}; MergeSo

2020-08-10 17:30:53

希尔排序

希尔排序/* 希尔排序:有数组arrary,取length/2为间隔(每轮迭代间隔折半), * 将array逻辑上划分为若干个子数组,对子数组进行插入排序 * */public class ShellSort { public static void main(String[] args) { int[] array = {20,10,8,5,15,13,40,18}; ShellSort sort = new ShellSort(); sort.shellSortSo

2020-08-10 17:29:55

快速排序(Java)

快速排序/* 快速排序 * 原理:思想上来看就是每轮选定一个基准点,将小于基准点的元素放在基准点前 * 将大于基准点的元素放在基准点之后。不断的切分原有的区间,当每个区间 * 最小时,就保证了整个数列时有序的。 * 实现:快速排序的实现分为两部分,左小右大的简单排序以及递归切分区间。 * * */public class QuictSort { /* 默认选中0号元素为基准点,left为左边界初始指向array[1],right为右边界初始指向arra

2020-08-10 17:28:55

简单选择排序(Java)

简单选择排序/* 简单选择排序:遍历无序数列,第i轮找出第i大的数放入第i个位置 * 时间复杂度:最坏情况外层循环每遍历一个,内层循环都要遍历i到array.length获取最小元素 * n+(n-1)+..+1 o(n**2) * 不稳定 * */public class SimpleSelectionSort { public static void main(String[] args) { //int[] array = {9,8,7,6,5,4,3,2,1};

2020-08-10 17:27:56

直接插入排序(Java)

直接插入排序/* 直接插入排序:默认前k个元素有序,每次将第i个元素插入到k个有序元素的正确位置 * 从array[1]开始遍历数组(默认初始有序数列未{array[0]}) * 遍历区间从待插入的新元素array[i]遍历到array[0] * 如果待插入的元素与前一个元素无序则交换 * 时间复杂度:最坏情况外层循环每遍历1个,内层循环遍历i个,1+2+3+...+n o(n**2) * 稳定 * * */public class StraightInsertion

2020-08-10 17:26:23

栈的压入弹出序列

栈的压入弹出序列/* 剑指offer31:栈的压入、弹出序列 * 题目描述:输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。 * 假设压入栈的所有数字均不相等。例如,序列 {1,2,3,4,5} 是某栈的压栈序列, * 序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列, * 但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。 * 解题思路: * 12345的入栈顺序是否能得到45321的出栈

2020-08-06 22:08:42

用队列实现栈

用队列实现栈/* 225:用队列实现栈 * 题目描述:使用队列实现栈的下列操作:push(x) -- 元素 x 入栈,pop() -- 移除栈顶元素 top() -- 获取栈顶元素,empty() -- 返回栈是否为空。 解题思路:声明两个队列,queue、queue1、queue2(queue指向当前存有元素的栈) push:如果两个队列都空,将元素放入queue1,若有一个队列非空元素入该队列 top:将当前非空的队列弹出到空的队列,最后一个弹出的元素,出栈

2020-08-06 22:07:30

包含min函数的栈

包含min函数的栈/* 剑指offer30:包含min函数的栈 * 题目描述:定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中, * 调用 min、push 及 pop 的时间复杂度都是 O(1)。 * 解题思路:用链表模拟栈,push、pop时间复杂度就是O(1),维持一个指针指向栈内最小元素 * 使min的时间复杂度也是O(1). * (这种解题思路是错误的,因为只能通过min指针找到 * 曾经称为过最小值的

2020-08-06 22:06:16

删除链表结点

删除链表结点/* 剑指offer18题:删除链表的节点 * 题目描述:给定单向链表的头指针和一个要删除的节点的值,定义一个函数删除该节点。 * 返回删除后的链表的头节点。 * 解题思路:该题在剑指offer中的原题是,给定一个单链表的头指针、指定结点指针, * 要求以o(1)的时间复杂度删除该结点。解决方法为将待删除结点的后继结点的值 * 赋给待删除结点然后将待删除结点的后继指向其后继的后继,然后释放掉待删除 * 结点的原始后继。对于待删除结点没有后继结点

2020-08-06 22:04:44

分割链表

分割链表/* 面试题 02.04 :分割链表 * 题目描述:编写程序以 x 为基准分割链表,使得所有小于 x 的节点排在大于或等于 x 的节点之前。 * 如果链表中包含 x,x 只需出现在小于 x 的元素之后(如下所示)。 * 分割元素 x 只需处于“右半部分”即可,其不需要被置于左右两部分之间。 * 解题思路:本题要求将大于基准的数置于结点左侧,小于结点的置于结点右侧,该功能类似于快速排序 * 的分割操作(基准指向0,left指向1、right指向leng

2020-08-06 22:03:07

奇偶链表

奇偶链表/* 328. 奇偶链表 * 题目描述:给定一个单链表,把所有的奇数节点和偶数节点分别排在一起。 * 请注意,这里的奇数节点和偶数节点指的是节点编号的奇偶性,而不是节点的值的奇偶性。 * 要求:空间复杂度O(1),时间复杂度O(n) * 解题思路:声明指针记录第二个结点,游标遍历链表,将每个结点的后继指向后继的后继, * 将游标最后指向的结点的后继指向第二个结点 * 测试:null,只有一个结点、只有两个结点、有若干结点、链表长为奇数或偶数、链表

2020-08-06 22:01:54

判断链表是否有环

判断链表是否有环/* 141 * 题目描述:判断链表中是否有环 * 解题思路:慢指针一次走一步、快指针一次走两步 * 当快指针指向空时链表无环,当快指针指向慢指针时链表有环 * */public class LinkedListCycle { public static void main(String[] args) { ListNode head = new ListNode(1); ListNode node1 = new ListNode(2); List

2020-08-06 21:59:45

链表倒数第K个结点

链表倒数第K个结点/* 剑指offer22;链表中第倒数第k个结点 * 题目描述:输入一个链表,输出该链表中倒数第k个节点。为了符合大多数人的习惯,本题从1开始计数, * 即链表的尾节点是倒数第1个节点。例如,一个链表有6个节点,从头节点开始, * 它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。 * 解题思路:1.倒数第k个结点的正序为:leng-k+1,先遍历链表求链表长度,再遍历链表取第length-k+1个结点 * 2.维

2020-08-06 21:58:10

合并有序链表

合并有序链表/* 剑指offer25:合并两个排序链表 * 题目描述:输入两个递增排序的链表,合并这两个链表并使新链表中的节点仍然是递增排序的。 * 解题思路:设两链表分别为L1、L2,P1、P2分别指向L1的第一、第二个结点,q指向L2的第一个结点 * 若q小于p1将q的后继设为p1,p1指向q p2指向p1,q指向后继 * 若q大于等于p1且小于p2将q插入p1 p2中,q指向后继,p1不动、p2指向q * 若q大于p2,p1指向p2,p

2020-08-06 21:56:20

链表的中间元素

链表的中间元素public class FindMiddleNode { /* 867 * 问题描述:找到链表的中间元素 * 解题思路: * 1.先求链表长度再遍历到第二分之length的结点 * 2.声明快指针p一次向后移动两步,慢指针q一次向后移动一步 * 当快指针到表尾时,慢指针到表的中间位置。 * 规定:只有一个或两个结点的情况下返回头结点 * */ public static void main(String[] a

2020-08-06 21:52:39

反转链表

反转链表/* 剑指offer24 反转链表 * 题目描述:定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。 * 解题思路: * 1.遍历链表,逐个结点入栈,栈中结点出栈重新组装链表 * 2.声明两个指针,p指向null(头结点的前一个结点)q指向头结点 * 遍历链表同时移动pq指针,声明temp指向q的后继,q的后继指向p,p指向q * 3.创建伪头结点,遍历链表顺序将各结点插在头结点之后 * 测试用例:防空串、只有一个结点的串

2020-08-04 22:35:40

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。