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

Commita328ac7

Browse files
author
piggy1991
committed
peak
1 parent6123720 commita328ac7

File tree

3 files changed

+175
-5
lines changed

3 files changed

+175
-5
lines changed

‎binarySearch/Divide.java

Lines changed: 71 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -1,24 +1,90 @@
11
packageAlgorithms.binarySearch;
22

33
publicclassDivide {
4-
publicintdivide(intdividend,intdivisor) {
4+
publicstaticvoidmain(String[]strs) {
5+
System.out.println(divide(-2147483648, -1));
6+
}
7+
8+
publicintdivide1(intdividend,intdivisor) {
59
longa =Math.abs((long)dividend);
610

711
// ref : http://blog.csdn.net/kenden23/article/details/16986763
8-
// Note: 在这里必须先取long再abs，否则int的最小值abs后也是原值
12+
// Note: 在这里必须先取long再abs，否则int的最小值abs后也是原值
913
longb =Math.abs((long)divisor);
1014

1115
intret =0;
12-
// 这里必须是= 因为相等时也可以减
16+
// 这里必须是= 因为相等时也可以减
1317
while (a >=b) {
14-
// 判断条件是 >=
18+
// 判断条件是 >=
1519
for (longdeduce =b,cnt =1;a >=deduce;deduce <<=1,cnt <<=1) {
1620
a -=deduce;
1721
ret +=cnt;
1822
}
1923
}
2024

21-
// 获取符号位。根据除数跟被除数的关系来定
25+
// 获取符号位。根据除数跟被除数的关系来定
2226
return (dividend >0) ^ (divisor >0) ? -ret:ret;
2327
}
28+
29+
publicstaticintdivide(intdividend,intdivisor) {
30+
if (divisor ==0) {
31+
returnInteger.MAX_VALUE;
32+
}
33+
34+
// Note: 在这里必须先取long再abs，否则int的最小值abs后也是原值
35+
longdividendTmp =Math.abs((long)dividend);
36+
longdivisorTmp =Math.abs((long)divisor);
37+
38+
// bug 3: ret should use Long to avoid overflow.
39+
longret =0;
40+
// bug 2: should use dividentTmp > divisor as the while judge.
41+
while (dividendTmp >=divisorTmp) {
42+
// bug 1: should use Long for tmp.
43+
longtmp =divisorTmp;
44+
intrst =1;
45+
while(tmp <=dividendTmp) {
46+
// bug 3: the two statement should inside the while LOOP.
47+
ret +=rst;
48+
dividendTmp -=tmp;
49+
50+
tmp <<=1;
51+
rst <<=1;
52+
}
53+
}
54+
// bug 4: out of range:
55+
/*
56+
Input:-2147483648, -1
57+
Output:-2147483648
58+
Expected:2147483647
59+
*/
60+
//ret = ((dividend > 0) ^ (divisor > 0)) ? -ret: ret;
61+
ret = ((((dividend ^divisor) >>31) &1) ==1) ? -ret:ret;
62+
63+
if (ret >Integer.MAX_VALUE ||ret <Integer.MIN_VALUE) {
64+
returnInteger.MAX_VALUE;
65+
}else {
66+
return (int)ret;
67+
}
68+
}
69+
70+
publicintdivide3(intdividend,intdivisor) {
71+
longa =Math.abs((long)dividend);
72+
longb =Math.abs((long)divisor);
73+
74+
longret =0;
75+
76+
while (a >=b) {
77+
for (longtmp =b,cnt =1;a >=tmp;tmp <<=1,cnt <<=1) {
78+
ret +=cnt;
79+
a -=tmp;
80+
}
81+
}
82+
83+
ret = (((dividend ^divisor) >>31) &1) ==1 ? -ret:ret;
84+
if (ret >Integer.MAX_VALUE ||ret <Integer.MIN_VALUE) {
85+
returnInteger.MAX_VALUE;
86+
}
87+
88+
return (int)ret;
89+
}
2490
}

‎binarySearch/FindPeakElement.java

Lines changed: 66 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,66 @@
1+
packageAlgorithms.binarySearch;
2+
3+
publicclassFindPeakElement {
4+
publicintfindPeakElement1(int[]num) {
5+
if (num ==null) {
6+
return0;
7+
}
8+
9+
if (num.length ==1) {
10+
return0;
11+
}
12+
13+
for (inti =0;i <num.length;i++) {
14+
if (i ==0) {
15+
if (num[i] >num[i +1]) {
16+
returni;
17+
}
18+
continue;
19+
}
20+
21+
if (i ==num.length -1) {
22+
if (num[i] >num[i -1]) {
23+
returni;
24+
}
25+
continue;
26+
}
27+
28+
if (num[i] >num[i +1] &&num[i] >num[i -1]) {
29+
returni;
30+
}
31+
}
32+
33+
return -1;
34+
}
35+
36+
publicintfindPeakElement(int[]num) {
37+
if (num ==null) {
38+
return0;
39+
}
40+
41+
if (num.length ==1) {
42+
return0;
43+
}
44+
45+
intl =0;
46+
intr =num.length -1;
47+
48+
while (l <r -1) {
49+
intmid =l + (r -l) /2;
50+
if (num[mid] >num[mid +1] &&num[mid] >num[mid -1]) {
51+
returnmid;
52+
}
53+
54+
if (num[mid] >num[mid -1] &&num[mid] <num[mid +1]) {
55+
// rising area. move right;
56+
l =mid;
57+
}elseif (num[mid] <num[mid -1] &&num[mid] >num[mid +1]) {
58+
r =mid;
59+
}else {
60+
l =mid;
61+
}
62+
}
63+
64+
returnnum[l] >num[r] ?l:r;
65+
}
66+
}

‎hash/Anagrams.java

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -49,4 +49,42 @@ public List<String> anagrams(String[] strs) {
4949

5050
returnret;
5151
}
52+
53+
publicstaticvoidmain(String[]strs1) {
54+
String[]strs = {"str1","str2","s1tr"};
55+
System.out.println(anagrams2(strs));
56+
}
57+
58+
publicstaticList<String>anagrams2(String[]strs) {
59+
List<String>ret =newArrayList<String>();
60+
if (strs ==null) {
61+
returnret;
62+
}
63+
64+
HashMap<String,List<String>>map =newHashMap<String,List<String>>();
65+
for (inti =0;i <strs.length;i++) {
66+
Strings =strs[i];
67+
char[]chars =s.toCharArray();
68+
69+
Arrays.sort(chars);
70+
StringsSort =newString(chars);
71+
72+
if (map.containsKey(sSort)) {
73+
map.get(sSort).add(s);
74+
}else {
75+
List<String>list =newArrayList<String>();
76+
list.add(s);
77+
map.put(sSort,list);
78+
}
79+
}
80+
81+
for (Map.Entry<String,List<String>>entry:map.entrySet()) {
82+
List<String>list =entry.getValue();
83+
if (list.size() >1) {
84+
ret.addAll(list);
85+
}
86+
}
87+
88+
returnret;
89+
}
5290
}

0 commit comments

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