Problem:
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
public class LRUCache {

private HashMap<Integer,Integer> _cache;

private int _capacity;

private Node _head=null;

private Node _end=null;

public LRUCache(int capacity) {

this._head=new Node();
this._end=new Node();

this._head.next=this._end;
this._end.next=null;

this._capacity=capacity;
this._cache=new HashMap<Integer,Integer>(capacity);
}

public int get(int key) {
int ret=-1;

if(this._cache.containsKey(key))
{
ret=this._cache.get(key);
this.moveToFirst(key);
}


return ret;
}

public void set(int key, int value) {
if(!this._cache.containsKey(key))
{
if(_cache.size()>=this._capacity)
{
this._cache.remove(this.popKey());
}

this.insertToFirst(key);
}else{
this.moveToFirst(key);
}

this._cache.put(key, value);
}

private void moveToFirst(Integer key)
{

Node node=this._head;
Node node2=null;

while(node.next!=null)
{

if(key.equals(node.key))
{
break;
}
node2=node;
node=node.next;
}

node2.next=node.next;
node.next=this._head.next;
this._head.next=node;
}

private void insertToFirst(Integer key)
{

Node node=new Node(key);
node.next=this._head.next;
this._head.next=node;

}


private Integer popKey()
{

int key=-1;
Node node=this._head;
Node node2=null;

while(node.next!=this._end)
{
node2=node;
node=node.next;
}

key=node.key;
node2.next=this._end;

return key;
}




class Node{
public Integer key;

public Node next;

public Node()
{


}

public Node(Integer key)
{

this.key=key;
}

public Node clone(){
Node node=new Node();
node.key=this.key;
node.next=this.next;

return node;
}
}
}

其实在Java中最方便实现LRUCache的方法就是使用LinkedHashMap,天然的集成了该功能,但是LeetCode在这题中并没有引用LinkedHashMap的包,-_-

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class LRUCache extends LinkedHashMap<Integer,Integer> {
private int maxCacheNum=10;

public LRUCache(int capacity)
{

super(capacity,0.75f,true);//这里第三个参数一定要为true,这样就表示该LinkedHashMap是使用了访问速度来链表
this.maxCacheNum=capacity;
}

public int get(int key) {
if(super.containsKey(key))
{
return super.get(key);
}else{
return -1;
}
}

public void set(int key, int value) {
super.put(key, value);
}

/**
* 重写删除最少用元素的方法
*/

@Override
protected boolean removeEldestEntry(Map.Entry<Integer,Integer> eldest) {
return this.size()>maxCacheNum;
}
}

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

Problem:
Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

    1
   / \
  2   5
 / \   \
3   4   6

The flattened tree should look like:

1
\
 2
  \
   3
    \
     4
      \
       5
        \
         6
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/

public class Solution {
public void flatten(TreeNode root) {
if(root==null)
return ;

flatten(root.left);

flatten(root.right);

if(root.left!=null)
{
//move the left leaf to the right
TreeNode tempNode=root.left;
while(tempNode.right!=null)
{
tempNode=tempNode.right;
}


tempNode.right=root.right;
root.right=root.left;
root.left=null;
}
}
}

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

Problem:
Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

For example:
Given the below binary tree and sum = 22,

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \      \
7    2      1

return

[
   [5,4,11,2],
   [5,8,4,5]
]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/

public class Solution {
public List<List<Integer>> pathSum(TreeNode root, int sum) {

List<List<Integer>> pathList=new ArrayList<List<Integer>>();

if(root!=null)
pathSearch(pathList,new Stack<Integer>(),root,sum);

return pathList;
}

public void pathSearch(List<List<Integer>> pathList,Stack<Integer> curPath,TreeNode node,int sum)
{

if(node!=null)
{
curPath.push(node.val);
sum-=node.val;

if(node.left==null && node.right==null&&sum==0)
{
pathList.add(Collections.list(((Stack<Integer>)curPath.clone()).elements()));
}

pathSearch(pathList,curPath,node.left,sum);
pathSearch(pathList,curPath,node.right,sum);
curPath.pop();


}
}
}

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

Problem:
Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \      \
7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/

public class Solution {


public boolean hasPathSum(TreeNode root, int sum) {
if(root == null)
return false;

sum-=root.val;

if(root.left ==null && root.right==null)
return sum==0;
else
return hasPathSum(root.left,sum) || hasPathSum(root.right,sum);

}


}

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

Problem:
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
/**
* Definition for a point.
* class Point {
* int x;
* int y;
* Point() { x = 0; y = 0; }
* Point(int a, int b) { x = a; y = b; }
* }
*/

public class Solution {
public int maxPoints(Point[] points) {

if(points.length<=1)
{
return points.length;
}

int[] pointNum=new int[points.length];//the number in average group
Point[] pointGroup=new Point[points.length];
int groupLength=0;
boolean flagAdd=false;
for(Point point:points)
{
flagAdd=false;
for(int i=0;i<groupLength;i++)
{
if(pointGroup[i].x==point.x && pointGroup[i].y==point.y)
{
pointNum[i]++;
flagAdd=true;
break;
}
}

if(!flagAdd)
{
pointGroup[groupLength]=point;
pointNum[groupLength]=1;
groupLength++;
}
}

int maxNum=pointNum[0],tempNum=0;
HashMap<Straight,Integer> straightMap=new HashMap<Straight,Integer>();

for(int i=0;i<groupLength;i++)
{
for(int j=i+1;j<groupLength;j++)
{
tempNum=pointNum[i]+pointNum[j];
Straight straight=new Straight(pointGroup[i],pointGroup[j]);

if(straightMap.containsKey(straight))
{
continue;
}else{
straightMap.put(straight, 1);
}

for(int k=j+1;k<groupLength;k++)
{
if(straight.isIn(pointGroup[k]))
{
tempNum+=pointNum[k];
}
}

if(maxNum<tempNum)
{
maxNum=tempNum;
}
}
}

return maxNum;
}

class Straight{

private double _gradient;
private double _intercept;

public Straight(Point p1,Point p2)
{

if(p1.x==p2.x)
{
this._gradient=Double.NaN;

this._intercept=p1.x;


}else{
this._gradient=(p2.y-p1.y)/(double)(p2.x-p1.x);
this._intercept=p1.y-this._gradient*p1.x;
}
}

public Straight(double gradient,double intercept)
{

this._gradient=gradient;
this._intercept=intercept;
}

/**
* judge this point whether in this straight
* @param point
* @return
*/

public boolean isIn(Point point)
{


if(Double.isNaN(this._gradient))
{
return this._intercept==point.x;
}
return Math.abs(point.y-(this._gradient*point.x+this._intercept))<=1e-7;
}

}
}

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

Problem:
Reverse digits of an integer.

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

1
2
3
4
5
6
7
8
9
10
11
12
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,并且,不得用于商业用途。如您有任何疑问或者授权方面的协商,请给我留言

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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-_-

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
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地址: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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
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;
}

测试用例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
/**
* 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);
}

参考


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

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

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

Read More

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

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

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

  1. 用ajax访问aspx页面:直接在page_load中输出html代码并且End掉多余标签的输出,但是他还要走生命周期,一个好好的aspx页面只用这个功能怪怪的,当然还可以直接在aspx.cs上面的方法上加上[webMethod]特性来标记ajax访问,但是必须该方法为静态,用起来也不是很爽。

  2. 用ajax访问ashx一般处理程序:这个是在.net的ajax开发中一种常见明确推荐的方式,他输出页面少,不冗余代码,调用灵活,但是他通常一个ashx页面只提供一个功能,但是市面上有可以通过switch方法的参数或者用委托或者反射的方法来实现一个ashx页面提供多个ajax访问的功能,但是没发现这样也挺乱的吗,我之前一直用这个,慢慢的 慢慢的开始讨厌这种写好写法!

  3. 用ajax直接调用webservice服务:这样的好处是在一个普通的webserive类中可以使用多个对外ajax访问点的发布,用起来很灵活,但是你一般的小网站为了ajax的访问还是部署webservice还是比较烦的吧!

  4. 用ajax去调用wcf:微软推出了wcf,并且现在公认为他是一种可以替代webservice的新产品,并且他还支持奖wcf部署在web服务器上,以url形式发布,当然了,这样就可以用ajax来访问调用,但是同上,小网站小应用还要去弄wcf,也是挺烦的一件事情!

Read More