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

Commit3e0ebca

Browse files
committed
spiral
1 parent87c647d commit3e0ebca

File tree

2 files changed

+254
-0
lines changed

2 files changed

+254
-0
lines changed

‎algorithm/dp/FindLargeCommonLine.java

Lines changed: 70 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,70 @@
1+
packageAlgorithms.algorithm.dp;
2+
3+
importjava.util.ArrayList;
4+
5+
publicclassFindLargeCommonLine {
6+
publicstaticvoidmain(String[]str) {
7+
int[][]input = {
8+
{0,1},
9+
{1,0}
10+
};
11+
12+
System.out.println(find(input));
13+
}
14+
15+
publicstaticclassDpType {
16+
ArrayList<Boolean>set0;
17+
ArrayList<Boolean>set1;
18+
intmax0;
19+
intmax1;
20+
21+
publicDpType(intmax0,intmax1) {
22+
super();
23+
this.set0 =newArrayList<Boolean>();
24+
this.set1 =newArrayList<Boolean>();
25+
this.max0 =max0;
26+
this.max1 =max1;
27+
}
28+
}
29+
30+
publicstaticintfind(int[][]input) {
31+
if (input ==null ||input.length ==0 ||input[0].length ==0) {
32+
return0;
33+
}
34+
35+
introws =input.length;
36+
intcols =input[0].length;
37+
38+
// create a DP
39+
int[]max1 =newint[cols];
40+
int[]max0 =newint[cols];
41+
42+
// initate to be one, means the first line.
43+
intmaxLine1 =1;
44+
intmaxLine0 =1;
45+
46+
for (inti =0;i <cols;i++) {
47+
if (input[0][i] ==0) {
48+
// no change.
49+
max0[i] =0;
50+
51+
// should reverse.
52+
max1[i] =1;
53+
}else {
54+
max0[i] =1;
55+
max1[i] =0;
56+
}
57+
}
58+
59+
// Dp from the 2nd line to the last.
60+
for (inti =1;i <rows;i++) {
61+
booleanis0 =true;
62+
for (intj =0;j <cols;j++) {
63+
//if (input[])
64+
}
65+
}
66+
67+
return0;
68+
}
69+
70+
}

‎array/SpiralOrder.java

Lines changed: 184 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,184 @@
1+
packageAlgorithms.array;
2+
3+
importjava.util.ArrayList;
4+
importjava.util.List;
5+
6+
publicclassSpiralOrder {
7+
publicstaticvoidmain(String[]strs) {
8+
int[][]matrix = {
9+
{1,2},
10+
{3,4}
11+
};
12+
spiralOrder(matrix);
13+
}
14+
15+
publicList<Integer>spiralOrder1(int[][]matrix) {
16+
List<Integer>ret =newArrayList<Integer>();
17+
if (matrix ==null ||matrix.length ==0
18+
||matrix[0].length ==0) {
19+
returnret;
20+
}
21+
22+
rec(matrix,0,0,matrix.length,matrix[0].length,ret);
23+
24+
returnret;
25+
}
26+
27+
publicstaticvoidrec(int[][]matrix,intx,inty,introws,intcols,List<Integer>ret) {
28+
if (rows <=0 ||cols <=0) {
29+
return;
30+
}
31+
32+
// first line
33+
for (inti =0;i <cols;i++) {
34+
ret.add(matrix[x][y +i]);
35+
}
36+
37+
// right column
38+
for (inti =1;i <rows -1;i++) {
39+
ret.add(matrix[x +i][y +cols -1]);
40+
}
41+
42+
// down row
43+
if (rows >1) {
44+
for (inti =cols -1;i >=0;i--) {
45+
ret.add(matrix[x +rows -1][y +i]);
46+
}
47+
}
48+
49+
// left column. GO UP.
50+
if (cols >1) {
51+
for (inti =rows -2;i >0;i--) {
52+
ret.add(matrix[x +i][y]);
53+
}
54+
}
55+
56+
rec (matrix,x +1,y +1,rows -2,cols -2,ret);
57+
}
58+
59+
/*
60+
Solution 2:
61+
REF: http://blog.csdn.net/fightforyourdream/article/details/16876107?reload
62+
此算法比较不容易算错
63+
*/
64+
publicList<Integer>spiralOrder2(int[][]matrix) {
65+
List<Integer>ret =newArrayList<Integer>();
66+
if (matrix ==null ||matrix.length ==0
67+
||matrix[0].length ==0) {
68+
returnret;
69+
}
70+
71+
intx1 =0;
72+
inty1 =0;
73+
74+
introws =matrix.length;
75+
intcols =matrix[0].length;
76+
77+
while (rows >=1 &&cols >=1) {
78+
// Record the right down corner of the matrix.
79+
intx2 =x1 +rows -1;
80+
inty2 =y1 +cols -1;
81+
82+
// go through the WHOLE first line.
83+
for (inti =y1;i <=y2;i++) {
84+
ret.add(matrix[x1][i]);
85+
}
86+
87+
// go through the right column.
88+
for (inti =x1 +1;i <x2;i++) {
89+
ret.add(matrix[i][y2]);
90+
}
91+
92+
// go through the WHOLE last row.
93+
if (rows >1) {
94+
for (inti =y2;i >=y1;i--) {
95+
ret.add(matrix[x2][i]);
96+
}
97+
}
98+
99+
// the left column.
100+
if (cols >1) {
101+
for (inti =x2 -1;i >x1;i--) {
102+
ret.add(matrix[i][y1]);
103+
}
104+
}
105+
106+
// in one loop we deal with 2 rows and 2 cols.
107+
rows -=2;
108+
cols -=2;
109+
x1++;
110+
y1++;
111+
}
112+
113+
returnret;
114+
}
115+
116+
/*
117+
Solution 3:
118+
使用方向矩阵来求解
119+
*/
120+
publicstaticList<Integer>spiralOrder(int[][]matrix) {
121+
List<Integer>ret =newArrayList<Integer>();
122+
if (matrix ==null ||matrix.length ==0
123+
||matrix[0].length ==0) {
124+
returnret;
125+
}
126+
127+
introws =matrix.length;
128+
intcols =matrix[0].length;
129+
130+
intvisitedRows =0;
131+
intvisitedCols =0;
132+
133+
// indicate the direction of x
134+
135+
// 1: means we are visiting the row by the right direction.
136+
// -1: means we are visiting the row by the left direction.
137+
int[]x = {1,0, -1,0};
138+
139+
// 1: means we are visiting the colum by the down direction.
140+
// -1: means we are visiting the colum by the up direction.
141+
int[]y = {0,1,0, -1};
142+
143+
// 0: right, 1: down, 2: left, 3: up.
144+
intdirect =0;
145+
146+
intstartx =0;
147+
intstarty =0;
148+
149+
intcandidateNum =0;
150+
intstep =0;
151+
while (true) {
152+
if (x[direct] ==0) {
153+
// visit Y axis.
154+
candidateNum =rows -visitedRows;
155+
}else {
156+
// visit X axis
157+
candidateNum =cols -visitedCols;
158+
}
159+
160+
if (candidateNum <=0) {
161+
break;
162+
}
163+
164+
ret.add(matrix[startx][starty]);
165+
step++;
166+
167+
if (step ==candidateNum) {
168+
step =0;
169+
visitedRows +=x[direct] ==0 ?0:1;
170+
visitedCols +=y[direct] ==0 ?0:1;
171+
172+
// move forward the direction.
173+
direct ++;
174+
direct =direct%4;
175+
}
176+
177+
// 根据方向来移动横坐标和纵坐标。
178+
startx +=y[direct];
179+
starty +=x[direct];
180+
}
181+
182+
returnret;
183+
}
184+
}

0 commit comments

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