Skip to content

Commit 54042d4

Browse files
dunwudunwu
committed
更新刷题
1 parent 1964a4d commit 54042d4

28 files changed

+1040
-365
lines changed

‎codes/algorithm/pom.xml‎

Lines changed: 53 additions & 48 deletions
Original file line numberDiff line numberDiff line change
@@ -1,55 +1,60 @@
11
<?xml version="1.0" encoding="UTF-8"?>
22
<project xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns="http://maven.apache.org/POM/4.0.0"
3-
xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
4-
<modelVersion>4.0.0</modelVersion>
3+
xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
4+
<modelVersion>4.0.0</modelVersion>
55

6-
<parent>
7-
<groupId>io.github.dunwu</groupId>
8-
<artifactId>dunwu-parent</artifactId>
9-
<version>1.0.8</version>
10-
</parent>
6+
<groupId>io.github.dunwu.algorithm</groupId>
7+
<artifactId>algorithm</artifactId>
8+
<version>1.0.0</version>
9+
<packaging>jar</packaging>
10+
<name>算法示例</name>
11+
<description>数据示例源码</description>
1112

12-
<groupId>io.github.dunwu.algorithm</groupId>
13-
<artifactId>algorithm</artifactId>
14-
<packaging>jar</packaging>
15-
<name>算法示例</name>
16-
<description>数据示例源码</description>
13+
<properties>
14+
<project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
15+
<java.version>1.8</java.version>
16+
<maven.compiler.source>${java.version}</maven.compiler.source>
17+
<maven.compiler.target>${java.version}</maven.compiler.target>
18+
</properties>
1719

18-
<properties>
19-
<project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
20-
<java.version>1.8</java.version>
21-
<maven.compiler.source>${java.version}</maven.compiler.source>
22-
<maven.compiler.target>${java.version}</maven.compiler.target>
23-
</properties>
20+
<dependencies>
21+
<dependency>
22+
<groupId>cn.hutool</groupId>
23+
<artifactId>hutool-all</artifactId>
24+
<version>5.8.29</version>
25+
</dependency>
26+
<dependency>
27+
<groupId>org.projectlombok</groupId>
28+
<artifactId>lombok</artifactId>
29+
<version>1.18.36</version>
30+
<scope>provided</scope>
31+
</dependency>
32+
<dependency>
33+
<groupId>ch.qos.logback</groupId>
34+
<artifactId>logback-classic</artifactId>
35+
<version>1.2.9</version>
36+
</dependency>
37+
<dependency>
38+
<groupId>org.junit.jupiter</groupId>
39+
<artifactId>junit-jupiter</artifactId>
40+
<version>5.8.2</version>
41+
</dependency>
42+
<dependency>
43+
<groupId>org.assertj</groupId>
44+
<artifactId>assertj-core</artifactId>
45+
<version>3.26.3</version>
46+
</dependency>
47+
</dependencies>
2448

25-
<dependencies>
26-
<dependency>
27-
<groupId>cn.hutool</groupId>
28-
<artifactId>hutool-all</artifactId>
29-
</dependency>
30-
<dependency>
31-
<groupId>ch.qos.logback</groupId>
32-
<artifactId>logback-classic</artifactId>
33-
</dependency>
34-
<dependency>
35-
<groupId>org.junit.jupiter</groupId>
36-
<artifactId>junit-jupiter</artifactId>
37-
</dependency>
38-
<dependency>
39-
<groupId>org.assertj</groupId>
40-
<artifactId>assertj-core</artifactId>
41-
</dependency>
42-
</dependencies>
43-
44-
<build>
45-
<plugins>
46-
<plugin>
47-
<groupId>org.apache.maven.plugins</groupId>
48-
<artifactId>maven-javadoc-plugin</artifactId>
49-
<configuration>
50-
<doclint>none</doclint>
51-
</configuration>
52-
</plugin>
53-
</plugins>
54-
</build>
49+
<build>
50+
<plugins>
51+
<plugin>
52+
<groupId>org.apache.maven.plugins</groupId>
53+
<artifactId>maven-javadoc-plugin</artifactId>
54+
<configuration>
55+
<doclint>none</doclint>
56+
</configuration>
57+
</plugin>
58+
</plugins>
59+
</build>
5560
</project>

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/array/丑数I.java‎

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
package io.github.dunwu.algorithm.array;
2+
3+
import org.junit.jupiter.api.Assertions;
4+
5+
import java.util.HashSet;
6+
import java.util.Set;
7+
8+
/**
9+
* <a href="https://leetcode.cn/problems/ugly-number/description/">263. 丑数</a>
10+
*
11+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
12+
* @date 2025-01-24
13+
*/
14+
public class 丑数I {
15+
16+
public static void main(String[] args) {
17+
Assertions.assertTrue(isUgly(6));
18+
Assertions.assertTrue(isUgly(1));
19+
Assertions.assertFalse(isUgly(14));
20+
}
21+
22+
public static boolean isUgly(int n) {
23+
while (n <= 0) return false;
24+
while (n % 2 == 0) n /= 2;
25+
while (n % 3 == 0) n /= 3;
26+
while (n % 5 == 0) n /= 5;
27+
return n == 1;
28+
}
29+
30+
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/array/丑数II.java‎

Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
1+
package io.github.dunwu.algorithm.array;
2+
3+
import org.junit.jupiter.api.Assertions;
4+
5+
/**
6+
* <a href="https://leetcode.cn/problems/ugly-number-ii/description/">264. 丑数II</a>
7+
*
8+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
9+
* @date 2025-01-24
10+
*/
11+
public class 丑数II {
12+
13+
public static void main(String[] args) {
14+
Assertions.assertEquals(12, nthUglyNumber(10));
15+
Assertions.assertEquals(1, nthUglyNumber(1));
16+
}
17+
18+
public static int nthUglyNumber(int n) {
19+
if (n == 1) {
20+
return 1;
21+
}
22+
23+
// 可以理解为三个指向有序链表头结点的指针
24+
int p2 = 1, p3 = 1, p5 = 1;
25+
// 可以理解为三个有序链表的头节点的值
26+
int product2 = 1, product3 = 1, product5 = 1;
27+
// 可以理解为最终合并的有序链表（结果链表）
28+
int[] ugly = new int[n + 1];
29+
// 可以理解为结果链表上的指针
30+
int u = 1;
31+
32+
while (u <= n) {
33+
int min = Math.min(product2, Math.min(product3, product5));
34+
ugly[u++] = min;
35+
if (min == product2) {
36+
product2 = 2 * ugly[p2];
37+
p2++;
38+
}
39+
if (min == product3) {
40+
product3 = 3 * ugly[p3];
41+
p3++;
42+
}
43+
if (min == product5) {
44+
product5 = 5 * ugly[p5];
45+
p5++;
46+
}
47+
}
48+
return ugly[n];
49+
}
50+
51+
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/array/丑数III.java‎

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
package io.github.dunwu.algorithm.array;
2+
3+
import org.junit.jupiter.api.Assertions;
4+
5+
/**
6+
* <a href="https://leetcode.cn/problems/ugly-number-ii/description/">264. 丑数II</a>
7+
*
8+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
9+
* @date 2025-01-24
10+
*/
11+
public class 丑数III {
12+
13+
public static void main(String[] args) {
14+
Assertions.assertEquals(4, nthUglyNumber(3, 2, 3, 5));
15+
Assertions.assertEquals(6, nthUglyNumber(4, 2, 3, 4));
16+
Assertions.assertEquals(10, nthUglyNumber(5, 2, 11, 13));
17+
Assertions.assertEquals(1999999984, nthUglyNumber(1000000000, 2, 217983653, 336916467));
18+
}
19+
20+
public static int nthUglyNumber(int n, int a, int b, int c) {
21+
int p = 1;
22+
int vA = a, vB = b, vC = c;
23+
long min = Integer.MAX_VALUE;
24+
while (p <= n) {
25+
min = Math.min(vA, Math.min(vB, vC));
26+
if (min == vA) {
27+
vA += a;
28+
}
29+
if (min == vB) {
30+
vB += b;
31+
}
32+
if (min == vC) {
33+
vC += c;
34+
}
35+
p++;
36+
}
37+
return (int) min;
38+
}
39+
40+
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/array/二进制求和.java‎

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
package io.github.dunwu.algorithm.array;
2+
3+
import org.junit.jupiter.api.Assertions;
4+
5+
/**
6+
* <a href="https://leetcode.cn/problems/add-binary/description/">67. 二进制求和</a>
7+
*
8+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
9+
* @date 2025-01-21
10+
*/
11+
public class 二进制求和 {
12+
13+
public static void main(String[] args) {
14+
Assertions.assertEquals("100", addBinary("11", "1"));
15+
Assertions.assertEquals("10101", addBinary("1010", "1011"));
16+
}
17+
18+
public static String addBinary(String a, String b) {
19+
20+
if (a == null || a.length() == 0) return b;
21+
if (b == null || b.length() == 0) return a;
22+
23+
char[] arrA = a.toCharArray();
24+
char[] arrB = b.toCharArray();
25+
StringBuilder sb = new StringBuilder();
26+
int carry = 0;
27+
int i = arrA.length - 1, j = arrB.length - 1;
28+
while (i >= 0 || j >= 0) {
29+
int value = carry;
30+
if (i >= 0) {
31+
value += arrA[i--] - '0';
32+
}
33+
if (j >= 0) {
34+
value += arrB[j--] - '0';
35+
}
36+
carry = value / 2;
37+
value = value % 2;
38+
sb.append(value);
39+
}
40+
if (carry != 0) {
41+
sb.append(carry);
42+
}
43+
return sb.reverse().toString();
44+
}
45+
46+
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/array/删除排序数组中的重复项.java‎

Lines changed: 2 additions & 38 deletions
Original file line numberDiff line numberDiff line change
@@ -1,46 +1,10 @@
11
package io.github.dunwu.algorithm.array;
22

3-
// 【删除排序数组中的重复项】
4-
5-
//
6-
// 给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
7-
//
8-
// 不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
9-
//
10-
// 示例 1:
11-
//
12-
// 给定数组 nums = [1,1,2],
13-
//
14-
// 函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
15-
//
16-
// 你不需要考虑数组中超出新长度后面的元素。
17-
// 示例 2:
18-
//
19-
// 给定 nums = [0,0,1,1,1,2,2,3,3,4],
20-
//
21-
// 函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
22-
//
23-
// 你不需要考虑数组中超出新长度后面的元素。
24-
// 说明:
25-
//
26-
// 为什么返回数值是整数，但输出的答案是数组呢?
27-
//
28-
// 请注意，输入数组是以“引用”方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
29-
//
30-
// 你可以想象内部操作如下:
31-
//
32-
// // nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
33-
// int len = removeDuplicates(nums);
34-
//
35-
// // 在函数里修改输入数组对于调用者是可见的。
36-
// // 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
37-
// for (int i = 0; i < len; i++) {
38-
// print(nums[i]);
39-
// }
40-
413
import org.junit.jupiter.api.Assertions;
424

435
/**
6+
* <a href="https://leetcode.cn/problems/remove-duplicates-from-sorted-array/description/">26. 删除有序数组中的重复项</a>
7+
*
448
* @author Zhang Peng
459
* @since 2018-11-05
4610
*/

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/array/有序矩阵中第K小的元素.java‎

Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
1+
package io.github.dunwu.algorithm.array;
2+
3+
import org.junit.jupiter.api.Assertions;
4+
5+
/**
6+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
7+
* @date 2025-01-21
8+
*/
9+
public class 有序矩阵中第K小的元素 {
10+
11+
public static void main(String[] args) {
12+
13+
int[][] matrix = { { 1, 5, 9 }, { 10, 11, 13 }, { 12, 13, 15 } };
14+
Assertions.assertEquals(13, kthSmallest(matrix, 8));
15+
16+
int[][] matrix2 = { { -5 } };
17+
Assertions.assertEquals(-5, kthSmallest(matrix2, 1));
18+
19+
int[][] matrix3 = { { 1, 2 }, { 1, 3 } };
20+
Assertions.assertEquals(1, kthSmallest(matrix3, 2));
21+
22+
int[][] matrix4 = { { 1, 2, 3 }, { 1, 2, 3 }, { 1, 2, 3 } };
23+
Assertions.assertEquals(3, kthSmallest(matrix4, 8));
24+
}
25+
26+
public static int kthSmallest(int[][] matrix, int n) {
27+
int row = matrix.length;
28+
if (row == 1) {
29+
return matrix[0][n - 1];
30+
}
31+
int i = 1;
32+
int[] arr = matrix[0];
33+
while (i < row) {
34+
arr = merge(matrix[i], arr);
35+
i++;
36+
}
37+
return arr[n - 1];
38+
}
39+
40+
public static int[] merge(int[] arr1, int[] arr2) {
41+
int i = 0, j = 0, k = 0;
42+
int[] merge = new int[arr1.length + arr2.length];
43+
while (i < arr1.length && j < arr2.length) {
44+
if (arr1[i] <= arr2[j]) {
45+
merge[k++] = arr1[i++];
46+
} else {
47+
merge[k++] = arr2[j++];
48+
}
49+
}
50+
if (i < arr1.length) {
51+
while (i < arr1.length) {
52+
merge[k++] = arr1[i++];
53+
}
54+
}
55+
if (j < arr2.length) {
56+
while (j < arr2.length) {
57+
merge[k++] = arr2[j++];
58+
}
59+
}
60+
return merge;
61+
}
62+
63+
}

0 commit comments

Comments
 (0)