"学理论.知团情"知识竞赛决赛题_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
"学理论.知团情"知识竞赛决赛题
上传于||文档简介
&&&​a​m​p​;​Q​U​O​T​;​学​理​论​.​知​团​情​&​a​m​p​;​Q​U​O​T​;​知​识​竞​赛​决​赛​题
阅读已结束，如果下载本文需要使用5下载券
想免费下载本文？
定制HR最喜欢的简历
你可能喜欢ACM等算法比赛中JAVA 常用&STL&总结:TreeMap,Queue,PriorityQueu
第一个：显然是I/O的class啦~！ /*IO相关*/ class InputReader { public InputReader() { // TODO Auto-generated constructor stub tokenizer = new StringTokenizer(""); reader = new BufferedReader(new InputStreamReader(System.in)); } public String nextTokenizer() throws IOException { while (!tokenizer.hasMoreTokens()) { tokenizer = new StringTokenizer(reader.readLine()); } return tokenizer.nextToken(); } public int nextInt() throws IOException { return Integer.valueOf(nextTokenizer()); } StringT BufferedR }
Map使用：比赛常用HashMap和TreeMap
先介绍TreeMap: 二叉树Map嘛，自然就是log级各种运算的时间。所以对自定义结构体需要定义比较函数。
比如常用的比较器这样写。 /*常用的包含x,y节点的node的class*/ class nodexy { int x,y; nodexy(){} nodexy(int xx, int yy) { x = y = } } /*使用这样的比较函数*/ static Comparator cmp = new Comparator() { public int compare(nodexy o1, nodexy o2) { // TODO Auto-generated method stub if (o1.x==o2.x) return o1.y-o2.y; return o1.x-o2.x; } }; 下面是一个简单的TreeMap的样例：
public static void main(String args[]) throws IOException { Mapq = new TreeMap(); //int,int类型的TreeMap,没有包含比较器！ q.put(1, 1); q.put(2, 2); q.put(3, 3); q.put(3, 4); //重复的key的value只保留最后一个~ key才是关键字 q.put(-1,0); q.put(-11,4); q.put(12,2); @SuppressWarnings("rawtypes") //消除下面的警告信息 Iterator it = q.entrySet().iterator(); //和C++一样用迭代器遍历 System.out.print("size = " + q.size()+"/n"); //总元素数量 while (it.hasNext()) { @SuppressWarnings("unchecked") //消除下面的警告信息 Map.Entry ent = (Entry) it.next(); int key = ent.getKey(); //key int value = ent.getValue(); //value System.out.println(key+" " + value); } }public static void main(String args[]) throws IOException { TreeMapq = new TreeMap(); //int,int类型的TreeMap,没有包含比较器！ q.put(1, 1); q.put(2, 2); q.put(3, 3); q.put(3, 4); //重复的key的value只保留最后一个~ key才是关键字 q.put(-1,0); q.put(-11,4); q.put(12,2); @SuppressWarnings({ "rawtypes", "unused" }) //消除下面的警告信息 Iterator it = q.entrySet().iterator(); //和C++一样用迭代器遍历 System.out.print("size = " + q.size()+"/n"); //总元素数量 /* * 不需要输出一次啦,直接这样 while (it.hasNext()) { @SuppressWarnings("unchecked") //消除下面的警告信息 Map.Entry ent = (Entry) it.next(); int key = ent.getKey(); //key int value = ent.getValue(); //value System.out.println(key+" " + value); } */ int ans = q.get(12); System.out.println(ans); //输出了2 /*对于不存在的键值的处理， 先判断是否是null*/ if (q.get(13) != null) { ans = q.get(13); System.out.println(ans); }else System.out.println("nothing");//输出了nothing System.out.println(q.higherKey(4));//比4大的是12，所以输出12 System.out.println(q.higherKey(12));//比12大的没有，输出null System.out.println(q.lastKey()); //输出最后一个key,也就是12，也是对的 q.remove(2); //删除键为2的 if (q.get(2) != null) { ans = q.get(2); System.out.println(ans); }else System.out.println("nothing");//因为2被删了，所以输出了nothing }
关于遍历，访问，删除迭代器指向内容的话
public static void main(String args[]) throws IOException { TreeMapq = new TreeMap(); //int,int类型的TreeMap,没有包含比较器！ q.put(1, 1); q.put(2, 2); q.put(3, 3); q.put(3, 4); //重复的key的value只保留最后一个~ key才是关键字 q.put(-1,0); q.put(-11,4); q.put(12,2); @SuppressWarnings({ "rawtypes", "unused" }) //消除下面的警告信息 Iterator it = q.entrySet().iterator(); //和C++一样用迭代器遍历 System.out.print("size = " + q.size()+"/n"); //总元素数量 while (it.hasNext()) { @SuppressWarnings("unchecked") //消除下面的警告信息 Map.Entry ent = (Entry) it.next(); int key = ent.getKey(); //key int value = ent.getValue(); //value if (key==-1 || key == 1 || key==12)it.remove(); //删除迭代器这个值，并且向后迭代！ System.out.println(key+" " + value); } System.out.println(); System.out.println(); /*再出输出一次，发现-1，1,12都已经被删啦！*/ it = q.entrySet().iterator(); while (it.hasNext()) { @SuppressWarnings("unchecked") //消除下面的警告信息 Map.Entry ent = (Entry) it.next(); int key = ent.getKey(); //key int value = ent.getValue(); //value System.out.println(key+" " + value); } }
/*下面例子依然是TreeMap,但是我们修改了key为一个class, 同时设置了比较函数~，比较经典*/ class Pack { int a, Pack(){} Pack(int x, int y) { a=x; b=y; } boolean same(Pack tmp) { if (tmp.a == a && tmp.b==b) } }; public class Doit { //一边访问，一边删除迭代器指向的内容 static Comparator cmp = new Comparator() { @Override public int compare(Pack o1, Pack o2) { // TODO Auto-generated method stub if (o1.a==o2.a) return o1.b-o2.b; return o1.a-o2.a; } }; public static void main(String args[]) throws IOException { TreeMapq = new TreeMap(cmp); //int,int类型的TreeMap,没有包含比较器！ q.put(new Pack(1,1), 1); q.put(new Pack(2,2), 2); q.put(new Pack(2,3), 3); q.put(new Pack(1,-1), 4); //重复的key的value只保留最后一个~ key才是关键字 q.put(new Pack(5,2),0); q.put(new Pack(5,3),4); q.put(new Pack(4,2),2); q.put(new Pack(4,2),2); @SuppressWarnings("rawtypes") Iterator it = q.entrySet().iterator(); //和C++一样用迭代器遍历 System.out.print("size = " + q.size()+"/n"); //总元素数量，输出为7个 while (it.hasNext()) { @SuppressWarnings("unchecked") //消除下面的警告信息 Map.Entry ent = (Entry) it.next(); Pack key = ent.getKey(); int key1 = ent.getKey().a; //key int key2 = ent.getKey().b; int value = ent.getValue(); //value if (key.same(new Pack(5,3)) || key.same(new Pack(2,2)))it.remove(); //删除迭代器这个值，并且向后迭代！ System.out.println(key1+" "+key2+" " + value); } System.out.println(); System.out.println(); /*再出输出一次，发现-1，1,12都已经被删啦！*/ it = q.entrySet().iterator(); while (it.hasNext()) { @SuppressWarnings("unchecked") //消除下面的警告信息 Map.Entry ent = (Entry) it.next(); Pack key = ent.getKey(); int key1 = ent.getKey().a; //key int key2 = ent.getKey().b; int value = ent.getValue(); //value System.out.println(key1+" "+key2+" " + value); } } }
===============================================大分割线=========================
实现c++的vector功能的arraylist.
用一个class的例子
class Pack { int a, Pack(){} Pack(int x, int y) { a=x; b=y; } boolean same(Pack tmp) { if (tmp.a == a && tmp.b==b) } }; public class Doit { //一边访问，一边删除迭代器指向的内容 static Comparator cmp = new Comparator() { @Override public int compare(Pack o1, Pack o2) { // TODO Auto-generated method stub if (o1.a==o2.a) return o1.b-o2.b; return o1.a-o2.a; } }; public static void main(String args[]) throws IOException { ArrayListq = new ArrayList(); q.add(new Pack(5,5));//塞入队尾 q.add(new Pack(4,4)); q.add(new Pack(7,7)); System.out.println(q.get(0).a + " " + q.get(0).b); System.out.println(q.get(1).a + " " + q.get(1).b); System.out.println(q.get(2).a + " " + q.get(2).b); //Pack sb[] = q.toArray(); Pack sb[]; sb = q.toArray(new Pack[q.size()]); //转换成数组 for (int i = 0; i != q.size(); ++ i) { System.out.println(sb[i].a); } } }
关于数组排序： class Pack { int a, Pack(){} Pack(int x, int y) { a=x; b=y; } boolean same(Pack tmp) { if (tmp.a == a && tmp.b==b) } }; public class Doit { //一边访问，一边删除迭代器指向的内容 static Comparator cmp = new Comparator() { @Override public int compare(Pack o1, Pack o2) { // TODO Auto-generated method stub if (o1.a==o2.a) return o1.b-o2.b; return o1.a-o2.a; } }; public static void main(String args[]) throws IOException { ArrayListq = new ArrayList(); q.add(new Pack(5,5));//塞入队尾 q.add(new Pack(4,4)); q.add(new Pack(7,7)); q.add(new Pack(4,3)); q.add(new Pack(4,2)); q.add(new Pack(4,10)); q.add(new Pack(4,4)); /*访问arraylist内元素方法用get*/ System.out.println(q.get(0).a + " " + q.get(0).b); System.out.println(q.get(1).a + " " + q.get(1).b); System.out.println(q.get(2).a + " " + q.get(2).b); //Pack sb[] = q.toArray(); /*arraylist转化为数组*/ Pack sb[]; sb = q.toArray(new Pack[q.size()]); //转换成数组 /* for (int i = 0; i != q.size(); ++ i) { System.out.println(sb[i].a); } */ /*数组排序的方法*/ Arrays.sort(sb,0, q.size(),cmp); //排序，[L,R)区间进行排序。 例子是[0,q.size()) 之间的数字进行排序 for (int i = 0; i != q.size(); ++ i) //输出了数组中的元素，从小到大 { System.out.println(sb[i].a + " " + sb[i].b); } } }
容器的排序： class Pack { int a, Pack(){} Pack(int x, int y) { a=x; b=y; } boolean same(Pack tmp) { if (tmp.a == a && tmp.b==b) } }; public class Doit { //一边访问，一边删除迭代器指向的内容 static Comparator cmp = new Comparator() { @Override public int compare(Pack o1, Pack o2) { // TODO Auto-generated method stub if (o1.a==o2.a) return o1.b-o2.b; return o1.a-o2.a; } }; public static void main(String args[]) throws IOException { ArrayListq = new ArrayList(); q.add(new Pack(5,5));//塞入队尾 q.add(new Pack(4,4)); q.add(new Pack(7,7)); q.add(new Pack(4,3)); q.add(new Pack(4,2)); q.add(new Pack(4,10)); q.add(new Pack(4,4)); q.add(new Pack(2,4)); /*访问arraylist内元素方法用get*/ System.out.println(q.get(0).a + " " + q.get(0).b); System.out.println(q.get(1).a + " " + q.get(1).b); System.out.println(q.get(2).a + " " + q.get(2).b); //Pack sb[] = q.toArray(); System.out.println(); System.out.println(); System.out.println(); Collections.sort(q,cmp); Iterator it = q.iterator(); while (it.hasNext()) { Pack tmp = (Pack) it.next(); System.out.println(tmp.a+" "+tmp.b); } } }
================================ 另一种做比较器的方法 用接口实现： class Pack { int a, Pack(){} Pack(int x, int y) { a=x; b=y; } boolean same(Pack tmp) { if (tmp.a == a && tmp.b==b) } }; class MyCmp implements Comparator { //@Override public int compare(Pack o1, Pack o2) { // TODO Auto-generated method stub if (o1.a==o2.a) return o1.b-o2.b; return o1.a - o2.a; } } public class Doit { //一边访问，一边删除迭代器指向的内容 static Comparator cmp = new MyCmp(); public static void main(String args[]) throws IOException { ArrayListq = new ArrayList(); q.add(new Pack(5,5));//塞入队尾 q.add(new Pack(4,4)); q.add(new Pack(7,7)); q.add(new Pack(4,3)); q.add(new Pack(4,2)); q.add(new Pack(4,10)); q.add(new Pack(4,4)); q.add(new Pack(2,4)); /*访问arraylist内元素方法用get*/ System.out.println(q.get(0).a + " " + q.get(0).b); System.out.println(q.get(1).a + " " + q.get(1).b); System.out.println(q.get(2).a + " " + q.get(2).b); //Pack sb[] = q.toArray(); System.out.println(); System.out.println(); System.out.println(); Collections.sort(q,cmp); Iterator it = q.iterator(); while (it.hasNext()) { Pack tmp = (Pack) it.next(); System.out.println(tmp.a+" "+tmp.b); } } }
===========分界线=========================================================== POJ 2386 挑战P32 BFS/DFS搜索裸题 queue使用方法 没有什么好说的 ====================分界线==============================
POJ 3253 挑战P47 贪心，JAVA heap注意事项, PrintWriter注意事项 =============分割线==================POJ 1182 挑战P89 并查集 食物链 关于new 对象数组
最新教程周点击榜
微信扫一扫普通的hash算法有个很大的问题:当hash的"模数"发生变化时,整个hash数据结构就需要重新hash,重新hash之后的数据分布一定会和hash之前的不同;在很多场景下,"模数"的变化时必然的,但是这种"数据分布"的巨大变化却会带来一些麻烦.所以,就有了"一致性hash",当然学术界对"一致性hash"的阐述,还远远不止这些.
在编程应用方面,最直观的例子就是"分布式缓存",一个cache集群中,有N台物理server,为了提升单台server的支撑能力,可能会考虑将数据通过hash的方式相对均匀的分布在每个server上.
判定方式: location = hashcode(key) % N;事实上,由于需要,N可能会被增加或者削减,不管程序上是否能够妥善的支持N的变更,单从"数据迁移"的面积而言,也是非常大的.
一致性Hash很巧妙的简化了这个问题,同时再使用"虚拟节点"的方式来细分数据的分布.
图示中表名,有2个物理server节点,每个物理server节点有多个Snode虚拟节点,server1和server2的虚拟节点互相"穿插"且依次排列,每个snode都有一个code,它表示接受数据的hashcode起始值(或终止值),比如上述图示中第一个snode.code为500,即当一个数据的hashcode值在[0,500]时则会被存储在它上.
引入虚拟节点之后,事情就会好很多;假如KEY1分布在Snode3上,snode3事实为物理server1,当server1故障后,snode2也将被移除,那么KEY1将会被分布在"临近的"虚拟节点上--snode2(或者snode4,由实现而定);无论是存取,下一次对KEY1的操作将会有snode2(或snode4)来服务.
1) 一个物理server在逻辑上分成N个虚拟节点(本例中为256个)
2) 多个物理server的虚拟节点需要散列分布,即互相"穿插".
3) 所有的虚拟节点,在逻辑上形成一个链表
4) 每个虚拟节点,负责一定区间的hashcode值.
import java.net.InetSocketA
import java.net.S
import java.net.SocketA
import java.nio.charset.C
import java.security.MessageD
import java.security.NoSuchAlgorithmE
import java.util.M
import java.util.NavigableM
import java.util.TreeM
public class ServersPool {
private static final int VIRTUAL_NODES_NUMBER = 256;
private static final String TAG = ".-vtag-.";
private NavigableMap&Long, SNode& innerPool = new TreeMap&Long, SNode&();
private Hashing hashing = new Hashing();
public synchronized void addServer(String address,int weight) throws Exception {
SNode prev = null;
SNode header = null;
String[] tmp = address.split(":");
InnerServer server = new InnerServer(tmp[0], Integer.parseInt(tmp[1]));
server.init();
int max = 1;
if(weight & 0){
max = VIRTUAL_NODES_NUMBER *
for (int i = 0; i & i++) {
long code = hashing.hash(address + TAG + i);
SNode current = new SNode(server, code);
if (header == null) {
current.setPrev(prev);
innerPool.put(code, current);
public synchronized void removeServer(String address) {
long code = hashing.hash(address + TAG + (VIRTUAL_NODES_NUMBER - 1));
SNode current = innerPool.get(code);
if(current == null){
if(!current.getAddress().equalsIgnoreCase(address)){
current.getServer().close();;
while (current != null) {
current = innerPool.remove(current.getCode()).getPrev();
public InnerServer getServer(String key) {
long code = hashing.hash(key);
SNode snode = innerPool.lowerEntry(code).getValue();
if (snode == null) {
snode = innerPool.firstEntry().getValue();
return snode.getServer();
class SNode {
SNode(InnerServer server, Long code) {
this.server =
this.code =
SNode getPrev() {
void setPrev(SNode prev) {
this.prev =
Long getCode() {
return this.
InnerServer getServer() {
String getAddress(){
return server.ip + ":" + server.
class Hashing {
private ThreadLocal&MessageDigest& md5Holder = new ThreadLocal&MessageDigest&();
private Charset DEFAULT_CHARSET = Charset.forName("utf-8");
public long hash(String key) {
return hash(key.getBytes(DEFAULT_CHARSET));
public long hash(byte[] key) {
if (md5Holder.get() == null) {
md5Holder.set(MessageDigest.getInstance("MD5"));
} catch (NoSuchAlgorithmException e) {
throw new IllegalStateException("no md5 algorythm found");
MessageDigest md5 = md5Holder.get();
md5.reset();
md5.update(key);
byte[] bKey = md5.digest();
long res = ((long) (bKey[3] & 0xFF) && 24)
| ((long) (bKey[2] & 0xFF) && 16)
| ((long) (bKey[1] & 0xFF) && 8) | (long) (bKey[0] & 0xFF);
class InnerServer {
InnerServer(String ip, int port) {
this.port =
synchronized void init() throws Exception {
SocketAddress socketAddress = new InetSocketAddress(ip, port);
socket = new Socket();
socket.connect(socketAddress, 30000);
public boolean write(byte[] sources) {
return true;
public byte[] read() {
return new byte[]{};
public void close(){
if(socket == null || socket.isClosed()){
socket.close();
} catch (Exception e){
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：3966次
排名：千里之外
原创：61篇
(1)(1)(1)(60)