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

Commit7b869d0

Browse files
author
piggy1991
committed
ip
1 parentebb4be3 commit7b869d0

File tree

2 files changed

+116
-2
lines changed

2 files changed

+116
-2
lines changed

‎divide2/SearchInsert.java

Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
packageAlgorithms.divide2;
2+
3+
publicclassSearchInsert {
4+
publicintsearchInsert1(int[]A,inttarget) {
5+
if (A ==null ||A.length ==0) {
6+
return0;
7+
}
8+
9+
intleft =0;
10+
intright =A.length -1;
11+
12+
while (left <right -1) {
13+
intmid =left + (right -left) /2;
14+
intnum =A[mid];
15+
16+
if (num ==target) {
17+
returnmid;
18+
}elseif (num <target) {
19+
left =mid +1;
20+
}else {
21+
right =mid -1;
22+
}
23+
}
24+
25+
// bug 1: should use <=
26+
if (target <=A[left]) {
27+
returnleft;
28+
// bug 2: should use <= . consider that may the result exit in left or right.
29+
}elseif (target <=A[right]) {
30+
returnright;
31+
}
32+
33+
returnright +1;
34+
}
35+
36+
// sol 2:
37+
publicintsearchInsert(int[]A,inttarget) {
38+
if (A ==null ||A.length ==0) {
39+
return0;
40+
}
41+
42+
intleft =0;
43+
intright =A.length -1;
44+
45+
while (left <=right) {
46+
intmid =left + (right -left) /2;
47+
intnum =A[mid];
48+
49+
if (num ==target) {
50+
returnmid;
51+
}elseif (num <target) {
52+
left =mid +1;
53+
}else {
54+
right =mid -1;
55+
}
56+
}
57+
58+
returnleft;
59+
}
60+
}

‎string/RestoreIpAddresses.java

Lines changed: 56 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -35,13 +35,11 @@ public void dfs(String s, int index, ArrayList<String> path, ArrayList<String> r
3535

3636
intlen =s.length();
3737
for (inti =index;i <index +3 &&i <len;i++) {
38-
// 不可以有005这样子的IP地址。
3938
if (s.charAt(index) =='0' &&i >index) {
4039
break;
4140
}
4241

4342
Stringpre =s.substring(index,i +1);
44-
// 过滤num > 255的情况。
4543
intnum =Integer.parseInt(pre);
4644
if (num >255) {
4745
continue;
@@ -52,4 +50,60 @@ public void dfs(String s, int index, ArrayList<String> path, ArrayList<String> r
5250
path.remove(path.size() -1);
5351
}
5452
}
53+
54+
// 2015.1.1 Redo:
55+
publicList<String>restoreIpAddresses2(Strings) {
56+
List<String>ret =newArrayList<String>();
57+
// Bug 1: not length, but length().
58+
if (s ==null ||s.length() <4 ||s.length() >12) {
59+
returnret;
60+
}
61+
62+
dfs(s,newArrayList<String>(),ret,0);
63+
returnret;
64+
}
65+
66+
publicvoiddfs(Strings,List<String>path,List<String>ret,intindex) {
67+
// THE BASE CASE:
68+
intlen =s.length();
69+
if (path.size() ==4) {
70+
// Create a solution.
71+
if (index ==len) {
72+
StringBuildersb =newStringBuilder();
73+
for (Stringstr:path) {
74+
sb.append(str);
75+
sb.append(".");
76+
}
77+
sb.deleteCharAt(sb.length() -1);
78+
79+
// bug 3: forget this statement.
80+
ret.add(sb.toString());
81+
}
82+
83+
return;
84+
}
85+
86+
// 2/ 25 / 255
87+
// bug 2: i should < len.
88+
for (inti =index;i <index +3 &&i <len;i++) {
89+
Stringsub =s.substring(index,i +1);
90+
if (s.charAt(index) =='0' &&i !=index) {
91+
// only allow 0, not 02, 022
92+
break;
93+
}
94+
95+
if (!isValid(sub)) {
96+
continue;
97+
}
98+
99+
path.add(sub);
100+
dfs(s,path,ret,i +1);
101+
path.remove(path.size() -1);
102+
}
103+
}
104+
105+
publicbooleanisValid(Strings) {
106+
intnum =Integer.parseInt(s);
107+
returnnum >=0 &&num <=255;
108+
}
55109
}

0 commit comments

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