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

Commit08ca067

Browse files
committed
GetIntersectionNode1
1 parent405c1a8 commit08ca067

File tree

2 files changed

+254
-3
lines changed

2 files changed

+254
-3
lines changed

‎list/GetIntersectionNode1.java

Lines changed: 98 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,98 @@
1+
packageAlgorithms.list;
2+
3+
importAlgorithms.algorithm.others.ListNode;
4+
5+
/**
6+
* Definition for singly-linked list.
7+
* public class ListNode {
8+
* int val;
9+
* ListNode next;
10+
* ListNode(int x) {
11+
* val = x;
12+
* next = null;
13+
* }
14+
* }
15+
*/
16+
publicclassGetIntersectionNode1 {
17+
publicListNodegetIntersectionNode1(ListNodeheadA,ListNodeheadB) {
18+
if (headA ==null ||headB ==null) {
19+
returnnull;
20+
}
21+
22+
intlenA =getLen(headA);
23+
intlenB =getLen(headB);
24+
25+
if (lenA >lenB) {
26+
while (lenA >lenB) {
27+
headA =headA.next;
28+
lenA--;
29+
}
30+
}else {
31+
while (lenA <lenB) {
32+
headB =headB.next;
33+
lenB--;
34+
}
35+
}
36+
37+
while (headA !=null) {
38+
if (headA ==headB) {
39+
returnheadA;
40+
}
41+
headA =headA.next;
42+
headB =headB.next;
43+
}
44+
45+
returnnull;
46+
}
47+
48+
publicintgetLen(ListNodenode) {
49+
intlen =0;
50+
while (node !=null) {
51+
len++;
52+
node =node.next;
53+
}
54+
returnlen;
55+
}
56+
57+
publicListNodegetIntersectionNode(ListNodeheadA,ListNodeheadB) {
58+
if (headA ==null ||headB ==null) {
59+
returnnull;
60+
}
61+
62+
ListNodepA =headA;
63+
ListNodepB =headB;
64+
65+
ListNodetailA =null;
66+
ListNodetailB =null;
67+
68+
while (true) {
69+
if (pA ==null) {
70+
pA =headB;
71+
}
72+
73+
if (pB ==null) {
74+
pB =headA;
75+
}
76+
77+
if (pA.next ==null) {
78+
tailA =pA;
79+
}
80+
81+
if (pB.next ==null) {
82+
tailB =pB;
83+
}
84+
85+
//The two links have different tails. So just return null;
86+
if (tailA !=null &&tailB !=null &&tailA !=tailB) {
87+
returnnull;
88+
}
89+
90+
if (pA ==pB) {
91+
returnpA;
92+
}
93+
94+
pA =pA.next;
95+
pB =pB.next;
96+
}
97+
}
98+
}

‎string/FullJustify.java

Lines changed: 156 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -10,7 +10,7 @@ public static void main(String[] strs) {
1010
fullJustify(words,L);
1111
}
1212

13-
// SOLUTION 1: recursion.
13+
// SOLUTION 1: recursion.
1414
publicList<String>fullJustify1(String[]words,intL) {
1515
List<String>ret =newArrayList<String>();
1616

@@ -98,14 +98,167 @@ public static void rec(String[] words, int L, int index, List<String> list) {
9898
}
9999

100100
// SOLUTION 2: iteration.
101-
publicList<String>fullJustify(String[]words,intL) {
101+
publicList<String>fullJustify2(String[]words,intL) {
102102
List<String>ret =newArrayList<String>();
103+
if (words ==null) {
104+
returnret;
105+
}
106+
107+
intlen =words.length;
108+
intindex =0;
109+
110+
while (index <len) {
111+
intLenTmp =L;
103112

113+
intend =index;
114+
for (inti =index;i <len &&words[i].length() <=LenTmp;i++) {
115+
LenTmp -=words[i].length();
116+
117+
// the space follow the word.
118+
LenTmp--;
119+
end =i;
120+
}
121+
122+
// 最后一个空格收回
123+
LenTmp++;
124+
125+
// Count how many words do we have.
126+
intnum =end -index +1;
127+
128+
intextraSpace =0;
129+
intfirstExtra =0;
130+
131+
// 单词数大于1，才需要分配，否则所有的空格加到最后即可
132+
if (num >1) {
133+
extraSpace =LenTmp / (num -1);
134+
// 首单词后多跟的空格
135+
firstExtra =LenTmp % (num -1);
136+
}
137+
138+
StringBuildersb =newStringBuilder();
139+
for (inti =index;i <=end;i++) {
140+
sb.append(words[i]);
141+
142+
// The space following every word.
143+
if (i !=end) {
144+
sb.append(' ');
145+
}
146+
147+
// 不是最后一行
148+
if (end !=len -1) {
149+
// The first words.
150+
if (firstExtra >0) {
151+
sb.append(' ');
152+
firstExtra--;
153+
}
154+
155+
// 最后一个单词后面不需要再加空格
156+
if (i ==end) {
157+
break;
158+
}
159+
160+
// 每个单词后的额外空格
161+
intcnt =extraSpace;
162+
while (cnt >0) {
163+
sb.append(' ');
164+
cnt--;
165+
}
166+
}
167+
}
168+
169+
// 最后一行的尾部的空格
170+
inttailLen =L -sb.length();
171+
while (tailLen >0) {
172+
sb.append(' ');
173+
tailLen--;
174+
}
175+
176+
ret.add(sb.toString());
177+
index =end +1;
178+
}
179+
180+
returnret;
181+
}
182+
183+
// SOLUTION 3: iteration2
184+
publicstaticList<String>fullJustify(String[]words,intL) {
185+
List<String>ret =newArrayList<String>();
104186
if (words ==null) {
105187
returnret;
106188
}
107189

108-
rec(words,L,0,ret);
190+
intlen =words.length;
191+
intindex =0;
192+
193+
while (index <len) {
194+
intLenTmp =L;
195+
196+
intend =index;
197+
for (inti =index;i <len &&words[i].length() <=LenTmp;i++) {
198+
LenTmp -=words[i].length();
199+
200+
// the space follow the word.
201+
LenTmp--;
202+
end =i;
203+
}
204+
205+
// 最后一个空格收回
206+
LenTmp++;
207+
208+
// Count how many words do we have.
209+
intnum =end -index +1;
210+
211+
intextraSpace =0;
212+
intfirstExtra =0;
213+
214+
// 单词数大于1，才需要分配，否则所有的空格加到最后即可
215+
if (num >1) {
216+
extraSpace =LenTmp / (num -1);
217+
// 首单词后多跟的空格
218+
firstExtra =LenTmp % (num -1);
219+
}
220+
221+
StringBuildersb =newStringBuilder();
222+
for (inti =index;i <=end;i++) {
223+
sb.append(words[i]);
224+
225+
intcnt =0;
226+
227+
if (i ==end) {
228+
break;
229+
}
230+
231+
// 不是最后一行
232+
if (end !=len -1) {
233+
// The first words.
234+
if (firstExtra >0) {
235+
cnt++;
236+
firstExtra--;
237+
}
238+
239+
// 最后一个单词后面不需要再加空格
240+
// 每个单词后的额外空格
241+
cnt +=extraSpace;
242+
}
243+
244+
// 1: 每个单词后本来要加的空格
245+
appendSpace(sb,cnt +1);
246+
}
247+
248+
// 最后一行的尾部的空格，或者是只有一个单词的情况
249+
appendSpace(sb,L -sb.length());
250+
251+
ret.add(sb.toString());
252+
index =end +1;
253+
}
254+
109255
returnret;
110256
}
257+
258+
publicstaticvoidappendSpace(StringBuildersb,intcnt) {
259+
while (cnt >0) {
260+
sb.append(' ');
261+
cnt--;
262+
}
263+
}
111264
}

0 commit comments

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