- 博客(102)
- 资源 (12)
- 收藏
- 关注
RSS订阅
原创 工厂模式总结
为什么使用工厂模式软件开发没有银弹，一种设计思路好，必然有道理。这里讲下工厂模式，工厂模式属于创建型设计模式。比如你有一家披萨店，可以造出各种各样的披萨，另外有客户订购披萨。这样就可以使用工厂模式来创建披萨。简单工厂在实际项目中使用最多的是简单工厂，而且一般业务问题也比较好抽象成简单工厂的方式。UML图:Tips:其中Pizza类可以做成一个抽象类，当然做成接口也可以，然后让对应的子类去实现。基类/抽象类/接口代码实现public abstract class Pizza {
2021-04-07 16:58:43
101
原创 代理模式
什么是代理模式代理模式的主要目的是通过代理对象访问目标对象，这样达到的效果和直接访问目标对象是一样的。代理模式的应用场景比较多，比如AOP的底层实现等。被代理对象的场景远程对象，不方便直接访问创建开销大的对象需要安全控制的对象需要加一些通用切面操作怎样设计代理模式首先需要知道客户端直接接触的是代理对象， 这个时候访问代理对象和访问原始对象一样。客户端使用代码如下: public static void main(String[] args) { OriginD
2021-04-06 18:37:17
181
原创 如何实现一个线程安全的LRU
LRU是什么LRU的中文名字为最近最少使用缓存，一言以蔽之，当加入元素超过存储容量的时候会剔除最少使用过的元素。并且需要get()操作的时间复杂度为O(1)。LRU有什么作用LRU在某种程度上可以作为一种淘汰策略使用，比如redis的淘汰策略中就有LRU的淘汰方式。LRU的简单实现通过上述描述可以知道，我们需要两种基本的数据结构，哈希表(用于get和put操作以及在O(1)时间复杂度下实现查询操作)和双向链表(可以设计为链表尾部加入最近访问的元素，链表头部剔除最近未被访问的元素) 。在Java中
2021-04-06 16:34:29
1942
2
原创 单例模式总结
单例模式的几种写法懒汉式加重型锁public class Single { private static Single instance; private Single() { } public synchronized static Single getInstance() { if (instance == null) { instance = new Single(); } retu
2021-03-29 20:23:35
112
原创 Two Sum类问题
引言：Two Sum类问题属于对撞型双指针问题，这类问题的思路不难，但是变形以及问法比较多，这里将部分题目做归纳总结。 在Two Sum问题中，需要用的预处理为排序。但有的时候需要返回索引的位置，就需要设计数据结构先保存索引信息，再进行排序。如果不想这样麻烦的话，可以借助哈希表这个常用的数据结构来代替双指针。题解：1.两数之和 II Two Sum问题的基本变形，在一组整数中找出多少对整数，大于给
2017-06-20 19:53:28
759
原创 滑动窗问题
引言：在面试中有一类问的比较多的问题–滑动窗问题，滑动窗问题本质上属于双指针问题中的前向型双指针（一个方向的双指针）。 滑动窗口问题一般题目会很典型，要求我们一直维护一个size为k的window，然后do some operation/calculate something within that window。基本思路就是每次不管三七二十一先把当前新的元素加进来，然后如果有需要(
2017-06-16 17:13:43
788
原创 背包问题细节探析
引言：上一周在看《背包九讲》，这周也在练习背包型动态规划的题目，在这里分享几点学习过程中的体会，涉及到空间优化：二维转一维的理解以及循环顺序的理解，最后会析背包问题的一些变种问题。为了叙述方便，这篇博客仅仅谈及01背白问题和完全背包问题，其余读者感兴趣可以自己查阅《背包九讲》01背包01背包问题是所有背包问题的基础，先来看裸的01背包问题： 题目：有N件物品和一个容量为V 的背包。第i件物品的费用
2017-06-08 21:12:57
4052
原创 java的list转换为树形结构
背景从数据库中取出一段数据, 这些数据会有层级关系, 带上id和parent_id, 现在需要把这些数据转化为树形结构…在实际工作中这个是一个比较常见的问题，比如部门的层级关系, 省市区的层级关系，四级目录关系…...
2021-06-01 10:44:19
320
原创 单调栈&单调队列总结
单调栈介绍单调栈的意思是维护一个单调递增或者单调递减的栈, 最通用的解法是找到右边第一个比它大的元素或者找到右边第一个比它小的元素。具体实现由于在Java中的Stack性能很差，而且不够灵活，所以不推荐使用.一般有两种替代方案:ArrayDeque -----底层为数组push()----压栈pop() —出栈peek() —取栈顶pollLast() —取栈尾(这里其实有点像队列了…)LinkedList ----底层为链表...
2021-04-22 14:38:03
119
原创 链表数据结构特点
引言最近在重温链表的算法题，发现很久没做，竟毫无思路。其中的一些基本套路都已经忘了，其实我想到其实是自己没有总结链表这个数据结构的一些tricks.链表数据结构的特点为了简便，这里以单链表为例子说明，为了便于读者理解，这里和数组作为对比。在数组中，是通过索引访问元素的，但是不要小看索引，好多精妙的算法都是利用了这个索引玩花样。但是链表不能，只能通过链一个一个的找。这个说明了链表的优势不在快速找到元素
2017-11-14 11:25:36
15897
原创 Java与C++编译过程比较
引言前段时间读了周志明的 《深入理解Java虚拟机》，学习了java编译器的工作过程，同时也顺带复习了 C++的编译过程，将两者进行学习对比，希望对读者有所帮助。Java编译过程 java的编译过程分为前端编译器(javac)与后端编译器(JIT),前端编译器生成字节码文件(xx.class)，后端编译器生成机器码。Java前端编译器(javac) 1 .注解处理：在JDK1.5之后开始支持注解
2017-05-27 16:57:34
1225
1
原创 排列序号
排列序号给出一个不含重复数字的排列，求这些数字的所有排列按字典序排序后该排列的编号。其中，编号从1开始。思路：这个问题是一个组合数学问题，如果知道 康托展开，那么好理解一点。但是绝大部分人应该都不知道康托展开。对于这道题，有高中数学基础也就够了，为了便于描述，这里给康托展开的描述，我来解释原因。 3 5 7 4 1 2 9 6 8 展开为 98884 X=2*8!+3*7!+4*6!+2*
2017-05-18 21:11:28
1939
原创 排列&组合问题总结
全排列(不带重复元素)Ex:给出一个列表[1,2,3]，其全排列为： [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]Code:解法一：class Solution { /** * @param nums: A list of integers. * @return:
2017-05-16 20:24:01
260
原创 下一个排列
问题描述：给定一个若干整数的排列，给出按正数大小进行字典序从小到大排序后的下一个排列。如果没有下一个排列，则输出字典序最小的序列。Ex:左边是原始排列，右边是对应的下一个排列。 1,2,3 → 1,3,23,2,1 → 1,2,31,1,5 → 1,5,1思路分析：刚开始看这个题目没有看懂，在网上搜集一番资料后，懂得了题目想要做的事情。 给出数字序列的全排列，按照字典序排好，找到对应的下一个排列
2017-05-14 15:15:37
243
原创 书籍复印
问题描述：给出一个数组A包含n个元素，表示n本书以及各自的页数。现在有个k个人复印书籍，每个人只能复印连续一段编号的书，比如A[1],A[2]由第一个人复印，但是不能A[1],A[3]由第一个人复印，求最少需要的时间复印所有书。Ex:A = [3,2,4],k = 2返回5，第一个人复印前两本书心路历程这是一道hard级别的题目，以前我认为hard题目太难，就没有管，非常喜欢做easy级别的难度题。
2017-05-11 19:59:02
753
原创 closest-number-in-sorted-array
问题描述：在一个排好序的数组 A 中找到 i 使得 A[i] 最接近 target解法一：思路:Naive二分查找，如果找到target就返回。出循环后，找到最近的那个边界。 ###Code: public class Solution { /** * @param A an integer array sorted in ascending order * @par
2017-05-09 20:51:30
231
原创 Divide Two Integers
Description:Divide two integers without using multiplication, division and mod operator.If it is overflow, return MAX_INT.问题描述实现整数除法思路：这是一道考察基本功的好题目，包括int型数值范围，处理数值计算的思路，以及细心。代码明天给出
2017-05-08 19:56:58
145
原创 Squirrel Simulation
Description:There’s a tree, a squirrel, and several nuts. Positions are represented by the cells in a 2D grid. Your goal is to find the minimal distance for the squirrel to collect all the nuts and put
2017-05-07 15:42:03
427
原创 Subtree of Another Tree
问题描述判断一颗二叉树t是否是一颗二叉树s的 子树.分析：这种题目属于对二叉树的结构进行判断和操作的题目。注意题目说明的是判断子树问题，而不是子结构问题，也不是判断 同一颗二叉树问题. 子树—–>子结构 同一颗二叉树—–>子树——>子结构解法一：Code:public class Solution { public boolean isSubtree(TreeNode s, TreeNo
2017-05-07 15:03:53
262
原创 BFS系列（二）
起源BFS本来就是因图搜索而生，所以系列二在一的基础上上图这一复杂的数据结构，并且顺带讲下树(树也是特殊的图)。图的表示图可以用链接表和链接矩阵表示，前者适合稠密图，后者适合稀疏图。现在以算法面试题中经常用于表示的图结构为例说明。 * Definition for Undirected graph. * class UndirectedGraphNode { * int label;
2017-04-21 20:02:14
310
原创 BFS系列（一）
起源最开始接触BFS算法是从图算法开始的，但是图本身不是一个适合初学者的数据结构，所以这个系列的文章为BFS的学习者引路。例子 Input: A graph Graph and a starting vertex root of Graph Output: Goal state. The parent links trace the shortest path back to r
2017-04-20 16:52:35
506
原创 取模操作(补充说明)
起源在算法中，有时候要用到取模操作，为的是避免数据过大溢出，而有时候只需要验证算法的有效性，并关心实际的值，下面给出取模操作的性质以及一个简单的应用例子。模运算性质 ( a + b ) % c = ( ( a % c ) + ( b % c ) ) % c ( a * b ) % c = ( ( a % c ) * ( b % c ) ) % c ( a – b ) % c = (
2017-04-17 11:37:39
3057
原创 Java中的PriorityQueue的使用提示
起源在Java中使用PriorityQueue的主要目的是使用堆这个数据结构，为了解决第K大/小的问题。。深入理解基本上自己定义的问题，需要重写比较器(Comparator),但是在重写比较器之前，需要知道初始比较器是怎么个作用。 这里以PriorityQueue Integer为例说明，默认是一个大堆，每次poll()出来的都第K大的数的最小者，但是要设置第k大，还要用if语句过滤，在里面po
2017-04-15 18:52:26
852
原创 哈希表知识梳理
哈希表基础知识哈希表查找某个键的时间复杂度为O(key of size)..一般简化为O(1). 具体实现有开放寻址(用链表去找)， 闭合寻址(线性探测)。。。实现哈希函数这里采用取模方法
2017-04-14 20:01:10
240
原创 哈希表知识梳理
哈希表基础知识哈希表查找某个键的时间复杂度为O(key of size)..一般简化为O(1). 具体实现有开放寻址(用链表去找)， 闭合寻址(线性探测)。。。实现哈希函数这里采用取模方法
2017-04-13 14:06:30
218
原创 计数排序
起源：今天用计数排序解决了几道问题，感觉这个算法很有用，于是仔细研究了下，并且在《算法导论》一书中读到了相关的内容。计数排序的优势计数排序的时间复杂度为O(n+ k)..其中要设定一个辅助count数组。统计原数组中，每个元素出现的次数。 直观的感觉是记录<=x元素的个数，那么把x元素放到后面就可以了，那么就将所有的元素都排好序了，但是这种思想还需要一个临时数组存储排好序的数组。 通俗地理解，
2017-04-12 18:23:01
462
原创 Three Sum
Description:给出一个有n个整数的数组S，在S中找到三个整数a, b, c，找到所有使得a + b + c = 0的三元组。 在三元组(a, b, c)，要求a <= b <= c。 结果不能包含重复的三元组。解法一：思路：这是一道综合题，考察函数设计，去重，双指针的知识，是非常值得一练的Two Sum变种题。Code:public class Solution { /**
2017-04-11 14:35:16
261
原创 Two Sum - Unique pairs
Description:Given an array of integers, find how many unique pairs in the array such that their sum is equal to a specific target number. Please return the number of pairs.Ex:Given nums = [1,1,2,45,46,
2017-04-11 09:35:50
458
原创 链表的基本处理技巧
算法题中链表的操作主要是对链表结构的操作，实现难度不大，但是由于操作比较细腻，所以比较考察基本功。虽然算法成面不多，但是还是有一些基本处理技巧的。注意事项： 时刻注意链表是否为空(和数组越界一样严重) 结构的操作，注意分析有没有影响前后结点，该怎样处理，这正是基本功所在。技巧一： 设置dummy Node… dummy Node 在几乎90%的链表题中会用到，当链表的 head 有可能变化（
2017-04-08 17:20:42
762
原创 二叉树的路径和
问题描述给定一个二叉树，找出所有路径中各节点相加总和等于给定 目标值 的路径。一个有效的路径，指的是从根节点到叶节点的路径。Ex:给定一个二叉树，和 目标值 = 5:1 / \ 2 4 / \ 2 3 返回：[ [1, 2, 2], [1, 4] ]解法一：思路：这个题目是二叉树的遍历问题，由于是从根节点出发的路径，所以用先序遍历。。并且维护从当前
2017-03-13 21:39:15
1311
原创 Smallest Rectangle Enclosing Black Pixels
Description:An image is represented by a binary matrix with 0 as a white pixel and 1 as a black pixel. The black pixels are connected, i.e., there is only one black region. Pixels are connected horizon
2017-03-12 18:56:24
228
原创 快速排序和归并排序
比较两种算法都是分治(Divide and Conquer)算法。。 但是快速排序是先整体(<= pivot pivot >= pivot)后局部….. 原地操作。。。具有稳定性。。平均O(nlogn) 而归并排序是先局部(小数组排好序)后整体(排好序的小数组Merge) 空间复杂为O(n)…..稳定。。。都是O(nlogn)Code:快速排序：public class QuickSort
2017-03-09 21:11:53
146
原创 Search a 2D Matrix
Description:Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:Integers in each row are sorted from left to right. The first integer of
2017-03-08 21:30:45
136
原创 Search a 2D Matrix II
Description:Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:Integers in each row are sorted in ascending from left to right. Integer
2017-03-08 21:24:37
148
原创 Repeated Substring Pattern
Description:Given a non-empty string check if it can be constructed by taking a substring of it and appending multiple copies of the substring together. You may assume the given string consists of lowe
2017-03-02 21:02:36
145
原创 Number of Segments in a String
Description:Count the number of segments in a string, where a segment is defined to be a contiguous sequence of non-space characters.Please note that the string does not contain any non-printable chara
2017-03-02 20:49:14
184
打字母小游戏
2015-02-06
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人