现在的位置: 首页 > 综合 > 正文

[读透代码]第一篇(TreeSet,ArrayList)

2018年02月15日 ⁄ 综合 ⁄ 共 7336字 ⁄ 字号 评论关闭

(中国大陆著名杀毒软件公司J2007年面试题)

题目:一个字符串中可能包含a~z中的多个字符,如有重复,如String data="dwsiqwksoqsmwqiswqwswqswqs",求出现次数最多的那个字幕及次数,如有多个重复则都求出。

分析:笔者拿到看到该题后,有多种思路涌现出来,比如我们可以创建一个长度为26的数组,用来记录每个字符出现的次数,fine,类似这样的思路我想大家应该都可以想到(笔者以前做过一个,是通过ArraylIst实现的)。下面的一个思路是从《Java程序员面试宝典》(第二版)(欧立奇,刘洋,段韬)这本书上看到的,很值得学习。下面是该书的解题。

解析:主要思路如下。

(1)引入TreeSet:通过集合快速找到所有出现的字符串。

(2)引入ArrayList :为了快速排序,再通过StringBuffer生成排序后的字符串。

(3)通过String API中的基本方法indexOflastIndexOf来计算TreeSet中每个字符串的最大值。

(4)如果出现相同的,则把相同的都记录在一个列表中。

(5)计算第一个出现次数最多的字符(为了计算多个字符串相同情况)。

(6)计算最大字符串列表中哪些才是真正出现次数最多的。


import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.TreeSet;

public class test_2 {
	public void doString(String input) {
		char[] chars = input.toCharArray();// 转换成字符数组
		ArrayList lists = new ArrayList();
		TreeSet set = new TreeSet();
		for (int i = 0; i < chars.length; i++) {
			lists.add(String.valueOf(chars[i]));
			set.add(String.valueOf(chars[i]));// 将字符数组依次加入到lists和set中
		}
		Collections.sort(lists);// 将lists排序
		System.out.println(lists);

		StringBuffer sb = new StringBuffer();
		for (int i = 0; i < lists.size(); i++)
			sb.append(lists.get(i));
		input = sb.toString();// 将排序后的字符重新赋值给input
		System.out.println(input);
		int max = 0;
		String maxString = "";
		ArrayList maxlist = new ArrayList();

		Iterator its = set.iterator();// 迭代器,set集合中每个元素依次计算其出现次数
		while (its.hasNext()) {
			String os = (String) its.next();
			int begin = input.indexOf(os);
			int end = input.lastIndexOf(os);
			int value = end - begin + 1;
			if (value > max) {
				max = value;
				maxString = os;// maxString 为最大的位置,比如q,w都最多,则maxString = q
				maxlist.add(os);
			} else if (value == max) {
				maxlist.add(os);// 很明显位于最末的是最大的
			}
		}

		int index = 0;
		for (int i = 0; i < maxlist.size(); i++) {
			if (maxlist.get(i).equals(maxString)) {
				index = i;//得到最大的那个下标,maxlist中,index后的都是出现最多的
				break;
			}
		}
		System.out.println("max data");
		for (int i = index; i < maxlist.size(); i++) {
			System.out.println(maxlist.get(i) + " ");
		}
		System.out.println();
		System.out.println("max" + max);
	}

	public static void main(String args[]) {
		String input = "dqwsqwsqzqzqwswcxewqeqww";
		new test_2().doString(input);
	}

}


笔者并不觉得该实现方案有多棒,反而觉得有点啰嗦,完全可以只使用数组来统计这样的问题。但是这个代码片段中涉及到了很多基本知识,拿来学习是个不错的选择。TreeSet可以求出集合(在这里就是所有出现的字符),再利用Collections中的排序方法来获得一个排过序的集合,再根据其下标求出出现次数。下面笔者总结下以上出现的一些类。

一、TreeSet

    TreeSet是 基于TreeMap的NavigableSet实现。TreeSet中的元素按照一定的原则进行排序(由constructor比较器决定)。很明显TreeSet是一个有序集合,他具有互异性。

    阅读API文档中关于TreeSet的介绍,知道它不是同步的。如果多个线程同时访问一个 TreeSet,而其中至少一个线程修改了该 set,那么它必须
外部同步。这一般是通过对自然封装该 set 的对象执行同步操作来完成的。如果不存在这样的对象,则应该使用Collections.synchronizedSortedSet 
方法来“包装”该 set。此操作最好在创建时行,以防止对 set 的意外非同步访问:

  				 SortedSet s = Collections.synchronizedSortedSet(new TreeSet(...));

    此类的 iterator 方法返回的迭代器是快速失败(fail-fast) 的:在创建迭代器之后,如果从结构上对 set 进行修改,除非通过迭代器自身的remove 方法,否则在其他任何时间以任何方式进行修改都将导致迭代器抛出ConcurrentModificationExption。因此,对于并发的修改,迭代器很快就完全失败,而不会冒着在将来不确定的时间发生不确定行为的风险。

    注意,迭代器的快速失败行为无法得到保证,一般来说,存在不同步的并发修改时,不可能作出任何肯定的保证。快速失败迭代器尽最大努力抛出ConcurrentModificationException。因此,编写依赖于此异常的程序的做法是错误的,正确做法是:迭代器的快速失败行为应该仅用于检测 bug。 

    下面我们通过几个例子来学习写TreeSet。

例1:针对TreeSet的几个构造方法,我们来学习如何使用TreeSet。

import java.util.TreeSet;

public class test_3 {
	public static void main(String args[]) {
		TreeSet<Integer> ts = new TreeSet<Integer>();
		ts.add(10);
		ts.add(21231);
		ts.add(29);
		ts.add(9021);
		ts.add(1);
		ts.add(10);
		System.out.println(ts);
	}
}

上述代码的运行结果是[1, 10, 29, 9021, 21231]。我们看出,TreeSet是默认的按照升序的方式,现在我们采用另外一种构造方法,如下:

import java.util.Comparator;
import java.util.TreeSet;

public class test_3 {
	public static void main(String args[]) {
		TreeSet<Integer> ts = new TreeSet<Integer>(new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {//与下述代码等价
				if(o1>o2)<span style="white-space:pre">			</span>    //return (o1-o2);
					return 1;                   //返回值可以不属于{-1,0,1}
				else if(o1==o2)                     //
					return 0;                   //
				else                                //
					return -1;
			}
		});
		ts.add(10);
		ts.add(21231);
		ts.add(29);
		ts.add(9021);
		ts.add(1);
		ts.add(10);
		System.out.println(ts);
	}
}

Fine,通过上述的构造方法,我们得到了与之前一样的结果。如果我们把的构造改写成下面的形式。再来观察下结果。

TreeSet<Integer> ts = new TreeSet<Integer>(new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				if(o1>o2)
					return 1;
				else
					return -1;
			}
		});

得到结果是这样的:[1, 10, 10, 29, 9021, 21231]。我们发现,这其中有2个10!这就不再是一个集合了,所以在使用TreeSet的时候,我们应该注意compare的编写。不然将会出现很严重的错误!

二、ArrayList

ArrayList就是传说中的动态数组,就是Array的复杂版本,它提供了如下一些好处:(1)动态的增加和减少元素;(2)实现了ICollection和IList接口;(3)灵活的设置数组的大小。

下面代码是一个ArrayList的一些简单的用法。

		ArrayList List = new ArrayList();
		for (int i = 0; i < 10; i++)
			List.add(i);	// 给数组增加10个Int元素
		List.remove(5);// 将第6个元素移除
		for (int i = 0; i < 3; i++)
			List.add(i + 20);	// 再增加3个元素
	

笔者认为,我们可以把ArrayList当成数组来使用,不同的是,数组使用[ ]来引用,而ArrayList通过get(index)方法来获得值。下面是笔者在网络上找到的。感觉写的不错。拿来与大家分享。

(笔者很认真的研读http://www.importnew.com/9928.html,对于其中部分的并不是很认同,部分地方有所修改,下面参考了这篇文章)

1、ArrayList的大小是如何自动增加的?你能分享一下你的代码吗?

这是最有技巧性的的一个问题,大多数人都无法回答。事实上,当有人试图在ArrayList中增加一个对象的时候,Java会去检查ArrayList,以确保已存在的数组中有足够的容量来存储这个新的对象。如果没有足够容量的话,那么就会新建一个长度更长的数组,旧的数组就会使用Arrays.copyOf方法被复制到新的数组中去,现有的数组引用指向了新的数组。看如下的代码段(摘自GrepCode.com中的Java
ArrayList Code
):

//ArrayList Add方法:
public boolean add(E e){
    ensureCapacity(size+1); //Increment modCount!!
    elementData[size++] = e;
    return true;
}
  
//ensureCapacity方法:处理ArrayList的大小
public void ensureCapacity(int minCapacity) {
    modCount++;
    int oldCapacity = elementData.length;
    if (minCapacity > oldCapacity) {
    Object oldData[] = elementData;
    int newCapacity = (oldCapacity * 3)/2 + 1;
    if (newCapacity < minCapacity)
        newCapacity = minCapacity;
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
    }
}

发现,是按照原来的3/2进行扩容,扩容之后再和minCapaticity容量对比,若发现minCapaticity大于newCapaticity,则按照minCapaticity的大小进行扩容。

请注意这样一个情况:新建了一个数组;旧数组的对象被复制到了新的数组中,并且现有的数组指向新的数组。

2、什么情况下你会使用ArrayList?什么时候你会选择LinkedList?

这又是一个大多数面试者都会困惑的问题。多数情况下,当你遇到访问元素比插入或者是删除元素更加频繁的时候,你应该使用ArrayList。另外一方面,当你在某个特别的索引中,插入或者是删除元素更加频繁,或者你压根就不需要访问元素的时候,你会选择LinkedList。这里的主要原因是,在ArrayList中访问元素的最糟糕的时间复杂度是”1″,而在LinkedList中可能就是”n”了。在ArrayList中增加或者删除某个元素,通常会调用System.arraycopy方法,这是一种极为消耗资源的操作,因此,在频繁的插入或者是删除元素的情况下,LinkedList的性能会更加好一点。

3、当传递ArrayList到某个方法中,或者某个方法返回ArrayList,什么时候要考虑安全隐患?如何修复安全违规这个问题呢?

当ArrayList被当做参数传递到某个方法中后,如果ArrayList在没有被复制的情况下直接被分配给了成员变量,那么就可能发生这种情况,即当原始的数组被调用的方法改变的时候,传递到这个方法中的数组也会改变。下面的这段代码展示的就是安全违规以及如何修复这个问题。

ArrayList被直接赋给成员变量——安全隐患:

(这点和C语言中的指针很相似,copy的仅仅是“门牌号”,门牌号对应的房间的内容遭到了修改,那么copy的对象访问的时候,找到的当然是被修改过的啦~,下面给大家示例一个例子)

import java.util.ArrayList;

public class test_4 {
	public static void main(String args[]) {
		ArrayList<Integer> List = new ArrayList<Integer>();
		for (int i = 0; i < 10; i++)
			List.add(i); // 给数组增加10个Integer元素
		ArrayList<Integer> newList = List;
		System.out.println(List);
		System.out.println(newList);// 结果证实当然是一样的
		List.set(2, 8);// 对List做出修改
		System.out.println(newList);// 啊哈,我们发现copy的对象也被修改了~!
	}
}

            

修复这个安全隐患:

方式一:利用copy()方法,将上句的

ArrayList<Integer> newList = List;
//修改成如下形式:
ArrayList<Integer> newList = (ArrayList<Integer>) List.clone();

方式二:利用其构造方法。修改成如下形式,
ArrayList<Integer> newList = new ArrayList<Integer>(List);

方式三:使用Collections的copy方法。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class test_4 {
	public static void main(String args[]) {
		ArrayList<Integer> List = new ArrayList<Integer>();
		for (int i = 0; i < 10; i++)
			List.add(i); 
		ArrayList<Integer> newList = new ArrayList<Integer>(Arrays.asList(new Integer[List.size()]));
		Collections.copy(newList, List);
		System.out.println(List);
		System.out.println(newList);
		List.set(2, 8);
		System.out.println(newList);
	}
}


可参看笔者在编写此代码犯错的解决方案:http://blog.csdn.net/u010536377/article/details/42011733

4、如何复制某个ArrayList到另一个ArrayList中去?写出你的代码?

下面就是把某个ArrayList复制到另一个ArrayList中去的几种技术:

  1. 使用clone()方法,比如ArrayList newArray = oldArray.clone();
  2. 使用ArrayList构造方法,比如:ArrayList myObject = new ArrayList(myTempObject);
  3. 使用Collections的copy方法。

注意1和2是浅拷贝(shallow copy)。

5、在索引中ArrayList的增加或者删除某个对象的运行过程?效率很低吗?解释一下为什么?

在ArrayList中增加或者是删除元素,要调用System.arraycopy这种效率很低的操作,如果遇到了需要频繁插入或者是删除的时候,你可以选择其他的Java集合,比如LinkedList。看一下下面的代码:

在ArrayList的某个索引i处添加元素:

删除ArrayList的某个索引i处的元素:

抱歉!评论已关闭.