通知 网站从因情语写改为晴雨,这个网站的模板也从calmlog_ex改为 whimurmur

leetcode探索之数组和字符串学习 二维数组简介

4417人浏览 / 0人评论 / | 作者:因情语写  | 分类: 设计模式与算法  | 标签: 设计模式与算法  /  leetcode

作者:因情语写

链接:https://www.qingyu.blue/article/223

声明:请尊重原作者的劳动,如需转载请注明出处


    前面的章节中,我们已经了解了一维数组。然而,有时候,我们可能需要用到多维数组,它更适合像表或矩阵这样更复杂的结构。

    本章节中,我们将重点围绕二维数组来解释:

  • 多维数组是如何工作的?
  • 如何运用二维数组来解决问题?

    二维数组简介

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

    示例

    让我们来看一个使用二维数组的例子:

// "static void main" must be defined in a public class.
public class Main {
    private static void printArray(int[][] a) {
        for (int i = 0; i < a.length; ++i) {
            System.out.println(a[i]);
        }
        for (int i = 0; i < a.length; ++i) {
            for (int j = 0; a[i] != null && j < a[i].length; ++j) {
                System.out.print(a[i][j] + " ");
            }
            System.out.println();
        }
    }
    public static void main(String[] args) {
        System.out.println("Example I:");
        int[][] a = new int[2][5];
        printArray(a);
        System.out.println("Example II:");
        int[][] b = new int[2][];
        printArray(b);
        System.out.println("Example III:");
        b[0] = new int[3];
        b[1] = new int[5];
        printArray(b);
    }
}

    原理

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

    1. C++ 将二维数组存储为一维数组。

    下图显示了大小为 M * N 的数组 A 的实际结构:

    因此,如果我们将 A 定义为也包含 M * N 个元素的一维数组,那么实际上 A[i][j] 就等于 A[i * N + j]。

    2. 在Java中,二维数组实际上是包含着 M 个元素的一维数组,每个元素都是包含有 N 个整数的数组。

    下图显示了 Java 中二维数组 A 的实际结构:

    动态二维数组

    与一维动态数组类似,我们也可以定义动态二维数组。 实际上,它可以只是一个嵌套的动态数组。 你可以自己尝试一下。


    算法说明

    对角线遍历

给定一个含有 M x N 个元素的矩阵(M 行,N 列),请以对角线遍历的顺序返回这个矩阵中的所有元素,对角线遍历如下图所示。

 

示例:

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

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

解释:

说明:

  1. 给定矩阵中的元素总数不会超过 100000 。 
// 想法:第一第二维索引不应该超出范围,当j >= length, i + 1,当i < 0, j + 1,当 i >= length,j + 1,当j < 0,i+1,
    // 注意这四个判断的顺序, 当i+j是偶数时,向右上,当i+j是奇数时,向左下
    public int[] findDiagonalOrder(int[][] matrix) {
        if(null == matrix || matrix.length == 0){
            return new int[0];
        }
        
        int[] result = new int[matrix.length * matrix[0].length];
        int i = 0;
        int j = 0;
        int k = 0;
        
        while(k < result.length){
            if(0 <= i && i < matrix.length && 0 <= j && j < matrix[0].length){
                result[k++] = matrix[i][j];
                if((i + j) % 2 == 0){
                    j++;
                    i--;
                }else{
                    j--;
                    i++;
                }
            }else if(j >= matrix[0].length){
                j--;
                i += 2;
            }else if(i < 0){
                i++;
            }else if(i >= matrix.length){
                i--;
                j += 2;
            }else if(j < 0){
                j++;
            }
        }
        
        return result;
    }

     找到上面的规则,按规则处理就可以了

    再看下面一个类似的算法

​
public int[] findDiagonalOrder(int[][] matrix) {
        if(matrix.length<1)
            return new int[]{};
        int row=matrix.length;
        int col=matrix[0].length;
        int []result=new int[row*col];
        int r=0;
        int c=0;
        int i=0;
        while(i<row*col){
            while(r>=0 && c<col){
                result[i++]=matrix[r--][c++];
            }
           if(c>=col)
           {
               r+=2;
               c-=1;
           }
           else{
                r+=1;
            }
            while(r<row && c>=0){
                result[i++]=matrix[r++][c--];
            }
            if(r>=row){
                r-=1;
                c+=2;
            }
            else{
                c+=1;
            }
        }
       return result;
    }

​

    这个算法就是先向左上,再向右下,找个规则就可以了


    螺旋矩阵

给定一个包含 m x n 个元素的矩阵(m 行, n 列),请按照顺时针螺旋顺序,返回矩阵中的所有元素。

示例 1:

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

示例 2:

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

 

​
// 想法:对行列i,j,当j>当前范围,j--,i++,当j<当前范围,j++,i--,当i>当前范围,i--,j--,当i<当前范围,本轮循环结束,
    // 第一轮范围为0~m-1,0~n-1,以后每轮下限加1,上限减1
    public List<Integer> spiralOrder(int[][] matrix) {
       if(matrix == null){
            return null;
        }
        
        if(matrix.length == 0){
            return new ArrayList<Integer>();
        }
        
        List<Integer> result = new ArrayList<>();
        int rowDown = 0, rowUp = matrix.length - 1, columnDown = 0, columnUp = matrix[0].length - 1, i = 0, j = 0;
        int direction = 1;
        boolean roundStart = true;
        while(rowDown <= rowUp && columnDown <= columnUp){
            if(i >= rowDown && i <= rowUp && j >= columnDown && j <= columnUp){
                if(i == rowDown && j == columnDown){
                    if(roundStart){
                        roundStart = false;
                        result.add(matrix[i][j]);
                    }
                }else{
                    result.add(matrix[i][j]);
                }
                    
                
                if(direction == 1){
                    j++;
                }else if(direction == 2){
                    i++;
                }else if(direction == 3){
                    j--;
                }else{
                    i--;
                }
            }else if(rowDown == rowUp){
            	break;
            }else if(j > columnUp){
                j--;
                i++;
                direction = 2;
            }else if(columnDown == columnUp){
            	break;
            }else if(j < columnDown){
                j++;
                i--;
                direction = 4;
            }else if(i > rowUp){
                i--;
                j--;
                direction = 3;
            }else{
                rowDown++;
                rowUp--;
                columnDown++;
                columnUp--;
                i = rowDown;
                j = columnDown;
                direction = 1;
                roundStart = true;
            }
        }
        
        return result;
    }

​

    每轮处理四个角为rowDown,rowUp,columnDown,columnUp的长方形上的元素,但起点只用处理一次,所以用了个roundStart标记一下,同时规定了一下方向direction,当检索到拐角时下个方向是什么样的

    再看一种比较直观的算法

public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> list = new ArrayList<Integer>();
        if(matrix == null || matrix.length == 0)
    		return list;
        int m = matrix.length;
        int n = matrix[0].length;
        int i = 0; 

        //统计矩阵从外向内的层数,如果矩阵非空,那么它的层数至少为1层
        int count = (Math.min(m, n)+1)/2;
        //从外部向内部遍历,逐层打印数据
        while(i < count) {
        	for (int j = i; j < n-i; j++) {
				list.add(matrix[i][j]);
			}
        	for (int j = i+1; j < m-i; j++) {
				list.add(matrix[j][(n-1)-i]);
			}
        	
        	for (int j = (n-1)-(i+1); j >= i && (m-1-i != i); j--) {
				list.add(matrix[(m-1)-i][j]);
			}
        	for (int j = (m-1)-(i+1); j >= i+1 && (n-1-i) != i; j--) {
				list.add(matrix[j][i]);
			}
        	i++;
        }    
        return list;
    }
}

    算了一个轮数,再用四个for循环计算四个方向,很直观的算法


    杨辉三角

给定一个非负整数 numRows,生成杨辉三角的前 numRows 行。

在杨辉三角中,每个数是它左上方和右上方的数的和。

示例:

输入: 5
输出:
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]
​
// 想法:中学的杨辉三角,根据性质通过上一行算下一行
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> temp;
        List<Integer> pre;
        
        if(numRows == 0){
            return result;
        }else if(numRows == 1){
            temp = new ArrayList<>();
            temp.add(1);
            result.add(temp);
            return result;
        }
        
        temp = new ArrayList<>();
        temp.add(1);
        result.add(temp);
        for(int i = 1; i < numRows; i++){
            temp = new ArrayList<>();
            temp.add(1);
            pre = result.get(i - 1);
            for(int j = 0; j < pre.size() - 1; j++){
                temp.add(pre.get(j) + pre.get(j + 1));
            }
            
            temp.add(1);
            result.add(temp);
        }
        
        return result;
    }

​

    再来看一种算法

public List<List<Integer>> generate(int numRows) {
        if (numRows <= 0) {
            return new ArrayList<>(0);
        }
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < numRows; i++) {
            List<Integer> list = new ArrayList<>(i+1);
            for (int j = 0; j < i + 1; j++) {
                if (j == 0 || j == i) {
                    list.add(1);
                    continue;
                }
                List<Integer> preList = result.get(i - 1);
                int t = preList.get(j-1) + preList.get(j);
                list.add(t);
            }
            result.add(list);
        }
        return result;
    }

    思路类似,但代码更加紧凑

 


自己写的文章声明标题示例:


点赞(0) 打赏

全部评论

还没有评论!