予辰

题解

未归档(4) 算法技巧(1)

/ 注册

全部文章 / 题解（共9篇）

单调栈问题集中详解

一、单调栈的定义及特点所谓的单调栈，就是在栈先进后出的特性之外再添加一个单调的特性，使得栈中元素是递增或者递减的。其具有以下几个小特点：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

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

题目描述给出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 895

求给定字符串中的最长回文串

题目描述找出给出的字符串S中最长的回文子串。假设S的最大长度为1000，并且只存在唯一解。思路分析首先要弄清楚回文串的概念，回文串就是正着顺序和反着顺序是一样的字符串，有aba和abba两种类型。现在我们怎么判断给定的字符串中的回文串呢？开始想着的是依次遍历字符串，然后从字符串的末尾和当前位置之间的...

2020-07-08

0 945

求两个有序数组的中位数

题目描述有两个大小分别为m和n的有序数组A和B。请找出这两个数组的中位数。你需要给出时间复杂度在O(log (m+n))以内的算法。思路分析两个大小分别为m和n的有序数组，我们要找出它们的中位数，而且要求时间复杂度是对数级别的，那么我们自然而然地就会想到二分查找算法，可是要怎么进行呢？寻找这两个数组...

2020-07-08

13 1120

算法小记

题目描述剑指offer面试题38：输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。题解方法一：分治法分治法：求一个规模为n的问题，先求左边规模大约为n/2的问题，再求右边规模大约为n/2的问题，然后合并左边和右边的解，从而求得最...

2020-06-30

0 590