Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit930129b

Browse files
author
piggy1991
committed
stack
1 parent386d1f0 commit930129b

File tree

7 files changed

+263
-11
lines changed

7 files changed

+263
-11
lines changed

‎array/FirstMissingPositive.java

Lines changed: 27 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -2,26 +2,20 @@
22

33
publicclassFirstMissingPositive {
44
publicstaticvoidmain(String[]strs) {
5-
int[]in = {1,2,0};
5+
int[]in = {1,4,2,3};
66
//int[] in = {3,4,-1,1};
77
System.out.println(firstMissingPositive(in));
88
}
99

10-
publicstaticintfirstMissingPositive(int[]A) {
10+
publicstaticintfirstMissingPositive1(int[]A) {
1111
if (A ==null) {
1212
return0;
1313
}
1414

15-
/*
16-
使用桶排序，将数字放置在正确的位置，如果最后发现在某个位置不存在正确的数字，说明这个数字是缺失的。
17-
在排序过程中，因为要不断交换直到不能再交换为止，所以遇到目标位置已经有正确数字时，不要再交换，以
18-
免发生死循环。
19-
*/
2015
intlen =A.length;
2116
for (inti =0;i <len;i++) {
2217
// 1. The number should be in the range.
2318
// 2. The number should be positive.
24-
// 注意：和将要交换的值不可以相同，否则会死循环
2519
while (A[i] <=len &&A[i] >0 &&A[A[i] -1] !=A[i]) {
2620
swap(A,i,A[i] -1);
2721
}
@@ -41,4 +35,29 @@ public static void swap(int[] A, int i, int j) {
4135
A[i] =A[j];
4236
A[j] =tmp;
4337
}
38+
39+
// SOLUTION 2:
40+
publicstaticintfirstMissingPositive(int[]A) {
41+
// bug 3: when length is 0, return 1;
42+
if (A ==null) {
43+
return0;
44+
}
45+
46+
for (inti =0;i <A.length;i++) {
47+
// 1: A[i] is in the range;
48+
// 2: A[i] > 0.
49+
// 3: The target is different;
50+
while (A[i] <=A.length &&A[i] >0 &&A[A[i] -1] !=A[i]) {
51+
swap(A,i,A[i] -1);
52+
}
53+
}
54+
55+
for (inti =0;i <A.length;i++) {
56+
if (A[i] !=i +1) {
57+
returni +1;
58+
}
59+
}
60+
61+
returnA.length +1;
62+
}
4463
}

‎dp/MaxProfit.java

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -16,4 +16,20 @@ public int maxProfit(int[] prices) {
1616

1717
returnmaxProfit;
1818
}
19+
20+
publicintmaxProfit2(int[]prices) {
21+
if (prices ==null) {
22+
return0;
23+
}
24+
25+
intmaxProfit =0;
26+
intminValue =Integer.MAX_VALUE;
27+
28+
for (inti:prices) {
29+
minValue =Math.min(minValue,i);
30+
maxProfit =Math.max(maxProfit,i -minValue);
31+
}
32+
33+
returnmaxProfit;
34+
}
1935
}

‎dp/MaxProfit2.java

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -15,4 +15,26 @@ public int maxProfit(int[] prices) {
1515

1616
returnprofit;
1717
}
18+
19+
/*
20+
* 2015.1.3
21+
* */
22+
publicintmaxProfit2(int[]prices) {
23+
if (prices ==null) {
24+
return0;
25+
}
26+
27+
intmaxProfit =0;
28+
29+
intlen =prices.length;
30+
for (inti =1;i <len;i++) {
31+
intdif =prices[i] -prices[i -1];
32+
33+
if (dif >0) {
34+
maxProfit +=dif;
35+
}
36+
}
37+
38+
returnmaxProfit;
39+
}
1840
}

‎dp/MaxProfit3.java

Lines changed: 63 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -10,28 +10,88 @@ public int maxProfit(int[] prices) {
1010
int[]left =newint[len];
1111
int[]right =newint[len];
1212

13-
// 计算i左边的最大利润
1413
intmin =prices[0];
1514
left[0] =0;
1615
for (inti =1;i <len;i++) {
1716
min =Math.min(min,prices[i]);
1817
left[i] =Math.max(left[i -1],prices[i] -min);
1918
}
2019

21-
// 计算i右边的最大利润
2220
intmax =prices[len -1];
2321
right[len -1] =0;
2422
for (inti =len -2;i >=0;i--) {
2523
max =Math.max(max,prices[i]);
2624
right[i] =Math.max(right[i +1],max -prices[i]);
2725
}
2826

29-
// 把2边的利润相加
3027
intrst =0;
3128
for (inti =0;i <len;i++) {
3229
rst =Math.max(rst,left[i] +right[i]);
3330
}
3431

3532
returnrst;
3633
}
34+
35+
// 2015.1.3: redo
36+
publicintmaxProfit2(int[]prices) {
37+
if (prices ==null) {
38+
return0;
39+
}
40+
41+
intret =0;
42+
43+
intlen =prices.length;
44+
int[]leftProfile =newint[len];
45+
intprofile =0;
46+
47+
intmin =Integer.MAX_VALUE;
48+
for (inti =0;i <len;i++) {
49+
min =Math.min(min,prices[i]);
50+
profile =Math.max(profile,prices[i] -min);
51+
leftProfile[i] =profile;
52+
}
53+
54+
intmax =Integer.MIN_VALUE;
55+
profile =0;
56+
for (inti =len -1;i >=0;i--) {
57+
max =Math.max(max,prices[i]);
58+
profile =Math.max(profile,max -prices[i]);
59+
60+
// sum the left profit and the right profit.
61+
ret =Math.max(ret,profile +leftProfile[i]);
62+
}
63+
64+
returnret;
65+
}
66+
67+
// DP solution:
68+
publicintmaxProfit3(int[]prices) {
69+
if (prices ==null ||prices.length ==0) {
70+
return0;
71+
}
72+
73+
intret =0;
74+
75+
intlen =prices.length;
76+
int[]leftProfile =newint[len];
77+
78+
intmin =prices[0];
79+
leftProfile[0] =0;
80+
for (inti =1;i <len;i++) {
81+
min =Math.min(min,prices[i]);
82+
leftProfile[i] =Math.max(leftProfile[i -1],prices[i] -min);
83+
}
84+
85+
intmax =Integer.MIN_VALUE;
86+
intprofile =0;
87+
for (inti =len -1;i >=0;i--) {
88+
max =Math.max(max,prices[i]);
89+
profile =Math.max(profile,max -prices[i]);
90+
91+
// sum the left profit and the right profit.
92+
ret =Math.max(ret,profile +leftProfile[i]);
93+
}
94+
95+
returnret;
96+
}
3797
}

‎stack/IsValid.java

Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
packageAlgorithms.stack;
2+
3+
importjava.util.Stack;
4+
5+
publicclassIsValid {
6+
publicbooleanisValid(Strings) {
7+
if (s ==null) {
8+
returnfalse;
9+
}
10+
11+
intlen =s.length();
12+
13+
// bug 1: don't use s as the name of the stack.
14+
Stack<Character>stk =newStack<Character>();
15+
16+
for (inti =0;i <len;i++) {
17+
charc =s.charAt(i);
18+
switch(c) {
19+
case'(':
20+
case'[':
21+
case'{':
22+
stk.push(c);
23+
break;
24+
case')':
25+
if (!stk.isEmpty() &&stk.peek() =='(') {
26+
stk.pop();
27+
}else {
28+
returnfalse;
29+
}
30+
break;
31+
case'}':
32+
if (!stk.isEmpty() &&stk.peek() =='{') {
33+
stk.pop();
34+
}else {
35+
returnfalse;
36+
}
37+
break;
38+
case']':
39+
if (!stk.isEmpty() &&stk.peek() =='[') {
40+
stk.pop();
41+
}else {
42+
returnfalse;
43+
}
44+
break;
45+
}
46+
}
47+
48+
returnstk.isEmpty();
49+
}
50+
}

‎string/Atoi.java

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -42,4 +42,45 @@ public int atoi(String str) {
4242

4343
return (int)num;
4444
}
45+
46+
// SOLUTION 2: the Leetcode test case is improved.
47+
publicintatoi2(Stringstr) {
48+
longret =0;
49+
50+
// ___+1234__
51+
// Delete the leading and tailing spaces.
52+
StringsNew =str.trim();
53+
54+
if (sNew.length() ==0) {
55+
return0;
56+
}
57+
58+
booleanpositive =true;
59+
for (inti =0;i <sNew.length();i++) {
60+
charc =sNew.charAt(i);
61+
if (i ==0 &&c =='+') {
62+
continue;
63+
}elseif (i ==0 &&c =='-') {
64+
positive =false;
65+
continue;
66+
}
67+
68+
if (!(c <='9' &&c >='0')) {
69+
break;
70+
}
71+
72+
intdig =positive ?c -'0':'0' -c;
73+
74+
ret =ret *10 +dig;
75+
76+
// bug 2: should consider the out of range.
77+
if (ret >Integer.MAX_VALUE) {
78+
returnInteger.MAX_VALUE;
79+
}elseif (ret <Integer.MIN_VALUE) {
80+
returnInteger.MIN_VALUE;
81+
}
82+
}
83+
84+
return (int)ret;
85+
}
4586
}

‎tree/BuildTree2.java

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
packageAlgorithms.tree;
2+
3+
/**
4+
* Definition for binary tree
5+
* public class TreeNode {
6+
* int val;
7+
* TreeNode left;
8+
* TreeNode right;
9+
* TreeNode(int x) { val = x; }
10+
* }
11+
*/
12+
publicclassBuildTree2 {
13+
publicTreeNodebuildTree(int[]inorder,int[]postorder) {
14+
if (inorder ==null ||postorder ==null) {
15+
returnnull;
16+
}
17+
18+
returndfs(inorder,postorder,0,inorder.length -1,0,postorder.length -1);
19+
}
20+
21+
publicTreeNodedfs(int[]inorder,int[]postorder,intinL,intinR,intpostL,intpostR) {
22+
if (inL >inR) {
23+
returnnull;
24+
}
25+
26+
// create the root node.
27+
TreeNoderoot =newTreeNode(postorder[postR]);
28+
29+
// find the position of the root node in the inorder traversal.
30+
intpos =0;
31+
for (;pos <=inR;pos++) {
32+
if (inorder[pos] ==postorder[postR]) {
33+
break;
34+
}
35+
}
36+
37+
intleftNum =pos -inL;
38+
39+
root.left =dfs(inorder,postorder,inL,pos -1,postL,postL +leftNum -1);
40+
root.right =dfs(inorder,postorder,pos +1,inR,postL +leftNum,postR -1);
41+
42+
returnroot;
43+
}
44+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp