Skip to content

Commit f835f67

Browse files
author
chenweijie
committed
cherry-pick提交
1 parent f561cb5 commit f835f67

File tree

10 files changed

+479
-0
lines changed

10 files changed

+479
-0
lines changed

‎src/main/java/com/chen/algorithm/study/test13/Solution.java

Lines changed: 81 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,81 @@
1+
package com.chen.algorithm.study.test13;
2+
3+
import org.junit.Test;
4+
5+
/**
6+
* @author : chen weijie
7+
* @Date: 2019-09-04 23:18
8+
*/
9+
public class Solution {
10+
11+
12+
public int romanToInt(String s) {
13+
14+
if (s == null || "".equals(s)) {
15+
return 0;
16+
}
17+
18+
char[] chars = s.toCharArray();
19+
Integer[] integers = new Integer[chars.length];
20+
21+
for (int i = 0; i < chars.length; i++) {
22+
23+
switch (chars[i]) {
24+
case 'I':
25+
integers[i] = 1;
26+
continue;
27+
case 'V':
28+
integers[i] = 5;
29+
continue;
30+
case 'X':
31+
integers[i] = 10;
32+
continue;
33+
case 'L':
34+
integers[i] = 50;
35+
continue;
36+
case 'C':
37+
integers[i] = 100;
38+
continue;
39+
case 'D':
40+
integers[i] = 500;
41+
continue;
42+
case 'M':
43+
integers[i] = 1000;
44+
continue;
45+
default:
46+
}
47+
}
48+
49+
50+
int firstValue = 0;
51+
int nextValue = 0;
52+
int sum = 0;
53+
54+
55+
for (int i = 0; i < integers.length; i++) {
56+
firstValue = integers[i];
57+
58+
if (i == s.length() - 1) {
59+
sum += firstValue;
60+
} else {
61+
nextValue = integers[i + 1];
62+
if (firstValue >= nextValue) {
63+
sum += firstValue;
64+
} else {
65+
sum -= firstValue;
66+
}
67+
}
68+
69+
70+
}
71+
return sum;
72+
}
73+
74+
75+
@Test
76+
public void testCase() {
77+
System.out.println(romanToInt("IV"));
78+
}
79+
80+
81+
}

‎src/main/java/com/chen/algorithm/study/test14/Solution.java

Lines changed: 64 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,64 @@
1+
package com.chen.algorithm.study.test14;
2+
3+
import org.junit.Test;
4+
5+
import java.util.HashMap;
6+
import java.util.Map;
7+
8+
/**
9+
*
10+
* 错误
11+
*
12+
*
13+
* @author : chen weijie
14+
* @Date: 2019-09-05 00:17
15+
*/
16+
public class Solution {
17+
18+
19+
public String longestCommonPrefix(String[] strs) {
20+
21+
if (strs == null || strs.length == 0) {
22+
23+
return "";
24+
}
25+
26+
27+
String result;
28+
Map<String, String> map = new HashMap<>();
29+
30+
loop:
31+
for (int j = 0; ; j++) {
32+
for (int i = 0; i < strs.length; i++) {
33+
if (strs[i] == null || "".equals(strs[i])) {
34+
return "";
35+
}
36+
37+
if (i == 0) {
38+
map.put(strs[i].substring(0, j), strs[i].substring(0, j));
39+
continue;
40+
}
41+
if (!map.containsKey(strs[i].substring(0, j))) {
42+
result = strs[i].substring(0, j - 1);
43+
break loop;
44+
}
45+
}
46+
}
47+
return result;
48+
49+
}
50+
51+
@Test
52+
public void testCase(){
53+
54+
55+
String [] strings = {""};
56+
57+
System.out.println(longestCommonPrefix(strings));
58+
59+
60+
61+
}
62+
63+
64+
}

‎src/main/java/com/chen/algorithm/study/test14/Solution2.java

Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
package com.chen.algorithm.study.test14;
2+
3+
import org.junit.Test;
4+
5+
/**
6+
* @author : chen weijie
7+
* @Date: 2019-09-05 00:55
8+
*/
9+
public class Solution2 {
10+
11+
12+
public String longestCommonPrefix(String[] strs) {
13+
14+
if (strs.length == 0) {
15+
return "";
16+
}
17+
18+
String prefix = strs[0];
19+
for (int i = 1; i < strs.length; i++) {
20+
while (!strs[i].startsWith(prefix)) {
21+
prefix = prefix.substring(0, prefix.length() - 1);
22+
if (prefix.isEmpty()) {
23+
return "";
24+
}
25+
}
26+
}
27+
return prefix;
28+
}
29+
30+
31+
@Test
32+
public void testCase(){
33+
34+
35+
String [] strings = {"flower","flow","flight"};
36+
37+
System.out.println(longestCommonPrefix(strings));
38+
39+
40+
41+
}
42+
43+
44+
45+
46+
47+
}

‎src/main/java/com/chen/algorithm/study/test4/Solution.java

Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
1+
package com.chen.algorithm.study.test4;
2+
3+
import org.junit.Test;
4+
5+
import java.util.ArrayList;
6+
import java.util.List;
7+
8+
/**
9+
* @author : chen weijie
10+
* @Date: 2019-09-03 23:10
11+
*/
12+
public class Solution {
13+
14+
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
15+
16+
List<Integer> resultList = new ArrayList<>();
17+
18+
19+
if (nums1 == null) {
20+
for (int value : nums2) {
21+
resultList.add(value);
22+
}
23+
} else if (nums2 == null) {
24+
for (int value : nums1) {
25+
resultList.add(value);
26+
}
27+
} else {
28+
29+
30+
31+
32+
}
33+
34+
35+
int n = resultList.size();
36+
37+
38+
double result = 0d;
39+
40+
if (n % 2 == 0) {
41+
result = resultList.get(resultList.size() / 2) + (resultList.get((resultList.size() / 2) - 1)) / 2;
42+
} else {
43+
double index = resultList.size() / 2;
44+
result = resultList.get((int) Math.ceil(index));
45+
}
46+
return result;
47+
}
48+
49+
50+
@Test
51+
public void testCase() {
52+
53+
int[] nums1 = {1, 2};
54+
int[] nums2 = {3, 4};
55+
56+
double d = findMedianSortedArrays(nums1, nums2);
57+
System.out.println(d);
58+
59+
60+
}
61+
62+
63+
}

‎src/main/java/com/chen/algorithm/study/test5/Solution.java

Lines changed: 58 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,58 @@
1+
package com.chen.algorithm.study.test5;
2+
3+
import org.junit.Test;
4+
5+
/**
6+
* 中心扩展算法
7+
*
8+
* @author : chen weijie
9+
* @Date: 2019-09-03 23:58
10+
*/
11+
public class Solution {
12+
13+
14+
public String longestPalindrome(String s) {
15+
16+
if (s == null || s.length() < 1) {
17+
return "";
18+
}
19+
20+
int start = 0, end = 0;
21+
22+
23+
for (int i = 0; i < s.length(); i++) {
24+
int len1 = expandArroundCenter(s, i, i);
25+
int len2 = expandArroundCenter(s, i, i + 1);
26+
27+
int len = Math.max(len1, len2);
28+
29+
if (len > end - start) {
30+
//中间值-长度的一半
31+
start = i - (len - 1) / 2;
32+
//中间值+长度的一半
33+
end = i + len / 2;
34+
}
35+
}
36+
return s.substring(start, end + 1);
37+
}
38+
39+
40+
private int expandArroundCenter(String s, int left, int right) {
41+
42+
int L = left, R = right;
43+
while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
44+
L--;
45+
R++;
46+
}
47+
return R - L - 1;
48+
}
49+
50+
51+
52+
@Test
53+
public void testCase(){
54+
System.out.println(longestPalindrome("dcacdefd"));
55+
}
56+
57+
58+
}

‎src/main/java/com/chen/algorithm/study/test7/Solution.java

Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
package com.chen.algorithm.study.test7;
2+
3+
import org.junit.Test;
4+
5+
/**
6+
* @author : chen weijie
7+
* @Date: 2019-09-04 01:17
8+
*/
9+
public class Solution {
10+
11+
public int reverse(int x) {
12+
13+
boolean belowZero = false;
14+
Long l = Long.parseLong(x + "");
15+
if (l < 0) {
16+
l = Math.abs(l);
17+
belowZero = true;
18+
}
19+
20+
char[] chars = (l + "").toCharArray();
21+
22+
StringBuilder sb = new StringBuilder();
23+
for (int i = chars.length - 1; i >= 0; i--) {
24+
sb.append(chars[i]);
25+
}
26+
27+
Long result = Long.parseLong(sb.toString());
28+
if (result > 2147483647 || result <-2147483648) {
29+
return 0;
30+
}
31+
32+
if (!belowZero) {
33+
return result.intValue();
34+
} else {
35+
return -result.intValue();
36+
}
37+
38+
}
39+
40+
41+
@Test
42+
public void testCase() {
43+
// -2147483648~2147483647
44+
System.out.println(reverse(-2143847412));
45+
46+
}
47+
48+
49+
}

0 commit comments

Comments
 (0)