数组和字符串

发表于 | Edited on | 分类于

介绍

数组是数据结构中最基本的。因为字符串是由字符数组形成的，所以二者是相似的。

数组简介

基本顺序类型，用于按顺序存储元素的集合。但是元素可以随机存取，因为数组中的每个元素都可以通过数组索引来识别。

寻找数组的中心索引

二维数组

二维数组也是由元素的序列组成。但是这些元素可以排列在矩形网格中而不是直线上。

原理

在一些语言中，多维数组实际上是在内部作为一维数组实现的，在其他一些语言中，实际上根本没有多维数组。

java中，二维数组实际上是包含M个元素的一维数组，每个元素都是包含有N个整数的数组。

对角线遍历

找规律

螺旋矩阵

1
2
3
4
5
6
7
输入:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]

直觉

绘制螺旋轨迹路径，发现当路径超出界限或者进入之前访问过的单元格时，会顺时针旋转方向。

算法

R行 C列，seen[r][c]表示第r行第c列的单元格之前已经被访问过了。当前所在位置为（r, c）前进方向是di。希望访问所偶的R * C个单元格。

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
class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> ans = new ArrayList<Integer>();
        if (matrix.length == 0) {
            return ans;
        }
        int R = matrix.length, C = matrix[0].length;
        boolean[][] seen = new boolean[R][C];
        int[] dr = {0, 1, 0, -1}; //横向如果是顺时针的话坐标，先不变，在加， 在不变，在减去
        int[] dc = {1, 0, -1, 0};
        int r = 0, c = 0, di = 0;
        for (int i = 0; i < R * C; i++) {
            ans.add(matrix[r][c]);
            seen[r][c] = true;
            int cr = r + dr[di];
            int cc = c + dc[di];
            if (0 <= cr && cr < R && 0 <= cc && cc < C && !seen[cr][cc]) {
                r = cr;
                c = cc;
            } else {
                //这说明碰到了墙壁，要折行了
                di = (di + 1) % 4;
                r += dr[di];
                c += dc[di];
            }
        }
        return ans;

    }
}

杨辉三角

动态规划

0%