小牛博客

题目链接：AcWing 15. 二维数组中的查找 ¶一、题解 题目大意： 在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。判断是否包含某个数字！ 思路分析： 本题真的是一个思维题目！巧妙的很！ 我们可以将右上角位置作为突破口！ 对于有上角来说，它是一行最大，它又是一列最小！ 这是一个很好的特性！ 若目标数字小于右上角，则它一定不是最后一列，删掉即可 若目标数字大于右上角，则它一定不是第一行，删掉即可 若目标数子等于右上角，则表名已经找到，否则没有找到 时间复杂度：矩阵一共有 n 行，m 列，则复杂度为 O(n + m) 空间复杂度：O(1) ¶二、AC代码 12345678910111213class Solution {public: bool searchArray(vector<vector<int>> array, int target) { if(array.empty() || array[0].empty()) return false; int i = 0, j ...

题目链接：AcWing 77. 翻转单词顺序 ¶一、题解 思路一： 开一个额外的字符串来存储每个单词 倒序进行扫描一遍，然后进行拼接res += tmp + " "即可 最后记得还要进行一次res += tmp 时间复杂度：O(n) 空间复杂度：O(n) 可以参考代码一！ 思路二： 思路一很明显使用了额外的空间，更优的做法是不使用额外的空间进行原地处理！ 可以先将整个字符串进行反转 然后对每一个单词进行反转即可 时间复杂度：O(n) 空间复杂度：O(1) 参考代码二！ ¶二、AC代码 参考代码一： 123456789101112class Solution {public: string reverseWords(string s) { string res, tmp; for(int i = s.size() - 1; i >= 0; i --){ if(s[i] == ' ') res += tmp + " ", tmp = ""; else tmp = s[i] + tmp; ...

题目链接：LeetCode 190. 颠倒二进制位 ¶一、题解 题目意思： 将一个32位无符号整数进行反转！ 思路： 可以从后往前取出该无符号整数的每一位即n >> 1 & 1 然后将结果左移空出最后一位再加上上一步的结果即可，(res << 1) + (n >> i & 1) 注意： 加法优先级高于位运算 移位运算高于与或非 时间复杂度：O(1) 空间复杂度：O(1) ¶二、AC代码 参考代码： 12345678class Solution {public: uint32_t reverseBits(uint32_t n) { uint32_t res = 0; for(int i = 0; i < 32; i ++) res = (res << 1) + (n >> i & 1); return res; }}; document.querySelectorAll('.github-emoji') ...

题目链接：AcWing 19. 二叉树的下一个节点 ¶一、题解 题目大意： 给定一个二叉树中的一个节点，找到使用中序遍历的下一个节点！ 思路： 分情况讨论即可！ 若当前节点有右子树（例如下图的C），则表示当前节点的左子树已经遍历完毕，则只要去找他的右子树得最左边节点就是该节点的后继节点（即B） 若当前节点没有右子树（例如下图的D），则表示当前节点左子树已经遍历完毕，需要沿着父节点找，找第一个是其父节点左儿子的节点，例如当前节点是D，则第一个满足是其父节点左儿子的节点是F，则C的father就是D的后继，即F是D的后继。 简图如下： 时间复杂度：O(n) 空间复杂度：O(1) ¶二、AC代码 参考代码： 12345678910111213141516171819202122/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode *father; * Tr ...

题目链接：LeetCode 173. 二叉搜索树迭代器 ¶一、题解 题目大意： 实现一个中序遍历的二叉树！但是要通过迭代器实现！即完成下面三个方法！ 思路： 其实就是二叉树中序遍历非递归写法的拆分！ 二叉树非递归中序遍历写法：LeetCode的94题就是！ 构造器处理第一部分 next处理下一部分，然后还得处理和构造器相同的部分 hasNext则可以直接判断栈是否为空即可 时间复杂度： O(n) 空间复杂度： O(h)，h为树的高度 ¶二、AC代码 参考代码： 1234567891011121314151617181920212223242526272829303132333435363738394041424344/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * ...

¶一、Maven介绍 ¶1、Maven是什么 Maven是一款服务于Java平台的自动化构建工具！是Apache的一款开源的项目管理工具！ 什么是构建？ 简单来说：就是以“Java源文件”、“框架配置文件”、“JSP”、“HTML”、“图片”等资源为“原材料”，去“生产”一个可以运行的项目的过程。 构建过程中的各个环节： 清理∶将以前编译得到的旧的class字节码文件删除，为下一次编译做准备[2]编译∶将Java源程序编程成class字节码文件 测试∶自动测试，自动调用junit程序 报告∶测试程序执行的结果 打包∶动态Web工程打war包，Java工程打jar包 安装：Maven特定的概念——将打包得到的文件复制到“仓库”中的指定位置 部署︰将动态Web工程生成的war包复制到Servlet容器的指定目录下，使其可以运行 ¶2、Maven能干什么 如果项目非常庞大，就不适合继续使用package来划分模块。借助于Maven就可以将一个项目拆分成多个工程。 借助于Maven，可以将jar包仅仅保存在“仓库”中，有需要使用的工程“引用”这个文件接口，并不需要真的把jar包复制过 ...

题目链接：LeetCode 61. 旋转链表 ¶一、题解 题目大意： 给定一个链表，将链表每个节点都向后移动k个位置！ 思路： k的数非常大，所以可以和链表长度去个模！ 由于k %= n，所以以防除0问题，先在最开始判断一下，若链表长度为0，则直接返回即可 将每个节点后移k位，即将链表后k个节点移到链表开头即可 指针向后移动n - k - 1次即可走到后k个节点的上一个节点 然后处理一下指针指向即可！ 时间复杂度： O(n) 空间复杂度： O(1) ¶二、AC代码 1234567891011121314151617181920212223242526/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListN ...

整个 Spring5 框架的代码基于 Java8，运行时兼容 JDK9，许多不建议使用的类和方法在代码库中删除！ Spring5中文版新功能可以在这里看到：https://cntofu.com/book/95/33-what-new-in-the-spring-framework.md ¶一、Spring整合Log4j2日志框架 Spring 5.0 框架自带了通用的日志封装 ，Spring5 已经移除 Log4jConfigListener，官方建议使用 Log4j2 ¶1、导包 ¶2、创建 log4j2.xml 配置文件 配置文件要放到src下，且名字只能为 log4j2.xml 1234567891011121314151617181920<?xml version="1.0" encoding="UTF-8"?><!--日志级别以及优先级排序: OFF > FATAL > ERROR > WARN > INFO > DEBUG > TRACE > ALL --><!--Configuratio ...

¶一、JdbcTemplate 可以使用Spring提供的JdbcTemplate来操作数据库！ 虽然后面会被其他框架代替！ ¶1、导包 导入如下包： ¶2、配置XML 开启注解扫描 配置数据库连接池 配置JdbcTemplate 12345678910111213141516171819202122232425262728293031<?xml version="1.0" encoding="UTF-8"?><beans xmlns="http://www.springframework.org/schema/beans" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:context="http://www.springframework.org/schema/context" xmlns:aop="http://www.springframework.org/schema/aop" xsi:schemaLocation="http:/ ...

¶一、AOP概述 ¶1、概述 Aspect Oriented Programming，面向切面编程，利用 AOP 可以对业务逻辑的各个部分进行隔离，从而使得业务逻辑各部分之间的耦合度降低，提高程序的可重用性，同时提高了开发的效率。 通俗描述：不通过修改源代码方式，在主干功能里面添加新功能 ¶2、AOP底层原理 底层自然是通过动态代理实现的！ ¶2.1、JDK动态代理 有接口情况，使用 JDK 动态代理！ 创建接口实现类代理对象，增强类的方法！ ¶2.2、CGLIB动态代理 没有接口情况，使用 CGLIB 动态代理！ 创建子类的代理对象，增强类的方法！ ¶二、JDK动态代理 ¶1、创建接口，定义方法 123public interface UserDao { int add(int a, int b);} ¶2、创建接口实现类，实现方法 12345678public class UserDaoImpl implements UserDao { @Override public int add(int a, int b) { System.o ...

¶一、Spring介绍 Spring 是轻量级的开源的 JavaEE 框架。Spring 可以解决企业应用开发的复杂性！ ¶1、概述 Spring 有两个核心部分： IOC：控制反转，把创建对象过程交给 Spring 进行管理 Aop：面向切面，不修改源代码进行功能增强 Spring 特点： 方便解耦，简化开发 Aop 编程支持 方便程序测试 方便和其他框架进行整合 方便进行事务操作 降低 API 开发难度 ¶2、Spring下载 下载地址，点击这里！ 下载完成后解压找到lib目录，其中就是相关jar包！ SpringIOC基本包： 注意：Spring使用依赖于一个日志包，commons-logging包，为第三方包！ ¶二、IOC概述 ¶1、什么是IOC IOC：（Inversion Of Control）控制反转，把对象创建和对象之间的调用过程，交给 Spring 进行管理 使用 IOC 目的：为了降低耦合度 ¶2、IOC底层原理 三大组成部分： xml 解析 工厂模式 反射 原理如下方简图： ¶三、IOC容器两种接口 IOC 思想基于 IOC 容器完成，IO ...

题目链接：LeetCode 82. 删除排序链表中的重复元素 II ¶一、题解 同样又是一道熟悉的链表题目：题目要求将有重复的节点全部删掉！ 这道题还是比较好想的： 如下图： 为了统一该链表，防止第一个节点就是重复节点导致，头结点的改变，我们使用虚拟头结点指向该头节点，实现统一操作！ 用一个指针p指向当前节点，另一个指针q指向下一个节点 接下来，q从p->next开始，一直走到第一个与p->next不同元素的位置，这时有两种情况： p->next->next == q：则说明p后面没有重复元素，直接后移p = p->next p->next->next != q：则说明p后面有重复元素，则跳过这一堆重复元素，p直接指向q即可，p->next = q 最后返回dummy->next即可 时间复杂度：O(n) 空间复杂度：O(1) ¶二、AC代码 参考代码： 12345678910111213141516171819202122232425/** * Definition for singly-linked list ...