Skip to content

Commit c6fb45d

Browse files
coderbruiscoderbruis
committed
Add
1 parent c33ccd1 commit c6fb45d

6 files changed

Lines changed: 379 additions & 31 deletions

File tree

‎src/main/java/com/bruis/algorithminjava/algorithm/leetcode/TwoSum.java‎

Lines changed: 90 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,90 @@
1+
package com.bruis.algorithminjava.algorithm.leetcode;
2+
3+
import java.util.HashMap;
4+
import java.util.Map;
5+
6+
/**
7+
* @Description
8+
* @Author luohaiyang
9+
* @Date 2022/4/28
10+
*/
11+
public class TwoSum {
12+
public int[] twoSum(int[] nums, int target) {
13+
// 暴力破解法
14+
// return forceSolution(nums, target);
15+
return optimizeSolution01(nums, target);
16+
}
17+
18+
/**
19+
* 对optimizeSolution01进行优化，少进行一次for循环
20+
* 时间复杂度: O(n)
21+
* 空间复杂度：O(n)
22+
* @param nums
23+
* @param target
24+
* @return
25+
*/
26+
private int[] optimizeSolution02(int[] nums, int target) {
27+
int n = nums.length;
28+
Map<Integer, Integer> arrayMap = new HashMap<>();
29+
for (int i = 0; i < n; i++) {
30+
int num = nums[i];
31+
if (arrayMap.containsKey(target - num)) {
32+
return new int[]{arrayMap.get(target - num), i};
33+
}
34+
arrayMap.put(num, i);
35+
}
36+
return new int[0];
37+
}
38+
39+
/**
40+
* 借助jdk hashmap，
41+
* 时间复杂度: O(n)
42+
* 空间复杂度：O(n)
43+
* @param nums
44+
* @param target
45+
* @return
46+
*/
47+
private int[] optimizeSolution01(int[] nums, int target) {
48+
int n = nums.length;
49+
Map<Integer, Integer> arrayMap = new HashMap<>();
50+
for (int i = 0; i < n; i++) {
51+
int num = nums[i];
52+
int targetVal = target - num;
53+
arrayMap.put(targetVal, i);
54+
}
55+
for (int i = 0; i < n; i++) {
56+
int num = nums[i];
57+
if (arrayMap.containsKey(num)) {
58+
int index = arrayMap.get(num);
59+
if (index > i) {
60+
return new int[]{i, index};
61+
} else {
62+
return new int[]{index, i};
63+
}
64+
}
65+
}
66+
return new int[0];
67+
}
68+
69+
/**
70+
* 暴力破解法
71+
* 时间复杂度：o(n^2)
72+
* 空间复杂度：O(n)
73+
* @param nums
74+
* @param target
75+
* @return
76+
*/
77+
private int[] forceSolution(int[] nums, int target) {
78+
int n = nums.length;
79+
for (int i = 0; i < n; i++) {
80+
int num = nums[i];
81+
int val = target - num;
82+
for (int j = i + 1; j < n; j++) {
83+
if (nums[j] == val) {
84+
return new int[]{i, j};
85+
}
86+
}
87+
}
88+
return new int[0];
89+
}
90+
}

‎src/main/java/com/bruis/algorithminjava/algorithm/leetcode/TwoSumII.java‎

Lines changed: 62 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,62 @@
1+
package com.bruis.algorithminjava.algorithm.leetcode;
2+
3+
/**
4+
* @Description
5+
* @Author luohaiyang
6+
* @Date 2022/4/28
7+
*/
8+
public class TwoSumII {
9+
public int[] twoSum(int[] numbers, int target) {
10+
return twoPointer(numbers, target);
11+
}
12+
13+
/**
14+
* 双指针
15+
* 时间复杂度：O(n)
16+
* 空间复杂度：O(1)
17+
* @param numbers
18+
* @param target
19+
* @return
20+
*/
21+
private int[] twoPointer(int[] numbers, int target) {
22+
int n = numbers.length;
23+
if (n < 2) {
24+
return numbers;
25+
}
26+
int i = 0, j = n - 1;
27+
while (i < j) {
28+
if (numbers[i] + numbers[j] == target) {
29+
return new int[]{i + 1, j + 1};
30+
}
31+
if (numbers[i] + numbers[j] > target) {
32+
j--;
33+
} else {
34+
i++;
35+
}
36+
}
37+
return new int[0];
38+
}
39+
40+
/**
41+
* 暴力法：
42+
* 时间复杂度：O(n^2)
43+
* 空间复杂度：O(1)
44+
* @param numbers
45+
* @param target
46+
* @return
47+
*/
48+
private int[] forceSolution(int[] numbers, int target) {
49+
int n = numbers.length;
50+
if (n < 2) {
51+
return numbers;
52+
}
53+
for (int i = 0; i < n; i++) {
54+
for (int j = i + 1; j < n; j++) {
55+
if (numbers[i] + numbers[j] == target) {
56+
return new int[]{i + 1, j + 1};
57+
}
58+
}
59+
}
60+
return new int[0];
61+
}
62+
}

‎src/main/java/com/bruis/algorithminjava/algorithm/leetcode/array/IsPalindrome.java‎

Lines changed: 1 addition & 28 deletions
Original file line numberDiff line numberDiff line change
@@ -12,34 +12,7 @@
1212
* @author LuoHaiYang
1313
*/
1414
public class IsPalindrome {
15-
public boolean isPalindrome(String s) {
16-
if (s.equals("") || s == null) {
17-
return false;
18-
}
19-
String lowerCase = s.toLowerCase();
20-
char[] chars = lowerCase.toCharArray();
21-
22-
int left = 0, right = chars.length - 1;
23-
24-
// a 97 z 97+26=125
25-
26-
while (left <= right) {
27-
while (chars[left] < 97 || chars[left] > 125) {
28-
left++;
29-
}
30-
while (chars[right] < 97 || chars[right] > 125) {
31-
right--;
32-
}
33-
if (chars[left] != chars[right]) {
34-
return false;
35-
}
36-
left++;
37-
right--;
38-
}
39-
return true;
40-
}
41-
42-
public boolean isPalindrome2(String str) {
15+
public boolean isPalindrome(String str) {
4316
int head = 0, tail = str.length() - 1;
4417
char a, b;
4518
while(head < tail) {

‎src/main/java/com/bruis/algorithminjava/algorithm/leetcode/array/MaximumGap.java‎

Lines changed: 101 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,7 @@
11
package com.bruis.algorithminjava.algorithm.leetcode.array;
22

3+
import java.util.Arrays;
4+
35
/**
46
* 最大间距
57
*
@@ -8,6 +10,102 @@
810
* @author LuoHaiYang
911
*/
1012
public class MaximumGap {
13+
14+
/**
15+
* 基于桶排序
16+
* 时间复杂度：O(N)
17+
* 空间复杂度：O(N)
18+
* @param nums
19+
* @return
20+
*/
21+
public int maximumGapOptimize2(int[] nums) {
22+
if (nums.length < 2) return 0;
23+
int len = nums.length;
24+
25+
// 找出最大值和最小值 为了方便后面确定桶的数量
26+
int max = -1, min = Integer.MAX_VALUE;
27+
for (int i = 0; i < len; i++) {
28+
max = Math.max(nums[i], max);
29+
min = Math.min(nums[i], min);
30+
}
31+
32+
// 排除nums全部为一样的数字，nums = [1,1,1,1,1,1];
33+
if (max - min == 0) return 0;
34+
// 用于存放每个桶的最大值
35+
int[] bucketMin = new int[len - 1];
36+
// 用于存放每个桶的最小值
37+
int[] bucketMax = new int[len - 1];
38+
Arrays.fill(bucketMax, -1);
39+
Arrays.fill(bucketMin, Integer.MAX_VALUE);
40+
41+
// 确定桶的间距
42+
int interval = (int)Math.ceil((double)(max - min) / (len - 1));
43+
for (int i = 0; i < len; i++) {
44+
// 找到每一个值所对应桶的索引
45+
int index = (nums[i] - min) / interval;
46+
if (nums[i] == min || nums[i] == max) continue;
47+
// 更新每个桶的数据
48+
bucketMax[index] = Math.max(bucketMax[index], nums[i]);
49+
bucketMin[index] = Math.min(bucketMin[index], nums[i]);
50+
}
51+
52+
// maxGap 表示桶之间最大的差距
53+
int maxGap = 0;
54+
// preMax 表示前一个桶的最大值
55+
int preMax = min;
56+
for (int i = 0; i < len - 1; i++) {
57+
// 表示某一个桶为空
58+
// 但凡某一个桶不为空，都会在前面的数据中更新掉bucketMax的值
59+
if (bucketMax[i] == -1) continue;
60+
maxGap = Math.max(bucketMin[i] - preMax, maxGap);
61+
preMax = bucketMax[i];
62+
}
63+
// [1,10000000]
64+
maxGap = Math.max(maxGap, max - preMax);
65+
return maxGap;
66+
}
67+
68+
/**
69+
* 基数排序：
70+
* 时间复杂度：O(N)
71+
* 空间复杂度：O(N)
72+
* @param nums
73+
* @return
74+
*/
75+
public int maximumGapOptimize(int[] nums) {
76+
int n = nums.length;
77+
if (n < 2) {
78+
return 0;
79+
}
80+
long exp = 1;
81+
int[] buf = new int[n];
82+
int maxVal = Arrays.stream(nums).max().getAsInt();
83+
84+
while (maxVal >= exp) {
85+
int[] cnt = new int[10];
86+
for (int i = 0; i < n; i++) {
87+
int digit = (nums[i] / (int) exp) % 10;
88+
cnt[digit]++;
89+
}
90+
for (int i = 1; i < 10; i++) {
91+
cnt[i] += cnt[i - 1];
92+
}
93+
for (int i = n - 1; i >= 0; i--) {
94+
int digit = (nums[i] / (int) exp) % 10;
95+
buf[cnt[digit] - 1] = nums[i];
96+
cnt[digit]--;
97+
}
98+
System.arraycopy(buf, 0, nums, 0, n);
99+
exp *= 10;
100+
}
101+
102+
int ret = 0;
103+
for (int i = 1; i < n; i++) {
104+
ret = Math.max(ret, nums[i] - nums[i - 1]);
105+
}
106+
return ret;
107+
}
108+
11109
public int maximumGap(int[] nums) {
12110
if (nums == null || nums.length < 2) {
13111
return 0;
@@ -54,7 +152,7 @@ private void quickSort3ways(int[] nums, int left, int right) {
54152
}
55153

56154
private int max(int i, int j) {
57-
return i > j ? i : j;
155+
return Math.max(i, j);
58156
}
59157

60158
private void swap(int[] nums, int i, int j) {
@@ -66,6 +164,7 @@ private void swap(int[] nums, int i, int j) {
66164
public static void main(String[] args) {
67165
int[] test = {3,6,9,1,20,15,11,30,31};
68166
MaximumGap maximumGap = new MaximumGap();
69-
System.out.println(maximumGap.maximumGap(test));
167+
// System.out.println(maximumGap.maximumGap(test));
168+
System.out.println(maximumGap.maximumGapOptimize2(test));
70169
}
71170
}

‎src/main/java/com/bruis/algorithminjava/algorithm/sort/BucketSort.java‎

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,6 @@
11
package com.bruis.algorithminjava.algorithm.sort;
22

3+
import java.util.Arrays;
34
import java.util.LinkedList;
45
import java.util.List;
56

@@ -50,6 +51,7 @@ public int[] doSort(int[] arr) {
5051

5152
public static void main(String[] args) {
5253
BucketSort bucketSort = new BucketSort(10);
53-
bucketSort.doSort(new int[]{4,1,3,2,6,9,9});
54+
int[] sort = bucketSort.doSort(new int[]{4, 1, 3, 2, 20, 6, 9, 9, 21, 19});
55+
System.out.println(Arrays.toString(sort));
5456
}
5557
}

0 commit comments

Comments
 (0)