Skip to content

Commit d9e6ecf

Browse files
coderbruiscoderbruis
committed
first add.
1 parent 642c6f1 commit d9e6ecf

13 files changed

Lines changed: 1074 additions & 0 deletions

File tree

‎.gitignore‎

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
HELP.md
2+
target/
3+
!.mvn/wrapper/maven-wrapper.jar
4+
!**/src/main/**
5+
!**/src/test/**
6+
7+
### STS ###
8+
.apt_generated
9+
.classpath
10+
.factorypath
11+
.project
12+
.settings
13+
.springBeans
14+
.sts4-cache
15+
16+
### IntelliJ IDEA ###
17+
.idea
18+
*.iws
19+
*.iml
20+
*.ipr
21+
22+
### NetBeans ###
23+
/nbproject/private/
24+
/nbbuild/
25+
/dist/
26+
/nbdist/
27+
/.nb-gradle/
28+
build/
29+
30+
### VS Code ###
31+
.vscode/

‎pom.xml‎

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
<?xml version="1.0" encoding="UTF-8"?>
2+
<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
3+
xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 https://maven.apache.org/xsd/maven-4.0.0.xsd">
4+
<groupId>com.bruis</groupId>
5+
<artifactId>algorithminjava</artifactId>
6+
<version>1-SNAPSHOT</version>
7+
<name>algorithminjava</name>
8+
<description>AlgorithmInJava</description>
9+
10+
<build>
11+
<plugins>
12+
<plugin>
13+
<groupId>org.apache.maven.plugins</groupId>
14+
<artifactId>maven-compiler-plugin</artifactId>
15+
<configuration>
16+
<source>8</source>
17+
<target>8</target>
18+
</configuration>
19+
</plugin>
20+
</plugins>
21+
</build>
22+
23+
</project>

‎src/main/java/com/bruis/algorithminjava/algorithm/MaximumProductSubarray.java‎

Lines changed: 69 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,69 @@
1+
package com.bruis.algorithminjava.algorithm;
2+
3+
/**
4+
* @author LuoHaiYang
5+
* @Date 2020-05-18
6+
*
7+
* url: https://leetcode-cn.com/problems/maximum-product-subarray/
8+
*
9+
*/
10+
public class MaximumProductSubarray {
11+
12+
13+
/**
14+
* 问题1 ：算法没有包括数组头部元素的比较；
15+
* 问题2 : 数组没有考虑到每个元素本身大小的比较；
16+
*
17+
*
18+
* @param nums
19+
* @return
20+
*/
21+
public int maxProduct(int[] nums) {
22+
23+
// 2, 3, -2, 4, 5, 8, -1, -3, 10
24+
// [ ]
25+
//
26+
27+
int length = nums.length;
28+
29+
if (length == 1) {
30+
return nums[0];
31+
}
32+
if (length == 2) {
33+
int result = nums[0] * nums[1];
34+
int anotherResult = nums[0] > nums[1] ? nums[0] : nums[1];
35+
return result > anotherResult ? result : anotherResult;
36+
}
37+
38+
int max = nums[0] * nums[1] > nums[0] ? nums[0] * nums[1] : nums[0];
39+
40+
for (int i = 0; i < length; i++) {
41+
int[] mul = new int[length];
42+
43+
for (int j = i; j < length; j++) {
44+
mul[j] = nums[j];
45+
}
46+
47+
for (int j = i + 1; j < length; j++) {
48+
int result = nums[j] * mul[j-1];
49+
//mul[j] = mul[j] > result ? mul[j] : result;
50+
mul[j] = result;
51+
if (nums[j] > max) {
52+
max = nums[j];
53+
}
54+
if (result > max) {
55+
max = result;
56+
}
57+
}
58+
}
59+
60+
return max;
61+
}
62+
63+
public static void main(String[] args) {
64+
MaximumProductSubarray maximumProductSubarray = new MaximumProductSubarray();
65+
int[] nums = {2, -1, 1, 1};
66+
//int[] nums = {2, 3, -2, 4, 5, 8, -1, -3, 10};
67+
System.out.println(maximumProductSubarray.maxProduct(nums));
68+
}
69+
}

‎src/main/java/com/bruis/algorithminjava/algorithm/MinStack.java‎

Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
1+
package com.bruis.algorithminjava.algorithm;
2+
3+
import java.util.Stack;
4+
5+
/**
6+
* @author LuoHaiYang
7+
*
8+
* @Date 2020.05.13
9+
*
10+
* url: https://leetcode-cn.com/problems/min-stack/
11+
*
12+
*
13+
*/
14+
public class MinStack {
15+
16+
/**
17+
* 问题：
18+
* 1. 用什么基础数据结构来存储数据？ 普遍解法都是通过已有数据结构stack来解决
19+
* 2. 如何自己实现一个栈结构？
20+
*/
21+
22+
/** initialize your data structure here. */
23+
private Stack<Integer> stack;
24+
private Stack<Integer> minStack;
25+
26+
public MinStack() {
27+
stack = new Stack<>();
28+
minStack = new Stack<>();
29+
}
30+
31+
public void push(int x) {
32+
stack.push(x);
33+
if (!minStack.isEmpty()) {
34+
int top = minStack.peek();
35+
//小于的时候才入栈
36+
if (x <= top) {
37+
minStack.push(x);
38+
}
39+
}else{
40+
minStack.push(x);
41+
}
42+
}
43+
44+
public void pop() {
45+
int pop = stack.pop();
46+
47+
int top = minStack.peek();
48+
//等于的时候再出栈
49+
if (pop == top) {
50+
minStack.pop();
51+
}
52+
53+
}
54+
55+
public int top() {
56+
return stack.peek();
57+
}
58+
59+
public int getMin() {
60+
return minStack.peek();
61+
}
62+
63+
}

‎src/main/java/com/bruis/algorithminjava/algorithm/SubarraySumEqualsK.java‎

Lines changed: 140 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,140 @@
1+
package com.bruis.algorithminjava.algorithm;
2+
3+
import java.util.HashMap;
4+
import java.util.Map;
5+
6+
/**
7+
* @author LuoHaiYang
8+
*
9+
* @Date 2020-05-15
10+
* 560. Subarray Sum Equals K
11+
* url: https://leetcode-cn.com/problems/subarray-sum-equals-k/
12+
*
13+
*
14+
*/
15+
public class SubarraySumEqualsK {
16+
/**
17+
* O (n^3)
18+
* @param nums
19+
* @param k
20+
* @return
21+
*/
22+
public int subarraySum01(int[] nums, int k) {
23+
int len = nums.length;
24+
int count = 0;
25+
for (int left = 0; left < len; left++) {
26+
for (int right = left; right < len; right++) {
27+
int sum = 0;
28+
for (int i = left; i <= right; i++) {
29+
sum += nums[i];
30+
}
31+
if (sum == k) {
32+
count++;
33+
}
34+
}
35+
}
36+
return count;
37+
}
38+
39+
/**
40+
* 1. 欠考虑情况
41+
* ① 单个元素作为一个子数组；
42+
* ② 所有元素值都相同的情况；
43+
*
44+
* 时间复杂：O (n^2)
45+
*
46+
* @param nums
47+
* @param k
48+
* @return
49+
*/
50+
public int subarraySum02(int[] nums, int k) {
51+
int length = nums.length;
52+
int count = 0;
53+
54+
// 0, 0, 0, 0
55+
// l
56+
// r
57+
58+
for (int left = 0; left < length; left++) {
59+
int right = left + 1;
60+
int sums = nums[left];
61+
if (sums == k) {
62+
count++;
63+
}
64+
while (right < length) {
65+
sums += nums[right++];
66+
if (sums == k) {
67+
count++;
68+
}
69+
}
70+
}
71+
return count;
72+
}
73+
74+
/**
75+
* 前缀和
76+
*
77+
*
78+
* @param nums
79+
* @param k
80+
* @return
81+
*/
82+
public int subarraySum03(int[] nums, int k) {
83+
int length = nums.length;
84+
85+
int[] preSum = new int[length + 1];
86+
preSum[0] = 0;
87+
for (int i = 0; i < length; i++) {
88+
preSum[i + 1] = preSum[i] + nums[i];
89+
}
90+
91+
// 1, 2, 3, 4
92+
// 0 1 3 6 10
93+
// l
94+
// r
95+
96+
int count = 0;
97+
for (int left = 0; left < length; left++) {
98+
int right = left + 1;
99+
while (right <= length) {
100+
if (preSum[right++] - preSum[left] == k) {
101+
count++;
102+
}
103+
}
104+
}
105+
return count;
106+
}
107+
108+
/**
109+
*
110+
* O (n)
111+
* 前缀和 + 哈希表
112+
*
113+
* @param nums
114+
* @param k
115+
* @return
116+
*/
117+
public int subarraySum04(int[] nums, int k) {
118+
Map<Integer, Integer> preSumFreq = new HashMap<>();
119+
preSumFreq.put(0, 1);
120+
121+
int preSum = 0;
122+
int count = 0;
123+
for (int num : nums) {
124+
preSum += num;
125+
if (preSumFreq.containsKey(preSum - k)) {
126+
count += preSumFreq.get(preSum - k);
127+
}
128+
preSumFreq.put(preSum, preSumFreq.getOrDefault(preSum, 0) + 1);
129+
}
130+
return count;
131+
}
132+
133+
public static void main(String[] args) {
134+
// 1. 可以进行排序不？
135+
SubarraySumEqualsK subarraySumEqualsK = new SubarraySumEqualsK();
136+
//int[] nums = {0,0,0,0,0,0,0,0,0,0};
137+
int[] nums = {1, 2, 3, 4};
138+
System.out.println(subarraySumEqualsK.subarraySum04(nums, 5));
139+
}
140+
}

0 commit comments

Comments
 (0)