ITeye博客

2015 年文章归档

共 45 篇文章

Java垃圾回收机制

java中的垃圾回收机制(Garbage Collection )可以自动清除在堆中不用的对象,为java程序员提供了方便,在c/c++中,我们就需要手动去释放堆中的内存。 在java中对象都是通过引用来使用的,如果没有引用指向这个对象,那么这个对象就不可到达,我们就没法使用和处理这个对象,GC机制就是释放这些不可达对象所占用的内存。 为了提高效率,JVM优化了GC机制,在不同的情况下采用不同的回收方式。不管采用什么方式,我们首先要搞清楚怎样才能访问到对象,正如在 堆栈总结 中说的,对象都是通过引用访问的,而引用都保存在栈中,因此我们可以通过栈来找到那些可以访问的对象。 JVM有两种基本的回…

2015-12-14 17:13 · 内存管理

Remove Duplicate from List(链表去重)

之前在 一篇文章里 总结了一部分链表的题目,这里主要例举一下链表去重的问题。链表去重有很多种情况,有些要求我们只保留单独出现的元素,有些要求我们使重复的元素只能出现一次。对于可能会删除头结点的题目,我们一般采用新建一个helper节点,使helper指向head,进行操作,最后返回helper.next就可以了。下面是leetcode中有关链表去重的一些题目 1,Remove Duplicates from Sorted List 给定一个链表,去除重复的元素,使每个元素最多出现一次。 例如:给定 1->1->2, 返回 1->2. 给定 1->1->2->3->3, 返回 1->2->3.…

2015-12-14 13:15 · Leetcode

Remove Duplicate from Array(数组去重)

给定一个数组,判断是否存在重复元素,或者让你找出重复的元素。遇到这类问题我们应该先想用哈希表,位运算,双指针是否可以解决,根据具体的情况选择合适的方法。下面是leetcode中有关数组去重或查重的几道题目。 1,Contains Duplicate 给定一个数组,判断里面是否存在重复元素,如果存在就返回true,如果不存在就返回false. 既然是判断是否存在重复元素,我们首先想到哈希表,遍历数组,存在重复元素直接return true;不重复的元素依次加入表中,直到结束。代码如下: public class Solution { public boolean containsDuplica…

2015-12-14 05:24 · Leetcode

Permutation总结

有关排列的问题我们可以与组合比较来考虑,解决这类问题我们都采用回溯法,在组合中不用考虑顺序,而在排列中就要考虑顺序,例如(1,2,3)和(2,1,3),在组合的概念中是相等的,但它们是不同的排列。下面列举leetcode中有关permutations的几道题目。 1,Permutation 给定一个数组numbers ,输出所有可能的排列。 例如:numbers = {1,2,3}; 输出:, , , , ,. 因为我们要考虑顺序,回溯的时候我们始终从第一个元素开始遍历,如果长度等于数组的长度我们就找到结果,保存这个结果,然后返回上一层,继续遍历。代码如下: public class Sol…

2015-12-13 18:05 · Leetcode

Combination Sum总结

关于组合的题目我们一般用回溯法来解决。我的理解回溯法就是按照要求一直找下去,如果找到一个结果就把这个结果记录下来,然后返回上一层,如果有其它路线可以走就继续尝试,如果没有,就继续返回上一层。回溯的实现一般用递归来完成。这里介绍一下关于组合的问题,以及它的一些延伸。 1,Combination 给定两个正整数n和k,返回所有长度为k的组合,组合中的元素为1...n。 例如:n = 4, k = 2 输出: , , , , , , ] 很明显我们要用链表来记录结果,通过链表的大小来判断是否继续找下去,如果链表长度已经为k,那么就记录这个结果,返回,然后把链表的长度减去1,这样可以继续找其他的结果…

2015-12-13 06:31 · Leetcode

2sum, 3sum, 4sum和3sum closest总结

2sum, 3sum, 4sum和3sum closest是四道类似的题目,后面三个都是2sum的延伸。 1,2sum 给定一个数组numbers和一个目标数值target,从数组中找到两个元素,使它们的和等于目标元素。返回这两个值的索引indices,并且index1 大于index2。(假设只有一个结果) 例如:输入: numbers={2, 7, 11, 15}, target=9 输出: index1=1, index2=2 (不是zero-based) 我们用hash来实现这道题,key中存放数组里面元素的值number*, value中存放对应的下标,hash(numbers*,…

2015-12-13 04:27 · Leetcode

堆栈变体以及栈和队列的相互实现

前面讲到了如何用数组以及链表实现一个基本的堆栈和队列,这篇文章介绍如何实现一个可以在O(1)时间复杂度下得到最小元素的堆栈,以及用堆栈实现一个队列,用队列实现一个堆栈。 1,实现一个可以得到最小元素的堆栈, 要求pop(),push(),getMin()的时间复杂度都为O(1). 如果我们按照普通的思路,类中有两个成员变量,value和minValue,当pop一个元素后,我们就需要更新minValue, 从而要遍历堆栈里剩余的元素,时间复杂度为O(n),假设堆栈中有n个元素,因此这个方法不符合题意。 我们想到用每个元素都记录当前的最小元素,当push一个新的元素进来,这个新的元素连同最小元…

2015-12-12 09:55 · 数据结构

链表总结

链表总结 链表也是计算机中一个重要的数据结构,有单向链表,双向链表等。和数组一样都是一种线性存储结构,但是它不能像数组那样通过下标查找数据,我们必须要知道链表的头结点,然后依次遍历来查找结果,在这一点上链表劣于数组;但是如果我们想删除一个数据,链表就比数组方便了很多,可以在O(1)的时间复杂度下完成,而数组删除元素需要移动其它元素,对于一个长度为n的数组删除一个节点i,时间复杂度为O(n)。 做链表题目时,如果没有一个清晰的思路很容易就乱了,链表的题目全都是围绕它的概念展开的,我们先通过实现一个单向链表来理解链表的特点。 public class LinkedList { LinkedLis…

2015-12-11 14:20 · 数据结构

MongoDB基本操作以及JDBC连接

MongoDB Mac上使用MongoDB的方法。 官网下载安装包,安装完毕后,如果是默认路径,就在根目录下 创建一个data文件夹 ,存放数据库中的数据。 开启MongoDB服务:在terminal中,切换到bin目录下执行./mongod就开启了MongoDB服务 连接数据库:新创建一个terminal窗口,在bin目录下执行./mongo,这是默认链接到test 退出数据库:用control + c 或者“>exit” 与数据库断开链接,这时服务器还是开启状态 关闭服务:首先切换到admin,然后执行db.shutdownServer(),这样就关闭了MongoDB服务 MongoDB…

2015-12-11 07:56 · 数据库

哈希表的实现

实现一个哈希表,首先我们要知道哈希表可以干什么,包含什么方法,实现哪些功能。 哈希表又叫散列表,是根据关键码值(Key, value)而直接进行访问的数据结构。oracle文档里面提到,用哈希表进行检索和存储,key首先要完成hashcode方法,以确定这个key属于哪个区间,也就是说具有相同hashcode的被放在同一块区间里,hashcode往往是取模得出的结果。 确定了位置,我们还要解决冲突问题,如果表中已经存在当前要存的key,我们应该先删除以前的那个key,先后把新的key加入到表中,这里我们要做两步,判断是否存在相同的key,如果存在就删除以前的key,注意的是这里说的key实际…

2015-12-10 02:27 · 数据结构

JDBC链接MySQL数据库

JDBC链接MySQL数据库 首先我们到官网(mysql.com)下载MySQL数据库,安装完毕后,我们还要去下载MySQL JDBC 驱动,然后我们就可以在一个java工程中使用JDBC链接数据库了。 具体过程: 1,加载驱动。将JDBC驱动的jar文件加入到工程的classpath中。我们通常在工程中创建一个lib文件夹,用来盛放需要的jar文件,然后添加JARs到classpath中(右键选择properties,然后选择java build path,选择libraries 添加相应的JARs)在老版本的MySQL还要使用Class.forName("com.mysql.jdbc.D…

2015-12-09 13:16 · 数据库

IT随笔之减少程序bug

写程序难免会出错,不管你有多细心,当我们运行程序的时候,总是会报错,有编译时的错误也有运行时的错误,尽管有很多工具可以帮我们debug,我认为我们不能依赖debug工具,我们要在写程序的时候就尽量的避免错误。在这里主要说一下编译错误,也就是因为粗心而写错。避免逻辑上的错误就得靠提高自身编程水平了。 在面试的时候,我们往往都是在白板上写代码,如果平时我们依赖编译器帮我们找错误,那我们在面试中就会很吃亏,如何尽量减少编译错误呢,下面的几点完全是我自己的体会。 写完一段程序,在运行之前,应该注意的问题: 1,先检查标点符号是否都正确,有没有遗漏标点 2,快速检查拼写,比如length写成lengt…

2015-12-08 11:20 · 随笔

图的深搜和广搜

DFS(深度优先遍历) 图的深度优先搜索和树的深度优先搜索思想很相似,都是从一个顶点v出发尽可能像纵深方向搜索,访问了顶点v,下一个访问与v相邻的顶点v1,然后以v1作为初始节点,依次访问后面的节点。对于深度优先搜索的实现,我们采用堆栈来实现。 递归实现DFS的伪代码: void dfs(vertex v) { if(v == null) return; v.visited = true; foreach(vertex v.adjancent){ if(v.adjancent.visted == false) dfs(v.adjancent); } } BFS(广度优先遍历) 广度优先遍历也…

2015-12-07 13:08 · 数据结构

解析Singleton开发模式

单例模式(Singleton pattern) 一个singleton 类是指这个类只能有一个实例,当系统只要求一个类的唯一实例时,我们就采用单例模式。要实现一个singleton类,我们首先要设置一个全局的点,以便其它类可以得到这个实例,其次很重要的一点是构造函数必须设定为私有,具体的实现通常有两种方式:饿汉式和懒汉式。从字面上去理解,懒汉式就是在不用的时候不去new这个实例,用到才去创建这个实例,它比较省空间,但是耗费时间;饿汗式是先提前new好实例,这样省时间但是耗费空间。 饿汉式: public class Singleton { //设置全局点,在类加载的时候就实例化 privat…

2015-12-06 09:56 · Design Pattern

Java多线程之Semaphore

Semaphore(信号量),是用来控制同时访问特定资源的线程数量,它通过计数来协调各个线程,以保证合理的使用公共资源。我的理解是:信号量控制着一个线程池中并发线程的数量。就好像我们去一家饭店吃饭,这家饭店最多可以同时供应50人,如果饭店中已经坐满50人,这时新来的客人就必须等待,直到有客人离开他们才可以进入,并且总的数量不可以超过50人。这里饭店就好比线程池,饭店里的服务人员和厨师就好比共享的资源,每个客人都相当于一个线程, semaphore就记录着里面的人数,要根据semaphore的数量来决定是否让新的客人进入。为了得到一个资源,每个线程都要先获取permit,以确保当前可以访问。 …

2015-12-05 02:34 · 多线程

java中的线程同步

在java中,每一个线程都是由Thread类对象创建和控制的。通常我们有两种方式来创建一个线程,一种是继承java.lang.Thread 类,第二种是创建类的时候实现Runnable接口。下面分别介绍两种方式。 1,继承Thread类 首先创建Thread子类的一个实例,然后重写run方法,然后子类的实例必须调用start()方法之后run方法才被执行. 代码如下: public class MultiThread extends Thread { public void run() { System.out.println(getName()+"线程开始运行"); for(int i =…

2015-12-04 03:57 · 多线程

MAC中安装5.7.9 Mysql的问题

去官网mysql.com下载相应地程序包,下载完成后,打开mysql.dmg文件,按照他的默认设置进行安装,值得我们注意的是,5.7以后安装的mysql不再使用旧版的默认密码:root,安装的过程中将出现一个弹窗提示,那里是一个临时密码,切记要保存这个密码,以便第一次连接数据库时使用。 打开终端,在终端中输入 sudo /usr/local/mysql/support-files/mysql.server start,这是服务器就开启了。还有一种方式是在系统设置里面,有mysql选项,可以手动开关mysql服务。 开启服务后,我们就开始连接数据库,在/bin目录下 输入./mysql -u …

2015-12-03 04:48 · 数据库

二叉树的深搜和广搜

二叉树是计算机中一个重要的数据结构,在这里主要谈一下二叉树的深度优先搜索(DFS)和广度优先搜索(BFS)。 所谓DFS,就是沿着树的深度一直往下,一直到达一个叶子节点,然后再返回遍历剩余的节点。根据树的性质,树结构不存在环,因此遍历的时候不需要标记。如果在遍历一个图的时候,因为图中有环的存在,因此需要标记访问过的节点,以防止程序进入死循环。言归正传,树的DFS有三种方式,分别为:前序遍历,中序遍历,和后序遍历。根据这个性质,我们很容易想到用堆栈完成DFS。遍历的时候我们将元素压栈,利用堆栈后进先出的性质来实现不同的遍历。 所谓前序遍历,就是每次都先访问根节点,然后依次为左子树,和右子树。根…

2015-12-02 12:40 · 数据结构

从堆和栈的角度看参数传递

在java中,参数的传递方式只有一种:值传递。但是这个“值”的的含义我们不能单从字面理解。确切的说它分为两种:一个是基本类型的值传递,一个是对象的值传递。 对于基本类型来讲,值传递很容易理解,就是把实参的的值传递给形参,例如 public static void add(int a) { a = a + 3; System.out.println(a); } public static void main(String[] args) { int a = 3; add(a); System.out.println(a); } 这段代码的输出为:6,3 当运行到main方法的时候,在栈中会给m…

2015-12-02 03:01 · 内存管理

几种常见的排序算法

常见的排序算法有冒泡排序,简单选择排序,直接插入排序,快速排序,归并排序,堆排序,桶排序等,这篇文章中我们主要分析前五种排序,包括它们的实现,稳定性分析,时间复杂度分析以及空间复杂度分析。 以下都假设给定一个长度为n的数组 1,冒泡排序 在冒泡排序中, 我们从数组的开始进行比较,如果第一个元素大于第二个元素,我们就将两个元素互换,接下来我们比较第二个元素和第三个元素,如果第二个元素大于第三个元素我们就把它们交换,以此类推,每次循环都得到一个最大的数。代码如下: public void bubblesort(int[] array){ for(int i=0;i<array.length-1;…

2015-12-01 12:39 · 算法