予辰

分类

未归档(4) 算法技巧(1) 题解(9)

/ 注册

全部文章（共14篇）

前缀和数组与差分数组

https://mp.weixin.qq.com/s/123QujqVn3--gyeZRhxR-A 前缀和数组前缀和技巧适用于快速、频繁地计算一个索引区间内的元素之和。对于一维数组的实现如下： class NumArray { private: // 前缀和数组 vector<...

C++ 数组

2021-12-09

0 503

前缀和、树状数组和线段树

1.前缀和前缀和说直白点其实就是先计算出某一个区间内元素的和保存在一个数组中，以便于后续的快速查找某区域内元素的和，细分为一维前缀和和二维前缀和。一维前缀和有数组A，数组A对应的前缀和数组为S，有：由此方便了范围查询：二维前缀和对于二维数组A，数组A对应的前缀和数组为S，有：计算时二维前缀和...

2021-03-23

0 908

单调栈问题集中详解

一、单调栈的定义及特点所谓的单调栈，就是在栈先进后出的特性之外再添加一个单调的特性，使得栈中元素是递增或者递减的。其具有以下几个小特点：1、栈内元素保持单调；2、每个元素都会入栈并且仅仅入栈一次；3、栈当中可以直接存储元素本身，也可以存放元素的下标索引(存放索引时是指索引对应的元素是单调的)；4、对...

2020-11-16

1 1149

二叉树的路径问题

二叉树的路径是指从二叉树的根节点到叶子节点（叶子节点是指没有子节点的节点）的路径。那么怎么求取二叉树的路径呢？方法1、采用递归访问二叉树的方法，访问节点时先将节点加入到一个path变量中，如果该节点是叶子节点，那么path里面存放的就是从根节点到该叶子节点的路径了，访问完了二叉树的所有节点后即可得到...

2020-10-30

1 812

岛屿问题——一类经典的网格搜索类问题

参考自博客https://leetcode-cn.com/problems/island-perimeter/solution/tu-jie-jian-ji-er-qiao-miao-de-dfs-fang-fa-java-by/如何在网格上做DFS网格问题是这样的一类搜索问题：有mn个小方格，组成...

2020-10-30

0 785

排列与组合问题

知识点之排列组合问题排列组合问题常常使用回溯算法来解决问题，回溯算法的结构框架如下： void backtracking(参数) { if(终止条件) { 存放结果； return; } for(选择：本层集合中元素(树中节点孩子的数量...

2020-09-19

2 695

动态规划与贪婪算法

动态规划与贪婪算法简记一动态规划算法应用范围如果是要求一个问题的最优解（通常是求最大值或最小值），而且该问题能够分解成若干个子问题，并且子问题之间还有重叠的更小的子问题，就可以考虑用动态规划来解决该问题。我们在应用动态规划之前要分析能否把大问题分解成小问题，分解后的每个小问题也存在最优解。如果小问...

2020-09-19

2 1129

给定一组矩形求能够形成的最大面积

题目描述给出n个数字，代表直方图的条高，直方图每一条的宽度为1，请计算直方图中最大矩形的面积。图中的阴影部分是该直方图中面积最大的矩形，面积为10个单位例如：给出的高度 =[2,1,5,6,2,3],返回10.思路分析可以依次遍历数组中的元素，可以知道较小的元素会成为矩形高的限制条件，比如遍历到1时...

2020-07-22

2 1336

寻找给定排列的下一个更大的排列

题目描述实现函数next permutation（下一个排列）：将排列中的数字重新排列成字典序中的下一个更大的排列。将排列中的数字重新排列成字典序中的下一个更大的排列。如果不存在这样的排列，则将其排列为字典序最小的排列（升序排列）。需要使用原地算法来解决这个问题，不能申请额外的内存空间。下面有几组样...

2020-07-12

1 1196

数据能够形成的最大容器

题目描述给定n个非负整数a1，a2，…，an，其中每个数字表示坐标(i, ai)处的一个点。以（i，ai）和（i，0）（i=1,2,3...n）为端点画出n条直线。你可以从中选择两条线与x轴一起构成一个容器，最大的容器能装多少水？例如：输入 [1,8,6,2,5,4,8,3,7]输出: 49思路分析...

2020-07-09

7 894