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

Commit35b4331

Browse files
add a solution for 33
1 parentcb00e1c commit35b4331

File tree

2 files changed

+187
-15
lines changed

2 files changed

+187
-15
lines changed

‎src/main/java/com/fishercoder/solutions/_33.java

Lines changed: 57 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -3,7 +3,6 @@
33
publicclass_33 {
44

55
publicstaticclassSolution1 {
6-
76
publicintsearch(int[]nums,inttarget) {
87
if (nums ==null ||nums.length ==0) {
98
return -1;
@@ -50,29 +49,74 @@ public int search(int[] nums, int target) {
5049
if (nums ==null ||nums.length ==0) {
5150
return -1;
5251
}
53-
intlo =0;
54-
inthi =nums.length -1;
55-
while (lo <hi) {
56-
intmid = (lo +hi) /2;
52+
intleft =0;
53+
intright =nums.length -1;
54+
while (left <right) {
55+
intmid = (left +right) /2;
5756
if (nums[mid] ==target) {
5857
returnmid;
5958
}
6059

61-
if (nums[lo] <=nums[mid]) {
62-
if (target >=nums[lo] &&target <nums[mid]) {
63-
hi =mid -1;
60+
if (nums[left] <=nums[mid]) {
61+
if (target >=nums[left] &&target <nums[mid]) {
62+
right =mid -1;
6463
}else {
65-
lo =mid +1;
64+
left =mid +1;
6665
}
6766
}else {
68-
if (target >nums[mid] &&target <=nums[hi]) {
69-
lo =mid +1;
67+
if (target >nums[mid] &&target <=nums[right]) {
68+
left =mid +1;
69+
}else {
70+
right =mid -1;
71+
}
72+
}
73+
}
74+
returnnums[left] ==target ?left : -1;
75+
}
76+
}
77+
78+
publicstaticclassSolution3 {
79+
/**
80+
* My completely original solution on 10/23/2021, although spaghetti code.
81+
*/
82+
publicintsearch(int[]nums,inttarget) {
83+
intleft =0;
84+
intright =nums.length -1;
85+
while (left <right) {
86+
if (nums[left] ==target) {
87+
returnleft;
88+
}elseif (nums[right] ==target) {
89+
returnright;
90+
}
91+
intmid =left + (right -left) /2;
92+
if (left ==mid ||right ==mid) {
93+
break;
94+
}
95+
if (nums[mid] ==target) {
96+
returnmid;
97+
}elseif (nums[mid] >target &&nums[right] >target &&nums[left] >target) {
98+
if (nums[right] <nums[mid]) {
99+
left =mid +1;
100+
}else {
101+
right =mid -1;
102+
}
103+
}elseif (nums[mid] >target &&nums[right] <target) {
104+
right =mid -1;
105+
}elseif (nums[mid] <target &&nums[right] >target) {
106+
left =mid +1;
107+
}elseif (nums[mid] <target &&nums[right] <target &&nums[left] <target) {
108+
if (nums[mid] <nums[left] &&nums[mid] <nums[right]) {
109+
right =mid -1;
70110
}else {
71-
hi =mid-1;
111+
left =mid+1;
72112
}
113+
}elseif (nums[mid] >target &&nums[left] <target) {
114+
right =mid;
115+
}elseif (nums[mid] <target &&nums[right] <target &&nums[left] >target) {
116+
right =mid -1;
73117
}
74118
}
75-
returnnums[lo] ==target ?lo : -1;
119+
return(right >=0 &&nums[right] ==target) ?right : (nums[left] ==target) ?left : -1;
76120
}
77121
}
78122
}

‎src/test/java/com/fishercoder/_33Test.java

Lines changed: 130 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -9,18 +9,146 @@
99
publicclass_33Test {
1010
privatestatic_33.Solution1solution1;
1111
privatestatic_33.Solution2solution2;
12+
privatestatic_33.Solution3solution3;
1213
privatestaticint[]nums;
14+
privatestaticintexpected;
15+
privatestaticinttarget;
1316

1417
@BeforeClass
1518
publicstaticvoidsetup() {
1619
solution1 =new_33.Solution1();
1720
solution2 =new_33.Solution2();
21+
solution3 =new_33.Solution3();
1822
}
1923

2024
@Test
2125
publicvoidtest1() {
2226
nums =newint[]{4,5,6,7,0,1,2};
23-
assertEquals(3,solution1.search(nums,7));
24-
assertEquals(3,solution2.search(nums,7));
27+
expected =3;
28+
target =7;
29+
assertEquals(expected,solution1.search(nums,target));
30+
assertEquals(expected,solution2.search(nums,target));
31+
assertEquals(expected,solution3.search(nums,target));
2532
}
33+
34+
@Test
35+
publicvoidtest2() {
36+
nums =newint[]{4,5,6,7,0,1,2};
37+
expected =4;
38+
target =0;
39+
assertEquals(expected,solution1.search(nums,target));
40+
assertEquals(expected,solution2.search(nums,target));
41+
assertEquals(expected,solution3.search(nums,target));
42+
}
43+
44+
@Test
45+
publicvoidtest3() {
46+
nums =newint[]{4,5,6,7,0,1,2};
47+
expected =1;
48+
target =5;
49+
assertEquals(expected,solution1.search(nums,target));
50+
assertEquals(expected,solution2.search(nums,target));
51+
assertEquals(expected,solution3.search(nums,target));
52+
}
53+
54+
@Test
55+
publicvoidtest4() {
56+
nums =newint[]{4,5,6,7,0,1,2};
57+
expected = -1;
58+
target =3;
59+
assertEquals(expected,solution1.search(nums,target));
60+
assertEquals(expected,solution2.search(nums,target));
61+
assertEquals(expected,solution3.search(nums,target));
62+
}
63+
64+
@Test
65+
publicvoidtest5() {
66+
nums =newint[]{1};
67+
expected = -1;
68+
target =0;
69+
assertEquals(expected,solution1.search(nums,target));
70+
assertEquals(expected,solution2.search(nums,target));
71+
assertEquals(expected,solution3.search(nums,target));
72+
}
73+
74+
@Test
75+
publicvoidtest6() {
76+
nums =newint[]{1,3,5};
77+
expected = -1;
78+
target =4;
79+
assertEquals(expected,solution1.search(nums,target));
80+
assertEquals(expected,solution2.search(nums,target));
81+
assertEquals(expected,solution3.search(nums,target));
82+
}
83+
84+
@Test
85+
publicvoidtest7() {
86+
nums =newint[]{1,3,5};
87+
expected = -1;
88+
target =6;
89+
assertEquals(expected,solution1.search(nums,target));
90+
assertEquals(expected,solution2.search(nums,target));
91+
assertEquals(expected,solution3.search(nums,target));
92+
}
93+
94+
@Test
95+
publicvoidtest8() {
96+
nums =newint[]{1,3,5};
97+
expected = -1;
98+
target =2;
99+
assertEquals(expected,solution1.search(nums,target));
100+
assertEquals(expected,solution2.search(nums,target));
101+
assertEquals(expected,solution3.search(nums,target));
102+
}
103+
104+
@Test
105+
publicvoidtest9() {
106+
nums =newint[]{5,1,3};
107+
expected = -1;
108+
target =4;
109+
assertEquals(expected,solution1.search(nums,target));
110+
assertEquals(expected,solution2.search(nums,target));
111+
assertEquals(expected,solution3.search(nums,target));
112+
}
113+
114+
@Test
115+
publicvoidtest10() {
116+
nums =newint[]{1,2,3,4,5,6};
117+
expected =3;
118+
target =4;
119+
assertEquals(expected,solution1.search(nums,target));
120+
assertEquals(expected,solution2.search(nums,target));
121+
assertEquals(expected,solution3.search(nums,target));
122+
}
123+
124+
@Test
125+
publicvoidtest11() {
126+
nums =newint[]{5,1,2,3,4};
127+
expected =1;
128+
target =1;
129+
assertEquals(expected,solution1.search(nums,target));
130+
assertEquals(expected,solution2.search(nums,target));
131+
assertEquals(expected,solution3.search(nums,target));
132+
}
133+
134+
@Test
135+
publicvoidtest12() {
136+
nums =newint[]{8,9,2,3,4};
137+
expected =1;
138+
target =9;
139+
assertEquals(expected,solution1.search(nums,target));
140+
assertEquals(expected,solution2.search(nums,target));
141+
assertEquals(expected,solution3.search(nums,target));
142+
}
143+
144+
@Test
145+
publicvoidtest13() {
146+
nums =newint[]{4,5,6,7,8,1,2,3};
147+
expected =4;
148+
target =8;
149+
assertEquals(expected,solution1.search(nums,target));
150+
assertEquals(expected,solution2.search(nums,target));
151+
assertEquals(expected,solution3.search(nums,target));
152+
}
153+
26154
}

0 commit comments

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