LeetCode地址:https://leetcode.com/problems/clone-graph/

Problem:
Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ’s undirected graph serialization:
Nodes are labeled uniquely.

We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.
As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

  1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
  2. Second node is labeled as 1. Connect node 1 to node 2.
  3. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

Visually, the graph looks like the following:

   1
  / \
 /   \
0 --- 2
     / \
     \_/
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
/**
* Definition for undirected graph.
* class UndirectedGraphNode {
* int label;
* List<UndirectedGraphNode> neighbors;
* UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
* };
*/

public class Solution {
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if(node==null)
return null;

HashMap<Integer,UndirectedGraphNode> graphMap=new HashMap<Integer,UndirectedGraphNode>();
Queue<UndirectedGraphNode> visit=new LinkedList<UndirectedGraphNode>();
UndirectedGraphNode temp;

visit.add(node);

while(!visit.isEmpty())
{
temp=visit.poll();

if(!graphMap.containsKey(temp.label))
{
UndirectedGraphNode graphNode=new UndirectedGraphNode(temp.label);
graphMap.put(temp.label, graphNode);

visit.addAll(temp.neighbors);
}
}

visit.add(node);
while(!visit.isEmpty())
{
temp=visit.poll();
UndirectedGraphNode graphNode=graphMap.get(temp.label);
if(graphNode.neighbors.size()==0 && temp.neighbors.size()!=0)
{
for(UndirectedGraphNode neighbor:temp.neighbors)
{
graphNode.neighbors.add(graphMap.get(neighbor.label));
visit.add(neighbor);
}
}
}

return graphMap.get(node.label);
}
}

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

LeetCode地址:https://leetcode.com/problems/candy/

Problem:
There are N children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

  • Each child must have at least one candy.
  • Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?

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 candy(int[] ratings) {
int n=ratings.length;
if(n<2) return n;

int[] maxseq=new int[n];
for(int i=n-2; i>=0; --i)
if(ratings[i]>ratings[i+1]) maxseq[i]=1+maxseq[i+1];

int[] candies=new int[n];

int sum=0;
for(int i=0; i<n; ++i){
candies[i]=1;

if(i!=0 && ratings[i]>ratings[i-1])
{
candies[i]=1+Math.max(candies[i-1], maxseq[i]);
}else{
candies[i]+=maxseq[i];
}

sum+=candies[i];
}
return sum;
}
}

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

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

Problem:
Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You must do this in-place without altering the nodes’ values.

For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

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

public class Solution {
public void reorderList(ListNode head) {
if(head==null || head.next==null)
return ;

Stack<ListNode> stack=new Stack<ListNode>();

ListNode temp=head;
while(temp!=null)
{
stack.push(temp);
temp=temp.next;
}

int length=stack.size();
temp=head;
for(int i=0;i<Math.floor((length+1)/2)-1;i++)
{
ListNode node=stack.pop();
node.next=temp.next;
temp.next=node;

temp=node.next;
}
stack.pop().next=null;
}
}

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

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