LeetCode地址:https://leetcode.com/problems/pascals-triangle/

Problem:
Given numRows, generate the first numRows of Pascal’s triangle.

For example, given numRows = 5,
Return

[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]
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
public class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> list=new ArrayList<List<Integer>>();

if(numRows==0)
return list;

list.add(Arrays.asList(1));

for(int i=1;i<numRows;i++)
{
List<Integer> rows=new ArrayList<Integer>();
rows.add(1);
for(int j=1;j<i;j++)
{
rows.add(list.get(i-1).get(j-1)+list.get(i-1).get(j));

}
rows.add(1);
list.add(rows);
}

return list;
}
}

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

LeetCode地址:https://leetcode.com/problems/pascals-triangle-ii/

Problem:
Given an index k, return the kth row of the Pascal’s triangle.

For example, given k = 3,
Return [1,3,3,1].

Note:
Could you optimize your algorithm to use only O(k) extra space?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
public List<Integer> getRow(int rowIndex) {
Integer[] ret=new Integer[rowIndex+1];

for(int i=0;i<ret.length;i++)
{
ret[i]=0;
}
ret[0]=1;
for(int i=1;i<rowIndex+1;i++)
{
for(int j=i;j>0;j--)
{
ret[j]+=ret[j-1];
}
}

return Arrays.asList(ret);
}
}

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

leetcode地址:https://leetcode.com/problems/triangle/

Problem:
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

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
public class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
int[][] sums=new int[triangle.size()][triangle.size()];
List<Integer> rows;
int ret=0,column;


if(triangle.size()>0)
{
for(int i=triangle.size()-1;i>=0;i--)
{
rows=triangle.get(i);

if(i==triangle.size()-1)
{
//the last rows
for(int j=0;j<rows.size();j++)
{
sums[i][j]=rows.get(j);
}
}else{

for(int j=0;j<rows.size();j++)
{

sums[i][j]=this.getMin(rows.get(j)+sums[i+1][j],rows.get(j)+sums[i+1][j+1]);
}
}

}

ret=sums[0][0];
}

return ret;

}

public Integer getMin(Integer a,Integer b)
{

return a>b?b:a;
}
}

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

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,并且,不得用于商业用途。如您有任何疑问或者授权方面的协商,请给我留言