- 博客(151)
- 收藏
- 关注
RSS订阅
原创 深入理解Java的接口与抽象类
首先，自己的理解： 接口类描述的是行为，抽象类描述的是根源；接口是对动作的抽象，抽象类是对根源的抽象。一、抽象类在了解抽象类之前，先来了解一下抽象方法。抽象方法是一种特殊的方法：它只有声明，而没有具体的实现。抽象方法的声明格式为：abstract void fun();抽象方法必须用abstract关键字进行修饰。抽象方法充当着占位的角色，它们的具体实现在子类中。如果一个类含有抽象方法，则称这个类...
2018-03-14 18:57:05
192
原创 常用的八种排序算法的原理实现及其比较（JAVA实现）
首先说明一个概念问题，排序的稳定性问题。如果Ai = Aj，排序前Ai在Aj之前，排序后Ai还在Aj之前，则称这种排序算法是稳定的，否则说明该算法不稳定。我们这里说说八大排序就是内部排序。 当n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序序。 快速排序：是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均...
2018-03-06 13:36:38
678
原创 初识RabbitMQ工作原理及简单使用
目录1. RabbitMQ简介2. 使用场景3. 为什么使用RabbitMQ4. 工作机制5. 消息持久化持久化工作原理持久化的缺点1. RabbitMQ简介MQ全称Message Queue，可以理解为消息队列的意思，简单来说就是消息以管道的方式进行传递。RabbitMQ是一个实现了AMQP（Advanced Message Queuing Proto...
2019-05-11 17:40:55
244
原创 LintCode 182：删除数字
描述给出一个字符串 A, 表示一个 n 位正整数, 删除其中 k 位数字, 使得剩余的数字仍然按照原来的顺序排列产生一个新的正整数。找到删除 k 个数字之后的最小正整数。N <= 240, k <= N样例给出一个字符串代表的正整数 A 和一个整数 k, 其中 A = 178542, k = 4返回一个字符串 "12"分析：用StringBuffer表示字符...
2018-07-29 16:28:10
700
原创 LintCode：402. 连续子数组求和
描述给定一个整数数组，请找出一个连续子数组，使得该子数组的和最大。输出答案时，请分别返回第一个数字和最后一个数字的下标。（如果两个相同的答案，请返回其中任意一个）样例给定 [-3, 1, 3, -3, 4], 返回[1,4].分析：变量ans保存当前最大的连续子数组之和，sum表示当前start-end之间的和，遍历数组，如果sum<0，则重置start和end位置，其他情况...
2018-07-25 17:21:04
401
原创 LintCode：170 旋转链表
描述给定一个链表，旋转链表，使得每个节点向右移动k个位置，其中k是一个非负数样例给出链表1->2->3->4->5->null和k=2返回4->5->1->2->3->null分析：首先，遍历一遍链表得到链表长度len和原链表最后一个结点pNode。然后k=k%len，如果k为0，表示移动后为本身，直接返回head...
2018-07-19 10:39:56
234
原创 LintCode：买股票的最佳时机系列
LintCode 149：假设有一个数组，它的第i个元素是一支给定的股票在第i天的价格。如果你最多只允许完成一次交易(例如,一次买卖股票),设计一个算法来找出最大利润。分析：因为只能买卖一次，所以应该选择价格最低的买入，价格最高的卖出，用变量保存最小的买进值，并得到当前卖出所得的利润，与当前最大利润相比选择较大的。public int maxProfit1(int[] prices...
2018-07-17 10:35:32
250
原创 LintCode：118.不同的子序列（考点：动态规划）
描述给出字符串S和字符串T，计算S的不同的子序列中T出现的个数。子序列字符串是原始字符串通过删除一些(或零个)产生的一个新的字符串，并且对剩下的字符的相对位置没有影响。(比如，“ACE”是“ABCDE”的子序列字符串,而“AEC”不是)。 样例给出S = "rabbbit", T = "rabbit"返回 3分析：采用动态规划的思想，dp[i][j]表示S前i个字符中含有T前j个字符的个数，不管S...
2018-07-14 13:35:33
269
原创 Lintcode：136.切割回文串 VS 108. 切割回文串II（考点：回溯法、DFS、DP）
136. 切割回文串描述给定一个字符串s，将s分割成一些子串，使每个子串都是回文串。返回s所有可能的回文串分割方案。样例给出 s = "aab"，返回[ ["aa", "b"], ["a", "a", "b"]]分析：本题采用回溯法，深度优先遍历字符串。注意保存子结果的条件以及每次返回上一层时（回溯时），需要把子结果中的在该层添加的（最后添加的）删掉再返回上一层。public c
2018-07-11 11:03:50
306
原创 2019多益网络秋招视频面试算法题：将一个长度为n的数组A的元素循环右移k位
题目：将一个长度为n的数组A的元素循环右移k位 比如数组 1, 2, 3, 4, 5 循环右移3位之后变成 3, 4, 5, 1, 2方法一： 首先考虑k。如果k能被数组长度len整除，那么数组顺序不变，可以直接输出数组。如果不能整除，得到k=k%len。将数组右移k次，每次都把数组最后一位保存，然后从下标为len-2到0的数都往右移动一位，最后把原来最后一位放到数组开头。public vo...
2018-07-09 15:08:38
2040
原创 LintCode：119.编辑距离(动态规划)
描述给出两个单词word1和word2，计算出将word1 转换为word2的最少操作次数。你总共三种操作方法：插入一个字符删除一个字符替换一个字符分析：采用动态规划解题，初始化dp数组，int[][] dp=new int[word1.length+1][word2.length+1]，dp[i][j]表示到word1下标为i，word2下标为j时的最小编辑距离。当i=0时，dp[0][j]=j...
2018-07-09 15:08:26
515
原创 LintCode：139.最接近零的子数组和
描述给定一个整数数组，找到一个和最接近于零的子数组。返回第一个和最右一个指数。你的代码应该返回满足要求的子数组的起始位置和结束位置您在真实的面试中是否遇到过这个题？ 是样例给出[-3, 1, 1, -3, 5]，返回[0, 2]，[1, 3]， [1, 1]， [2, 2] 或者 [0, 4]。挑战O(nlogn)的时间复杂度分析：定义一个pair结构有两个成员变量 sum和 index，表示的...
2018-07-08 21:35:11
496
原创 LintCode：跳跃游戏 I VS跳跃游戏 II
描述给出一个非负整数数组，你最初定位在数组的第一个位置。 数组中的每个元素代表你在那个位置可以跳跃的最大长度。 判断你是否能到达数组的最后一个位置。分析：方法一：基于动态规划的做法，时间复杂度O(n^2)。数组dp[i]表示能否到达下标为i的位置，对于从下标i=1开始的每一个位置，都从下标j=0开始到i-1判断能否到达j，并且判断从j开始最远能否跳到或超过i的位置，如果能，则令dp[i]...
2018-07-07 14:47:08
533
原创 LintCode：110.最小路径和（动态规划）
描述给定一个只含非负整数的m*n网格，找到一条从左上角到右下角的可以使数字和最小的路径。你在同一时间只能向下或者向右移动一步分析：典型的动态规划题。dp数组为m+1行，n+1列。dp[i][j]表示到网格(i,j)处时的最小路径和，可表示为dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i-1][j-1]，但注意第一行和第一列的元素只能从其左边元素和上边元素得到，...
2018-07-05 13:40:27
496
原创 LintCode：124.最长连续序列
题目：描述给定一个未排序的整数数组，找出最长连续序列的长度。说明要求你的算法复杂度为O(n)样例给出数组[100, 4, 200, 1, 3, 2]，这个最长的连续序列是 [1, 2, 3, 4]，返回所求长度 4分析：由题可以看出要求时间复杂度为O(n)，所以排序不能使用。想到使用hashset数据结构保存数组元素，然后依次遍历数组，对于每一个数组元素，分别找到其下一个元素right和上一个元素...
2018-07-05 11:24:05
491
原创 数字和为sum的方法数（动态规划）——网易2017内推笔试编程题
链接：https://www.nowcoder.com/questionTerminal/7f24eb7266ce4b0792ce8721d6259800来源：牛客网给定一个有n个正整数的数组A和一个整数sum,求选择数组A中部分数字和为sum的方案数。 当两种选取方案有一个数字的下标不一样,我们就认为是不同的组成方案。输入描述:输入为两行: 第一行为两个正整数n(1 ≤ n ≤ 1000)，s...
2018-07-02 17:08:16
1416
原创 幸运的袋子——网易2017内推笔试编程题
链接：https://www.nowcoder.com/questionTerminal/a5190a7c3ec045ce9273beebdfe029ee来源：牛客网一个袋子里面有n个球，每个球上面都有一个号码(拥有相同号码的球是无区别的)。如果一个袋子是幸运的当且仅当所有球的号码的和大于所有球的号码的积。 例如：如果袋子里面的球的号码是{1, 1, 2, 3}，这个袋子就是幸运的，因为1 + 1...
2018-07-01 16:32:31
487
原创 LintCode：100. 删除排序数组中的重复数字VS 101. 删除排序数组中的重复数字II
描述给定一个排序数组，在原数组中删除重复出现的数字，使得每个元素只出现一次，并且返回新的数组的长度。不要使用额外的数组空间，必须在原地没有额外空间的条件下完成。样例给出数组A =[1,1,2]，你的函数应该返回长度2，此时A=[1,2]。分析：遍历数组，定义变量size=0，从nums[size]开始依次与nums中每一个元素比较，若相等，则比较后一个元素；若不等，则将size+1，将nums[s...
2018-06-30 15:18:42
180
原创 LintCode：134.LRU缓存策略
描述为最近最少使用（LRU）缓存策略设计一个数据结构，它应该支持以下操作：获取数据（get）和写入数据（set）。获取数据get(key)：如果缓存中存在key，则获取其数据值（通常是正数），否则返回-1。写入数据set(key, value)：如果key还没有在缓存中，则写入其数据值。当缓存达到上限，它应该在写入新数据之前删除最近最少使用的数据用来腾出空闲位置。分析可以定义一个双向链表来实现元素...
2018-06-29 20:21:36
393
原创 统计回文——网易2017内推笔试编程题
链接：https://www.nowcoder.com/questionTerminal/9d1559511b3849deaa71b576fa7009dc来源：牛客网“回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。花花非常喜欢这种拥有对称美的回文串，生日的时候她得到两个礼物分别是字符串A和字符串B。现在她非常好奇有没有办法将字符串B插入字符串A使产生的字...
2018-06-29 17:30:41
282
原创 手写Spring MVC框架（包含Java注解的实现）
主要从以下几点入手 ： 一、了解SpringMVC运行流程及九大组件 二、梳理自己的SpringMVC的设计思路 三、实现自己的SpringMVC框架了解SpringMVC运行流程及九大组件运行流程：1.用户发送请求->DispatcherServlet；用户向服务端发送请求，被Spring的前端控制器DispatcherServlet截获。2.DispatcherServlet->H...
2018-06-26 11:08:18
1146
原创 LintCode：44.最小子数组
题目：给定一个整数数组，找到一个具有最小和的子数组。返回其最小和。分析：贪心算法，数组的每个元素都可以加或者不加，从第一个元素开始判断，包括第一个元素时和不包括第一个元素的情况取最小值。public int minSubArray(List<Integer> nums) { // write your code here int min=nums.get...
2018-06-23 13:50:51
303
原创 LintCode 104：Merge K Sorted Lists（合并K个排序链表）
题目：合并k个排序链表，并且返回合并后的排序链表。样例给出3个排序链表[2->4->null,null,-1->null]，返回 -1->2->4->null分析：采用归并排序的思想。数组的数递归划分，一分二，二分四…直至最后一个数单独的成为一组，然后再进行归并划分采用的递归实现。即把K个链表一直对分直到最后一个链表为一组，然后进行递归两两归并，两两归并的操作即...
2018-06-22 13:17:57
190
原创 LintCode388：第k个排列
题目：给定 n 和 k，求123..n组成的排列中的第 k 个排列。分析：首先考虑能不能确定第k个排列是以哪个数字开头，以[1,2,3,4]的全排列为例，找第14个排列以1开头的排列总共有3!个，原因是第一个位置是1，剩下3个位置可以随便排列，有6个以2开头的排列总共有3!个，原因是第一个位置是2，剩下3个位置可以随便排列，有6个此时已经有12个排列所以剩下的两个排列即第14个排列一定在以3开头的...
2018-06-21 11:49:31
186
原创 分苹果——网易2017内推笔试编程题
链接：https://www.nowcoder.com/questionTerminal/a174820de48147d489f64103af152709?source=relative来源：牛客网n 只奶牛坐在一排，每个奶牛拥有 ai 个苹果，现在你要在它们之间转移苹果，使得最后所有奶牛拥有的苹果数都相同，每一次，你只能从一只奶牛身上拿走恰好两个苹果到另一个奶牛上，问最少需要移动多少次可以平...
2018-06-20 10:36:59
608
原创 合唱团——网易2017内推笔试编程题
链接：https://www.nowcoder.com/questionTerminal/661c49118ca241909add3a11c96408c8来源：牛客网有 n 个学生站成一排，每个学生有一个能力值，牛牛想从这 n 个学生中按照顺序选取 k 名学生，要求相邻两个学生的位置编号的差不超过 d，使得这k 个学生的能力值的乘积最大，你能返回最大的乘积吗？ 分析：本题采用动态规划的思想。对该问...
2018-06-19 14:14:36
504
原创 LintCode：最长上升子序列、最长公共子序列、最长公共子串
问题1：最长上升子序列最长上升子序列的定义：最长上升子序列问题是在一个无序的给定序列中找到一个尽可能长的由低到高排列的子序列，这种子序列不一定是连续的或者唯一的分析：动态规划，dp[i]表示到nums[i]为止的最长上升子序列长度。dp[i]=max(dp[i],dp[j]+1)，其中0<=j<i且nums[j]<nums[i]其中，dp[i]初始都设为1，因为自身也是一个上升子...
2018-06-14 11:09:20
264
原创 LintCode：64. 合并排序数组
题目：合并两个排序的整数数组A和B变成一个新的数组。你可以假设A具有足够的空间（A数组的大小大于或等于m+n）去添加B中的元素。分析：采用归并排序的方法，首先开辟一个额外空间，大小是两个数组之和，存放排序后的数组。也可以不使用额外空间，如果数组为一长一短且长的数组能容纳所有元素的话，可以从数组末尾开始遍历，进行归并排序。//额外的空间，从前往后遍历 public void mergeSor...
2018-06-13 09:59:58
390
原创 LintCode：433. 岛屿的个数
题目：给一个01矩阵，求不同的岛屿的个数。0代表海，1代表岛，如果两个1相邻，那么这两个1属于同一个岛。我们只考虑上下左右为相邻。分析：采用深度优先搜索的方法，对于位置(i,j)的数，若为1，则为岛屿，则对该位置进行深度优先遍历，使得其四周为1的置为0，并递归下去，类似于深度搜索。将该位置四周的为1的变为0的意思就是把它们看成与该位置为同一个岛屿，则再遍历的时候就不会计它们的数（如果原来为1，岛屿...
2018-06-12 20:03:55
651
原创 LintCode：701. 修剪二叉搜索树
题目：修建二叉树，使得树中所有的结点值在区间[a,b]之间。输入：输出：思路：关于二叉树的题，大部分都采用递归的方法来做。当root位于L和R之间时，递归的修剪其左右子树，并返回root。当root的值小于L，其左子树都小于L，故舍弃其左子树，递归的修剪其右子树，并返回修剪后的右子树。当root的值大于L，其右子树都大于L，故舍弃其右子树，递归的修剪其左子树，并返回修剪后的左子树。如果root的值...
2018-06-10 23:35:25
322
原创 LintCode: 78. 最长公共前缀（LCP）
题目：分析：直接两两进行比较，用res保存当前最长的公共前缀。public class Solution { /** * @param strs: A list of strings * @return: The longest common prefix */ public String longestCommonPrefix(String[] st...
2018-06-06 11:32:03
575
原创 LintCode：15. 全排列（不含重复元素）VS 16. 全排列（含重复元素）
题目：分析：采用深度优先搜索的递归方法，考虑一个个将元素放入排列中，递归求解，建立一个访问标志数组，记录已经访问过的数，递归终止的条件是排列的长度等于数组的长度时，递归结束。（需要记得回溯）public class Solution { /* * @param nums: A list of integers. * @return: A list of permutat...
2018-06-04 15:19:37
215
原创 LintCode：650. Find Leaves of Binary Tree
题目：分析：遍历二叉树，找到叶子结点后，将其加入到list中，然后置为null，这样可以一层层剥离开来。/** * Definition of TreeNode: * public class TreeNode { * public int val; * public TreeNode left, right; * public TreeNode(int val)...
2018-06-04 10:20:39
274
原创 LintCode：30. 插入区间
题目：分析：在非重叠的区间中插入一个新的区间，可能还需要与原有的区间进行合并，因此要对给定的区间集合进行遍历，需要考虑两点：新插入的区间与原有区间不重叠，重叠的情况分为两种：第一种是新区间的start>原区间的end；第二种是新区间的end<原区间的start。这种情况直接将新区间插入到对应的位置即可。新插入的区间与原有区间重叠，可能存在多个重叠，所以需要更新区间的范围来包含所有重叠。...
2018-06-02 16:59:50
302
原创 ConcurrentHashMap的JDK1.7和JDK1.8的实现
JDK1.7 ConcurrentHashMap（支持并发）ConcurrentHashMap 是一个 Segment 数组，Segment 通过继承 ReentrantLock 来进行加锁，所以每次需要加锁的操作锁住的是一个 segment，这样只要保证每个 Segment 是线程安全的，也就实现了全局的线程安全。ConcurrentHashMap 有 16 个 Segments，所以理论上，最...
2018-05-30 20:27:44
848
原创 LintCode：62. 搜索旋转排序数组 VS 63. 搜索旋转排序数组II
题目：分析：看到排序数组的查找问题，就要想到二分查找。旋转排序数组其实是由两个递增子数组组成，且前一个子数组中的任意元素都大于后一个数组中元素。left,right分别是指向数组首尾的两个指针。循环条件：left<=right若A[mid]==target，表示若A[mid]>A[left]，表示left与mid均处于前一个递增数组中。 若target>=A...
2018-05-30 15:49:54
421
原创 LintCode：91.最小调整代价（动态规划）
题目：分析：本题类似于一个背包问题，数组中的元素一个个调整，由于是求相邻元素的差值，所以只和前一个相邻元素的值有关，所以只需要记录上一个调整的值就可以。dp[i][j]表示调整到第i个数时，此时，第i个数取值为j，为代价和最小。显然dp[i-1][k]已知，则调整的总代价为dp[i][j]=dp[i-1][k]+abs(j-A[i])由于j和k有多种取值可能，所以循环求解判断，k表示前一个数，j表...
2018-05-29 10:03:12
1149
原创 LintCode: 889 屏幕句子适配
分析：直接采用暴力法解决，对于每一行，分析该行可以容纳的单词数，这涉及到列数与单词长度之间的大小关系。public class Solution { /** * @param sentence: a list of string * @param rows: an integer * @param cols: an integer * @return...
2018-05-25 10:14:07
375
原创 LintCode：785. 最大权值和路径（动态规划）
思路：这是一道典型的动态规划题，思路类似于背包问题，dp中每个元素的值分别是来自于该位置上方和该位置右边的较大的一个值，新建dp矩阵，int[][] dp=new int[row+1][col+1]。注意是从右上角开始到左下角结束，状态转移方程为 dp[i][j]=max(dp[i][j+1]+nums[i-1][j],dp[i-1][j]+nums[i-1][j])（i从1开始，j从col-1递...
2018-05-24 10:33:58
1324
原创 LintCode：511. 交换链表中的两个节点
分析：首先，因为头结点也有可能被交换，所以需要在头结点之前创建一个新结点，然后连接到现有的链表之前。新建指针pre1和pre2作为v1和v2的前结点，扫描链表，若pre1或者pre2为空，说明未找到v1或v2。如果pre1和pre2相邻，即pre1.next=pre2，则交换，使得pre1在前pre2在后。讨论两种情况，分别为pre1.next==pre2和pre1与pre2不相邻的情况。publ...
2018-05-23 10:57:09
386
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人