day3_prefixSum

2024-05-11 23:12
文章标签 day3 prefixsum

本文主要是介绍day3_prefixSum,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一、前缀和技巧

重点

前缀和技巧适用于快速、频繁地计算一个索引区间内的元素之和

个人理解;预计算,空间换时间

1.(一维数组的前缀和)303区域和检索-数组不可变

获取闭区间值 [left,right] -> preSum[right + 1] - preSum[left],其中preSum[right+1]表示累加到right时的总和

class NumArray {// 前缀和数组private int[] preSum;/* 输入一个数组,构造前缀和 */public NumArray(int[] nums) {// preSum[0] = 0,便于计算累加和preSum = new int[nums.length + 1];// 计算 nums 的累加和for (int i = 1; i < preSum.length; i++) {preSum[i] = preSum[i - 1] + nums[i - 1];}}/* 查询闭区间 [left, right] 的累加和 */public int sumRange(int left, int right) {return preSum[right + 1] - preSum[left];}
}/*** Your NumArray object will be instantiated and called as such:* NumArray obj = new NumArray(nums);* int param_1 = obj.sumRange(left,right);*/
2.(二维数组的前缀和)

同样的预计算

class NumMatrix {
// 定义:preSum[i][j] 记录 matrix 中子矩阵 [0, 0, i-1, j-1] 的元素和private int[][] preSum;public NumMatrix(int[][] matrix) {int m = matrix.length, n = matrix[0].length;if (m == 0 || n == 0) return;// 构造前缀和矩阵preSum = new int[m + 1][n + 1];for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {// 计算每个矩阵 [0, 0, i, j] 的元素和preSum[i][j] = preSum[i-1][j] + preSum[i][j-1] + matrix[i - 1][j - 1] - preSum[i-1][j-1];}}}// 计算子矩阵 [x1, y1, x2, y2] 的元素和public int sumRegion(int x1, int y1, int x2, int y2) {// 目标矩阵之和由四个相邻矩阵运算获得return preSum[x2+1][y2+1] - preSum[x1][y2+1] - preSum[x2+1][y1] + preSum[x1][y1];}
}/*** Your NumMatrix object will be instantiated and called as such:* NumMatrix obj = new NumMatrix(matrix);* int param_1 = obj.sumRegion(row1,col1,row2,col2);*/

在这里插入图片描述

  1. 任何一个小矩阵可以由上图的矩阵计算得到
  2. 而下面这四个矩阵对应的是小矩阵的四个顶点(根据参数可推)
  3. 所以预计算每个以(0,0),(x,y)结尾的矩阵的值,经过计算即可得到

二、二叉树(纲领篇)

参考链接东哥带你刷二叉树(纲领篇) | labuladong 的算法笔记

先在开头总结一下,二叉树解题的思维模式分两类:

1、是否可以通过遍历一遍二叉树得到答案?

如果可以,用一个 traverse 函数配合外部变量来实现,这叫「遍历」的思维模式。

2、是否可以定义一个递归函数,通过子问题(子树)的答案推导出原问题的答案?

如果可以,写出这个递归函数的定义,并充分利用这个函数的返回值,这叫「分解问题」的思维模式。

无论使用哪种思维模式,你都需要思考:

如果单独抽出一个二叉树节点,它需要做什么事情?需要在什么时候(前/中/后序位置)做?其他的节点不用你操心,递归函数会帮你在所有节点上执行相同的操作。

1.二叉树的重要性

举个例子,比如两个经典排序算法 快速排序 和 归并排序,对于它俩,你有什么理解?

如果你告诉我,快速排序就是个二叉树的前序遍历,归并排序就是个二叉树的后序遍历,那么我就知道你是个算法高手了

如果你一眼就识破这些排序算法的底细,还需要背这些经典算法吗?不需要。你可以手到擒来,从二叉树遍历框架就能扩展出算法了。

说了这么多,旨在说明,二叉树的算法思想的运用广泛,甚至可以说,只要涉及递归,都可以抽象成二叉树的问题

2.深入理解前中后序

根据几个问题引发思考

1、你理解的二叉树的前中后序遍历是什么,仅仅是三个顺序不同的 List 吗?

2、请分析,后序遍历有什么特殊之处?

3、请分析,为什么多叉树没有中序遍历?

鄙人是肯定答不上来的

void traverse(TreeNode root) {if (root == null) {return;}// 前序位置traverse(root.left);// 中序位置traverse(root.right);// 后序位置
}

你也注意到了,只要是递归形式的遍历,都可以有前序位置和后序位置,分别在递归之前和递归之后。

所谓前序位置,就是刚进入一个节点(元素)的时候,后序位置就是即将离开一个节点(元素)的时候,那么进一步,你把代码写在不同位置,代码执行的时机也不同:

在这里插入图片描述

比如说,如果让你倒序打印一条单链表上所有节点的值,你怎么搞?

实现方式当然有很多,但如果你对递归的理解足够透彻,可以利用后序位置来操作

/* 递归遍历单链表,倒序打印链表元素 */
void traverse(ListNode head) {if (head == null) {return;}traverse(head.next);// 后序位置print(head.val);
}

教科书里只会问你前中后序遍历结果分别是什么,所以对于一个只上过大学数据结构课程的人来说,他大概以为二叉树的前中后序只不过对应三种顺序不同的 List<Integer> 列表。

但是我想说,前中后序是遍历二叉树过程中处理每一个节点的三个特殊时间点,绝不仅仅是三个顺序不同的 List:

  1. 前序位置的代码在刚刚进入一个二叉树节点的时候执行;
  2. 后序位置的代码在将要离开一个二叉树节点的时候执行;
  3. 中序位置的代码在一个二叉树节点左子树都遍历完,即将开始遍历右子树的时候执行。

在这里插入图片描述

这里你也可以理解为什么多叉树没有中序位置,因为二叉树的每个节点只会进行唯一一次左子树切换右子树,而多叉树节点可能有很多子节点,会多次切换子树去遍历,所以多叉树节点没有「唯一」的中序遍历位置。

重点1

二叉树的所有问题,就是让你在前中后序位置注入巧妙的代码逻辑,去达到自己的目的,你只需要单独思考每一个节点应该做什么,其他的不用你管,抛给二叉树遍历框架,递归会在所有节点上做相同的操作

3.两种解题思路

二叉树题目的递归解法可以分两类思路,第一类是遍历一遍二叉树得出答案,第二类是通过分解问题计算出答案,这两类思路分别对应着 回溯算法核心框架 和 动态规划核心框架

在这里插入图片描述

4.后序位置的特殊之处

中序位置主要用在 BST 场景中,你完全可以把 BST 的中序遍历认为是遍历有序数组。

前序位置本身其实没有什么特别的性质,之所以你发现好像很多题都是在前序位置写代码,实际上是因为我们习惯把那些对前中后序位置不敏感的代码写在前序位置罢了。

你可以发现,前序位置的代码执行是自顶向下的,而后序位置的代码执行是自底向上的:

在这里插入图片描述

重点2

但这里面大有玄妙,意味着前序位置的代码只能从函数参数中获取父节点传递来的数据,而后序位置的代码不仅可以获取参数数据,还可以获取到子树通过函数返回值传递回来的数据

举具体的例子,现在给你一棵二叉树,我问你两个简单的问题:

1、如果把根节点看做第 1 层,如何打印出每一个节点所在的层数?

2、如何打印出每个节点的左右子树各有多少节点?

第一个问题从根节点就能给出答案,而第二个问题必须遍历完子树之后才能给出答案

结合这两个简单的问题,你品味一下后序位置的特点,只有后序位置才能通过返回值获取子树的信息。

那么换句话说,一旦你发现题目和子树有关,那大概率要给函数设置合理的定义和返回值,在后序位置写代码了

例题lc543题 二叉树的直径

5.以树的视角看 动归/回溯/DFS算法的区别和联系

DFS 算法和回溯算法非常类似,只是在细节上有所区别

这个细节上的差别是什么呢?其实就是「做选择」和「撤销选择」到底在 for 循环外面还是里面的区别,DFS 算法在外面,回溯算法在里面。

为什么有这个区别?还是要结合着二叉树理解。这一部分我就把回溯算法、DFS 算法、动态规划三种经典的算法思想,以及它们和二叉树算法的联系和区别,用一句话来说明:

动归/DFS/回溯算法都可以看做二叉树问题的扩展,只是它们的关注点不同

  • 动态规划算法属于分解问题的思路,它的关注点在整棵「子树」
  • 回溯算法属于遍历的思路,它的关注点在节点间的「树枝」
  • DFS 算法属于遍历的思路,它的关注点在单个「节点」

三个例子解释三种情况

1.计算一棵二叉树有多少个节点?

// 定义:输入一棵二叉树,返回这棵二叉树的节点总数
int count(TreeNode root) {if (root == null) {return 0;}// 我这个节点关心的是我的两个子树的节点总数分别是多少int leftCount = count(root.left);int rightCount = count(root.right);// 后序位置,左右子树节点数加上自己就是整棵树的节点数return leftCount + rightCount + 1;
}

你看,这就是动态规划分解问题的思路,它的着眼点永远是结构相同的整个子问题,类比到二叉树上就是「子树」

你再看看具体的动态规划问题,比如 动态规划框架套路详解 中举的斐波那契的例子,我们的关注点在一棵棵子树的返回值上:

2.使用遍历的思路写一个traverse函数,打印出遍历这棵二叉树的过程

回溯算法遍历的思路,它的着眼点永远是在节点之间移动的过程,类比到二叉树上就是[树枝]

3.把二叉树的每个节点值都+1

void traverse(TreeNode root) {if (root == null) return;// 遍历过的每个节点的值加一root.val++;traverse(root.left);traverse(root.right);
}

你看,这就是 DFS 算法遍历的思路,它的着眼点永远是在单一的节点上,类比到二叉树上就是处理每个「节点」

你再看看具体的 DFS 算法问题,比如 一文秒杀所有岛屿题目 中讲的前几道题,我们的关注点是 grid 数组的每个格子(节点),我们要对遍历过的格子进行一些处理,所以我说是用 DFS 算法解决这几道题的:

有了这些铺垫,你就很容易理解为什么回溯算法和 DFS 算法代码中「做选择」和「撤销选择」的位置不同了,看下面两段代码:

// DFS 算法把「做选择」「撤销选择」的逻辑放在 for 循环外面
void dfs(Node root) {if (root == null) return;// 做选择print("我已经进入节点 %s 啦", root)for (Node child : root.children) {dfs(child);}// 撤销选择print("我将要离开节点 %s 啦", root)
}// 回溯算法把「做选择」「撤销选择」的逻辑放在 for 循环里面
void backtrack(Node root) {if (root == null) return;for (Node child : root.children) {// 做选择print("我站在节点 %s 到节点 %s 的树枝上", root, child)backtrack(child);// 撤销选择print("我将要离开节点 %s 到节点 %s 的树枝上", child, root)}
}

看到了吧,你回溯算法必须把「做选择」和「撤销选择」的逻辑放在 for 循环里面,否则怎么拿到「树枝」的两个端点?

6.层序遍历(简单过一下)

二叉树题型主要是用来培养递归思维的,而层序遍历属于迭代遍历,也比较简单,这里就过一下代码框架吧:

// 输入一棵二叉树的根节点,层序遍历这棵二叉树
void levelTraverse(TreeNode root) {if (root == null) return;Queue<TreeNode> q = new LinkedList<>();q.offer(root);// 从上到下遍历二叉树的每一层while (!q.isEmpty()) {int sz = q.size();// 从左到右遍历每一层的每个节点for (int i = 0; i < sz; i++) {TreeNode cur = q.poll();// 将下一层节点放入队列if (cur.left != null) {q.offer(cur.left);}if (cur.right != null) {q.offer(cur.right);}}}
}

这篇关于day3_prefixSum的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/980928

相关文章

Android智能家居实训day3

今日内容比较少啊 今日内容主要是通过hellocharts绘制折线图,主要是导包之后,在xml文件中添加控件的时候要写全路径,之后就是在生成图表的时候先通过 AxisValue集合接收横坐标数据集合,PointValues集合接收点集,再通过点集赋值给Line线对象,通过line内部的函数来对折线进行美化,最后放到线集里赋给折线对象。 XY轴的设置是通过Axis对象,也是要通过内部函数设置属性没

C++入门day3-面向对象编程(中)

前言:C++入门day2-面向对象编程(上)-CSDN博客 运算符重载 我们接触过函数重载,就是同名的函数有不同的功能。那么运算符重载,顾名思义也是赋予运算符其他的功能。在这里,我个人以为,运算符就是特殊函数的简写。我们先以加法切入本知识点: +加法运算符重载 如果我们想定义两数相加的函数我们该怎么办。第一时间我们就想到了这样写: int add(int a,int b){retu

【苍穹外卖】Day3 菜品接口

1 公共字段自动填充(待添加) 2 菜品接口 2.1 新增菜品 2.1.1 根据类型查询分类 接口 (已完成) 2.1.2 文件上传 接口 通用接口 配置文件 在自定义配置类中定义了四个属性 在配置文件中 代表当前使用的配置环境是 dev 开发环境 在 dev 里面继续配置阿里云 OSS 然后创建一个配置类 @Bean

YOLOV5入门教程day3

一. 导入包和基本配置 import argparseimport mathimport osimport randomimport subprocessimport sysimport timefrom copy import deepcopyfrom datetime import datetime, timedeltafrom pathlib import Pathtr

实习项目|苍穹外卖|day3

抽离出细节,复习Java开发的整个架构:JAVA三层架构,持久层,业务层,表现层的理解(SSH) 持久层是软件开发中的一个重要概念,它指的是负责数据持久化和数据库交互的部分。 公共字段自动填充(难度大) 1.根据原型进行需求分析与设计(接口文档) 2.根据接口设计DTO 3.编码controller-》service-》mapper 如何创建注解?SpringBoot如何创

【C++ Qt day3】

2、设计一个Per类,类中包含私有成员:姓名、年龄、指针成员身高、体重,再设计一个Stu类,类中包含私有成员:成绩、Per类对象p1,设计这两个类的构造函数、析构函数和拷贝构造函数。

Fx - day3 - 沙盒/更改集/互联更改集/配置包

Fxiaoke - day3 - 沙盒/更改集/互联更改集/配置包 学习目标:熟悉 沙盒,更改集,配置包,互联更改集 的概念以及使用场景 0、前言 沙盒理解 很多时候我们可能需要一个沙盒环境,什么是沙盒环境? 沙盒环境(sandbox org)拥有模拟生产环境去做上线前的测试,一般也叫UAT环境,沙盒在计算机安全领域中是一种安全机制,为运行中的程序提供的隔离环境。防止对系统其他部分产生不

黑马程序员2024最新SpringCloud微服务开发与实战 个人学习心得、踩坑、与bug记录Day3 全网最全

你好,我是Qiuner. 为帮助别人少走弯路和记录自己编程学习过程而写博客 这是我的 github https://github.com/Qiuner ⭐️ gitee https://gitee.com/Qiuner 🌹 如果本篇文章帮到了你 不妨点个赞吧~ 我会很高兴的 😄 (^ ~ ^) 想看更多 那就点个关注吧 我会尽力带来有趣的内容 😎 这篇中规中举,有不少bug记录与方便您复制

《Linux就该这么学》学习笔记—day3

同样的,今天学习的内容在我前面的几篇博客中已经写过了: Linux命令之4系统状态检测命令 Linux命令之5工作目录切换命令 Linux命令之6文本文件编辑命令 Linux命令之7文件目录管理命令 Linux命令之8打包压缩与搜索命令 然后放补充的笔记: ——2020.02.16

爆肝三天,制作属于自己的地图——DAY3(地图数据发布详细教程)

4,重建顶层。 倾斜摄影数据的组织方式,一个 Data 目录下的 Tile 可能会成千上万,如果不使用重建顶层,那么输出的3DTiles的包围盒会非常非常多,增加加载时长。重建顶层,程序会根据瓦片的空间结构关系采用八叉树重建,包围盒该合并的合并,该废弃的废弃,最终加快加载速度。 爆肝第三天,地图数据发布详细教程 作者:御剑飞行 在第二篇中,我们介绍了Maomost Studio支持的数