【Java】dp数组的遍历方向

简介: 文章目录前言创建数组反向遍历分析斜向遍历分析

前言

一时刷题一时爽,一直刷题一直爽,当我刷到动态规划时,发现一个问题,那就是在遍历数组的时候不知道该怎么遍历,有和我同样困惑的朋友给我点个赞吧(不是骗赞哦,嘻嘻),所以我在前人的基础上总结了一些遍历的方法。

创建数组

首先为了方便检验,先创建一个数组,大家只需要复制就行了

1 4 7 5
3 6 1 7
3 1 4 7
3 5 9 1
5 8 1 4

用代码创建一个二维数组

import java.util.Scanner;
class Test2{
    public static void main(String[] args) {
        int m=5, n=4;
        Scanner sc = new Scanner(System.in);
        int dp[][] = new int[m][n];
        for (int i = 0;i<m;i++){
            for (int j = 0;j<n;j++){
                dp[i][j] = sc.nextInt();
            }
        }
    }
}

反向遍历

// 反向遍历
        for (int i = m-1;i>=0;i--){
            for (int j = n-1;j>=0;j--)
                System.out.print(dp[i][j]+" ");
            System.out.println();
        }

结果如下

4 1 8 5 
1 9 5 3 
7 4 1 3 
7 1 6 3 
5 7 4 1

分析

为了方便讲解,我就用区间的形式来表述。

反向遍历是从 [4, 3] 开始,随着j的递减,也就是向左遍历,如果实在不理解,可以把i,j看作二维数组的行和列,列的索引值逐渐减小,每遍历完一行就会继续向上面的一行继续遍历。最终会得到上面的结果

正向遍历就不多说了,直接上代码

for (int i = 0; i < m; i++)
    for (int j = 0; j < n; j++)

斜向遍历

//右上方遍历
for(int l = 2;l<=m;l++){
  for(int i = 0;i<=n-l;i++){
    int j = l +i-1;
    System.out.println(dp[i][j]);
    }
}

分析

给出的条件为:m=5, n=4。

我们要实现斜向遍历,必然从[0, 1]开始 ,列的变化是随着行来变的 ,n-l 的值就为行和列的变化情况。

再看列的变化,也就是 int j = l+i-1 的值,这个是怎么来的呢,换个角度理解

如果这样写呢 int j = (l-1)+i

假设l=2时,这个时候相当于 j = 1 +i,也就是i的递增,也就是行的下移,列也随着加1,整个过程看起来就是下图红线的方向

相当于确定好行后再来算列,for循环i++就为一次遍历

结果为

4
1
7
7
7
5

左下方的遍历与右上方类似,只不过 i<=n-l+1 在原来的基础上加了1,因为m和n不相等,如果不加上1的话,遍历的值会不完整,然后只需要将i,和j换个位置就行了。 dp[j][i]

//左下方遍历
for(int l = 2;l<=m;l++){
  for(int i = 0;i<=n-l+1;i++){
    int j = l +i-1;
        System.out.println(dp[j][i]);
  }
}

Tips

如果数组是一个正方形矩阵的话,左下方的遍历就是下面的代码

for(int l = 2;l<=m;l++){
  for(int i = 0;i<=n-l;i++){
    int j = l +i-1;
    System.out.println(dp[j][i]);
            }
        }

目录
打赏
0
0
0
0
0
分享
相关文章
Java快速入门之数组、方法
### Java快速入门之数组与方法简介 #### 一、数组 数组是一种容器,用于存储同种数据类型的多个值。定义数组时需指定数据类型,如`int[]`只能存储整数。数组的初始化分为静态和动态两种: - **静态初始化**:直接指定元素,系统自动计算长度,如`int[] arr = {1, 2, 3};` - **动态初始化**:手动指定长度,系统给定默认值,如`int[] arr = new int[3];` 数组访问通过索引完成,索引从0开始,最大索引为`数组.length - 1`。遍历数组常用`for`循环。常见操作包括求和、找最值、统计特定条件元素等。
Java基础(六):数组
Java基础(六):数组
30 10
Java基础(六):数组
|
29天前
|
Java数组:静态初始化与动态初始化详解
本文介绍了Java中数组的定义、特点及初始化方式。
62 12
在 Java 中,如何遍历一个 Set 集合?
【10月更文挑战第30天】开发者可以根据具体的需求和代码风格选择合适的遍历方式。增强for循环简洁直观,适用于大多数简单的遍历场景;迭代器则更加灵活,可在遍历过程中进行更多复杂的操作;而Lambda表达式和`forEach`方法则提供了一种更简洁的函数式编程风格的遍历方式。
Java|如何正确地在遍历 List 时删除元素
从源码分析如何正确地在遍历 List 时删除元素。为什么有的写法会导致异常,而另一些不会。
91 3
Java 数组
【10月更文挑战第19天】Java 数组是一种非常实用的数据结构,它为我们提供了一种简单而有效的方式来存储和管理数据。通过合理地使用数组,我们能够提高程序的运行效率和代码的可读性。更加深入地了解和掌握 Java 数组的特性和应用,为我们的编程之旅增添更多的精彩。
48 4
提高 Java 数组性能的方法
【10月更文挑战第19天】深入探讨了提高 Java 数组性能的多种方法。通过合理运用这些策略,我们可以在处理数组时获得更好的性能表现,提升程序的运行效率。
61 2
|
4月前
|
Java“(array) <X> Not Initialized” (数组未初始化)错误解决
在Java中,遇到“(array) &lt;X&gt; Not Initialized”(数组未初始化)错误时,表示数组变量已被声明但尚未初始化。解决方法是在使用数组之前,通过指定数组的大小和类型来初始化数组,例如:`int[] arr = new int[5];` 或 `String[] strArr = new String[10];`。
128 2
java基础:map遍历使用;java使用 Patten 和Matches 进行正则匹配;后端传到前端展示图片三种情况,并保存到手机
这篇文章介绍了Java中Map的遍历方法、使用Pattern和matches进行正则表达式匹配,以及后端向前端传输图片并保存到手机的三种情况。
49 1
|
4月前
|
Java数组动态扩容和动态缩减
Java数组动态扩容和动态缩减
44 3

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等