发表于

AcWing 41 包含 min 函数得栈

题目

设计一个支持push，pop，top等操作并且可以在O(1)时间内检索出最小元素的堆栈

  • push(x)–将元素x插入栈中
  • pop()–移除栈顶元素
  • top()–得到栈顶元素
  • getMin()–得到栈中最小元素

样例

1
2
3
4
5
6
7
8
MinStack minStack = new MinStack();
minStack.push(-1);
minStack.push(3);
minStack.push(-4);
minStack.getMin();   --> Returns -4.
minStack.pop();
minStack.top();      --> Returns 3.
minStack.getMin();   --> Returns -1.
阅读全文 »

发表于

剑指 Offer——面试题 3-1

题目

找出数组中的重复数字

在一个长度为n的数组里的所有数字都在0 ~ n - 1的范围内，数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次，请找出数组中任意一个重复的数字

输入样例

1
[2, 3, 1, 0, 2, 5, 3]

输出样例

1
2 或 3
阅读全文 »

发表于

AcWing 1452 寻找矩阵的极小值

题目

给定一个n × n的矩阵，矩阵中包含n × n个_互不相同_的整数

定义极小值：如果一个数的值比与它相邻的所有数字的值都小，则这个数值就被称为极小值

一个数的相邻数字是指其上下左右四个方向相邻的四个数字，另外注意，处于边界或角落的数的相邻数字可能少于四个

要求在O(nlogn)的时间复杂度之内找出任意一个极小值的位置，并输出它在第几行第几列

本题中矩阵是隐藏的，你可以通过我们预设的int函数query来获得矩阵中某个位置的数值是多少

例如，query(a,b)即可获得矩阵中第a行第b列的位置的数值

注意：

  1. 矩阵的行和列均从0开始编号
  2. query()函数的调用次数不能超过(n + 2) × ⌈log2n⌉ + n
  3. 答案不唯一，输出任意一个极小值的位置即可

数据范围

1 ≤ n ≤ 300，矩阵中的整数在int范围内

输入样例：

1
[[1, 2, 3], [4, 5, 6], [7, 8, 9]]

输出样例：

1
[0, 0]
阅读全文 »

发表于

AcWing 1451 单链表快速排序

题目

给定一个单链表，请使用快速排序算法对其排序

要求：期望平均时间复杂度为O(nlogn)，期望额外空间复杂度为O(logn)

思考题： 如果只能改变链表结构，不能修改每个节点的val值该如何做呢

数据范围

链表中的所有数大小均在int范围内，链表长度在[0, 10000]

输入样例：

1
[5, 3, 2]

输出样例：

1
[2, 3, 5]
阅读全文 »

发表于

AcWing 756 蛇形矩阵

题目

输入两个整数n和m，输出一个n行m列的矩阵，将数字1到n * m按照回字蛇形填充至矩阵中

具体矩阵形式可参考样例

输入格式

输入共一行，包含两个整数n和m

输出格式

输出满足要求的矩阵

矩阵占n行，每行包含m个空格隔开的整数

数据范围

1≤n, m≤100

输入样例：

1
3 3

输出样例：

1
2
3
1 2 3
8 9 4
7 6 5
阅读全文 »

发表于

什么是 SpringMVC？

​ SpringMVC 是一种基于 Java 实现的 MVC 设计模式的请求驱动类型的轻量级 web 框架，使用了 MVC 架构模式的思想，将 web 层进行职责解耦，基于请求驱动指的就是使用请求-响应模型，框架的目的就是帮助我们简化开发

阅读全文 »

发表于

JAVA 代理模式

​ 简而言之，代理是一种通过创建代理对象的方式，从而实现对被代理对象实现功能增强的一种方式，JAVA 中有静态和动态两种代理，动态代理又可以分为_基于接口的动态代理_（JDK 实现）和_基于子类的动态代理_（cglib 实现），这里我们讲解基于子类的动态代理

阅读全文 »

发表于

完全使用注解实现 IOC

​ 通过使用注解的方式，可以更方便的将我们自己创建的对象放入到 Spring bean 容器中，我们这里介绍使用纯注解的方式实现 IOC，并且主要介绍替代.xml文件配置的过程，虽然这种方式对于包装好的对象使用起来有些麻烦

阅读全文 »

发表于

Spring 中的依赖注入

​ 依赖注入：Dependency Injection，它是 spring 框架核心 ioc 的具体实现

​ 我们的程序在编写时，通过控制反转，把对象的创建交给了 spring，但是代码中不可能出现没有依赖的情况，ioc 解耦只是降低他们的依赖关系，但不会消除

​ 例如：我们的业务层仍会调用持久层的方法，那这种业务层和持久层的依赖关系，在使用 spring 之后，就让 spring 来维护了，简单的说，就是坐等框架把持久层对象传入业务层，而不用我们自己去获取

阅读全文 »

发表于

Spring-IOC

​ IOC（Inversion of Control）意为控制反转，把创建对象的权利交给框架，是框架的重要特征，IOC 的作用是消减程序的耦合，解除我们代码中的依赖关系

​ 下面我们主要说明基于XML 文件来使用 IOC 的过程，以及使用 XML 文件创建 bean 的三种方式

阅读全文 »