LeetCode地址:https://leetcode.com/problems/linked-list-cycle/

Problem:
Given a linked list, determine if it has a cycle in it.

Follow up:
Can you solve it without using extra space?

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
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/

public class Solution {
public boolean hasCycle(ListNode head) {
boolean ret=false;

if(head==null)
return ret;

ListNode singleStepNode=head,
doubleStepNode=head;

while(singleStepNode.next !=null &&
doubleStepNode.next!=null &&
doubleStepNode.next.next !=null)
{
singleStepNode=singleStepNode.next;
doubleStepNode=doubleStepNode.next.next;

if(singleStepNode.next==doubleStepNode.next)
{
ret=true;
break;
}
}


return ret;
}
}

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

LeetCode地址:https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/

Problem:
Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

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
public class Solution {
public int maxProfit(int[] prices) {
int ret=0,
buy=0,
sale=0,
length=prices.length;

if(length<2)
return ret;

int[] historyProfit=new int[length];

buy=prices[0];
for(int i=1;i<length;i++)
{
historyProfit[i]=getMax(historyProfit[i-1], prices[i]-buy);
buy=getMin(buy, prices[i]);
}

sale=prices[length-1];
ret=historyProfit[length-1];
for(int i=length-1;i>0;i--)
{
ret=getMax(ret, historyProfit[i-1]+sale-prices[i]);
sale=getMax(sale, prices[i]);
}

return ret;
}

public int getMax(int a,int b)
{

return a>b?a:b;
}

public int getMin(int a,int b)
{

return a>b?b:a;
}
}

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

LeetCode地址:https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/

Problem:
Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

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
public class Solution {
public int maxProfit(int[] prices) {
int ret=0,
leftValue=0,
length=prices.length,
state=-1;//-1=buy,1=sale

for(int i=0;i<length;i++)
{
if(state==-1)
{
if(i+1<length && prices[i]<prices[i+1])
{
leftValue=prices[i];
state=1;
}
}else{
if((i==length-1 && prices[i]>leftValue) || prices[i]>prices[i+1])
{
ret+=prices[i]-leftValue;
state=-1;
}
}
}

return ret;
}
}

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

LeetCode地址:https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

Problem:
Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

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
public class Solution {
public int maxProfit(int[] prices) {
int ret=0,
leftValue=Integer.MAX_VALUE,
rightPos=0,
length=prices.length;

for(int i=0;i<length-1;i++)
{
if(prices[i]>leftValue)
continue;

for(int j=i+1;j<length;j++)
{
if(prices[j]-prices[i]>ret)
{
ret=prices[j]-prices[i];
leftValue=prices[i];
}
}
}


return ret;
}
}

thr runtime is 1548ms -_-!

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
public class Solution {
public int maxProfit(int[] prices) {
int ret=0,
buy=0,
length=prices.length;

if(prices.length<2)
return ret;

buy=prices[0];
for(int i=1;i<length;i++)
{
if(prices[i]-buy>ret)
{
ret=prices[i]-buy;
}

if(prices[i]<buy)
{
buy=prices[i];
}
}


return ret;
}
}

thr runtime is 376ms


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

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

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

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