小牛博客

题目链接：AcWing 131. 直方图中最大的矩形 这道题自然就是非常典型的单调栈问题！ ¶一、题解 该题目如下图：找一个最大的矩形出来！ 有了前面单调栈知识的积累，会轻易的发现这道题就是一道单调栈的应用！ 我们看图可以知道，以其中一个矩形的顶部作为一条边，那么他向左和向右最大能拓展的长度就是他的宽度！最终面积就是能拓展的最大宽度乘以该矩形的高就是以该矩形顶部为边的最大矩形！每个矩形都枚举一次即可得到最大矩形的面积！ 问题来了，如何快速找到该矩形向左和向右最远能拓展到哪里呢？ 其实，这个问题换句话说就是，如何可以快速的找到左边或右边第一个比他低的矩形的位置！ 现在可以发现了吧！ 这就是单调栈的定义呗！ 具体操作： 从左到右维护一个单调栈，从右到做维护一个单调栈即可！ 由于要维护两次，为了方便我们使用自己实现的栈结构q l r数组分别表示左边或右边第一个比他矮的矩形的下标位置 最终面积就是h[i] * (r[i] - l[i] - 1) 注意点： 本题数据大，可能爆int，使用long long强转一下！ 两次扫描之间，记得清空栈 为了便于处理边界数据，从1 - n进行循环 ...

题目链接：LeetCode 456. 132模式 这是一道非典型的单调栈问题！ ¶一、题解 先来简单分析一下该题： 就是找是否有满足如下条件的数 i < j < k 并且 nums[i] < nums[k] < nums[j]，对于本题，我们可以从暴力角度考虑，即三层for循环，但实在是过于暴力，于是乎就产生了一个新的想法： 我们可以枚举每个nums[i]，对于每个nums[i]，判断其后是否有一个慢如如下要求的nums[k]： nums[k] > nums[i] nums[i] 和 nums[k] 之间存在一个 nums[j] 且 nums[j] > nums[k] 对于如上要求的nums[k]，我们可以进行转化： 即只要找到满足要求（所谓满足要求，这里是指上面的两个要求都满足）的nums[k]中最大的nums[k]即可！ 即此时的nums[k]是大于nums[i]的数且比num[j]小的数中的最大的数！ 而这样的数一定满足要求！ 如果有这样的数，则本题有解，否则无解 那么，如何求得满足要求的最大的 nums[k] 呢？ 这里就要用到单 ...

题目链接：AcWing 1497.树的遍历 经典的题目，给定中序和后序遍历得到层序遍历！ ¶一、题解 一道经典的问题，通过中序和后序遍历建树，然后再bfs搜一遍即可得到层序遍历的结果！ 如何通过中序和后序进行建树呢？ 我们知道，后序遍历的最后一个节点是根节点 中序遍历可以通过后序遍历得到的根节点将该序列分为两部分，左子树和右子树 然后即可递归的找到每一个根节点 一个问题，如何快速的从中序遍历序列中找到根节点所在的下标呢？ 很简单，在进行输入中序遍历的时候可以使用哈希表将中序遍历的值和下标进行一次存储，便可在使用的时候通过O(1)的时间内将其找出来！ 其他存储： 左右子树的存储同样使用哈希表进行存储，很方便！ 具体来说： 需要一个递归函数，该函数返回值为当前的根节点 参数为当前中序遍历的区间[il, ir]和后序遍历的区间[pl, pr] 若中序序列中根节点的下标为k，则可以得到： 对于左子树：(il, k - 1, pl, k - 1 - il + pl) 对于右子树：(k + 1, ir, k - 1 - il + pl + 1, pr - 1) 时间复杂度：O(n ...

题目链接：AcWing 85.不用加减乘除做加法 计算机底层加法的实现原理 — 全加器！ ¶一、题解 要求不使用加减乘除实现加法！这样的话，必然就是计算机底层实现加法的原理了！即全加器的实现！ 所谓全加器：就是将一个数加另一个数转换为不进位加法与加法的和！ 过程如下： 先通过异或运算得到不进位加法的结果 再通过与运算得到进位加法的进的位，由于进位是向左边的数进位，因此将结果左移一位即可 二者相加即为最终结果！ 一个问题，上一步要用到加法，题目要求不能使用加法，如何处理？ 我们可以将得到的两个结果通过迭代的方式再次进行一次异或和与运算，直到进位结果为0为止！得到的就是最终答案**！** 那么，如何确定该循环一定会结束？ 我们会发现每次进行进位运算时，都会左移1，即末尾会至少多个0，每次迭代多一个0，那么最多迭代32次，必然该数为0，退出循环！ 时间复杂度：O(1) 空间复杂度：O(1) ¶二、AC代码 参考如下： 1234567891011class Solution {public: int add(int num1, int num2){ while( ...

题目链接：AcWing 3302. 表达式求值 本题可以作为模板，处理含有任何运算符的中缀表达式问题！ ¶一、题意 给定一个表达式，其中运算符仅包含 +,-,*,/（加 减 乘 整除），可能包含括号，请你求出表达式的最终值。 ¶二、题解 简单分析： 给定一个中缀表达式，例如(2+2)*(1+1)，要我们计算出最终结果！包含加减乘除和括号！ 这时候，我们想到了后缀表达式，但是由于后缀表达式的特殊性，我们只要将该表达式放入一个栈中，遇到数字入栈，遇到运算符则出栈两个栈顶元素计算后再入栈，最终栈顶元素就是我们的表达式的值！ 但是中缀表达式不一样，它并没有这样的性质！ 后缀表达式是表达式树的后序遍历，中缀表达式就是表达式树的中序遍历！ 对于上方样例(2+2)*(1+1)，表达式树的后序遍历为2 2 + 1 1 + *，没有问题；中序遍历为2 + 2 * 1 + 1，很明显，中序遍历得到的结果有一个优先级问题！ 括号：括号只影响表达式优先级，不影响表达式树的结构！ 我们建立表达式树进行分析： 叶子节点为运算数 其他节点为运算符 如下方简图： 我们可以对该表达式树进行递归运算，但是并没有 ...

¶一、反转链表I 题目链接：https://www.acwing.com/problem/content/33/ ¶1、解法一 如下方简图： 迭代： 维护两个一前一后的指针a, b即可，每次将 b 指向 a 完成反转 然后 a, b 两个指针都后移一步，由于b指向a会导致b->next丢失，所以先将其保存下来作为c指针 直到b指针为空，再将头结点指向空，返回a节点即可 时间复杂度：O(n)​ 空间复杂度：O(1) AC代码： 12345678910111213141516171819202122/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public: ListNode* reverseList(ListNode* head) { if(!head || !head ...

¶一、JSON ¶1、概述 JSON (JavaScript Object Notation) 是一种轻量级的数据交换格式。易于人阅读和编写。同时也易于机器解析和生成。JSON采用完全独立于语言的文本格式，而且很多语言都提供了对 json 的支持。 这样就使得 JSON 成为理想的数据交换格式。 json 是一种轻量级的数据交换格式。（轻量级指的是跟 xml 做比较。） 数据交换指的是客户端和服务器之间业务数据的传递格式。 ¶2、JSON基本使用 json 是由键值对组成，并且由花括号（大括号）包围。每个键由引号引起来，键和值之间使用冒号进行分隔，多组键值对之间进行逗号进行分隔。 json 本身是一个对象。 json 中的 key 我们可以理解为是对象中的一个属性。 json 中的 key 访问就跟访问对象的属性一样： json 对象.key 123456789101112131415161718192021222324252627282930313233343536// json的定义var jsonObj = { "key1":12, "key2":"abc ...

¶一、Filter ¶1、概述 Filter 过滤器它是 JavaWeb 的三大组件之一。三大组件分别是：Servlet 程序、Listener 监听器、Filter 过滤器。 Filter 过滤器它是 JavaEE 的规范。也就是接口。 Filter 过滤器它的作用是：拦截请求，过滤响应。 拦截请求常见的应用场景有： 权限检查 日记操作 事务管理 ¶2、Filter使用 Filter 过滤器的使用步骤： 编写一个类去实现 Filter 接口 实现过滤方法 doFilter() 到 web.xml 中去配置 Filter 的拦截路径 AdminFilter.java： doFilter方法中的filterChain.doFilter()方法必须要写，可以让未被拦截的请求继续向下执行，若不写该方法，则不被拦截的请求也无法访问到目标资源文件！具体原理请看下方的Filter实现原理图示！ 123456789101112131415161718192021222324252627282930313233343536373839404142public class AdminFi ...

¶一、概述 ¶1、表单重复提交 一些操作可能会导致表单的重复提交，造成数据错误的发生！这时验证码就横空出世了！ 提交完表单。服务器使用请求转发进行页面跳转。这个时候，用户按下功能键 F5，就会发起最后一次的请求。造成表单重复提交问题。解决方法：使用重定向来进行跳转 用户正常提交服务器，但是由于网络延迟等原因，迟迟未收到服务器的响应，这个时候，用户以为提交失败，就会着急，然后多点了几次提交操作，也会造成表单重复提交。 用户正常提交服务器。服务器也没有延迟，但是提交完成后，用户回退浏览器。重新提交。也会造成表单重复提交。 ¶2、验证码解决表单重复提交原理 如下图所示： 经过Servlet程序进行拦截！ ¶二、谷歌Kaptcha使用 ¶1、导包 需要导入谷歌验证码的包kaptcha-2.3.2.jar ¶2、XML配置 在web.xml文件中进行配置如下： 12345678<servlet> <servlet-name>KaptchaServlet</servlet-name> <servlet-class>com.g ...

¶一、Cookie ¶1、Cookie概述 Cookie 翻译过来是饼干的意思。 Cookie 是服务器通知客户端保存键值对的一种技术。 客户端有了 Cookie 后，每次请求都发送给服务器。 每个 Cookie 的大小不能超过 4kb，对同一个域名下的总cookie数量限制为20个。 作用： Cookie一般用于存储少量的安全性较低的数据 在不登陆的情况下，完成服务器对客户端的身份识别， ¶2、Cookie创建 BaseServlet.java： 创建的Servlet程序都继承自该抽象类！可以使用反射动态获取执行方法！ 123456789101112131415161718192021222324252627282930public abstract class BaseServlet extends HttpServlet { @Override protected void doGet(HttpServletRequest req, HttpServletResponse resp) throws ServletException, IOException { ...

¶一、文件上传 ¶1、文件上传介绍 要有一个 form 标签，method=post 请求 form 标签的 encType 属性值必须为 multipart/form-data 值 在 form 标签中使用 input type=file 添加上传的文件 编写服务器代码（Servlet 程序）接收，处理上传的数据。 注意：encType=multipart/form-data 表示提交的数据，以多段（每一个表单项一个数据段）的形式进行拼接，然后以二进制流的形式发送给服务器。 upload.jsp文件： 注意：get的url长度有限制，post无限制，一般上传使用post 123456<%--get的url长度有限制，post无限制--%><form action="uploadServlet" method="post" enctype="multipart/form-data"> 用户名：<input type="text" name="username"><br> 头像：<input type= ...

¶一、EL表达式 ¶1、EL表达式概述 EL 表达式的全称是：Expression Language。是表达式语言。 EL 表达式的什么作用：EL 表达式主要是代替 jsp 页面中的表达式脚本在 jsp 页面中进行数据的输出。 因为 EL 表达式在输出数据的时候，要比 jsp 的表达式脚本要简洁很多。 EL 表达式的格式是：${表达式} EL 表达式在输出 null 值的时候，输出的是空串。jsp 表达式脚本输出 null 值的时候，输出的是 null 字符串。 1234567891011<% request.setAttribute("key1", "value1");%>表达式脚本输出：<%=request.getAttribute("key1")%> <br><%-- 放入key值即可！ --%>EL表达式输出：${key1} <br>表达式脚本输出：<%=request.getAttribute("key2")%> <br>EL表达式输出：${key2} <br>表达式脚本判 ...