练习:杨辉三角
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int numberOfRows = 9;
int[][] yangHuiTriangle = new int[numberOfRows][];
yangHuiTriangle[0] = new int[1];
yangHuiTriangle[0][0] = 1;
for (int i = 1; i < numberOfRows; i++) {
yangHuiTriangle[i] = new int[i + 1];
for (int j = 0; j < i; j++) {
if (j == 0 || j == i - 1) {
yangHuiTriangle[i][j] = 1;
continue;
}
yangHuiTriangle[i][j] = yangHuiTriangle[i - 1][j - 1] + yangHuiTriangle[i - 1][j];
}
}
for (int[] row : yangHuiTriangle) {
for (int element : row) {
if (element == 0) continue;
System.out.print(element + " ");
}
System.out.println();
}
}
}
|
在写杨辉三角案例的时候发现了一个二维数组初始化的问题。
如果只初始化行的话, 二维的数组默认值是null
1
2
3
| int numberOfRows = 5;
int[][] yangHuiTriangle = new int[numberOfRows][];
yangHuiTriangle[0][0] = 1;
|
如果不初始化就进行赋值的话就会报错
1
2
| Exception in thread "main" java.lang.NullPointerException: Cannot store to int array because "yangHuiTriangle[0]" is null
at Main.main(Main.java:10)
|
所以必须初始化之后在进行赋值
1
2
3
4
| int numberOfRows = 5;
int[][] yangHuiTriangle = new int[numberOfRows][];
yangHuiTriangle[0] = new int[1];
yangHuiTriangle[0][0] = 1;
|
数组初始化并赋值的2种方式
1
2
3
4
5
6
| // 方式一
int[] arr = []{1,2,3,4}
//方式二
int[] arr = {1,2,3,4}
|
练习:随机赋值
创建一个长度为6的int型数组，要求数组元素的值都在1-30之间， 且是随机赋值。同时，要求元素的值各不相同。
1
2
3
4
5
6
7
8
9
10
| int[] arr = new int[6];
for(int i = 0; i < arr.length; i++){
for(int j = 0; j < i; j++){
if(arr[i] == arr[j]){
i--;
break;
}
}
}
|
练习:遍历扑克牌
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| import java.util.Arrays;
public class Main {
public static void main(String[] args) {
String[] suit = new String[]{"♣", "♦", "♥", "♠"};
String[] scores = new String[]{"3", "4", "5", "6", "7", "8", "9", "10", "J", "Q", "K", "A", "2"};
String[] poker = new String[56];
int total = 0;
for (int i = 0; i < suit.length; i++) {
for (int j = 0; j < scores.length; j++) {
poker[total++] = suit[i] + scores[j];
}
}
poker[total++] = "Big Joker";
poker[total++] = "Little Joker";
for (int i = 0; i < total; i++) {
if (i % 13 == 0 && i != 0) {
System.out.println();
}
System.out.print(poker[i] + " ");
}
}
}
|
练习: 螺旋矩阵
思路分析
1. 螺旋矩阵的特点
螺旋矩阵是指数字从外向内顺时针螺旋排列方阵.
我们来拿4 * 4的方阵举例
1
2
3
4
5
6
7
| 1 → 2 → 3 → 4
↓
12 →13 →14 5
↑ ↓ ↓
11 16 ←15 6
↑ ↓
10 ←9 ←8 ← 7
|
2. 实现思路
我们采用”边界收缩法”来实现
- 定义四个边界 top, bottom, left, right
- 按照”上边 -> 右边 -> 下边 -> 左边”的顺序来填充
- 每填充完一条边,对应的边界像内搜索
- 重复此过程直到所有数字填完
- 我们先来定义一个nxn的二维数组来存放数据
1
2
3
| n = 4
int num = 1;
int[][] arr = new int[n][n]
|
- 定义4条边界
1
| int top = 0, bottom = n -1, left = 0, right = n -1
|
top = 0 代表上边界的第0行
bottom = 0 代表下边界的 最后一行
left = 0 代表左边界的第 0 列
right = n -1 代表 右边的最后一列
- 定义循环控制条件
- 从左向右填充
1
2
3
4
| for(int i = left; i <= right;i++){
arr[left][i] = num++;
}
top++
|
此时我们就完成了从左到右的填充
1
2
3
4
5
6
7
8
9
10
11
12
13
| [
[1, 2, 3, 4],
[0, 0, 0, 0], ← top++ 将移动到这行
[0, 0, 0, 0],
[0, 0, 0, 0]
]
top++
|
- 从上到下填充
1
2
3
4
| for(int i = top; i <= bottom;i++){
arr[i][right] = num++;
}
right--
|
此时就完成了从上到下的填充
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| [
[1, 2, 3, 4],
[0, 0, 0, 5],
[0, 0, 0, 6],
[0, 0, 0, 7]
↑
right-- 此时就指向了这一列
]
|
- 从右到左填充
1
2
3
4
| for(int i = right; i >= left; i--){
arr[bottom][i] = num++;
}
bottom--;
|
此时就完成了从右到左的填充
1
2
3
4
5
6
7
8
9
10
11
12
| [
[1, 2, 3, 4],
[0, 0, 0, 5],
bottom--之后指向的位置 → [0, 0, 0, 6],
[10, 9, 8, 7]
]
|
- 从下到上填充
1
2
3
4
| for(int i = bottom; i >= top; i--){
arr[i][left] = num++;
}
left++;
|
此时就填充完了一圈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| [
[1, 2, 3, 4],
↓ 此时的left ++
[12, 0, 0, 5],
[11, 0, 0, 6],
[10, 9, 8, 7]
]
|
在填充 n轮后 到达 边界检测条件后就完成了填充
完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| public class Main {
public static void main(String[] args) {
int n = 4;
int[][] arr = new int[n][n];
int num = 1;
int top = 0, bottom = n - 1, left = 0, right = n - 1;
while (num <= n * n) {
for (int i = left; i <= right; i++) {
arr[top][i] = num++;
}
top++;
for (int i = top; i <= bottom; i++) {
arr[i][right] = num++;
}
right--;
for (int i = right; i >= left; i--) {
arr[bottom][i] = num++;
}
bottom--;
for (int i = bottom; i >= top; i--) {
arr[i][left] = num++;
}
left++;
}
}
}
|
这套实现方法有局限性只能 做固定起点、固定顺时针的矩阵填充,不能做动态方向/中心扩展/不规则矩阵/变化版螺旋布局
第二套实现方案
方向数组 + 步长控制
实现思路和步骤
初始化一个 3×3 的二维整型数组 matrix，用于存储结果，所有元素初始值为 0
定义方向数组 directions，表示顺时针的移动方向：分别为「向右 (0,1)」、「向下 (1,0)」、「向左 (0,-1)」和「向上 (-1,0)」的行列偏移量。
设置起点位置为 (row, col) = (0, 0)（矩阵左上角），并将当前方向索引 dir 初始化为 0（对应「向右」方向）
使用 for 循环依次生成数字 1 到 9：在每次循环中，先将当前数字填入 matrix[row][col]。
在循环内计算下一步的位置：newRow = row + directions[dir][0]，newCol = col + directions[dir][1]。
如果 newRow 或 newCol 超出边界（< 0 或 ≥ 3）或 matrix[newRow][newCol] 已经不为 0（意味着该位置已被填充），则顺时针切换方向：dir = (dir + 1) % 4，并基于新的方向重新计算 newRow、newCol。
更新当前坐标：将 row = newRow、col = newCol，继续下一次循环
循环结束后，使用双重 for 循环遍历并打印矩阵 matrix，即可得到完整的 3×3 螺旋矩阵结果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| public class SpiralMatrix {
public static void main(String[] args) {
int n = 3;
int[][] matrix = new int[n][n];
int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int dir = 0;
int row = 0, col = 0;
for (int num = 1; num <= n * n; num++) {
matrix[row][col] = num;
int newRow = row + directions[dir][0];
int newCol = col + directions[dir][1];
if (newRow < 0 || newRow >= n || newCol < 0 || newCol >= n
|| matrix[newRow][newCol] != 0) {
dir = (dir + 1) % 4;
newRow = row + directions[dir][0];
newCol = col + directions[dir][1];
}
row = newRow;
col = newCol;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.print(matrix[i][j] + "\t");
}
System.out.println();
}
}
}
|
练习 数组反转
双指针交换法
- 循环条件：i < arr.length / 2 确保只遍历前半部分
- 索引计算：arr.length - i - 1 动态计算对称位置
- 交换逻辑：通过temp变量实现三数交换
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] arr = {1,2,3,4,5,6,7,8,9,10};
for (int i = 0; i < arr.length / 2; i++) {
int temp = arr[i];
arr[i] = arr[arr.length - i - 1];
arr[arr.length - i - 1] = temp;
}
System.out.println(Arrays.toString(arr));
}
}
|
练习 数组的扩容与缩容
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| import java.util.Arrays;
public class MyArrayList<E> {
private Object[] data;
private int size;
private static final int INIT_CAPACITY = 10;
public MyArrayList() {
data = new Object[INIT_CAPACITY];
size = 0;
}
public void add(E element) {
if (size == data.length) {
resize(data.length * 2);
}
data[size++] = element;
}
public E remove(int index) {
checkIndex(index);
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0) {
System.arraycopy(data, index + 1, data, index, numMoved);
}
data[--size] = null;
if (size > 0 && size == data.length / 4) {
resize(data.length / 2);
}
return oldValue;
}
private void resize(int newCapacity) {
data = Arrays.copyOf(data, newCapacity);
}
@SuppressWarnings("unchecked")
private E elementData(int index) {
return (E) data[index];
}
private void checkIndex(int index) {
if (index < 0 || index >= size) throw new IndexOutOfBoundsException();
}
public int size() {
return size;
}
}
|
练习 获取一个字符串在另一个字符串中出现的次数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
String str = "abababkkcadkabkebfkabkskab";
String subStr = "ab";
int index = 0;
while(true){
index = str.indexOf(subStr);
if(index != -1){
str = str.substring(index + 1);
count++
}else break;
}
|
找出字符串中的最大公共前缀
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
public class PrefixFinder {
public static String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) return "";
String prefix = strs[0];
for (int i = 1; i < strs.length; i++) {
while (!strs[i].startsWith(prefix)) {
prefix = prefix.substring(0, prefix.length() - 1);
if (prefix.isEmpty()) return "";
}
}
return prefix;
}
public static void main(String[] args) {
String[] inputs = {"com.example.user", "com.example.admin", "com.example.config"};
System.out.println("公共前缀: " + longestCommonPrefix(inputs));
}
}
|
