LeetCode-Reverse Integer

发表于 2014-06-25

Problem:
Reverse digits of an integer.

Example1: x = 123, return 321
Example2: x = -123, return -321

public class Solution {
    public int reverse(int x) {
        int ret=0,temp=x;
		
		do{
			ret=ret*10+temp%10;
			temp/=10;
		}while(temp!=0);
		
		return ret;
    }
}

本作品采用[知识共享署名-非商业性使用-相同方式共享 2.5]中国大陆许可协议进行许可，我的博客欢迎复制共享，但在同时，希望保留我的署名权kubiCode，并且，不得用于商业用途。如您有任何疑问或者授权方面的协商，请给我留言。

LeetCode-Reverse Words in a String

By Kubi Code

发表于 2014-06-24

Problem:
Given an input string, reverse the string word by word.

For example,
Given s = “the sky is blue”,
return “blue is sky the”.

For C programmers: Try to solve it in-place in O(1) space.

public class Solution {
    public String reverseWords(String s) {
        String[] strs=s.trim().split("\\s+");
        StringBuilder sb=new StringBuilder();
        
        for(int i=strs.length-1;i>=0;i--)
        {
            sb.append(strs[i]);
            
            if(i!=0)
            {
                sb.append(" ");
            }
        }
        
        return sb.toString();
    }
}

thr runtime is 384ms

本来想说用二次字符串翻转来做的，比如第一次先以空格分隔翻转：eht yks si eulb，然后再一次进行全部翻转之后即可得到blue is sky the，但是代码提交到LeetCode之后他的Test Case中有去空格的Demo，老是Wrong，想想大致能用二次翻转完成就好，就没有继续调试了0-_-

public String reverseWords2(String s) {
	byte[] bs=s.getBytes();
    int length=bs.length;
    int start=0,end=0;
    
    for(int i=0;i<=length;i++)
    {
    	if(i==length || bs[i]==32)
    	{
    		end=i-1;
    		
    		reverse(bs,start,end);
        	start=i+1;
    	}
    }
    
    reverse(bs,0,length-1);
    
    return new String(bs);
}

private void reverse(byte[] bs,int i,int j)
{
	for(;i<j;i++,j--)
	{
		byte b=bs[i];
		bs[i]=bs[j];
		bs[j]=b;
	}
}

JUnit Test Code

List<TestExample> testExampleList=new ArrayList<TestExample>();
	
@Before
public void before()
{
	this.testExampleList.add(new TestExample("   a   b ","b a"));//这个会失败 就没再测了
	this.testExampleList.add(new TestExample("LeetCode","LeetCode"));
	this.testExampleList.add(new TestExample("Hello World","World Hello"));
	this.testExampleList.add(new TestExample("the sky is blue","blue is sky the"));
	
}

@Test
public void test()
{
	ReverseWordsinaString reverse=new ReverseWordsinaString();
	
	for(TestExample example:this.testExampleList)
	{
		Assert.assertEquals(reverse.reverseWords2(example.sourceStr),example.reverseStr);
	}
}

@After
public void after()
{
	this.testExampleList.clear();
}

static class TestExample{
	public String sourceStr;
	public String reverseStr;
	
	public TestExample(String sourceStr,String reverseStr)
	{
		this.sourceStr=sourceStr;
		this.reverseStr=reverseStr;
	}
}

本作品采用[知识共享署名-非商业性使用-相同方式共享 2.5]中国大陆许可协议进行许可，我的博客欢迎复制共享，但在同时，希望保留我的署名权kubiCode，并且，不得用于商业用途。如您有任何疑问或者授权方面的协商，请给我留言。

LeetCode-3Sum

By Kubi Code

发表于 2014-03-26

leetcode地址：https://leetcode.com/problems/3sum/

Problem:
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:

Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
The solution set must not contain duplicate triplets.
For example, given array S = {-1 0 1 2 -1 -4},

A solution set is:
(-1, 0, 1)
(-1, -1, 2)

解法1

最简单的暴力求解,O(N^3)，利用HashMap进行去重，加了一个剪枝方法，竟然也AC了，runtime：936ms

public List<List<Integer>> threeSum(int[] num) {
	List<List<Integer>> ret=new ArrayList<List<Integer>>();
	
	HashMap<String,ThreeNum> coupleMap=new HashMap<String,ThreeNum>();
    int a,b,c,temp;
	boolean isCut=false;
    
    //sort the num list as asc
    for(int i=0;i<num.length;i++)
    {
        for(int j=i+1;j<num.length;j++)
        {
            if(num[i]>num[j])
            {
                temp=num[i];
                num[i]=num[j];
                num[j]=temp;
            }
        }
    }
    
    
    //a<=c<=b
    for(int i=0;i<num.length;i++)
    {
    	a=num[i];
        for(int j=num.length-1;j>i;j--)
        {
        	b=num[j];
        	isCut=false;
            for(int k=j-1;k>i;k--)
            {
            	c=num[k];
            	if(a+b+c==0)
            	{
            		ThreeNum threeNum=new ThreeNum(a,c,b);
            		if(!coupleMap.containsKey(threeNum.toString()))//check the couple whether is exist
            		{
            			coupleMap.put(threeNum.toString(), threeNum);
            			break;
            		}
            	}else if(a+b+c<0){
            		//we will cut it
            		isCut=true;
            		break;
            	}
            }
        }
    }
    
    for(String threeNumString:coupleMap.keySet())
    {
    	ArrayList<Integer> threeNumList=new ArrayList<Integer>();
    	threeNumList.add(coupleMap.get(threeNumString).a);
    	threeNumList.add(coupleMap.get(threeNumString).b);
    	threeNumList.add(coupleMap.get(threeNumString).c);
    	ret.add(threeNumList);
    }
    
    return ret;
}

class ThreeNum{
	public int a,b,c;
	
	public ThreeNum(int a,int b,int c)
	{
		this.a=a;
		this.b=b;
		this.c=c;
	}
	
	public String toString()
	{
		return a+","+b+","+c;
	}
}

解法2

按照一维数组中2求两个数字之和的思路：复杂度为O(N^2),runtime:322ms

public List<List<Integer>> threeSum(int[] num) {
	List<List<Integer>> ret=new ArrayList<List<Integer>>();
	
	int p,q,temp,sum;
	for(int i=0;i<num.length;i++)
    {
        for(int j=i+1;j<num.length;j++)
        {
            if(num[i]>num[j])
            {
                temp=num[i];
                num[i]=num[j];
                num[j]=temp;
            }
        }
    }
	
	for(int k=0;k<num.length-1;k++)
	{
		if(k>0 && num[k-1]==num[k])
			continue;//去重
		p=k+1;
		q=num.length-1;//初始化两端的指针
		
		while(p<q)
		{
			sum=num[k]+num[p]+num[q];
			if(p>k+1 && num[p]==num[p-1])
			{
				p++;
				continue;
			}
			
			if(q<num.length-1 && num[q]==num[q+1])
			{
				q--;
				continue;
			}
			
			
			if(sum<0)
			{
				//p指针向右
				p++;
			} else if(sum==0)
			{//求得解
				ret.add(Arrays.asList(num[k],num[p],num[q]));
				p++;
				q--;
			}else{
				q--;//q指针向左
			}
			
			
		}
	}
	
	
	
	return ret;
}

测试用例

/**
 * test data,except data
 */
List<TestExample> testExampleList=new ArrayList<TestExample>();

@Before
public void before()
{
	this.testExampleList.add(new TestExample(new int[]{-1,0,1,2,-1,-4},Arrays.asList("-1,0,1","-1,-1,2")));
	this.testExampleList.add(new TestExample(new int[]{0,0,0,0},Arrays.asList("0,0,0")));
	this.testExampleList.add(new TestExample(new int[]{-1,1,-1,1},new ArrayList<String>()));
	this.testExampleList.add(new TestExample(new int[]{-2,0,1,1,2},Arrays.asList("-2,0,2","-2,1,1")));
}

@Test
public void testThreeSum1()
{
	ThreeSum threeSum=new ThreeSum();

	for(TestExample example:this.testExampleList)
	{
		List<List<Integer>> ret=threeSum.threeSum(example.testPara);
		int count=0;
		if(ret.size()==example.testExcept.size())
		{
			for(List list:ret)
			{
				if(example.testExcept.contains(join(list,",")))
				{
					count++;
				}else{
					break;
				}
			}
		}
		Assert.assertEquals(count, example.testExcept.size());
		
	}
	
}

@After
public void after()
{
	this.testExampleList.clear();
}

/**
 * 测试样例数据
 * @author Administrator
 *
 */
static class TestExample{
	public int[] testPara;
	public List<String> testExcept;
	
	public TestExample(int[] testPara,List<String> testExcept)
	{
		this.testPara=testPara;
		this.testExcept=testExcept;
	}
}

/**
 * join 操作
 * @param strList
 * @param split
 * @return
 */
public static String join(List<Integer> strList,String split){
    StringBuffer sb=new StringBuffer();
    for(int i=0;i<strList.size();i++){
         if(i==(strList.size()-1)){
             sb.append(strList.get(i));
         }else{
             sb.append(strList.get(i)).append(split);
         }
    }
    
    return new String(sb);
}

参考

http://blog.csdn.net/zhouworld16/article/details/16917071

本作品采用[知识共享署名-非商业性使用-相同方式共享 2.5]中国大陆许可协议进行许可，我的博客欢迎复制共享，但在同时，希望保留我的署名权kubiCode，并且，不得用于商业用途。如您有任何疑问或者授权方面的协商，请给我留言。

读《这就是搜索引擎：核心技术详解》有感总结

By Kubi Code

发表于 2014-01-17

搜索引擎的使用对于我们来说不陌生，对于一个正常的搜索流程，比如用户输入查询“搜索引擎技术”，搜索引擎需要分别将存储的磁盘上的两个单词的倒排序索引读入内存，之后进行解压缩，然后求两个单词对应倒排序列表的搅基，找到所有包含两个单词的文档集合，根据排序算法来对每个文档的相关性进行打分，按照相关度输入相关最高的搜索结果。

但是对于这系列步骤中海量文档数据的来源，存储，查找的技术又是如何的呢？下面是我最近看了《这就是搜索引擎：核心技术详解》这书的大致总结：

基于.Net 写我自己的Ajax后台框架AjaxFramework

By Kubi Code

发表于 2013-05-09

为什么要写自己的Ajax后台框架

现在Ajax在web应用方面已经用的稀巴烂了，如果你做一个网站没有用到ajax都不好意思拿出手，虽然面对ajax的潮流下，在.net开放方向，微软已经做了很多工作了，比如推出了ajax的服务器端控件，但是他不够灵活，用的人多吗？不多！

在.Net环境下与ajax配合的几种情况（主要是针对webform，因为.net mvc你只要写action就可以将方法给发布出来，实现ajax的调用）：

用ajax访问aspx页面：直接在page_load中输出html代码并且End掉多余标签的输出，但是他还要走生命周期，一个好好的aspx页面只用这个功能怪怪的，当然还可以直接在aspx.cs上面的方法上加上[webMethod]特性来标记ajax访问，但是必须该方法为静态，用起来也不是很爽。
用ajax访问ashx一般处理程序：这个是在.net的ajax开发中一种常见明确推荐的方式，他输出页面少，不冗余代码，调用灵活，但是他通常一个ashx页面只提供一个功能，但是市面上有可以通过switch方法的参数或者用委托或者反射的方法来实现一个ashx页面提供多个ajax访问的功能，但是没发现这样也挺乱的吗，我之前一直用这个，慢慢的慢慢的开始讨厌这种写好写法!
用ajax直接调用webservice服务：这样的好处是在一个普通的webserive类中可以使用多个对外ajax访问点的发布，用起来很灵活，但是你一般的小网站为了ajax的访问还是部署webservice还是比较烦的吧！
用ajax去调用wcf：微软推出了wcf，并且现在公认为他是一种可以替代webservice的新产品，并且他还支持奖wcf部署在web服务器上，以url形式发布，当然了，这样就可以用ajax来访问调用，但是同上，小网站小应用还要去弄wcf，也是挺烦的一件事情！

基于C#在Mongodb的Skip-Limit和Where-Limit的分页对比并且含mongodb帮助类的源码

By Kubi Code

发表于 2013-05-06

最近在设计的日志服务中需要用到Mongodb这个Nosql数据库（不知道Mongodb的点我），由于是用于纯存日志，而且日志量巨大，百万千万级的，所以需要用到它的分页查询。
不过LZ也是刚刚接触这个数据库，不是很了解里面的命令语法，便在网上查了一些资料，结果结果说mongodb自带的简单很方便的Skip方式的分页效率很低，无奈，无奈得用其他的，
有多篇文章都推荐Where+Limit的方式分页，说他效率比Skip方式高多了，但是好多资料都是讲一些思路，并没有很具体，但是也很有帮助拉，现在简单的来讲一下这个分页思路（Skip的方式那么简单就不讲啦）：
假设一张表中（Mongodb用集合来代替）有如下条数据：1,3,4,5,6,7,8,9,20,30,50,51,52,59,60（仅仅标志该记录的ID号你可以理解为主键）
现在的也尺寸PageSize=4，那么

第一页的数据为1,3,4,5，这个用where的方式解释为SQL语句为Select top 4 * from table where id>0 因为上一页是没有记录所以用0来代替
第二页的数据为6,7,8,9,20，这个用where的方式解释为SQL语句为Select top 4 * from table where id>5 这里的5就是上一页的最后一条记录
第二页的数据为30,50,51,52,，这个用where的方式解释为SQL语句为Select top 4 * from table where id>20

整合一个基于c#的RSA私钥加密公钥解密的Helper类,含源码

By Kubi Code

发表于 2013-04-28

最近在搞单点登录的设计,在设计中需要一个Token令牌的加密传输,这个令牌在整个连接单点的各个站中起着连接认证作用,如果被仿造将会有不可预计的损失,但是这个Token是要可逆的.然后我就找.net中的各种加密，各种找。
因为是可逆的,所以像那种md5,sha之类的不可逆加密就没法用了,然后可逆的加密主要是分为对称加密盒非对称加密:

对称加密:用加密的钥匙来解密,比如DES,AES的加解密
非对称加密:一个钥匙加密,用另一个钥匙解密,这个主要就是RSA比较成熟(点我看科普)

当然这么看来非对称加密更加适合我这个需求,然后我又各种找RSA,.NET中自己实现了加密RSA加密类RSACryptoServiceProvider，但是这个用起来着实不爽，公钥和私钥是用xml来显示，太长太大，而且由于没有实现一些标准，只能用公钥加密，私钥解密（这个XML种私钥中可以看出公钥），但是事实上RSA的一对有效密钥公钥加密私钥解密和私钥加密公钥解密均可我想要的是后面的效果啊，结果又继续各种找，在找了好久看不到希望之际时，在csdn和博客园上看到了这两篇文章：

在ashx中利用反射+jquery轻松处理ajax 含Demo源码

By Kubi Code

发表于 2013-02-25

由于jquery的出现，编写js代码已经变得异常的平民化，同时现在的web也已经是ajax满天飞，哪天你自己写一个web不含ajax的拿不出手
当然，在.net的控件模式开发中一种去控件化开发已经变的变得更加通用：jquery+ajax+ashx 这种方式更加适用于一些小应用的开发，轻量、简单、自由
由于那时候太年轻，刚刚开始这种模式开发的时候是一个ajax请求一个ashx页面，这样的结果可想而知，一个小的权限系统光光ashx文件就几十个了，而且文件名还大同小异，悲剧。

后来做了一会儿变聪明了，把相同类别的请求都放到一个ashx文件中，每个请求传一个请求标志通过switch来调用相应的请求方法，当然，这样要比原来好多了，至少没那么多ashx文件了，但是每新建一个文件都要去添加switch方法，蛋疼啊有木有，更加可耻的是每次增删改一个请求都要去修改那个可恶的switch语句，烦啊

用c#写的一个局域网聊天客户端类似小飞鸽

By Kubi Code

发表于 2012-12-07

最紧在公司实习，新人不给活干，就自己随便看看，了解一些DevExpress控件啊，编码规范啊之类的，自己就寻思着写一点点小东西练习练习

出于自己对c# socket这块不熟，就选择了这块，顺便可以进一步了解委托代理。

闲话不说，先说下这次做的东西：一个局域网聊天的小软件主要基于udp的通信，如果读者还不知道udp or tcp 那请度娘一下。。。

基本思路

这也都是网上查的，还查了飞鸽传书的基本原理，在此感谢网上的各位高手哈：

软件开启的时候先新开一个线程，该线程充当服务器端，一直死循环监听
开了新线程了，调用广播的方法
此时如果局域网内已经有有其它主机打开了这个软件，将会监听到这个广播，收到这个广播后将返回自己的主机，并且将监听到的主机添加自己的在线列表中，当然，发起广播的软件也能收到其它软件的回信，收到他们的主机后也加入自己的在线列表，这样各自的列表就都能建立起来，并且将当前的列表加入一个静态的泛型列表中（用于以后和其它用户的通信，维护他们的状态）
通信发送消息：双击一个主机列表后得到该主机host 传到交谈窗体并查询出他主机的endpoint，这样就可以进行本机和向该endpoint点发送消息了
下线下线之前软件会发一个下线的广播，其它的软件接到该广播的时候将会将该主机从自己的在线列表中移除

分享javascript中方便增删改cookie的一个类

By Kubi Code

发表于 2012-10-09

在学校失业一个半月了，还没找到实习，悲剧，蛋疼，把jquery.cookie.js改了一下，改成了纯javascript版本，以备我以后项目只需，增加了一个得到页面全部cookie键值的功能。
主要是通过对document.cookie字符串的分析来进行功能的组装的。
温习一下javascript中对cookie的操作：

增加cookie可以用document.cookie=”userId=111”;来实现
完整版可以用：document.cookie=”userId=111;domain=.google.com;path=\;secure=secure;expire=”+date.toGMTString();
可以设置cookie的过期时间，域名，路径

Kubi Code'Blog

The palest ink is better than the best memory.

LeetCode-Reverse Integer

LeetCode-Reverse Words in a String

LeetCode-3Sum

解法1

解法2

测试用例

参考

读《这就是搜索引擎：核心技术详解》有感总结

基于.Net 写我自己的Ajax后台框架AjaxFramework

为什么要写自己的Ajax后台框架

基于C#在Mongodb的Skip-Limit和Where-Limit的分页对比并且含mongodb帮助类的源码

整合一个基于c#的RSA私钥加密公钥解密的Helper类,含源码

在ashx中利用反射+jquery轻松处理ajax 含Demo源码

用c#写的一个局域网聊天客户端类似小飞鸽

基本思路

分享javascript中方便增删改cookie的一个类