策码奔腾的小单-CSDN博客

原创带你彻底掌握 Lambda 表达式（上）

更多技术文章，欢迎关注我的微信公众号：码不停蹄的小鼠松（微信号：busy_squirrel），也可扫下方二维码关注获取最新文章哦~说明：由于 Lambda 表达式涉及的周边知识点实在太多，因此拆分为上、下两篇文章讲解，本篇为上篇，下篇随后放出，大家可在我公众号中查找。目录介绍：上篇，主要讲 1~4 章节，下篇，主要介绍 5~8 章节。序言JDK8 日渐成为项目开发中的主流。...

2020-01-17 09:37:40 2650 6

原创一文讲透HashMap

更多2019年的技术文章，欢迎关注我的微信公众号：码不停蹄的小鼠松（微信号：busy_squirrel），也可扫下方二维码关注获取最新文章哦~文章目录：文章目录序言一、JDK7中的HashMap底层实现1.1 基础知识1.2 put()方法1.2.1 特殊key值处理1.2.2 扩容1.2.3 如何计算bucket下标？① hash值的计算② 取模的逻辑③ 拓展1.2.4 在目标buck...

2019-12-02 09:56:10 1488

原创 Java中的多态和动态绑定

1 定义Example动态绑定的内部机制　1. 定义根据Core Java：多态：一个对象变量可以指示多种实例类型的现象。动态绑定：在运行时刻能够自动选择调用哪个方法的现象。签名：方法名和参数列表构成一个签名多态和动态绑定大多与继承有关，因为有了继承的出现，才有了父类与子类，然后就是随之而来的方法重写(override)，即子类重写父类的方法。另一个出现的就是子

2016-05-31 18:26:57 2741

原创《剑指offer》——正则表达式匹配

T: 题目描述：请实现一个函数用来匹配包括’.’和’‘的正则表达式。模式中的字符’.’表示任意一个字符，而’‘表示它前面的字符可以出现任意次（包含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a”和”ab*ac*a”匹配，但是与”aa.a”和”ab*a”均不匹配前两天刚看了有关正则表达式的基本语法和用法，今天刷牛客，就恰好碰到了这个题。

2016-05-20 14:30:25 1336

原创《剑指offer》-- 二叉树的下一个结点

题目描述：给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。解题思路： /** * 思路： * * 对于一个节点，其后续节点有三种形式： * 1. 该节点的右指针为null，那么就往前找其父节点（设为a）， *

2016-04-03 09:32:51 1435

原创《剑指offer》——孩子们的游戏(圆圈中最后剩下的数)

T: 题目描述 * 每年六一儿童节,NowCoder都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为NowCoder的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,

2015-12-14 20:51:13 1297

原创《剑指offer》——链表中环的入口结点

T: 题目描述一个链表中包含环，请找出该链表的环的入口结点。基本做法不考虑其中潜在的规律，就按照一般的方法，创建一个list，把扫描过的节点都存储在list中，知道下一个节点在list中已经存在，那就说明该节点就是入口节点。这种方式下的时间复杂度为O(n2)O(n^2)我的code: /* public class ListNode { int va

2015-12-13 20:02:01 4318 1

原创《剑指offer》——左旋转字符串

T: 题目描述汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！片段截取法这种方法，相对于最笨的方法来说，已经做了改进。改进的地方在于：如果

2015-12-10 21:34:42 694

原创《剑指offer》——把字符串转换成整数

T: 题目描述将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。这种题目交代不清楚，也没啥技巧含量和思考价值，既然出现了，就顺带着做一下吧。。code: /** * T: 把字符串转换成整数 * * 题目描述 * 将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。 * * date:

2015-12-10 20:53:08 874

原创《剑指offer》——对称的二叉树

定义法递归法T: 题目描述请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。定义法这道题目，竟然没有想出来如何用递归做，虽然也在最开始做了挣扎，还是没找到递归的切入点，只得从定义出发，先按照原二叉树，搞一个新的镜像，然后再搞个函数，对比两个树是否完全相同，貌似很麻烦，其实做起来，确实很麻烦。。。code: cla

2015-12-09 22:35:03 1693

原创《剑指offer》——字符流中第一个不重复的字符

T: 题目描述请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符”go”时，第一个只出现一次的字符是”g”。当从该字符流中读出前六个字符“google”时，第一个只出现一次的字符是”l”。输出描述: 如果当前字符流没有存在出现一次的字符，返回#字符。这道题目不知所云，做的也是稀里糊涂。。。。ORZ……code: impor

2015-12-08 21:14:41 829

原创《剑指offer》——和为S的连续正数序列

遍历穷举法滑动窗口法T: 题目描述小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!

2015-12-07 21:56:55 2213 1

原创《剑指offer》——重建二叉树

T: 题目描述输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。不解释了，麻烦的连自己都懒得解释了，直接上代码吧，今天也太累了，事情太多，心里乱糟糟的。。code: /** * T:

2015-12-06 22:34:03 471

原创《剑指offer》——调整数组顺序使奇数位于偶数前面

T: 题目描述输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。这道题目，我思考了好久，想过各种解决方案，都是基于在本数组上进行操作，无额外的数组开销，还要考虑线性复杂度。但是最终还是没找到解决方案，只得用额外开辟数组的方式来解决。我的核心code: /*

2015-12-05 19:55:44 553

原创《剑指offer》——数组中重复的数字

T: 题目描述在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是重复的数字2或者3。太初级的题目，不解释了。。。我的code:/** * T: 数组中重复的数字 * * 题目描述

2015-12-04 21:46:13 1023

原创《剑指offer》——按之字形顺序打印二叉树

T: 题目描述请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。这道题目与前几天做的一道题目《把二叉树打印成多行》类似，只不过拿到题目里，把每一层的节点都保存在一个单独数组当中，这道题目中，需要按照“之”字形保存，很简单，用个flag标记一下就能做到。我的code: import j

2015-12-04 14:42:52 590

原创《剑指offer》——二叉搜索树与双向链表

T: 题目描述输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。这道题目，解决思路不难，类似于先序遍历，只不过要在压栈和出栈的过程中，把树的结构变为一个双向链表。一张图解释用栈的解题思路：详细说明都在代码注释当中.code： /** public class TreeNode { int

2015-12-03 21:24:37 453

原创《剑指offer》——二叉树的镜像

T: 题目描述操作给定的二叉树，将其变换为源二叉树的镜像。题目考察的是在二叉树中递归的使用。这种递归也是最简单的递归，初级的不能再初了。。。code: /** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null;

2015-12-02 21:55:42 824

原创《剑指offer》——把二叉树打印成多行

T: 题目描述从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。解法都在代码注释当中了。我的code: import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; /* public class TreeNode {

2015-12-01 16:50:49 1053

原创《剑指offer》——二叉树中和为某一值的路径

T: 题目描述输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。这道题从昨天晚上就在抠，抠了两个小时，最终代码写出来了，感觉有bug，没敢提交。前一个小时，自己独立思考，寻找解题思路，也知道用递归，可如果使用递归？递归函数的定义该怎么设置？还是没思路。。。后来在网上看到有博客中给出了相关的二叉

2015-11-30 10:50:32 1397

原创《剑指offer》——二叉搜索树的后序遍历序列

T: 题目描述输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。考察二叉搜索树的后序遍历特征，具体的特征说明，以及结题思路，已在代码的注释当中详细解释。code: /** * T: 二叉搜索树的后序遍历序列 * * 题目描述 * 输入一个整数数组

2015-11-28 11:32:22 737

原创《剑指offer》——数组中出现次数超过一半的数字

T: 题目描述数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。如果用暴力搜索，那就太没意思了，所有的问题都可以用枚举法解决。我的解法：把当前array数组的第0号元素，即array[0]，与后面的作比较，如果相等，计数

2015-11-27 17:14:15 896

原创《剑指offer》——和为S的两个数字

T: 题目描述输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。输出描述: 对应每个测试案例，输出两个数，小的先输出。注意到数组有序，最基本的做法，那就是两层循环，挨个找，但是耗时，时间复杂度为O(n2)O(n^2)。既然数组有序，能不能利用“有序”的特性呢？两者比较，始终以前面的

2015-11-26 19:10:41 691

原创《剑指offer》——删除链表中重复的结点

T: 题目描述在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。例如，链表1->2->3->3->4->4->5 处理后为 1->2->5 题目不难，细心做就行。code: /* public class ListNode { int val; ListNode next = null;

2015-11-25 20:07:35 685

原创《剑指offer》——扑克牌顺子

T: 题目描述 LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^_^)…他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿！！“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子…..LL不高兴了,他想了想,决定大\小王可以看成任何数字,并且A看作1,J为11,Q为1

2015-11-24 19:46:27 500

原创《剑指offer》——从上往下打印二叉树

T: 题目描述从上往下打印出二叉树的每个节点，同层节点从左至右打印。这道题没什么难的，就是一个树的层次遍历，用个队列即可。code: import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.Queue; /*

2015-11-23 21:34:18 834

原创《剑指offer》——数组中只出现一次的数字

hashMap利用只出现一次的关系T: 题目描述一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。题目类似于前两天做的一道题目：”第一个只出现一次的字符位置”。但不同的是这次找出数组中，只出现一次的数字，仅仅是元素类别不同，结题方式就完全不同了。hashMap首先想到的是用hashMap去做，但是这种做法，并不算高效，解法没有第二种方法巧

2015-11-22 20:24:29 741

原创《剑指offer》——数字在排序数组中出现的次数

非二分查找二分查找T: 题目描述统计一个数字在排序数组中出现的次数。先来说说这道题的用时判断，真的是不太一样啊，非二分查找比二分查找的用时还短，只能说明是出题者给出的测试用例的问题。非二分查找如果不用二分查找，其复杂度均为O(n)O(n)。一般的有两种方式：可以从前往后遍历，先碰到一个为k的，然后找下一个不是为k的下标；从两端开始遍历，即分别找k元素的两端，然后相减。这两种

2015-11-22 14:54:23 388

原创《剑指offer》——平衡二叉树

T: 题目描述输入一棵二叉树，判断该二叉树是否是平衡二叉树。该题目我想了好久，总是想在一个递归函数内解决这个问题，最后没能找出解决方案。本题的关键在于两个部分的求解：要计算每个节点的深度（或者计算该节点两个孩子节点的深度）；根据两个子节点的深度差判断该以该节点为子树的结构是否为平衡二叉树。第一个问题的求解，就需要递归解决，第二个问题，也要递归解决。比如：节点a的两个子节

2015-11-21 17:25:41 816

原创《剑指offer》——把数组排成最小的数

T: 题目描述输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。最开始的想法就是找规律，没有想到用java当中的Collections的排序功能去做。找规律既然是找规律，那就找吧，可这个规律也是不太好找，一次次的试错，才找出如下规律：既然是将数组中的各个元素

2015-11-21 13:21:15 483

原创《剑指offer》——整数中1出现的次数（从1到n整数中1出现的次数）

T: 题目描述求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数。两种解决方式：找规律和暴力遍历暴力遍历化为字符串，或者用10取余，都是一样的道理：c

2015-11-19 19:53:48 959

原创《剑指offer》——第一个只出现一次的字符位置

T: 题目描述在一个字符串(1<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符的位置。若为空串，返回-1。位置索引从0开始. 这道题目，和以下问题的解决思路类似：问题：给定一个字符串，该字符串都是由阿拉伯数字0~9组成，该字符串可能很长(几万，甚至更长)，问如何更快的找出所有只出现过一次的数字？解法相同，而设定场景不同，这就是需要融会贯通的地方。比

2015-11-17 22:20:20 1078

原创《剑指offer》——两个链表的第一个公共结点

T: 题目描述输入两个链表，找出它们的第一个公共结点。最基本的方法，遍历：code: class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } } /**

2015-11-16 19:20:54 362

原创《剑指offer》——栈的压入、弹出序列

T: 题目描述输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4，5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。看到这道题目，我想到了本科的时候，算法选修课上老师讲到的一个火车进站、出站的问题：当时说说有n节有编

2015-11-16 08:52:26 440

原创《剑指offer》——复杂链表的复制

T: 题目描述输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点）。这个题，看到一阵子，没搞懂什么意思，待看到函数名Clone，才恍然大悟过来，随即来了句return pHead; 提交之后发现错误，得知其后台是有内存地址判断机制的，不能把原来的一模一样的给照搬过去。比较常规，效率也比较高的做法，就是在每个节点后面都再插入一个新的

2015-11-15 10:50:27 1183

原创《剑指offer》——链表中倒数第k个结点

T: 题目描述输入一个链表，输出该链表中倒数第k个结点.这种考题是比较简单的一种，以前也碰到过类似的题目，从耗时来说，一般都是使用两个指针，一前一后的走，中间间隔k或者k-1个步长，这个视判断语句而定。当前一个指针走到末端时，后一个指针正好落在倒数第k个节点处，直接返回该节点。code: /* public class ListNode { int val

2015-11-13 20:46:35 572

原创《剑指offer》——丑数

T: 题目描述把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。啥都不说了，都在代码里了……code: /** * T: 丑数 * * 题目描述 * 把只包含因子2、3和5的数称作丑数（Ugly Numbe

2015-11-12 21:16:25 400

原创《剑指offer》——数组中的逆序对

T: 题目描述在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。暴力搜索法直接看代码，简洁明了。 code:public int InversePairs(int [] array) { int nums = 0; for (int i = 1; i < array.length; i++)

2015-11-12 09:12:24 501

原创《剑指offer》——连续子数组的最大和

T: 题目描述 HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。你会不会被他忽悠住

2015-11-09 21:39:51 505

原创《剑指offer》——最小的k个数

T: 题目描述输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。这道题目的常规做法，就是用先对原有的数组按升序排序，取前k个即可。但是当数组很大，而k值相比之下比较小时，这种做法就是费时费力不讨好了，因为花了很多的无用功对k后面的数进行排序。。。怎么避免呢？比较常用的就是冒泡法，新开辟一个数组，将原数组遍历一遍，

2015-11-08 20:29:20 528