johnwong_个人页_阿里云开发者社区

发表了文章 2016-04-12

Android NDK学习记录

游戏项目开始转向Cocos2d-x来开发。需要用什么NDK、cygwin。硬着头皮开始学习。下载NDK，最新版r7。解压到D:\Develop，地址如下：http://dl.google.com/android/ndk/android-ndk-r7-windows.zip 项目的native代码放在 <project>/jni/... 创建 <project>/jni/Android.mk 描述navive代码。编译native代码： cd <project> < ndk>/ndk-build 程序中的类内加载编译好的.so文件使用代码： static { System.loadLibrary("hello-jni"); } 用到的方法在类中使用示例:public native String stringFromJNI(); 6.android-ndk-r7\samples\下有示例代码，hello-jni运行成功。 Cygwin下编译native代码只是第四步有所不同。需要安装Cygwin的以下包： autoconf2.1 automake1.10 binutils gcc-core gcc4-core gdb pcre pcre-devel GNU awk 在D:\cygwin\home\Administrator.bash_profile添加： NDK=/cygdrive/d/Develop/android-ndk-r7 export NDK 进入Cygwin Bash，进入项目目录，用$NDK/ndk-build即可编译native代码。常见错误参见http://www.chinavideo.org/archiver/?tid-10821.html ndk试验成功，万里长征第一步，接下来配置cocos-2d。

发表了文章 2016-04-12

SFS&Android——SFS客户端全部事件详细

SFS是smartfoxserver的缩写。最近公司的一个Android项目要求使用SFS作为服务器。我去，服务器开发目前就我自己在研究。他们也真是放心。因为这个服务器是针对Flash开发的，官网上说支持Android，但是相关资料几乎没有。首先从学习SFS的Java客户端开始学习。首先需要安装SFS，然后使用其中的API。SFS有pro和2x两个适合的版本，2x是新版，但是暂且用pro了。去官网可以下载JavaSE和Android的例程。Java的例程导入Eclipse需要使用File->new->other，选择Java project from from existing ant buildfile。其中需要使用loadConfig方法载入xml配置文件。xml文件路径可能有错误，使用的是程序的默认用户路径，可以通过程序中打印用户路径来找到这个路径拷入配置文件。使用API主要用到了SmartFoxClient这个类。在程序中对其事件进行相应即可。还是要小小激动一下，毕业设计做的五子棋服务器端没有参考资料，凭经验琢磨出来了一套消息机制。没想到基本的消息流程跟SFS还是比较一致的。这里列出所有事件： sfs = new SmartFox(); //接收服务器超管信息事件 sfs.addEventListener(SFSEvent.ADMIN_MESSAGE, listener); //接收加载配置文件失败事件 sfs.addEventListener(SFSEvent.CONFIGLOADFAILURE, listener); //接收加载配置文件成功事件 sfs.addEventListener(SFSEvent.CONFIGLOADSUCCESS, listener); //接收连接服务器成功事件 sfs.addEventListener(SFSEvent.CONNECTION, listener); //接收连接服务器失败事件 sfs.addEventListener(SFSEvent.CONNECTION_LOST, listener); //接收连接服务器恢复事件 sfs.addEventListener(SFSEvent.CONNECTION_RESUME, listener); //接收重试服务器连接事件 sfs.addEventListener(SFSEvent.CONNECTION_RETRY, listener); //接收响应后台扩展事件 sfs.addEventListener(SFSEvent.EXTENSION_RESPONSE, listener); //接收用户邀请事件 sfs.addEventListener(SFSEvent.INVITATION, listener); //接收用户邀请事件 sfs.addEventListener(SFSEvent.INVITATION_REPLY, listener); //接收被邀请用户的回复事件 sfs.addEventListener(SFSEvent.INVITATIONREPLYERROR, listener); //接收用户登陆区域事件 sfs.addEventListener(SFSEvent.LOGIN, listener); //接收用户登区错误事件 sfs.addEventListener(SFSEvent.LOGIN_ERROR, listener); //接收用户登出区域事件 sfs.addEventListener(SFSEvent.LOGOUT, listener); //接收用户登出区域事件 sfs.addEventListener(SFSEvent.MODERATOR_MESSAGE, listener); //接收领头者消息事件 sfs.addEventListener(SFSEvent.OBJECT_MESSAGE, listener); //接收游戏者成功转换为观察者事件 sfs.addEventListener(SFSEvent.PLAYERTOSPECTATOR, listener); //接收游戏者转换为观察者错误事件 sfs.addEventListener(SFSEvent.PLAYERTOSPECTATOR_ERROR, listener); //接收私人消息事件 sfs.addEventListener(SFSEvent.PRIVATE_MESSAGE, listener); //接收公共消息事件 sfs.addEventListener(SFSEvent.PUBLIC_MESSAGE, listener); //接收创建房间事件 sfs.addEventListener(SFSEvent.ROOM_ADD, listener); //接收房间基础属性改变事件 sfs.addEventListener(SFSEvent.ROOMCAPACITYCHANGE, listener); //接收房间基础属性改变错误事件 sfs.addEventListener(SFSEvent.ROOMCAPACITYCHANGE_ERROR, listener); //接收查找房间的信息结果事件 sfs.addEventListener(SFSEvent.ROOMFINDRESULT, listener); //接收订阅一个房间组事件 sfs.addEventListener(SFSEvent.ROOMGROUPSUBSCRIBE, listener); //接收订阅一个房间组错误事件 sfs.addEventListener(SFSEvent.ROOMGROUPSUBSCRIBE_ERROR, listener); //接收创建房间错误事件 sfs.addEventListener(SFSEvent.ROOMCREATIONERROR, listener); //接收取消已订阅的一个房间组事件 sfs.addEventListener(SFSEvent.ROOMGROUPUNSUBSCRIBE, listener); //接收取消已订阅的一个房间组错误事件 sfs.addEventListener(SFSEvent.ROOMGROUPUNSUBSCRIBE_ERROR, listener); //接收进入房间事件 sfs.addEventListener(SFSEvent.ROOM_JOIN, listener); //接收进入房间错误事件 sfs.addEventListener(SFSEvent.ROOMJOINERROR, listener); //接收房间名更改事件 sfs.addEventListener(SFSEvent.ROOMNAMECHANGE, listener); //接收房间名更改错误事件 sfs.addEventListener(SFSEvent.ROOMNAMECHANGE_ERROR, listener); //接收房间密码更改事件 sfs.addEventListener(SFSEvent.ROOMPASSWORDSTATE_CHANGE, listener); //接收房间密码更改错误事件 sfs.addEventListener(SFSEvent.ROOMPASSWORDSTATECHANGEERROR, listener);

发表了文章 2016-04-12

FineReport简明教程

软件安装及帮助软件下载地址：http://www.finereport.com/products/trial 注册及获取激活码：http://www.finereport.com/products/login需要手机接收验证码或者致电获取。注册成功后收到邮件包含用户名密码及激活码。帮助系统：http://www.finereporthelp.com/或者安装后帮助->学习教程第一次安装后打开软件需要填入获取的验证码。试用版本禁用了一些功能，限制了最大连接数。系统演示。帮助->演示可以配置的管理员用户名和密码，这些信息保存在： %安装目录%\WebReport\WEB-INF\resources\privilege.xml 定义数据连接打开模版设计器软件服务器->定义数据连接支持JDBC和JNDI，JDBC包括Oracle、Mysql、DB2、SQLServer、Sybase、Access等只需填写URL和用户名密码即可。数据连接保存在： %安装目录%\WebReport\WEB-INF\resources\datasource.xml 设计报表打开模版设计器软件新建工作簿，在数据集面板新建数据库查询，将查询到的字段拖拽到工作簿中，添加表头等即可。我们设计了报表GoodsList.cpt。默认设计好的报表保存目录是： %安装目录%\WebReport\WEB-INF\reportlets。部署可以选择独立部署或者嵌入式部署。由于是集成到已有项目中，因此选择嵌入式部署。将%FineReport_HOME%\WebReport\WEB-INF目录下面的classes,lib,reportlets,resources四个目录复制到%项目目录%\WEB-INF下。整合web.xml文件 tomcat集成只需要在已有工程的web.xml中添加相应的servlet与servlet-mapping子元素。将%FineReport_HOME%/WebReport/WEB-INF下的web.xml中如下的部分复制到 %项目目录%/WEB-INF下的web.xml中，在最后一个servlet之后插入： <servlet> <servlet-name>ReportServer</servlet-name> <servlet-class>com.fr.web.ReportServlet</servlet-class> <load-on-startup>0</load-on-startup> </servlet> <servlet-mapping> <servlet-name>ReportServer</servlet-name> <url-pattern>/ReportServer</url-pattern> </servlet-mapping> 检测是否部署成功重新启动Tomcat，启动浏览器，在地址栏输入 http:/ip:服务器端口号/项目所在目录/ReportServer，能成功进入管理平台，则表明FineReport应用部署Tomcat服务器成功。 ReportServer?op=fs是数据决策系统 ReportServer?op=fr_platform是FR管理平台，这里可以设置管理员账号以及自定义身份验证。 Web页面集成 FineRepor报表可以通过Frame框架直接集成到Web页面中，Web页面可以有很多种脚本语言写的，比如Jsp、Asp、PHP、VB、JavaScript、Html 等，可以将报表嵌入在Frame框架内从而显示在Web页面中。若您希望自己系统页面中的按钮调用FineReport内部现成的js方法如（打印方法），需要加载FineReport的js文件，实际情况下，一个页面中可能不仅有报表部分，还会加载您自己的js文件，为避免引起不必要的js冲突，我们建议将报表内容显示在Frame中，而不要显示在div中。这样调用FineReport内部的js方法时，可以不用引入FineReport的js文件，直接通过Frame获取报表再调用方法，具体可参考分页文档中自定义工具栏节点。

发表了文章 2016-04-12

设计模式[1]-Memento

开始研究设计模式。一个非常perfect的设计模式示意图http://www.mcdonaldland.info/2007/11/28/40/ Type: Behavioral Memento：模式在不破坏封装性的情况下，捕获一个对象的内部状态传递到外部，使得稍后可以将该对象恢复到这个状态。代码参考了http://www.cppblog.com/converse/archive/2006/08/09/11063.html #include <iostream> #include <string> using namespace std; typedef std::string State; class Originator; class Memento{ private: friend class Originator; Memento(const State& rState): state(rState){}; State state; }; class Originator { public: Originator(const State& rState): state(rState){} Memento* createMemento(){ return new Memento(state); } void setMemento(Memento* pMemento){ state = pMemento->state; } void printState(){ cout<<"State:"<<state<<endl; } void setState(const State& rState){ state = rState; } private: State state; }; int main() { // 创建一个原发器 Originator* pOriginator = new Originator("old state"); pOriginator->printState(); // 创建一个备忘录存放这个原发器的状态 Memento *pMemento = pOriginator->createMemento(); // 更改原发器的状态 pOriginator->setState("new state"); pOriginator->printState(); // 通过备忘录把原发器的状态还原到之前的状态 pOriginator->setMemento(pMemento); pOriginator->printState(); system("Pause"); return 0; }

发表了文章 2016-04-12

设计模式[2]-Chain of Responsibility

Type: Behavioral #include <iostream> using namespace std; typedef int Request; class Handler { public: Handler(Handler *pSuccessor = NULL):m_pSuccessor(pSuccessor){}; // 纯虚函数,由派生类实现 virtual void handleRequest(Request request) = 0; protected: Handler* m_pSuccessor; }; class ConcreateHandler1: public Handler { public: void handleRequest(Request request) { if(request > 0) { cout<<"ConcreateHandler1 handle request."<<endl; } else { if(m_pSuccessor != NULL){ m_pSuccessor->handleRequest(request); } } } }; class ConcreateHandler2: public Handler { public: ConcreateHandler2(Handler *pSuccessor = NULL){ m_pSuccessor = pSuccessor; } void handleRequest(Request request) { if(request > 10) { cout<<"ConcreateHandler2 handle request."<<endl; } else { if(m_pSuccessor != NULL){ m_pSuccessor->handleRequest(request); } } } }; int main() { Handler *p1 = new ConcreateHandler1(); Handler *p2 = new ConcreateHandler2(p1); Request request = 1; p2->handleRequest(request); request = 12; p2->handleRequest(request); system("pause"); return 0; }

发表了文章 2016-04-12

[算法]-Longest Increasing Subsequence

看微软笔试题遇到的。 Longest Increasing Subsequence(LIS) means a sequence containing some elements in another sequence by the same order, and the values of elements keeps increasing.For example, LIS of {2,1,4,2,3,7,4,6} is {1,2,3,4,6}, and its LIS length is 5.Considering an array with N elements , what is the lowest time and space complexity to get the length of LIS？算法一：动态规划 #include <iostream> #include <vector> using namespace std; #define SIZE 8 int s[SIZE]= {2,1,4,2,3,7,4,6}; // sequence int length[SIZE]; // 第 x 格的值為 s[0...x] 的 LIS 長度 void LIS() { // 初始化。每一個數字本身就是長度為一的 LIS。 for (int i=0; i<SIZE; i++) length[i] = 1; for (int i=0; i<SIZE; i++) // 找出 s[i] 後面能接上哪些數字， // 若是可以接，長度就增加。 for (int j=i+1; j<SIZE; j++) if (s[i] < s[j]) length[j] = max(length[j], length[i] + 1); // length[] 之中最大的值即為 LIS 的長度。 int n = 0; for (int i=0; i<SIZE; i++) n = max(n, length[i]); cout << "LIS的長度是" << n; } int main(void) { LIS(); system("pause"); return 0; } 算法二：#include <iostream> #include <vector> using namespace std; #define SIZE 8 int s[SIZE]= {2,1,4,2,3,7,4,6}; // sequence int b[SIZE]; // num为要查找的数,k是范围上限 // 二分查找大于num的最小值，并返回其位置 int bSearch(int num, int k) { int low=1, high=k; while(low<=high) { int mid=(low+high)/2; if(num>=b[mid]) low=mid+1; else high=mid-1; } return low; }; void LIS() { int low = 1, high = SIZE; int k = 1; b[1] = s[1]; for(int i=2; i<=SIZE; ++i) { if(s[i]>=b[k]) b[++k] = s[i]; else { int pos = bSearch(s[i], k); b[pos] = s[i]; } } printf("%d", k); } int main(void) { LIS(); system("pause"); return 0; }

发表了文章 2016-04-12

设计模式[3]-Observer

Type: Behavioral 观察者模式：在对象间定义一对多的依赖关系，这样当一个对象改变状态时，自动通知更新依赖他的对象。 #include <iostream> #include <list> using namespace std; typedef int STATE; class Observer { public: virtual void update(STATE state) = 0; }; class ConcreteObserver : public Observer { public: void update(STATE state){ cout<<"Update Observer State:"<<state<<endl; observerState = state; }; private: STATE observerState; }; class Subject { public: virtual void notify(); void attach(Observer *pObserver){ m_ListObserver.push_back(pObserver); }; void detach(Observer *pObserver){ list<Observer*>::iterator iter; iter = find(m_ListObserver.begin(), m_ListObserver.end(), pObserver); if (m_ListObserver.end() != iter) { m_ListObserver.erase(iter); } }; protected: list<Observer*> m_ListObserver; }; class ConcreteSubject : public Subject { public: void notify(){ list<Observer*>::iterator list_it; for (list_it = m_ListObserver.begin(); list_it != m_ListObserver.end(); ++list_it) { (*list_it)->update(subjectState); } }; void setState(STATE state){ subjectState = state; }; private: STATE subjectState; }; int main() { Observer *p1 = new ConcreteObserver; Observer *p2 = new ConcreteObserver; ConcreteSubject* p = new ConcreteSubject; p->attach(p1); p->attach(p2); p->setState(4); p->notify(); p->detach(p1); p->setState(10); p->notify(); system("pause"); return 0; }

发表了文章 2016-04-12

2013编程之美全国挑战赛第一场-传话游戏

传话游戏时间限制: 1000ms 内存限制: 256MB 描述 Alice和Bob还有其他几位好朋友在一起玩传话游戏。这个游戏是这样进行的：首先，所有游戏者按顺序站成一排，Alice站第一位，Bob站最后一位。然后，Alice想一句话悄悄告诉第二位游戏者，第二位游戏者又悄悄地告诉第三位，第三位又告诉第四位……以此类推，直到倒数第二位告诉Bob。两位游戏者在传话中，不能让其他人听到，也不能使用肢体动作来解释。最后，Bob把他所听到的话告诉大家，Alice也把她原本所想的话告诉大家。由于传话过程中可能出现一些偏差，游戏者越多，Bob最后听到的话就与Alice所想的越不同。Bob听到的话往往会变成一些很搞笑的东西，所以大家玩得乐此不疲。经过几轮游戏后，Alice注意到在两人传话中，有些词汇往往会错误地变成其他特定的词汇。Alice已经收集到了这样的一个词汇转化的列表，她想知道她的话传到Bob时会变成什么样子，请你写个程序来帮助她。输入输入包括多组数据。第一行是整数 T，表示有多少组测试数据。每组数据第一行包括两个整数 N 和 M，分别表示游戏者的数量和单词转化列表长度。随后有 M 行，每行包含两个用空格隔开的单词 a 和 b，表示单词 a 在传话中一定会变成 b。输入数据保证没有重复的 a。最后一行包含若干个用单个空格隔开的单词，表示Alice所想的句子，句子总长不超过100个字符。所有单词都只包含小写字母，并且长度不超过20，同一个单词的不同时态被认为是不同的单词。你可以假定不在列表中的单词永远不会变化。输出对于每组测试数据，单独输出一行“Case #c: s”。其中，c 为测试数据编号，s 为Bob所听到的句子。s 的格式与输入数据中Alice所想的句子格式相同。数据范围 1 ≤ T ≤ 100 小数据：2 ≤ N ≤ 10, 0 ≤ M ≤ 10 大数据：2 ≤ N ≤ 100, 0 ≤ M ≤ 100 样例输入 2 4 3 ship sheep sinking thinking thinking sinking the ship is sinking 10 5 tidy tiny tiger liar tired tire tire bear liar bear a tidy tiger is tired 样例输出 Case #1: the sheep is thinking Case #2: a tiny bear is bear 题目很简单，理解上开始没注意到N的作用。 import java.util.HashMap; import java.util.Scanner; public class Ex1 { public static void main(String[] args) { Scanner in = new Scanner(System.in); int count = in.nextInt(); for (int i = 0; i < count; i++) { int N = in.nextInt(); int M = in.nextInt(); HashMap<String, String> map = new HashMap<String, String>(); for (int j = 0; j < M; j++) { map.put(in.next(), in.next()); } in.nextLine(); String[] sentence = in.nextLine().split(" "); System.out.print("Case #" + (i + 1) + ":"); for(int j=0; j<sentence.length; j++){ if(map.containsKey(sentence[j])){ String word = map.get(sentence[j]); for (int k = 0; k < N - 2;k++){ if(map.containsKey(word)){ word = map.get(word); } else { break; } } System.out.print(" " + word); } else { System.out.print(" " + sentence[j]); } } System.out.println(); } } }

发表了文章 2016-04-12

2013编程之美全国挑战赛第一场-树上的三角形

树上三角形时间限制: 2000ms 内存限制: 256MB 描述有一棵树，树上有只毛毛虫。它在这棵树上生活了很久，对它的构造了如指掌。所以它在树上从来都是走最短路，不会绕路。它还还特别喜欢三角形，所以当它在树上爬来爬去的时候总会在想，如果把刚才爬过的那几根树枝/树干锯下来，能不能从中选三根出来拼成一个三角形呢？输入输入数据的第一行包含一个整数 T，表示数据组数。接下来有 T 组数据，每组数据中：第一行包含一个整数 N，表示树上节点的个数（从 1 到 N 标号）。接下来的 N-1 行包含三个整数 a, b, len，表示有一根长度为 len 的树枝/树干在节点 a 和节点 b 之间。接下来一行包含一个整数 M，表示询问数。接下来M行每行两个整数 S, T，表示毛毛虫从 S 爬行到了 T，询问这段路程中的树枝/树干是否能拼成三角形。输出对于每组数据，先输出一行"Case #X:",其中X为数据组数编号，从 1 开始。接下来对于每个询问输出一行，包含"Yes"或“No”，表示是否可以拼成三角形。数据范围 1 ≤ T ≤ 5 小数据：1 ≤ N ≤ 100, 1 ≤ M ≤ 100, 1 ≤ len ≤ 10000 大数据：1 ≤ N ≤ 100000, 1 ≤ M ≤ 100000, 1 ≤ len ≤ 1000000000 样例输入 2 5 1 2 5 1 3 20 2 4 30 4 5 15 2 3 4 3 5 5 1 4 32 2 3 100 3 5 45 4 5 60 2 1 4 1 3 样例输出 Case #1: No Yes Case #2: No Yes 思路很简单，Dijkstra算法求出最短路径，暂没考虑多条路径的情况。然后三角形判断。可是最后Wrong Answer。 import java.util.ArrayList; import java.util.Arrays; import java.util.HashMap; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int T = in.nextInt(); for (int i = 0; i < T; i++) { int N = in.nextInt(); int[][] data = new int[N + 1][N + 1]; for (int j = 0; j < N - 1; j++) { int from = in.nextInt(); int to = in.nextInt(); int cost = in.nextInt(); data[from][to] = cost; data[to][from] = cost; } int Q = in.nextInt(); System.out.println("Case #" + (i+1) + ":"); for (int j = 0; j < Q; j++) { int from = in.nextInt(); int to = in.nextInt(); int[] cost = new int[N + 1]; boolean[] isFind = new boolean[N + 1]; HashMap<Integer, ArrayList<Integer>> path = new HashMap<Integer, ArrayList<Integer>>(); int current = from; isFind[current] = true; // Dijstra from->to for (int l = 1; l < N+1; l++) { int min = -1; for (int k = 1; k < N+1; k++) { if (data[current][k] > 0 && !isFind[k]) { int temp = cost[current] + data[current][k]; if (cost[k] == 0 || temp < cost[k]) { ArrayList<Integer> newPath = new ArrayList<Integer>(); newPath.add(data[current][k]); if (path.get(current) != null) { newPath.addAll(path.get(current)); path.put(k, newPath); } path.put(k, newPath); cost[k] = temp; } if (min < 0 || cost[k] < cost[min]) { min = k; } } } current = min; // System.out.println("current:" + current); if (current < 0) { break; } else if (current == to) { break; } isFind[current] = true; } System.out.println(path.get(to)); // 寻找 if (path.get(to) != null) { Integer[] pathArray = path.get(to).toArray(new Integer[0]); boolean find = false; for (int ii=0; ii<pathArray.length; ii++) { for(int ij=ii+1;ij<pathArray.length; ij++){ for(int ik=ij+1;ik<pathArray.length;ik++){ // System.out.println("path:" + pathArray[ii] + " " + pathArray[ij] + " " + pathArray[ik]); if(pathArray[ii] + pathArray[ij] > pathArray[ik] && pathArray[ij] + pathArray[ik] > pathArray[ii] && pathArray[ik] + pathArray[ii] > pathArray[ij]){ find = true; break; } } if(find)break; } if(find)break; } if(find) System.out.println("Yes"); else System.out.println("No"); } else { System.out.println("No"); } } } } }

发表了文章 2016-04-12

设计模式[4]-Command

Type: Behavioral #include <iostream> #include <vector> using namespace std; class Receiver { public: void action() { cout <<"Receiver Action"<<endl;; } }; class Command { public: virtual void execute()=0; }; class ConcreteCommand: public Command { public: ConcreteCommand(Receiver* pReceiver): m_pReceiver(pReceiver){}; void execute() { m_pReceiver->action(); }; private: Receiver* m_pReceiver; }; class Invoker { public: void addCommand(Command *pCommand) { mCommand.push_back(pCommand); pCommand->execute(); } private: vector<Command*> mCommand; }; int main() { Receiver* pReceiver = new Receiver(); Command* pCommand = new ConcreteCommand(pReceiver); Invoker* pInvoker = new Invoker(); pInvoker->addCommand(pCommand); system("pause"); return 0; }

发表了文章 2016-04-12

设计模式[5]-State

Type: Behavioral State模式：允许一个对象在其内部状态改变的时候改变其行为。 #include <iostream> using namespace std; class State; class Context { public: Context(State* pState): mState(pState){}; void request(); void setState(State* pState); private: State *mState; }; class State { public: virtual void handle(Context* pContext) = 0; }; class ConcreteState1: public State { public: void handle(Context* pContext); }; class ConcreteState2: public State { public: void handle(Context *pContext); }; void Context:: request() { mState->handle(this); } void Context:: setState(State* pState){ delete(this->mState); this->mState = pState; } void ConcreteState1::handle(Context *pContext) { cout<<"Handled by ConcreteState1"<<endl; pContext->setState(new ConcreteState2()); } void ConcreteState2::handle(Context *pContext) { cout<<"Handled by ConcreteState2"<<endl; pContext->setState(new ConcreteState1()); } int main() { Context *pContext = new Context(new ConcreteState1); pContext->request(); pContext->request(); pContext->request(); delete(pContext); system("pause"); return 0; }

发表了文章 2016-04-12

2013编程之美全国挑战赛第二场-集会

昨天做编程之美的题感觉只有这一道是水题。思路没问题但是写程序写错了一个地方没AC。今天翻出来想了一下终于解决了。解题思路：要寻找的这个目标点的纵坐标为0，设横坐标为x。以示例数据为例，可以得到目标点到这些点的距离，更直观一点，绘制成图形点击查看。观察可知符合要求的点可能出现的位置是某两个抛物线的交点或者某个抛物线的顶点。求出这些点来比较计算出的距离，取最小的即可。没机会提交的代码如下： import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int T = in.nextInt();// T个测试 for (int t = 0; t < T; t++) { int N = in.nextInt(); int x[] = new int[N]; int y[] = new int[N]; for (int i = 0; i < N; i++) { x[i] = in.nextInt(); y[i] = in.nextInt(); } double min = Double.MAX_VALUE; double ret = 0; for (int i = 0; i < N; i++) { for (int j = i + 1; j < N; j++) { double d = 0.5 * (sq(x[i]) - sq(x[j]) + sq(y[i]) - sq(y[j])) / (x[i] - x[j]); double res = calc(x, y, d); if (res < min) { min = res; ret = d; } } } for (int i = 0; i < N; i++) { double d = x[i]; double res = calc(x, y, d); if (res < min) { min = res; ret = d; } } System.out.println("Case #" + (t + 1) + ": " + ret); } } public static int sq(int x) { return x * x; } public static double sq(double x) { return x * x; } public static double calc(int[] x, int[] y, double d) { double max = 0.0; for (int i = 0; i < x.length; i++) { double temp = sq(x[i] - d) + sq(y[i]); if (temp > max) max = temp; } return max; } }

发表了文章 2016-04-12

设计模式[6]-Interpreter

Type: Behavioral Interpreter：给定一个语言，定义其语法的含义，同时拦截器利用其含义拦截其中的句子。 #include <iostream> #include <string> #include <vector> using namespace std; class Context { public: Context(string pInput):mInput(pInput){}; string mInput; }; class AbstractExpression { public: virtual void interpret(Context* contex) =0; }; class TerminalExpression : public AbstractExpression { public: void interpret(Context* context) { string &s = context->mInput; cout<<"TerminalExpression:"; for(int i=0; i<s.length(); i++){ if(s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/' ) cout<<" "<<s[i]; } cout<<endl; } }; class NonterminalExpression : public AbstractExpression { public: void interpret(Context* context) { cout<<"NonterminalExpression:"; string &s = context->mInput; for(int i=0; i<s.length(); i++){ if(s[i] == '0' || s[i] == '1' || s[i] == '2' || s[i] == '3' || s[i] == '4' || s[i] == '5' || s[i] == '6' || s[i] == '7' || s[i] == '8' || s[i] == '9' ) cout<<" "<<s[i]; } cout<<endl; } }; int main() { Context* context=new Context("123 + 456 * 789"); vector<AbstractExpression*> expressions; expressions.push_back(new TerminalExpression()); expressions.push_back(new NonterminalExpression()); vector<AbstractExpression*>::iterator iter=expressions.begin(); while(iter!=expressions.end()) { (*iter)->interpret(context); iter++; } system("pause"); }

发表了文章 2016-04-12

设计模式[7]-Strategy

Type: Behavioral Strategy模式：定义一系列的算法，封装每一个，使他们实现通用。让算法相对于使用他的clients可以独立地变化。 #include <iostream> using namespace std; class Strategy { public: virtual void execute() = 0; }; class ConcreteStrategyA: public Strategy { public: void execute() { cout<<"ConcreteStrategyA executed"<<endl; } }; class ConcreteStrategyB: public Strategy { public: void execute() { cout<<"ConcreteStrategyB executed"<<endl; } }; class Context { public: Context (Strategy* pStrategy): m_pStrategy(pStrategy){}; void setStrategy(Strategy* pStrategy) { m_pStrategy = pStrategy; } void invoke() { if(m_pStrategy != NULL) m_pStrategy->execute(); } private: Strategy* m_pStrategy; }; int main() { Strategy* pStrategy = new ConcreteStrategyA(); Context* pContext = new Context(pStrategy); pContext->invoke(); pStrategy = new ConcreteStrategyB(); pContext->setStrategy(pStrategy); pContext->invoke(); system("pause"); return 0; }

发表了文章 2016-04-12

设计模式[8]-Iterator

Type: Behavioral Iterator：提供一个方法连续访问一个聚合对象的元素，同时不暴露其底层表示 #include <iostream> using namespace std; #define Data int class Iterator { public: virtual Data* next()=0; }; class ConcreteIterator: public Iterator { public: ConcreteIterator(Data* data, int* size) { m_pData = data; m_pSize = size; mIndex = 0; }; Data* next() { if(m_pData != NULL && mIndex < *m_pSize){ return &m_pData[mIndex++]; } else { return NULL; } }; private: int mIndex; Data* m_pData; int* m_pSize; }; class Aggregate { public: virtual Iterator* createIterator() = 0; }; class ConcreteAggregate: public Aggregate { public: ConcreteAggregate(int size) { mSize = size; mData = new Data[size]; for(int i=0;i<size; i++) mData[i] = i; }; Iterator* createIterator() { Iterator* iterator = new ConcreteIterator(this->mData, &this->mSize); return iterator; }; private: Data* mData; int mSize; }; int main() { Aggregate* pAggregate = new ConcreteAggregate(4); Iterator* pIterator = pAggregate->createIterator(); Data* data; int count = 0; while (data = pIterator->next()) { if(count ++ > 10) break; cout <<*data<<endl; } system("pause"); return 0; }

发表了文章 2016-04-12

设计模式[9]-Template Method

Type: Behavioral Template Method: 在一个操作中定义一个算法的骨架，将一些步骤推迟到子类中。让子类在不修改算法结构的基础上重新定义其中步骤。 #include <iostream> using namespace std; class AbstractClass { public: void templateMethod() { cout<<"AbstractClass: Call subMethod"<<endl; subMethod(); }; protected: virtual void subMethod(); }; class ConcreteClass: public AbstractClass { public: void subMethod() { cout<<"ConcreteClass: subMethod"<<endl; }; }; int main() { ConcreteClass* pConcreteClass = new ConcreteClass; pConcreteClass->templateMethod(); system("pause"); return 0; }

发表了文章 2016-04-12

设计模式[10]-Mediator

Type: Behavioral Mediator: 定义一个对象，包装一系列对象如何交互。这些对象不必明确地互相引用，从而促进松散耦合，并且能够使你独立地改变他们之间的交互。 #include <iostream> using namespace std; class Mediator { public: virtual void inform(int id)=0; }; class Colleague { public: virtual void update()=0; }; class ConcreteColleague: public Colleague { public: ConcreteColleague(int id, Mediator* pMediator): mId(id),m_pMediator(pMediator){}; void update() { cout<<"ConcreteColleague"<<mId<<"update"<<endl; }; void send() { cout<<"ConcreteColleague"<<mId<<"send"<<endl; if(mId == 1) m_pMediator->inform(2); else if(mId == 2) m_pMediator->inform(1); }; private: int mId; Mediator* m_pMediator; }; class ConcreteMediator: public Mediator { public: void inform(int id) { if(id==1){ m_pColleague1->update(); } else if(id == 2){ m_pColleague2->update(); } }; void setColleague1(Colleague* pColleague) { m_pColleague1 = pColleague; }; void setColleague2(Colleague* pColleague) { m_pColleague2 = pColleague; }; private: Colleague* m_pColleague1; Colleague* m_pColleague2; }; int main() { ConcreteMediator* pMediator = new ConcreteMediator(); ConcreteColleague* pColleague1 = new ConcreteColleague(1, pMediator); ConcreteColleague* pColleague2 = new ConcreteColleague(2, pMediator); pMediator->setColleague1(pColleague1); pMediator->setColleague2(pColleague2); pColleague1->send(); pColleague2->send(); system("pause"); return 0; }

发表了文章 2016-04-12

设计模式[11]-Visitor

Type: Behavioral Visitor: Visitor提供要对对象结构中元素执行的操作。让你可以在不修改其操作的元素的情况下定义新操作。在元素类型很少改变的情况下适用。 #include <iostream> using namespace std; class ConcreteElementA; class ConcreteElementB; class Visitor { public: virtual void visitElementA(ConcreteElementA* a) = 0; virtual void visitElementB(ConcreteElementB* b) = 0; }; class Element { public: virtual void accept(Visitor* v)=0; }; class ConcreteVisitor: public Visitor { public: void visitElementA(ConcreteElementA* a) { cout<<"visitElementA"<<endl; }; void visitElementB(ConcreteElementB* b) { cout<<"visitElementB"<<endl; }; }; class ConcreteElementA: public Element { public: void accept(Visitor* v) { v->visitElementA(this); }; }; class ConcreteElementB: public Element { public: void accept(Visitor* v) { v->visitElementB(this); }; }; int main() { Visitor *pVisitor = new ConcreteVisitor; Element *pElement = new ConcreteElementA; pElement->accept(pVisitor); pElement = new ConcreteElementB; pElement->accept(pVisitor); system("pause"); return 0; }

发表了文章 2016-04-12

设计模式[12]-Adapter

Type: Structural Adapter: 将一个类的接口转换成clients期望的另一个接口。类不会因为接口不兼容而无法一起工作。实现方式有两种，继承和委让。这里使用的是委让。 #include <iostream> using namespace std; class Adapter { public: virtual void operation()=0; }; class Adaptee { public: void adaptedOperation() { cout<<"adaptedOperation"<<endl; }; }; class ConcreteAdapter: public Adapter { public: ConcreteAdapter(Adaptee* pAdaptee):m_pAdaptee(pAdaptee){}; void operation() { cout<<"ConcreteAdapter operation"<<endl; m_pAdaptee->adaptedOperation(); }; private: Adaptee* m_pAdaptee; }; int main() { Adaptee *pAdaptee = new Adaptee; Adapter *pTarget = new ConcreteAdapter(pAdaptee); pTarget->operation(); system("pause"); return 0; }

发表了文章 2016-04-12

设计模式[13]-Bridge

Type: Structural Bridge: 将抽象与其实现解耦，这样两者可以独立地变化。 #include <iostream> using namespace std; class Implementor { public: virtual void operationImpl() = 0; }; class ConcreteImplementorA: public Implementor { public: void operationImpl() { cout<<"ConcreteImplementorA operationImpl"<<endl; }; }; class ConcreteImplementorB: public Implementor { public: void operationImpl() { cout<<"ConcreteImplementorB operationImpl"<<endl; }; }; class Abstraction { public: void setImplementor(Implementor* pImplementor) { m_pImplementor = pImplementor; }; void operation() { if(m_pImplementor != NULL) m_pImplementor->operationImpl(); }; private: Implementor* m_pImplementor; }; int main() { ConcreteImplementorA *pImplA = new ConcreteImplementorA(); ConcreteImplementorB *pImplB = new ConcreteImplementorB(); Abstraction *pAbstraction = new Abstraction; pAbstraction->setImplementor(pImplA); pAbstraction->operation(); pAbstraction->setImplementor(pImplB); pAbstraction->operation(); system("pause"); return 0; }

发表了文章 2016-04-12

设计模式[14]-Composite

Type: Structural Composite: 通过递归手段来构造诸如文件系统之类的树形的对象结构；Composite模式所代表的数据构造是一群具有统一接口界面的对象集合，并可以通过一个对象来访问所有的对象（遍历）。 #include <iostream> #include <vector> #include <typeinfo> using namespace std; class Component { public: virtual void operation()=0; virtual void add(Component* c){}; virtual void remove(Component* c){}; virtual Component* getChild(int i){}; }; class Leaf: public Component { public: void operation() { cout<<"Leaf"<<endl; }; }; class Composite: public Component { public: void operation() { cout<<"Composite"<<endl; }; void add(Component* c) { mChildren.insert(mChildren.begin(), c); }; void remove(Component* c) { vector<Component*>::iterator it; for(it = mChildren.begin(); it < mChildren.end(); it++) if(*it == c) { mChildren.erase(it); break; } }; Component* getChild(int i) { if(i < 0 || i >= mChildren.size()) return NULL; return mChildren[i]; }; private: vector<Component*> mChildren; }; void printComponent(Component* pComponent) { pComponent->operation(); if(!dynamic_cast<Composite*>(pComponent)) return; int i=0; Component* childComponent; while(childComponent = pComponent->getChild(i++)) { printComponent(childComponent); }; }; int main() { Leaf *pLeaf1 = new Leaf(); Leaf *pLeaf2 = new Leaf(); Composite* pComposite = new Composite; pComposite->add(pLeaf1); pComposite->add(pLeaf2); Composite* pComposite2 = new Composite; pComposite2->add(pComposite); printComponent(pComposite2); system("pause"); return 0; }

发表了文章 2016-04-12

设计模式[15]-Decorator

Type: Structural Decorator: 动态给一个对象添加一些额外的职责，就象在墙上刷油漆。使用Decorator模式相比用生成子类方式达到功能的扩充显得更为灵活。 FileReader fr = new FileReader(filename); BufferedReader br = new BufferedReader(fr); 实际上Java 的I/O API就是使用Decorator实现的,I/O变种很多,如果都采取继承方法,将会产生很多子类,显然相当繁琐 #include <iostream> #define Data int using namespace std; class Component { public: virtual void operation()=0; }; class ConcreteComponent: public Component { public: void operation() { cout<<"ConcreteComponent operation"<<endl; }; }; class Decorator { public: virtual void operation() = 0; }; class ConcreteDecorator: public Decorator { public: ConcreteDecorator(Component* pComponent): m_pComponent(pComponent){}; void operation() { cout<<"ConcreteDecorator operation"<<endl; addedBehavior(); }; void addedBehavior() { m_pComponent->operation(); }; private: Data addedState; Component* m_pComponent; }; int main() { Component* pComponent = new ConcreteComponent(); Decorator* pDecorator = new ConcreteDecorator(pComponent); pDecorator->operation(); system("pause"); return 0; }

发表了文章 2016-04-12

设计模式[16]-Facede

Type: Structural Facade: 为子系统中的一组接口提供一个一致的界面。典型应用是数据库JDBC的应用。 Jsp中常用的操作数据库的方法如下： public class DBCompare { 　　Connection conn = null; 　　PreparedStatement prep = null; 　　ResultSet rset = null; 　　try { 　　　　Class.forName( "<driver>" ).newInstance(); 　　　　 conn = DriverManager.getConnection( "<database>" ); 　　　　　　　　 String sql = "SELECT * FROM <table> WHERE <column name> = ?"; 　　　　 prep = conn.prepareStatement( sql ); 　　　　 prep.setString( 1, "<column value>" ); 　　　　 rset = prep.executeQuery(); 　　　　 if( rset.next() ) { 　　　　　　　　System.out.println( rset.getString( "<column name" ) ); 　　　　　} 　　} catch( SException e ) { 　　　　 e.printStackTrace(); 　　} finally { 　　　　 rset.close(); 　　　　 prep.close(); 　　　　 conn.close(); 　　} } 在应用中,经常需要对数据库操作,每次都写上述一段代码肯定比较麻烦,需要将其中不变的部分提炼出来,做成一个接口,这就引入了facade外观对象.如果以后我们更换Class.forName中的<driver>也非常方便,比如从Mysql数据库换到Oracle数据库,只要更换facade接口中的driver就可以。 public class DBCompare { 　 String sql = "SELECT * FROM <table> WHERE <column name> = ?";　　　　try { 　　　　Mysql msql=new mysql(sql); 　　　　 msql.setString( 1, "<column value>" ); 　　　　 rset = msql.executeQuery(); 　　　　 if( rset.next() ) { 　　　　　　　　System.out.println( rset.getString( "<column name" ) ); 　　　　　} 　　} catch( SException e ) { 　　　　 e.printStackTrace(); 　　} finally { 　　　　 mysql.close(); 　　　　 mysql=null; 　　} }

发表了文章 2016-04-12

设计模式[17]-Flyweight

Type: Structural Flyweight: 避免大量拥有相同内容的小类的开销(如耗费内存)，使大家共享一个类(元类)。找出这些对象群的共同点,设计一个元类，封装可以被共享的类。另外，还有一些特性是取决于应用(context)，是不可共享的，这也Flyweight中两个重要概念内部状态intrinsic和外部状态extrinsic之分。#include <iostream> #include <map> using namespace std; #define State int class Flyweight { public: virtual void operation(State extrinsicState) = 0; }; class ConcreteFlyweight: public Flyweight { public: ConcreteFlyweight(State key):intrinsicState(key){}; void operation(State extrinsicState) { cout<<"ConcreteFlyweight intrinsicState:"<<intrinsicState <<" extrinsicState"<<extrinsicState<<endl; }; private: State intrinsicState; }; class UnsharedConcreteFlyweight: public Flyweight { public: void operation(State extrinsicState) { cout<<"UnsharedConcreteFlyweight"<<endl; }; private: State allState; }; class FlyweightFactory { public: Flyweight* getFlyweight(State key) { Flyweight* pFlyweight = m_Flyweights[key]; if(pFlyweight == NULL) { pFlyweight = new ConcreteFlyweight(key); m_Flyweights[key] = pFlyweight; } return pFlyweight; }; private: map<State, Flyweight*> m_Flyweights; }; int main() { FlyweightFactory flyweightfactory; flyweightfactory.getFlyweight(0)->operation(0); flyweightfactory.getFlyweight(1)->operation(0); system("pause"); return 0; }

发表了文章 2016-04-12

设计模式[18]-Proxy

Type: Structural Proxy: 提供一个替代品或者占位符来控制对一个对象的访问。#include <iostream> using namespace std; class Subject { public: virtual void request()=0; }; class RealSubject: public Subject { public: void request() { cout<<"Real request"<<endl; } }; class Proxy: public Subject { public: Proxy(RealSubject* pRealSubject):m_pRealSubject(pRealSubject){}; void request() { cout<<"Proxy request"<<endl; m_pRealSubject->request(); }; private: RealSubject* m_pRealSubject; }; int main() { RealSubject* pRealSubject = new RealSubject; Subject* pProxy = new Proxy(pRealSubject); pProxy->request(); system("pause"); return 0; }

发表了文章 2016-04-12

设计模式[19]-Abstract Factory

Type: Creational Abstract Factory: 提供一个接口创建一系列相关或者依赖的对象，而无需指定其实现类。如果没有应对“多系列对象构建”的需求变化，则没有必要使用Abstract Factory模式。Abstract Factory模式主要在于应对“新系列”的需求变动。缺点是难以应对“新对象”的需求变动。Abstract Factory模式经常和Factory Method模式共同组合来应对“对象创建”的需求变化。 #include <iostream> using namespace std; class AbstractProductA{}; class AbstractProductB{}; class ConcreteProductA1: public AbstractProductA{ public: ConcreteProductA1() { cout<<"ConcreteProductA1"<<endl; }; }; class ConcreteProductB1: public AbstractProductB { public: ConcreteProductB1() { cout<<"ConcreteProductB1"<<endl; }; }; class ConcreteProductA2: public AbstractProductA { public: ConcreteProductA2() { cout<<"ConcreteProductA2"<<endl; }; }; class ConcreteProductB2: public AbstractProductB { public: ConcreteProductB2() { cout<<"ConcreteProductB2"<<endl; }; }; class AbstractFactory { public: virtual AbstractProductA* createProductA()=0; virtual AbstractProductB* createProductB()=0; }; class ConcreteFactory1: public AbstractFactory { public: AbstractProductA* createProductA() { return new ConcreteProductA1; }; AbstractProductB* createProductB() { return new ConcreteProductB1; }; }; class ConcreteFactory2: public AbstractFactory { public: AbstractProductA* createProductA() { return new ConcreteProductA2; }; AbstractProductB* createProductB() { return new ConcreteProductB2; }; }; int main() { ConcreteFactory1 *pFactory1 = new ConcreteFactory1; AbstractProductA *pProductA = pFactory1->createProductA(); AbstractProductB *pProductB = pFactory1->createProductB(); ConcreteFactory2 *pFactory2 = new ConcreteFactory2; pProductA = pFactory2->createProductA(); pProductB = pFactory2->createProductB(); system("pause"); return 0; }

发表了文章 2016-04-12

设计模式[20]-Builder

Type: Creational Builder: 将一个复杂对象的构建与它的表示分离,使得同样的构建过程可以创建不同的表示。是为了将构建复杂对象的过程和它的部件解耦。Builder负责构建部件，Director负责处理构建的过程。 #include <iostream> using namespace std; class Part{}; class Product { public: Product(Part* pPartA, Part* pPartB, Part* pPartC){}; }; class Builder { public: virtual void buildPartA()=0; virtual void buildPartB()=0; virtual void buildPartC()=0; }; class ConcreteBuilder: public Builder { public: void buildPartA() { cout<<"Build Part A"<<endl; mPartA = new Part; }; void buildPartB() { cout<<"Build Part B"<<endl; mPartB = new Part; }; void buildPartC() { cout<<"Build Part C"<<endl; mPartC = new Part; }; Product* getResult() { cout<<"Get Result"<<endl; return new Product(mPartA, mPartB, mPartC); }; private: Part *mPartA, *mPartB, *mPartC; }; class Director { public: Director(Builder* pBuilder):m_pBuilder(pBuilder){}; void construct() { cout<<"Director construct"<<endl; m_pBuilder->buildPartA(); m_pBuilder->buildPartB(); m_pBuilder->buildPartC(); }; private: Builder* m_pBuilder; }; int main() { ConcreteBuilder* pBuilder = new ConcreteBuilder; Director *pDirector = new Director(pBuilder); pDirector->construct(); pBuilder->getResult(); system("pause"); return 0; }

发表了文章 2016-04-12

设计模式[21]-Factory Method

Type: Creational Factory Method: 定义一个创建对象的接口，但是让子类决定实例化哪个类。新增加一个产品的时候，只需派生一个该类型的工厂而无需修改原来的代码。每个具体工厂只负责返回一种产品类。是最典型的模板方法模式(Templete Method pattern)应用。 #include <iostream> using namespace std; class Product{}; class ConcreteProduct: public Product { public: ConcreteProduct() { cout<<"ConcreteProduct"<<endl; }; }; class Creator { public: virtual Product* factoryMethod() = 0; }; class ConcreteCreator: public Creator { public: Product* factoryMethod() { cout<<"ConcreteCreator decide which class to instantiate"<<endl; return new ConcreteProduct; }; }; int main() { Creator* pCreator = new ConcreteCreator; Product* pProduct = pCreator->factoryMethod(); system("pause"); };

发表了文章 2016-04-12

设计模式[22]-Prototype

Type: Creational Prototype: 用原型实例指定创建对象的种类，并且通过拷贝这些原型创建新的对象。 #include <iostream> using namespace std; class Prototype { public: virtual Prototype* clone()= 0; int mType; }; class ConcretePrototype: public Prototype { public: ConcretePrototype* clone() { ConcretePrototype* pConcretePrototype = new ConcretePrototype; pConcretePrototype->mType = this->mType; return pConcretePrototype; }; }; int main() { Prototype* pPrototype1 = new ConcretePrototype; pPrototype1->mType = 47; cout<<"pPrototype1 "<<pPrototype1->mType<<endl; Prototype* pPrototype2 = pPrototype1->clone(); cout<<"pPrototype2 "<<pPrototype2->mType<<endl;; system("pause"); } #include <iostream> using namespace std; class Prototype { public: virtual Prototype* clone()= 0; int mType; }; class ConcretePrototype: public Prototype { public: ConcretePrototype* clone() { ConcretePrototype* pConcretePrototype = new ConcretePrototype; pConcretePrototype->mType = this->mType; return pConcretePrototype; }; }; int main() { Prototype* pPrototype1 = new ConcretePrototype; pPrototype1->mType = 47; cout<<"pPrototype1 "<<pPrototype1->mType<<endl; Prototype* pPrototype2 = pPrototype1->clone(); cout<<"pPrototype2 "<<pPrototype2->mType<<endl;; system("pause"); }

发表了文章 2016-04-12

设计模式[23]-Singleton

Type: Creational Singleton: 保证一个类只有一个示例，并且提供一个全局指针指向他。Singleton也能够被无状态化。提供工具性质的功能。 #include <iostream> using namespace std; class Singleton { public: static Singleton* instance() { static Singleton uniqueInstance; return &uniqueInstance; }; private: Singleton() { cout<<"Singleton"<<endl; }; static string singletonData; }; int main() { Singleton* pInstance1 = Singleton::instance(); Singleton* pInstance2 = Singleton::instance(); cout<<"Address compare: "<<boolalpha<<(pInstance1 == pInstance2)<<endl; system("pause"); } 设计模式学习完了。花了好几天的时间。感觉自己理解的还很肤浅。想要学透，只能在实践中慢慢体会。解道网是个很不错的网站，以后要学会从更大的角度思考问题。明天开始抓紧看看面试题，准备微软的面试。加油！

发表了文章 2016-04-12

CareerCup-BASE CASE AND BUILD

这个题刷起来感觉比编程之美什么的easy多了。 Description: Solve the algorithm first for a base case (e g , just one element) Then, try to solve it for elements one and two, assuming that you have the answer for element one Then, try to solve it for elements one, two and three, assuming that you have the answer to elements one and two Example: Design an algorithm to print all permutations of a string For simplicity, assume all characters are unique. Testing String: abcdefg Case “a” --> {a} Case “ab” --> {ab, ba} Case “abc” --> ? #include <iostream> using namespace std; void print(char* prefix, char* data, int index, int length) { if(index >= length) { static int count = 0; printf("%d: %s\n", count++, prefix); return; } int prelength = strlen(prefix); for(int i=0; i<prelength+1; i++) { char* s = new char[prelength + 2];; int count = 0, j; for(j=0; j<prelength+1; j++) { if(j == i) s[j] = data[index]; else s[j] = prefix[count++]; } s[j] = '\0'; print(s, data, index+1, length); } }; int main() { char* data = "abcd"; print("", data, 0, strlen(data)); system("pause"); };

发表了文章 2016-04-12

CareerCup-PATTERN MATCHING

CareerCup是一本相当好Code面试的书，开始研读。 Description: Consider what problems the algorithm is similar to, and figure out if you can modify the solution to develop an algorithm for this problem Example: A sorted array has been rotated so that the elements might appear in the order 3 4 5 6 7 1 2 How would you find the minimum element? #include <iostream> using namespace std; int find(int* data, int low, int high) { printf("%d->%d\n", low, high); if(low == high) return data[low]; if(data[low] < data[high]) return data[low]; int mid = (low + high)/2; if(data[mid] >= data[low]) return find(data, mid+1, high); else return find(data, low, mid); }; int main() { int data[] = {3, 4, 5, 6, 7, 1, 2}; printf("%d", find(data, 0, sizeof(data)/sizeof(int)-1)); system("pause"); };

发表了文章 2016-04-12

Java内存泄露

1. Java内存泄漏与C++的区别在Java 中，内存泄漏就是存在一些被分配的对象，这些对象有下面两个特点，首先，这些对象是可达的，即在有向图中，存在通路可以与其相连；其次，这些对象是无用的，即程序以后不会再使用这些对象。如果对象满足这两个条件，这些对象就可以判定为Java 中的内存泄漏，这些对象不会被GC 所回收，然而它却占用内存。在C++中，内存泄漏的范围更大一些。有些对象被分配了内存空间，然后却不可达，由于C++中没有GC，这些内存将永远收不回来。在Java 中，这些不可达的对象都由GC 负责回收，因此程序员不需要考虑这部分的内存泄漏。 2. 内存泄露示例 Vector v = new Vector(10); for (int i = 1; i < 100; i++) { Object o = new Object(); v.add(o); o = null; } Vector中引用的对象存在引用未被释放，出现内存泄漏。 3. 内存泄漏原因 3.1 静态集合类如HashMap，Vector。 3.2 监听器，例如addXXXListener()释放的时候需要删除监听器 3.3 物理连接，如数据库连接，网络连接，不使用的时候需要close。如果使用连接池，显式关闭连接外还需要显式关闭ResultSet Statement对象。附：subString的内存泄漏 List<String> handler = new ArrayList<String>(); for (int i = 0; i < 1000; i++) { String str = new String(new char[10000000]); handler.add(str.substring(1, 5)); } 分析subString源码： String(int offset, int count, char value[]) { this.value = value; this.offset = offset; this.count = count; } 实际上为了加快运行的效率，牺牲了内存空间。导致subString得到的对象占用空间并未减少。因此需要调用其拷贝构造方法，修改为 handler.add(new String(str.substring(1, 5))); 分析该构造方法的代码，如果String的大小比其中包含的char数组大小要小，那么就做一次部分拷贝。否则与subString方法类似。

发表了文章 2016-04-12

CareerCup-1.6

Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees Can you do this in place? 唉！还是会有错误，这次控制到只有一处错误。 #include <iostream> using namespace std; #define N 5 void rotate(int data[N][N]) { int temp, m; for(int i=0; i<N-2; i++) { m = N-1; for(int j=i; j<N-i-1; j++) { temp = data[i][j]; data[i][j] = data[m-j][i]; data[m-j][i] = data[m-i][m-j]; data[m-i][m-j] = data[j][m-i]; data[j][m-i] = temp; } } } void print(int data[N][N]) { for(int i=0; i<N; i++) { for(int j=0; j<N; j++) cout<<data[i][j]<<"\t"; cout<<endl; } cout<<"End"<<endl; } int main() { int data[N][N]; int count = 0; for(int i=0; i<N; i++) for(int j=0; j<N; j++) data[i][j] = ++count; print(data); rotate(data); print(data); system("pause"); }; #include <iostream> using namespace std; #define N 5 void rotate(int data[N][N]) { int temp, m; for(int i=0; i<N-2; i++) { m = N-1; for(int j=i; j<N-i-1; j++) { temp = data[i][j]; data[i][j] = data[m-j][i]; data[m-j][i] = data[m-i][m-j]; data[m-i][m-j] = data[j][m-i]; data[j][m-i] = temp; } } } void print(int data[N][N]) { for(int i=0; i<N; i++) { for(int j=0; j<N; j++) cout<<data[i][j]<<"\t"; cout<<endl; } cout<<"End"<<endl; } int main() { int data[N][N]; int count = 0; for(int i=0; i<N; i++) for(int j=0; j<N; j++) data[i][j] = ++count; print(data); rotate(data); print(data); system("pause"); };

发表了文章 2016-04-12

C++ STL使用帮助

基本确定以后code interview抛弃java用c++。所以不得不面对STL以加快写代码速度。#include <iostream> #include <vector> #include <list> #include <stack> #include <queue> #include <set> #include <map> using namespace std; template<typename T> void printContainer(T data) { cout<<"Print============================="<<endl; typename T::iterator iter; for(iter = data.begin(); iter!=data.end(); iter++) { cout<<*iter<<" "; } cout<<endl<<"End-------------------------------"<<endl; }; // 删除一个元素 template<typename T> void deleteContainer(T data, int d) { typename T::iterator iter; iter = find(data.begin(), data.end(), d); if(iter != data.end()) data.erase(iter); } bool comp(const int a, const int b){ return a>b;}; void testVector() { vector<int> vi; vi.assign(5, 8); // 构造vector，类似copy函数 vi.pop_back(); // 移除最后一个元素 vi.push_back(3); // 在最后添加一个元素 vi.insert(vi.begin(), 2); // 插入一个元素 swap(vi[0], vi[1]); // 交换两个元素 cout<<"Capacity: "<<vi.capacity()<<endl; //返回能容纳元素数量 cout<<"At: "<<vi.at(2)<<" "<<vi[1]<<endl; // 访问指定位置元素 cout<<"Front: "<<vi.front()<<endl; // 返回第一个位置元素 cout<<"Back: "<<vi.back()<<endl; // 返回最后一个位置元素 cout<<"Empty: "<<boolalpha<<vi.empty()<<endl; // 容器是否为空 cout<<"Size: "<<vi.size()<<endl; // 容器中元素数量 sort(vi.begin(), vi.end()); // vector排序 // 正序遍历在删除时自动后移，反序遍历删除没问题。 // for(vector<int>::iteratoriter = vi.end()-1; iter>= vi.begin();iter--) vi.clear(); //清除所有元素 }; void testList() { list<int> li; li.assign(5, 8); // 构造vector，类似copy函数 li.pop_back(); // 移除最后一个元素 li.push_back(3); // 在最后添加一个元素 li.pop_front(); li.push_front(9); li.insert(++li.begin(), 2); // 插入一个元素 cout<<"Front: "<<li.front()<<endl; // 返回第一个位置元素 cout<<"Back: "<<li.back()<<endl; // 返回最后一个位置元素 cout<<"Empty: "<<boolalpha<<li.empty()<<endl; // 容器是否为空 cout<<"Size: "<<li.size()<<endl; // 容器中元素数量 list<int> li2; swap(li2, li); // 交换两个list li.splice(li.end(), li2, li2.begin()); // 指定的部分插入到list中 li.splice(li.end(), li2); // 全部插入list中 li.splice(li.end(), li2, li2.begin(), li2.end()); // 源list中元素将清除 li.merge(li2); // 合并，源list中将清除元素 li.unique(); // 删除重复元素 li.sort(); // 元素排序 li.clear(); //清除所有元素 }; void testStack() { stack<int> si; si.push(8); // 压栈 si.push(2); si.pop(); // 退栈 cout<<"Size: "<<si.size()<<endl; cout<<"Top: "<<si.top()<<endl; }; void testQueue() { queue<int> qi; qi.push(8); // 末尾加入元素 qi.push(2); cout<<"Front: "<<qi.front()<<endl; cout<<"Back: "<<qi.back()<<endl; qi.pop(); // 退栈 cout<<"Size: "<<qi.size()<<endl; qi.empty(); // 清空栈 }; void testSet() { set<int> si; si.insert(4); // 插入元素 si.insert(3); // 插入元素 si.insert(1); // 插入元素 si.insert(si.begin(), 2); // 指定位置插入元素 cout<<"Size: "<<si.size()<<endl; cout<<"Empty: "<<boolalpha<<si.empty()<<endl; cout<<"Count: "<<si.count(3)<<endl; // 返回在set中数目，1或0 cout<<"Find: "<<*si.find(3)<<endl; // 查找在set中位置 pair<set<int>::const_iterator,set<int>::const_iterator> ret; ret = si.equal_range(3); // return the bounds of a range cout<<"Lower bound: "<<*ret.first<<endl; cout<<"Upper bound: "<<*ret.second<<endl; si.erase(si.lower_bound(3), si.upper_bound(4)); //upper_bound与lower_bound set<int> si2; si.swap(si2); si.insert(si2.begin(), si2.end()); set<int>::iterator iter; for(iter = si.begin(); iter!=si.end(); ) { if(*iter == 2) si.erase(iter++); // increase iterator before delete else iter++ ; } si.clear(); }; void testMap() { map<int, string> mi; mi[3] = "3"; mi.insert(pair<int, string>(4, "4")); // 插入需要pair的形式 mi.insert(pair<int, string>(2, "2")); mi.insert(pair<int, string>(5, "5")); cout<<"Size: "<<mi.size()<<endl; cout<<"Count: "<<mi.count(3)<<endl; cout<<"At: "<<mi[3]<<endl; mi.erase(mi.lower_bound(4), mi.upper_bound(4)); map<int, string>::iterator it = mi.find(3); mi.erase(it); map<int, string> mi2; swap(mi, mi2); // 交换两个set cout<<"Print============================="<<endl; for(it = mi.begin(); it != mi.end(); it++) { cout<<it->first<<": "<<it->second<<endl; } cout<<"End-------------------------------"<<endl; mi.clear(); }; int main() { //testVector(); //testList(); //testStack(); //testQueue(); //testSet(); testMap(); system("pause"); }; #include <iostream> #include <vector> #include <list> #include <stack> #include <queue> #include <set> #include <map> using namespace std; template<typename T> void printContainer(T data) { cout<<"Print============================="<<endl; typename T::iterator iter; for(iter = data.begin(); iter!=data.end(); iter++) { cout<<*iter<<" "; } cout<<endl<<"End-------------------------------"<<endl; }; // 删除一个元素 template<typename T> void deleteContainer(T data, int d) { typename T::iterator iter; iter = find(data.begin(), data.end(), d); if(iter != data.end()) data.erase(iter); } bool comp(const int a, const int b){ return a>b;}; void testVector() { vector<int> vi; vi.assign(5, 8); // 构造vector，类似copy函数 vi.pop_back(); // 移除最后一个元素 vi.push_back(3); // 在最后添加一个元素 vi.insert(vi.begin(), 2); // 插入一个元素 swap(vi[0], vi[1]); // 交换两个元素 cout<<"Capacity: "<<vi.capacity()<<endl; //返回能容纳元素数量 cout<<"At: "<<vi.at(2)<<" "<<vi[1]<<endl; // 访问指定位置元素 cout<<"Front: "<<vi.front()<<endl; // 返回第一个位置元素 cout<<"Back: "<<vi.back()<<endl; // 返回最后一个位置元素 cout<<"Empty: "<<boolalpha<<vi.empty()<<endl; // 容器是否为空 cout<<"Size: "<<vi.size()<<endl; // 容器中元素数量 sort(vi.begin(), vi.end()); // vector排序 // 正序遍历在删除时自动后移，反序遍历删除没问题。 // for(vector<int>::iteratoriter = vi.end()-1; iter>= vi.begin();iter--) vi.clear(); //清除所有元素 }; void testList() { list<int> li; li.assign(5, 8); // 构造vector，类似copy函数 li.pop_back(); // 移除最后一个元素 li.push_back(3); // 在最后添加一个元素 li.pop_front(); li.push_front(9); li.insert(++li.begin(), 2); // 插入一个元素 cout<<"Front: "<<li.front()<<endl; // 返回第一个位置元素 cout<<"Back: "<<li.back()<<endl; // 返回最后一个位置元素 cout<<"Empty: "<<boolalpha<<li.empty()<<endl; // 容器是否为空 cout<<"Size: "<<li.size()<<endl; // 容器中元素数量 list<int> li2; swap(li2, li); // 交换两个list li.splice(li.end(), li2, li2.begin()); // 指定的部分插入到list中 li.splice(li.end(), li2); // 全部插入list中 li.splice(li.end(), li2, li2.begin(), li2.end()); // 源list中元素将清除 li.merge(li2); // 合并，源list中将清除元素 li.unique(); // 删除重复元素 li.sort(); // 元素排序 li.clear(); //清除所有元素 }; void testStack() { stack<int> si; si.push(8); // 压栈 si.push(2); si.pop(); // 退栈 cout<<"Size: "<<si.size()<<endl; cout<<"Top: "<<si.top()<<endl; }; void testQueue() { queue<int> qi; qi.push(8); // 末尾加入元素 qi.push(2); cout<<"Front: "<<qi.front()<<endl; cout<<"Back: "<<qi.back()<<endl; qi.pop(); // 退栈 cout<<"Size: "<<qi.size()<<endl; qi.empty(); // 清空栈 }; void testSet() { set<int> si; si.insert(4); // 插入元素 si.insert(3); // 插入元素 si.insert(1); // 插入元素 si.insert(si.begin(), 2); // 指定位置插入元素 cout<<"Size: "<<si.size()<<endl; cout<<"Empty: "<<boolalpha<<si.empty()<<endl; cout<<"Count: "<<si.count(3)<<endl; // 返回在set中数目，1或0 cout<<"Find: "<<*si.find(3)<<endl; // 查找在set中位置 pair<set<int>::const_iterator,set<int>::const_iterator> ret; ret = si.equal_range(3); // return the bounds of a range cout<<"Lower bound: "<<*ret.first<<endl; cout<<"Upper bound: "<<*ret.second<<endl; si.erase(si.lower_bound(3), si.upper_bound(4)); //upper_bound与lower_bound set<int> si2; si.swap(si2); si.insert(si2.begin(), si2.end()); set<int>::iterator iter; for(iter = si.begin(); iter!=si.end(); ) { if(*iter == 2) si.erase(iter++); // increase iterator before delete else iter++ ; } si.clear(); }; void testMap() { map<int, string> mi; mi[3] = "3"; mi.insert(pair<int, string>(4, "4")); // 插入需要pair的形式 mi.insert(pair<int, string>(2, "2")); mi.insert(pair<int, string>(5, "5")); cout<<"Size: "<<mi.size()<<endl; cout<<"Count: "<<mi.count(3)<<endl; cout<<"At: "<<mi[3]<<endl; mi.erase(mi.lower_bound(4), mi.upper_bound(4)); map<int, string>::iterator it = mi.find(3); mi.erase(it); map<int, string> mi2; swap(mi, mi2); // 交换两个set cout<<"Print============================="<<endl; for(it = mi.begin(); it != mi.end(); it++) { cout<<it->first<<": "<<it->second<<endl; } cout<<"End-------------------------------"<<endl; mi.clear(); }; int main() { //testVector(); //testList(); //testStack(); //testQueue(); //testSet(); testMap(); system("pause"); };

发表了文章 2016-04-12

jQuery UI在Server 2008 IE8下DatePicker问题修复

这真是个WTF的问题，类似参见Stack Overflow 这个DatePicker问题只在Server 2008的IE8下出现。至于为什么win7的IE8支持，Server2008的IE8不支持，就不知道了。可能升级jQuery UI版本能够升级这个问题，但是由于实验室项目比较庞大，升级代价太大。所以只能试图修复。 Debug一段时间，发现问题究其根本是由于button、a、td标签的onclick方法不被IE8支持。现在实用的jQuery UI版本是min版，看着真是费劲，从网上下载来源码，看着舒服多了。修改jQuery源代码。7894行：_selectDay: function(id, month, year, td) { var target = $(id); if ($(td).hasClass(this._unselectableClass) || this._isDisabledDatepicker(target[0])) { return; } var inst = this._getInst(target[0]); inst.selectedDay = inst.currentDay = $('a', td).html(); 修改为 _selectDay: function(id, month, year, day) { var target = $(id); if (this._isDisabledDatepicker(target[0])) { return; } var inst = this._getInst(target[0]); inst.selectedDay = inst.currentDay = day; 8445行和8454行将响应方法由onclick转移到href。8462-8467行的button标签修改为a标签。同样将响应方法从onclick转移到href。这两个button修改标签之后样式不和谐，加入了一些css来控制与之前一致 float: right; margin: 0.5e m 0.2e m 0.4e m; padding: 0.2e m 0.6e m 0.3e m 0.6e m; color: #2f6ca9; font-size: 0.8em; font-weight: bold; text-align: center; text-decoration: none; 最烦浏览器兼容性问题，这次又成功解决了。

发表了文章 2016-04-12

CareerCup-2.1

Write code to remove duplicates from an unsorted linked list. FOLLOW UP How would you solve this problem if a temporary buffer is not allowed? #include <iostream> using namespace std; // Creating a Linked List: struct Node { Node(int d):data(d){next = NULL;}; int data; Node* next; }; void printNode(Node* head) { cout<<"Print:"<<endl; while(head != NULL) { cout<<head->data<<endl; head = head->next; } cout<<"End"<<endl; }; // Deleting a Node from a Singly Linked List bool deleteFromPre(Node** head, Node* pre) { if(*head == NULL || pre == NULL) return false; Node *p; if((*head) == pre) { p = *head; *head = p->next; delete p; return true; } if(pre->next == NULL) return false; p = pre->next; pre->next = pre->next->next; delete p; return true; }; void removeDuplicates(Node** head) { if(head == NULL) return; Node *p, *q; for(p = *head; p != NULL; p = p->next) { for(q = p; q->next != NULL; q = q->next) { if(p->data == q->next->data) { deleteFromPre(head, q); // 这里栽跟头了删除操作后无法保证q->next不为空 if(q->next == NULL) break; } } } }; int main() { Node* head = new Node(2); head->next = new Node(4); head->next->next = new Node(4); printNode(head); removeDuplicates(&head); printNode(head); system("pause"); };

发表了文章 2016-04-12

CareerCup-2.4

You have two numbers represented by a linked list, where each node contains a single digit The digits are stored in reverse order, such that the 1’s digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list. EXAMPLE Input: (3 -> 1 -> 5) + (5 -> 9 -> 2) Output: 8 -> 0 -> 8 我采用非递归，按照答案的思路写了递归的方法 #include <iostream> using namespace std; // Creating a Linked List: struct Node { Node(int d):data(d){next = NULL;}; int data; Node* next; }; void printNode(Node* head) { cout<<"Print:"<<endl; while(head != NULL) { cout<<head->data<<endl; head = head->next; } cout<<"End"<<endl; }; Node* plusNode(Node *o1, Node *o2) { if(o1 == NULL || o2 == NULL) return NULL; Node *head = new Node(0); Node *p = head, *q; int temp, flag = 0; while(o1 != NULL || o2 != NULL) { temp = (o1==NULL?0:o1->data) + (o2==NULL?0:o2->data) + flag; flag = temp / 10; q = new Node(temp % 10); p->next = q; p = p->next; if(o1 != NULL) o1 = o1->next; if(o2 != NULL) o2 = o2->next; } p->next = NULL; p = head->next; delete head; return p; }; Node* plusNodeRec(Node *o1, Node *o2, int carry) { if(o1 == NULL && o2 == NULL) return NULL; int result = (o1==NULL?0:o1->data) + (o2==NULL?0:o2->data) + carry; Node* p = new Node(result % 10); Node* next = plusNodeRec(o1==NULL?NULL:o1->next, o2==NULL?NULL:o2->next, result / 10); p->next = next; return p; }; int main() { Node* head1 = new Node(3); head1->next = new Node(1); Node* head2 = new Node(5); head2->next = new Node(9); head2->next->next = new Node(2); // printNode(plusNode(head1, head2)); printNode(plusNodeRec(head1, head2, 0)); system("pause"); };

发表了文章 2016-04-12

CareerCup-3.2

How would you design a stack which, in addition to push and pop, also has a function min which returns the minimum element? Push, pop and min should all operate in O(1) time. 微软实习生一面就遇到了这个问题，当时想到的是笨办法。但是面试官一点点引导，终于想出来这么做。 #include <iostream> using namespace std; typedef int Data; // Creating a Linked List: struct Node { Node(Data d=0):data(d){next = NULL;}; Data data; Node* next; }; class Stack { public: Stack():top(NULL){minNode = NULL;}; void pop() { if(top != NULL) { Node* p = top; top = top->next; delete p; Node* m = minNode; minNode = minNode->next; delete m; } }; Data peek() { if(top != NULL) { return top->data; } else { throw "Empty Stack"; } }; void push(Data data) { Node* d = new Node(data); d->next = top; top = d; if(minNode != NULL && minNode->data < data) data = minNode->data; Node *m = new Node(data); m->next = minNode; minNode = m; }; Data min() { if(minNode == NULL) throw "Empty Stack"; else return minNode->data; }; bool isEmpty(){return top == NULL;}; private: Node* top; Node* minNode; }; int main() { Stack stack; stack.push(3); cout<<stack.min()<<endl; stack.push(2); cout<<stack.min()<<endl; stack.pop(); cout<<stack.min()<<endl; system("pause"); };

发表了文章 2016-04-12

CareerCup-3.5

Implement a MyQueue class which implements a queue using two stacks 开始想到的方法是入队的时候数据进入栈0，出队的时候数据移入栈1再pop。看了答案方法更好。只需要单向挪动。问题在于思维定势，想到队列，总觉得这些数据必须按照顺序在一个栈里。 #include <iostream> using namespace std; typedef int Data; struct Node { Node(Data d):data(d){next = NULL;}; Data data; Node* next; }; class Stack { public: Stack():topNode(NULL){}; void pop() { if(topNode != NULL) { Node* p = topNode; topNode = topNode->next; delete p; } else { throw "Empty Stack"; } }; Data top() { if(topNode != NULL) { return topNode->data; } else { throw "Empty Stack"; } }; void push(Data data) { Node* d = new Node(data); d->next = topNode; topNode = d; }; bool isEmpty(){return topNode == NULL;}; private: Node* topNode; }; class MyQueue { public: void enqueue(Data data) { stack[0].push(data); }; Data dequeue() { if(stack[1].isEmpty()) { while(!stack[0].isEmpty()) { stack[1].push(stack[0].top()); stack[0].pop(); } } if(stack[1].isEmpty()) throw "Empty Queue"; Data data = stack[1].top(); stack[1].pop(); return data; }; bool isEmpty(){return stack[0].isEmpty() && stack[1].isEmpty();}; private: Stack stack[2]; }; int main() { MyQueue queue; for(int i=0; i<5; i++) { queue.enqueue(i*2); queue.enqueue(i*2+1); cout<<queue.dequeue()<<endl; cout<<queue.dequeue()<<endl; } system("pause"); };

发表了文章 2016-04-12

CareerCup-4.1

Implement a function to check if a tree is balanced For the purposes of this question, a balanced tree is defined to be a tree such that no two leaf nodes differ in distance from the root by more than one 答案是两次遍历分别求出最大深度与最小深度，我试着一次遍历求出最大和最小深度 #include <iostream> using namespace std; typedef int Data; struct TreeNode { TreeNode(Data d):data(d){left = right = NULL;}; Data data; TreeNode* left; TreeNode* right; }; class Tree { public: Tree():root(NULL){}; TreeNode* root; void insert(Data data, TreeNode* node = NULL) { if(root == NULL) { root = new TreeNode(data); return; } if(node == NULL) node = root; if(data == node->data) { return; } else if(data < node->data) { if(node->left == NULL) node->left = new TreeNode(data); else insert(data, node->left); } else { if(node->right == NULL) node->right = new TreeNode(data); else insert(data, node->right); } }; void inorderPrint(TreeNode* TreeNode) { if(TreeNode == root) cout<<"Print:"<<endl; if(TreeNode != NULL) { inorderPrint(TreeNode->left); cout<<TreeNode->data<<" "; inorderPrint(TreeNode->right); } if(TreeNode == root) cout<<endl<<"End"<<endl; }; void preorderPrint(TreeNode* TreeNode) { if(TreeNode == root) cout<<"Print:"<<endl; if(TreeNode != NULL) { cout<<TreeNode->data<<" "; preorderPrint(TreeNode->left); preorderPrint(TreeNode->right); } if(TreeNode == root) cout<<endl<<"End"<<endl; }; void postorderPrint(TreeNode* node) { if(node == root) cout<<"Print:"<<endl; if(node != NULL) { postorderPrint(node->left); postorderPrint(node->right); cout<<node->data<<" "; } if(node == root) cout<<endl<<"End"<<endl; }; bool isBalanced() { int min=0 ,max=0; calDepth(root, 0, &min, &max); cout<<"Min: "<<min<<endl<<"Max: "<<max<<endl; if(max - min < 2) return true; else return false; }; void calDepth(TreeNode* node, int depth, int* min, int* max) { if(node == NULL) return; depth++; if(node->left == NULL && node->right == NULL) { if(depth < *min || *min <= 0) *min = depth; if(depth > *max || *max <= 0) *max = depth; } calDepth(node->left, depth, min, max); calDepth(node->right, depth, min, max); }; }; int main() { Tree tree; tree.insert(5); tree.insert(1); tree.insert(7); tree.insert(4); tree.insert(3); cout<<boolalpha<<tree.isBalanced(); system("pause"); };

发表了文章 2016-04-12

CareerCup-4.2

Given a directed graph, design an algorithm to find out whether there is a route between two nodes. 开始想用Dijkstra算法，后来发现根本不需要最短只求连通性。回头还得回忆下Dijkstra，写起来有点生疏了。 #include <iostream> #include <stack> using namespace std; #define Data int class Graph { public: Graph(int size):mSize(size) { data = new Data*[size]; for(int i=0; i<size; i++) { data[i] = new Data[size]; for(int j=0; j<size; j++) { data[i][j] = 0; } } }; void addLink(int src, int dst, int weight=1) { data[src][dst] = weight; }; bool isReached(int src, int dst) { if(src == dst) return true; bool reached[mSize]; for(int i=0; i<mSize; i++) reached[i] = false; stack<Data> stack; stack.push(src); reached[src] = true; while(true) { Data d = stack.top(); cout<<"Reach: "<<d<<endl; if(d == dst) return true; stack.pop(); for(int i=0; i<mSize; i++) { if(data[d][i] > 0 && !reached[i]) stack.push(i); }; if(stack.empty()) break; }; return false; }; private: int mSize; Data** data; }; int main() { Graph graph(4); graph.addLink(0, 3); graph.addLink(3, 2); cout<<boolalpha<<graph.isReached(0, 1)<<endl; system("pause"); }

发表了文章 2016-04-12

CareerCup-5.1

You are given two 32-bit numbers, N and M, and two bit positions, i and j Write a method to set all bits between i and j in N equal to M (e g , M becomes a substring of N located at i and starting at j) EXAMPLE: Input: N = 10000000000, M = 10101, i = 2, j = 6 Output: N = 10001010100 第一个方法是我的思路第二个是参考答案的思路实现的 #include <iostream> #include <bitset> using namespace std; typedef int Data; void setBits(bitset<32>* N, bitset<32>* M, int i, int j) { *N = *N^(*N<<(32-j+i-1)>>(32-j-1))^(*M<<i); }; void setBits2(bitset<32>* N, bitset<32>* M, int i, int j) { bitset<32> t((~0<<(j+1)|((1<<i)-1))); *N = t&*N|(*M<<i); }; int main() { bitset<32> N((string)"10000000000"); bitset<32> M((string)"10101"); int i=2, j=6; setBits2(&N, &M, i, j); cout<<N<<endl; system("pause"); };

发表了文章 2016-04-12

CareerCup-5.2

Given a (decimal - e g 3.72) number that is passed in as a string, print the binary representation. If the number can not be represented accurately in binary, print “ERROR”. 答案没有考虑负数的情况。但是有没有负数从题目无法推断出。 #include <iostream> #include <bitset> using namespace std; typedef int Data; void printDecimal(string s) { int size = s.size(); if(size<1) { cout<<"Error"<<endl; return; } string r; int i=0; if(s[i] == '+' || s[i] == '-') { r += s[i++]; if(size == 1) { cout<<"Error"<<endl; return; } } else { r += '+'; } int index = s.find(".", i); if(index < 1) { cout<<"Error"<<endl; return; } string s1 = s.substr(0, index); string s2 = s.substr(index+1, size); if(s1.size() < 1 || s2.size() < 1) { cout<<"Error"<<endl; return; } int d1 = atoi(s1.c_str()); int d2 = atoi(s2.c_str()); int len = 1; for(int j=s2.size()-1; j>=0; j--) { len *= 10; } do { r += '0' + d1%2; d1 = d1/2; } while(d1 != 0); reverse(r.begin()+1, r.end()); r += '.'; int count = 32; do { d2 *= 2; r += d2>=len?'1':'0'; d2 = d2%len; count--; } while(d2 != 0 && count > 0); if(count == 0) r = "ERROR"; cout<<r<<endl; }; int main() { string s = "3.375"; printDecimal(s); system("pause"); };

发表了文章 2016-04-12

bat实现IP切换

出差调试设备，需要在几个网段之间切换，因此做了个bat实现快速切换。 @echo off set nic="本地连接" set num=151 set /p choice="输入0切换为自动获取，输入1切换到外网，输入2切换到192.168.20.%num%，输入3切换到192.168.0.%num%:" if "%choice%"=="0" goto C0 if "%choice%"=="1" goto C1 if "%choice%"=="2" goto C2 if "%choice%"=="3" goto C3 goto END :C0 echo 开始设置自动获取IP netsh interface ip set address "%nic%" dhcp goto END :C1 echo 切换到外网... netsh interface ip set address "%nic%" static 192.168.24.%num% 255.255.255.0 192.168.24.1 netsh interface ip add dns name="%nic%" addr=8.8.8.8 echo 已经切换到外网 goto END :C2 echo 切换到20网段 netsh interface ip set address "%nic%" static 192.168.20.%num% 255.255.255.0 echo 已经切换到20网段 goto END :C3 echo 切换到0网段 netsh interface ip set address "%nic%" static 192.168.0.%num% 255.255.255.0 echo 已经切换到0网段 goto END :END pause

发表了文章 2016-04-12

CareerCup-5.3

Given an integer, print the next smallest and next largest number that have the sam number of 1 bits in their binary representation. 理解题意费了些时间。明白了之后就没什么难度了。答案没考虑负数的情况和无法找到这样的数字的情况，同时有一定的冗余。 #include <iostream> #include <bitset> using namespace std; #define MAX_INDEX 30 bool getBit(int data, int i) { return (data & (1 << i)) >> i; }; int setBit(int data, int i, bool v) { if(v) { return (data | (1 << i)); } else { return (data & ~(1 << i)); } }; int getNext(int d, bool isLarger) { int index = 0; while(isLarger^getBit(d, index) && index <= MAX_INDEX) { index++; }; while(!isLarger^getBit(d, index) && index <= MAX_INDEX) { index++; } if(index > MAX_INDEX) { cout<<"Can not find"<<endl; return 0; } d = setBit(d, index--, isLarger); d = setBit(d, index--, !isLarger); int i=0; while(index > i) { while(isLarger^getBit(d, index)) { index--; } while(!isLarger^getBit(d, i)) { i++; } if(index > i) { d = setBit(d, index, !isLarger); d = setBit(d, i, isLarger); } } return d; }; int getNextLarger(int d) { if(d >= 0) return getNext(d, true); else return -getNext(-d, false); }; int getNextSmaller(int d) { if(d >= 0) return getNext(d, false); else return -getNext(-d, true); }; int main() { cout<<getNextLarger(4)<<endl<<getNextSmaller(4)<<endl; cout<<getNextLarger(-4)<<endl<<getNextSmaller(-4)<<endl; system("pause"); };

发表了文章 2016-04-12

在Java下使用NTP获取时间

NTP是仍在使用中的最古老的网络协议之一（在1985年前开始）。NTP最初由德拉瓦州大学的Dave Mills设计，他与一群志愿者仍在维护NTP。常用的NTP服务器参考https://www.douban.com/note/171309770/ 身在北邮，当然是使用北邮的NTP服务器最快，但是在外网发现访问不到。推荐上海交通大学的NTP服务，在其他网络仍然能够访问到。两个类，一个用于解析NTP消息，另一个根据配置文件使用NTP协议获取时间。由于是JavaEE项目，文件路径使用的ServletActionContext的路径。如果是一般Java项目写成配置所在路径即可。 package monitor.util; import java.io.File; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.io.IOException; import java.io.InterruptedIOException; import java.net.ConnectException; import java.net.DatagramPacket; import java.net.DatagramSocket; import java.net.InetAddress; import java.net.NoRouteToHostException; import java.net.UnknownHostException; import java.text.DecimalFormat; import java.text.SimpleDateFormat; import java.util.Date; import java.util.Properties; import org.apache.struts2.ServletActionContext; public class NtpUtil { static final String configFile = ServletActionContext.getServletContext() .getRealPath( File.separator + "WEB-INF" + File.separator + "time.txt"); static String ntpServer = null; static Integer retry = null; static Integer port = null; static Integer timeout = null; /** * 读取time.txt中的配置，返回标准时间与本地时间的差值，单位秒 * * @return */ public static Double localClockOffset() { if (ntpServer == null) { Properties props = new Properties(); try { props.load(new FileInputStream(new File(configFile))); } catch (FileNotFoundException e) { // TODO Auto-generated catch block e.printStackTrace(); } catch (IOException e) { // TODO Auto-generated catch block e.printStackTrace(); } ntpServer = props.getProperty("server"); retry = Integer.parseInt(props.getProperty("retry")); port = Integer.parseInt(props.getProperty("port")); timeout = Integer.parseInt(props.getProperty("timeout")); } // get the address and NTP address request // InetAddress ipv4Addr = null; try { ipv4Addr = InetAddress.getByName(ntpServer);// 更多NTP时间服务器参考附注 } catch (UnknownHostException e1) { e1.printStackTrace(); } int serviceStatus = -1; DatagramSocket socket = null; long responseTime = -1; double localClockOffset = 0; try { socket = new DatagramSocket(); socket.setSoTimeout(timeout); // will force the // InterruptedIOException for (int attempts = 0; attempts <= retry && serviceStatus != 1; attempts++) { try { // Send NTP request // byte[] data = new NtpMessage().toByteArray(); DatagramPacket outgoing = new DatagramPacket(data, data.length, ipv4Addr, port); long sentTime = System.currentTimeMillis(); socket.send(outgoing); // Get NTP Response // // byte[] buffer = new byte[512]; DatagramPacket incoming = new DatagramPacket(data, data.length); socket.receive(incoming); responseTime = System.currentTimeMillis() - sentTime; double destinationTimestamp = (System.currentTimeMillis() / 1000.0) + 2208988800.0; // 这里要加2208988800，是因为获得到的时间是格林尼治时间，所以要变成东八区的时间，否则会与与北京时间有8小时的时差 // Validate NTP Response // IOException thrown if packet does not decode as expected. NtpMessage msg = new NtpMessage(incoming.getData()); localClockOffset = ((msg.receiveTimestamp - msg.originateTimestamp) + (msg.transmitTimestamp - destinationTimestamp)) / 2; // System.out // .println("poll: valid NTP request received the local clock offset is " // + localClockOffset // + ", responseTime= " // + responseTime + "ms"); // System.out.println("poll: NTP message : " + // msg.toString()); serviceStatus = 1; } catch (InterruptedIOException ex) { // Ignore, no response received. } } } catch (NoRouteToHostException e) { System.out.println("No route to host exception for address: " + ipv4Addr); } catch (ConnectException e) { // Connection refused. Continue to retry. e.fillInStackTrace(); System.out.println("Connection exception for address: " + ipv4Addr); } catch (IOException ex) { ex.fillInStackTrace(); System.out .println("IOException while polling address: " + ipv4Addr); } finally { if (socket != null) socket.close(); } // Store response time if available // // if (serviceStatus == 1) { // System.out.println("responsetime==" + responseTime); // } return localClockOffset; } } class NtpMessage { /** */ /** * This is a two-bit code warning of an impending leap second to be * inserted/deleted in the last minute of the current day. It''s values may * be as follows: * * Value Meaning ----- ------- 0 no warning 1 last minute has 61 seconds 2 * last minute has 59 seconds) 3 alarm condition (clock not synchronized) */ public byte leapIndicator = 0; /** */ /** * This value indicates the NTP/SNTP version number. The version number is 3 * for Version 3 (IPv4 only) and 4 for Version 4 (IPv4, IPv6 and OSI). If * necessary to distinguish between IPv4, IPv6 and OSI, the encapsulating * context must be inspected. */ public byte version = 3; /** */ /** * This value indicates the mode, with values defined as follows: * * Mode Meaning ---- ------- 0 reserved 1 symmetric active 2 symmetric * passive 3 client 4 server 5 broadcast 6 reserved for NTP control message * 7 reserved for private use * * In unicast and anycast modes, the client sets this field to 3 (client) in * the request and the server sets it to 4 (server) in the reply. In * multicast mode, the server sets this field to 5 (broadcast). */ public byte mode = 0; /** */ /** * This value indicates the stratum level of the local clock, with values * defined as follows: * * Stratum Meaning ---------------------------------------------- 0 * unspecified or unavailable 1 primary reference (e.g., radio clock) 2-15 * secondary reference (via NTP or SNTP) 16-255 reserved */ public short stratum = 0; /** */ /** * This value indicates the maximum interval between successive messages, in * seconds to the nearest power of two. The values that can appear in this * field presently range from 4 (16 s) to 14 (16284 s); however, most * applications use only the sub-range 6 (64 s) to 10 (1024 s). */ public byte pollInterval = 0; /** */ /** * This value indicates the precision of the local clock, in seconds to the * nearest power of two. The values that normally appear in this field range * from -6 for mains-frequency clocks to -20 for microsecond clocks found in * some workstations. */ public byte precision = 0; /** */ /** * This value indicates the total roundtrip delay to the primary reference * source, in seconds. Note that this variable can take on both positive and * negative values, depending on the relative time and frequency offsets. * The values that normally appear in this field range from negative values * of a few milliseconds to positive values of several hundred milliseconds. */ public double rootDelay = 0; /** */ /** * This value indicates the nominal error relative to the primary reference * source, in seconds. The values that normally appear in this field range * from 0 to several hundred milliseconds. */ public double rootDispersion = 0; /** */ /** * This is a 4-byte array identifying the particular reference source. In * the case of NTP Version 3 or Version 4 stratum-0 (unspecified) or * stratum-1 (primary) servers, this is a four-character ASCII string, left * justified and zero padded to 32 bits. In NTP Version 3 secondary servers, * this is the 32-bit IPv4 address of the reference source. In NTP Version 4 * secondary servers, this is the low order 32 bits of the latest transmit * timestamp of the reference source. NTP primary (stratum 1) servers should * set this field to a code identifying the external reference source * according to the following list. If the external reference is one of * those listed, the associated code should be used. Codes for sources not * listed can be contrived as appropriate. * * Code External Reference Source ---- ------------------------- LOCL * uncalibrated local clock used as a primary reference for a subnet without * external means of synchronization PPS atomic clock or other * pulse-per-second source individually calibrated to national standards * ACTS NIST dialup modem service USNO USNO modem service PTB PTB (Germany) * modem service TDF Allouis (France) Radio 164 kHz DCF Mainflingen * (Germany) Radio 77.5 kHz MSF Rugby (UK) Radio 60 kHz WWV Ft. Collins (US) * Radio 2.5, 5, 10, 15, 20 MHz WWVB Boulder (US) Radio 60 kHz WWVH Kaui * Hawaii (US) Radio 2.5, 5, 10, 15 MHz CHU Ottawa (Canada) Radio 3330, * 7335, 14670 kHz LORC LORAN-C radionavigation system OMEG OMEGA * radionavigation system GPS Global Positioning Service GOES Geostationary * Orbit Environment Satellite */ public byte[] referenceIdentifier = { 0, 0, 0, 0 }; /** */ /** * This is the time at which the local clock was last set or corrected, in * seconds since 00:00 1-Jan-1900. */ public double referenceTimestamp = 0; /** */ /** * This is the time at which the request departed the client for the server, * in seconds since 00:00 1-Jan-1900. */ public double originateTimestamp = 0; /** */ /** * This is the time at which the request arrived at the server, in seconds * since 00:00 1-Jan-1900. */ public double receiveTimestamp = 0; /** */ /** * This is the time at which the reply departed the server for the client, * in seconds since 00:00 1-Jan-1900. */ public double transmitTimestamp = 0; /** */ /** * Constructs a new NtpMessage from an array of bytes. */ public NtpMessage(byte[] array) { // See the packet format diagram in RFC 2030 for details leapIndicator = (byte) ((array[0] >> 6) & 0x3); version = (byte) ((array[0] >> 3) & 0x7); mode = (byte) (array[0] & 0x7); stratum = unsignedByteToShort(array[1]); pollInterval = array[2]; precision = array[3]; rootDelay = (array[4] * 256.0) + unsignedByteToShort(array[5]) + (unsignedByteToShort(array[6]) / 256.0) + (unsignedByteToShort(array[7]) / 65536.0); rootDispersion = (unsignedByteToShort(array[8]) * 256.0) + unsignedByteToShort(array[9]) + (unsignedByteToShort(array[10]) / 256.0) + (unsignedByteToShort(array[11]) / 65536.0); referenceIdentifier[0] = array[12]; referenceIdentifier[1] = array[13]; referenceIdentifier[2] = array[14]; referenceIdentifier[3] = array[15]; referenceTimestamp = decodeTimestamp(array, 16); originateTimestamp = decodeTimestamp(array, 24); receiveTimestamp = decodeTimestamp(array, 32); transmitTimestamp = decodeTimestamp(array, 40); } /** */ /** * Constructs a new NtpMessage */ public NtpMessage(byte leapIndicator, byte version, byte mode, short stratum, byte pollInterval, byte precision, double rootDelay, double rootDispersion, byte[] referenceIdentifier, double referenceTimestamp, double originateTimestamp, double receiveTimestamp, double transmitTimestamp) { // ToDo: Validity checking this.leapIndicator = leapIndicator; this.version = version; this.mode = mode; this.stratum = stratum; this.pollInterval = pollInterval; this.precision = precision; this.rootDelay = rootDelay; this.rootDispersion = rootDispersion; this.referenceIdentifier = referenceIdentifier; this.referenceTimestamp = referenceTimestamp; this.originateTimestamp = originateTimestamp; this.receiveTimestamp = receiveTimestamp; this.transmitTimestamp = transmitTimestamp; } /** */ /** * Constructs a new NtpMessage in client -> server mode, and sets the * transmit timestamp to the current time. */ public NtpMessage() { // Note that all the other member variables are already set with // appropriate default values. this.mode = 3; this.transmitTimestamp = (System.currentTimeMillis() / 1000.0) + 2208988800.0; } /** */ /** * This method constructs the data bytes of a raw NTP packet. */ public byte[] toByteArray() { // All bytes are automatically set to 0 byte[] p = new byte[48]; p[0] = (byte) (leapIndicator << 6 | version << 3 | mode); p[1] = (byte) stratum; p[2] = (byte) pollInterval; p[3] = (byte) precision; // root delay is a signed 16.16-bit FP, in Java an int is 32-bits int l = (int) (rootDelay * 65536.0); p[4] = (byte) ((l >> 24) & 0xFF); p[5] = (byte) ((l >> 16) & 0xFF); p[6] = (byte) ((l >> 8) & 0xFF); p[7] = (byte) (l & 0xFF); // root dispersion is an unsigned 16.16-bit FP, in Java there are no // unsigned primitive types, so we use a long which is 64-bits long ul = (long) (rootDispersion * 65536.0); p[8] = (byte) ((ul >> 24) & 0xFF); p[9] = (byte) ((ul >> 16) & 0xFF); p[10] = (byte) ((ul >> 8) & 0xFF); p[11] = (byte) (ul & 0xFF); p[12] = referenceIdentifier[0]; p[13] = referenceIdentifier[1]; p[14] = referenceIdentifier[2]; p[15] = referenceIdentifier[3]; encodeTimestamp(p, 16, referenceTimestamp); encodeTimestamp(p, 24, originateTimestamp); encodeTimestamp(p, 32, receiveTimestamp); encodeTimestamp(p, 40, transmitTimestamp); return p; } /** */ /** * Returns a string representation of a NtpMessage */ public String toString() { String precisionStr = new DecimalFormat("0.#E0").format(Math.pow(2, precision)); return "Leap indicator: " + leapIndicator + " " + "Version: " + version + " " + "Mode: " + mode + " " + "Stratum: " + stratum + " " + "Poll: " + pollInterval + " " + "Precision: " + precision + " (" + precisionStr + " seconds) " + "Root delay: " + new DecimalFormat("0.00").format(rootDelay * 1000) + " ms " + "Root dispersion: " + new DecimalFormat("0.00").format(rootDispersion * 1000) + " ms " + "Reference identifier: " + referenceIdentifierToString(referenceIdentifier, stratum, version) + " " + "Reference timestamp: " + timestampToString(referenceTimestamp) + " " + "Originate timestamp: " + timestampToString(originateTimestamp) + " " + "Receive timestamp: " + timestampToString(receiveTimestamp) + " " + "Transmit timestamp: " + timestampToString(transmitTimestamp); } /** */ /** * Converts an unsigned byte to a short. By default, Java assumes that a * byte is signed. */ public static short unsignedByteToShort(byte b) { if ((b & 0x80) == 0x80) return (short) (128 + (b & 0x7f)); else return (short) b; } /** */ /** * Will read 8 bytes of a message beginning at <code>pointer</code> and * return it as a double, according to the NTP 64-bit timestamp format. */ public static double decodeTimestamp(byte[] array, int pointer) { double r = 0.0; for (int i = 0; i < 8; i++) { r += unsignedByteToShort(array[pointer + i]) * Math.pow(2, (3 - i) * 8); } return r; } /** */ /** * Encodes a timestamp in the specified position in the message */ public static void encodeTimestamp(byte[] array, int pointer, double timestamp) { // Converts a double into a 64-bit fixed point for (int i = 0; i < 8; i++) { // 2^24, 2^16, 2^8, .. 2^-32 double base = Math.pow(2, (3 - i) * 8); // Capture byte value array[pointer + i] = (byte) (timestamp / base); // Subtract captured value from remaining total timestamp = timestamp - (double) (unsignedByteToShort(array[pointer + i]) * base); } // From RFC 2030: It is advisable to fill the non-significant // low order bits of the timestamp with a random, unbiased // bitstring, both to avoid systematic roundoff errors and as // a means of loop detection and replay detection. array[7] = (byte) (Math.random() * 255.0); } /** */ /** * Returns a timestamp (number of seconds since 00:00 1-Jan-1900) as a * formatted date/time string. */ public static String timestampToString(double timestamp) { if (timestamp == 0) return "0"; // timestamp is relative to 1900, utc is used by Java and is relative // to 1970 double utc = timestamp - (2208988800.0); // milliseconds long ms = (long) (utc * 1000.0); // date/time String date = new SimpleDateFormat("dd-MMM-yyyy HH:mm:ss") .format(new Date(ms)); // fraction double fraction = timestamp - ((long) timestamp); String fractionSting = new DecimalFormat(".000000").format(fraction); return date + fractionSting; } /** */ /** * Returns a string representation of a reference identifier according to * the rules set out in RFC 2030. */ public static String referenceIdentifierToString(byte[] ref, short stratum, byte version) { // From the RFC 2030: // In the case of NTP Version 3 or Version 4 stratum-0 (unspecified) // or stratum-1 (primary) servers, this is a four-character ASCII // string, left justified and zero padded to 32 bits. if (stratum == 0 || stratum == 1) { return new String(ref); } // In NTP Version 3 secondary servers, this is the 32-bit IPv4 // address of the reference source. else if (version == 3) { return unsignedByteToShort(ref[0]) + "." + unsignedByteToShort(ref[1]) + "." + unsignedByteToShort(ref[2]) + "." + unsignedByteToShort(ref[3]); } // In NTP Version 4 secondary servers, this is the low order 32 bits // of the latest transmit timestamp of the reference source. else if (version == 4) { return "" + ((unsignedByteToShort(ref[0]) / 256.0) + (unsignedByteToShort(ref[1]) / 65536.0) + (unsignedByteToShort(ref[2]) / 16777216.0) + (unsignedByteToShort(ref[3]) / 4294967296.0)); } return ""; } } 配置文件很简单： server = ntp.sjtu.edu.cn retry = 2 port = 123 timeout = 3000

发表了文章 2016-04-12

阿里实习面试总结

这次妥妥的倒在了一面上。还是基础不够扎实。 1. 重载与多态区别重载（overload）一般是用于在一个类内实现若干重载的方法，这些方法的名称相同而参数形式不同。重载的规则： a、在使用重载时只能通过相同的方法名、不同的参数形式实现。不同的参数类型可以是不同的参数类型，不同的参数个数，不同的参数顺序（参数类型必须不一样）； b、不能通过访问权限、返回类型、抛出的异常进行重载； c、方法的异常类型和数目不会对重载造成影响；重写/覆盖（override），子类在继承父类时，重写父类中的方法。重写的规则： a、重写方法的参数列表必须完全与被重写的方法的相同,否则不能称其为重写而是重载. b、重写方法的访问修饰符一定要大于被重写方法的访问修饰符（public>protected>default>private）。 c、重写的方法的返回值必须和被重写的方法的返回一致； d、重写的方法所抛出的异常必须和被重写方法的所抛出的异常一致，或者是其子类； e、被重写的方法不能为private，否则在其子类中只是新定义了一个方法，并没有对其进行重写。 f、静态方法不能被重写为非静态的方法（会编译出错）。多态为了避免在父类里大量重载引起代码臃肿且难于维护。通过重写实现。 public class Shape { public static void main(String[] args) { Triangle tri = new Triangle(); System.out.println("Triangle is a type of shape? " + tri.isShape());// 继承 Shape shape = new Triangle(); System.out.println("My shape has " + shape.getSides() + " sides."); // 多态 Rectangle Rec = new Rectangle(); Shape shape2 = Rec; System.out.println("My shape has " + shape2.getSides(Rec) + " sides."); // 重载 } public boolean isShape() { return true; } public int getSides() { return 0; } public int getSides(Triangle tri) { // 重载 return 3; } public int getSides(Rectangle rec) { // 重载 return 4; } } class Triangle extends Shape { public int getSides() { // 重写,实现多态 return 3; } } class Rectangle extends Shape { public int getSides() { // 重写,实现多态 return 4; } } 2. read()执行时操作系统完成的工作 3. 进程有哪些状态基本状态：运行-就绪-阻塞（也称为等待或睡眠）。实际的系统中经常引入新建态和终止态。有的系统引入了挂起态。 Java线程状态共6个：NEW、RUNNABLE、BLOCKED、WAITING、TIMED_WAITING、TERMINATED 4. url中参数去掉一部分的算法当时想到了切分字符串和正则替换，但是写的正则有问题。面试结束和面试官交流，他提示扫描一遍就可以。 package monitor; import java.util.Arrays; class CheckHelper { private char temp[] = new char[64]; private String params[]; private boolean check[]; private int tag = 0; public CheckHelper(String params[]) { this.params = params; check = new boolean[params.length]; } public void initCheck() { for (int i = 0; i < check.length; i++) check[i] = true; tag = 0; } public void doCheck(char c) { for (int i = 0; i < params.length; i++) { String param = params[i]; temp[tag] = c; if (tag >= param.length() || param.charAt(tag) != c) { check[i] = false; } } tag++; } public String getResult() { for (int i = 0; i < params.length; i++) { String param = params[i]; if (check[i] && param.length() == tag) { initCheck(); return null; } } String ret = new String(Arrays.copyOf(temp, tag)); initCheck(); return ret; } } public class Test { public static String removeParam(String url, String[] params) { CheckHelper ch = new CheckHelper(params); ch.initCheck(); StringBuilder sb = new StringBuilder(); boolean start = false; boolean rest = false; boolean copy = false; for (int i = 0; i < url.length(); i++) { char c = url.charAt(i); if (!start) { sb.append(c); if (c == '?') start = true; } else if (c == '=') { rest = true; String ret = ch.getResult(); if (ret != null) { if (sb.charAt(sb.length() - 1) != '?') sb.append('&'); sb.append(ret); sb.append('='); copy = true; } else { copy = false; } } else if (!rest) { ch.doCheck(c); } else if (c != '&') { if (copy) sb.append(c); } else { ch.initCheck(); rest = false; copy = false; } } return sb.toString(); } public static void main(String[] args) throws Exception { String url = "http://s.taobao.com/search?spm=a230r.1.0.100.S98nmj&" + "q=Apple%2F%C6%BB%B9%FB+MacBook+Pro+MD101CH%2FA&v=product&p=" + "detail&pspuid=202666380&cat=1101&from_pos=55_1101.xlcombo_1_2_202666380"; String[] params = { "spm", "pspuid", "cat" }; System.out.println(removeParam(url, params)); } } PS. 2014年的今天已经是阿里巴巴的一员了。觉得应该对自己的Java有信心并提出让Java工程师来面试我。

发表了文章 2016-04-12

Java SecurityManager

Java的SecurityManager用于完成对一些本地方法的权限管理。其他安全特性可以保证程序Java程序安全运行，但是当调用本地方法时，Java安全沙箱完全不起作用，因此需要在调用本地方法前确认它是可信任的。启动SecurityManager开关：默认情况下，JVM是不启动安全检查的。打开的方式有两种：一种是在启动运行中追加JVM参数-Djava.security.manager，另一种方式是在程序中直接设置：System.setSecurityManager(new SecurityManager())。第二种方法可以设置为系统的SecurityManager或者自定义类扩展该类。这两种方式是等价的，但是不能同时使用。 Java安全管理器控制权限的方法：使用系统的SecurityManager 编写.policy文件；扩展SecurityManager修改其check方法，使用上述第二种方法启动SecurityManager。使用系统的SecurityManager需要修改policy文件：修改jvm自带的java.policy文件，或者指定为另一个文件。java.policy文件位于%JAVA_HOME%/ jre/lib/security/。指定为其他方法启动时加参数-Djava.security.policy=c:/all.policy。另外在调试过程中我使用了命令行的方式编译带包声明的Java，与不带包声明的方式有点差别，命令如下： set classpath=. javac -d ./ Test.java #第二个参数 java monitor.Test SecurityManager中做权限检查实际上调用的是AccessController来完成检查。检查的过程是从栈顶开始，一直检查到栈底部，遇到某个类的保护域没有权限则抛出异常。这样的算法防止了任何代码执行任何不信任的代码。有的时候靠近栈顶的代码希望之星一段代码，而这段代码在较下层不允许执行，例如一个不可靠的applet请求Java API加载字体，因此需要打开这个字体文件的权限。这种情况下AccessController的doPrivileged方法可以解决问题。检查权限的过程中，检查到doPrivileged方法后，检查到调用其的类后不再继续检查。

发表了文章 2016-04-12

Java ClassLoader详解

深入Java虚拟机，ClassLoader是其中重要的一个环节。看书+查资料+动手，整理出如下要点： Class loader using following four steps: a, Bootstrap ClassLoader/启动类加载器主要负责jdkhome/lib目录下的核心 api 或 -Xbootclasspath 选项指定的jar包装入工作. b, Extension ClassLoader/扩展类加载器主要负责jdkhome/lib/ext目录下的jar包或 -Djava.ext.dirs 指定目录下的jar包装入工作 c, System ClassLoader/系统类加载器主要负责java -classpath/-Djava.class.path所指的目录下的类与jar包装入工作. b, User Custom ClassLoader/用户自定义类加载器(java.lang.ClassLoader的子类)在程序运行期间, 通过java.lang.ClassLoader的子类动态加载class文件, 体现java动态实时类装入特性. 加载顺序是：自底向上检查类是否已经装在，有则返回，否则自顶向下尝试加载类。类装入的方式有两种 —— 显式或隐式，两者之间有些细微差异。显式类装入发生在使用以下方法调用装入的类的时候： cl.loadClass()（cl 是 java.lang.ClassLoader 的实例） Class.forName()（启动的类装入器是当前类定义的类装入器）隐式类装入发生在由于引用、实例化或继承导致装入类的时候（不是通过显式方法调用）。在每种情况下，装入都是在幕后启动的，JVM 会解析必要的引用并装入类。与显式类装入一样，如果类已经装入了，那么只是返回一个引用；否则，装入器会通过委托模型装入类。项目源码与jar中存在同包名同类名的类，运行时加载源码中该类原因：他们都属于User classes，由系统类加载器加载。加载的时候搜索路径顺序： a. 缺省值：调用java或javaw的当前路径，是项目class所在目录 b. 环境变量classpath设置的路径 c. 执行Java命令行-classpath或-cp的值。如果指定了这两个命令行参数之一,它的值会覆盖环境变量CLASSPATH的值。 d. -jar 选项:如果通过java -jar 来运行一个可执行的jar包,这当前jar包会覆盖上面所有的值.换句话说,-jar 后面所跟的jar包的优先级别最高,如果指定了-jar选项,所有环境变量和命令行制定的搜索路径都将被忽略.JVM APPClassloader将只会以jar包为搜索范围. 有关可执行jar有许多相关的安全方面的描述,可以参考http://java.sun.com/docs/books/tutorial/jar/ 来全面了解. 这也是为什么应用程序打包成可执行的jar包后,不管你怎么设置classpath都不能引用到第三方jar包的东西了. 另附ClassLoader.loadClass与Class.forName的区别，主要在于是否初始化： public class Test { public static void main(String[] argv) throws ClassNotFoundException, InstantiationException, IllegalAccessException { // Class classT = ClassLoader.getSystemClassLoader().loadClass("Ti"); //not print static // Class classT = Class.forName("Ti"); //print static // Class classT = Class.forName("Ti", true, ClassLoader.getSystemClassLoader()); //print static Class classT = Class.forName("Ti", false, ClassLoader.getSystemClassLoader()); // not print static } } class Ti { static { System.out.println("static"); } }

johnwong_个人页

个人介绍

擅长的技术

Android NDK学习记录

SFS&Android——SFS客户端全部事件详细

FineReport简明教程

设计模式[1]-Memento

设计模式[2]-Chain of Responsibility

[算法]-Longest Increasing Subsequence

设计模式[3]-Observer

2013编程之美全国挑战赛第一场-传话游戏

2013编程之美全国挑战赛第一场-树上的三角形

设计模式[4]-Command

设计模式[5]-State

2013编程之美全国挑战赛第二场-集会

设计模式[6]-Interpreter

设计模式[7]-Strategy

设计模式[8]-Iterator

设计模式[9]-Template Method

设计模式[10]-Mediator

设计模式[11]-Visitor

设计模式[12]-Adapter

设计模式[13]-Bridge

设计模式[14]-Composite

设计模式[15]-Decorator

设计模式[16]-Facede

设计模式[17]-Flyweight

设计模式[18]-Proxy

设计模式[19]-Abstract Factory

设计模式[20]-Builder

设计模式[21]-Factory Method

设计模式[22]-Prototype

设计模式[23]-Singleton

CareerCup-BASE CASE AND BUILD

CareerCup-PATTERN MATCHING

Java内存泄露

CareerCup-1.6

C++ STL使用帮助

jQuery UI在Server 2008 IE8下DatePicker问题修复

CareerCup-2.1

CareerCup-2.4

CareerCup-3.2

CareerCup-3.5

CareerCup-4.1

CareerCup-4.2

CareerCup-5.1

CareerCup-5.2

bat实现IP切换

CareerCup-5.3

在Java下使用NTP获取时间

阿里实习面试总结

Java SecurityManager

Java ClassLoader详解

Android NDK学习记录

SFS&Android——SFS客户端全部事件详细

FineReport简明教程

设计模式[1]-Memento

设计模式[2]-Chain of Responsibility

[算法]-Longest Increasing Subsequence

设计模式[3]-Observer

2013编程之美全国挑战赛第一场-传话游戏

2013编程之美全国挑战赛第一场-树上的三角形

设计模式[4]-Command

设计模式[5]-State

2013编程之美全国挑战赛第二场-集会

设计模式[6]-Interpreter

设计模式[7]-Strategy

设计模式[8]-Iterator

设计模式[9]-Template Method

设计模式[10]-Mediator

设计模式[11]-Visitor

设计模式[12]-Adapter

设计模式[13]-Bridge