swaggyW's Blog

​ 当用户向服务器发送请求时。

​ 在servlet阶段，用户发送请求后，servlet端会接收用户端传来的数据，并通过service层进行业务的处理，再将处理后的结果，通过请求转发或者重定向的方式，反馈给用户。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

public class HelloServlet extends HttpServlet {
    @Override
    protected void doGet(HttpServletRequest req, HttpServletResponse resp) throws ServletException, IOException {
        String username = req.getParameter("username");
        System.out.println(username);
        req.setAttribute("username", username);
        req.getRequestDispatcher("/test/a.jsp").forward(req,resp);
    }

    @Override
    protected void doPost(HttpServletRequest req, HttpServletResponse resp) throws ServletException, IOException {
        doGet(req,resp);
    }
}

​ 在整个过程中，我们需要再web.xml文件中配置相应的Servlet。当用户发送不同的请求，我们就需要创建不同的Servlet程序，并且在xml文件中进行配置。

1
2
3
4
5
6
7
8

<servlet>
    <servlet-name>HelloServlet</servlet-name>
    <servlet-class>servlet.HelloServlet</servlet-class>
</servlet>
<servlet-mapping>
    <servlet-name>HelloServlet</servlet-name>
    <url-pattern>/helloServlet</url-pattern>
</servlet-mapping>

​ 但是，在实际的开发过程中，一个web工程有很多不同的功能，如果这样，用户发送不一样的请求，就要新建一个servlet，就要配置一个servlet，这样会让代码冗余，而且工作量也十分大。那么怎么解决这个问题呢？ SpringMVC很好的解决了这个问题。

​ 在SpringMVC中，你不需要编写servlet程序，因此也不需要在 web.xml中对其进行配置。springMVC对其进行了分离，当用户发送请求时，SpringMVC会通过前端控制器（DispatcherServlet）对用户的请求进行拦截和过滤，分别通过处理器映射、处理器适配、视图解析器处理之后，将结果渲染到视图上。而在此过程中，在处理器适配完成之后，会找到相应的控制器（Controller），进行业务的执行。整个springMVC的执行看下图：

​ 根据上图可以得出具体的执行原理：

1.用户发送请求之后，请求由前端控制器（DispatcherServlet）接收，前端控制器是整个SpringMVC框架的核心。

整数反转

​ 将一个整数进行反转，如123 反转为321

​ 属于是比较简单了、

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
    public int reverse(int num) {
        //记录结果
        long result = 0;
        while (num != 0) {
            result = result * 10 + sum % 10;
            sum /= 10;
        }
        
        return (int) result == result ? result : 0;
    }
}

回文数

判断一个数是不是回文数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
    public boolean isNum(int num) {
        //非负整数判断
        if (num < 0) return false;
        int temp = num;
        int result = 0;
         
        while (temp != 0) {
            result = result * 10 + temp % 10;
            temp /= 10;
        }
        
        return result == num;
    }
}

无重复字符的最长子串

​ 给定一个字符串，找出其中不含有重复字符的最长的子串。并返回其长度。

​ 例：

​ 输入的是: String s = “abcabcbb”

​ 则最长子串是 “abc” 输出3

​ 双指针，一个指针标记起始位置，一个指针标记结束位置。

​ 对于例子来说，假设标记起始位置的指针是 start，遍历字符串，并确定start的值，最开始为0，将字符串中每个字符的下标记录下来，因为在确定start的值时，有可能这个字符出现过，如果出现过，则让start从上一次出现的下一个的位置，开始进行扫描，并且每一次循环，都可以得到当前的子串长度为 i-start+1。

​ 整个遍历过程中，我们如何得到最大长度，假设最终长度是res， 只需要取出当前循环得到的长度和原先长度中的最大值就可以了。如何记录字符串元素的下标。我们知道字符在java内存是通过ASCII的方式，以整型来进行存储的。

根据ASCII对照表，选择一个int数组，大小为128就可以了。

链表相加

​ 题目： 给定两个非空链表，存放的数据都是非负整数，并且都是按照逆序的方式进行存储，要求把这两个数字相加，并返回同样的链表。

​ LeetCode的题目描述都令人头大。直接写个例子。

​ 假设有两个链表：

​ 链表1： 2 —->>>> 4 —->>>> 3

​ 链表2： 5 —->>>> 6 —->>>> 4

由于是逆序的，所以数字是 342和465

相加得到 342+465=807

所以返回的链表是 ： 7 —->>>> 0 —->>>> 8

快速排序

 快速排序的思想是快速排序，通过首尾两个指针进行扫描

先让val=arr[0]
尾指针先开始移动，如果所指元素大于val， 则指针往前移动，当arr[i] < val的时候， 并且arr[0] = arr[i],尾指针停止移动
首指针开始移动, 当所指元素小于val的时候，指针后移，当arr[i] > val 的时候，让arr[尾指针位置] = arr[i]
终止条件： 尾指针的索引小于或者等于首指针

​ 这样一轮过后，就可以确定该元素在数组中的位置，通过迭代的方法，来将基准数归位。

​ 假设现在有这样一个数组

​

​ 取出int val = arr[0] = 3, 首先，尾指针开始移动，直到找到arr[i]=1 < val,这时尾指针停止移动，并且把这个值赋给首指针指向的空间。

​

​ 此时首指针开始移动，当arr[i] > val 的时候，将此时的值赋给尾指针所指向的位置。

都升序排列

冒泡

​ 代码, 每一趟都找出最大的数沉底，比较相邻的两个元素，时间复杂度O(n*n)

​ 冒泡算法是稳定的，对于相同的两个值，冒泡排序不会改变它们的相对位置。

1
2
3
4
5
6
7
8
9
10
11

public void bubbleSort(int[] nums) {
  for (int i = 0; i < nums.length - 1; i++) {
    for (int j = 0; j < nums.length - i - 1; j++) {
      if (nums[j] > nums[j + 1]) {
        int t = nums[j];
        nums[j] = nums[j + 1];
        nums[j + 1] = t;
      }
    }
  }
}

选择

​ 选择排序是按顺序取出元素，并将当前元素与后面所有元素进行比较，如果后面元素小于该当前元素，则交换位置，保证每一趟选择排序都可以得到剩下数组元素中的最小值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

public void selectSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        int min = arr[i]; //最小值
        int index = i; //最小值的下标
        for (int j = i + 1; j < arr.length; j++) {
            if (min > arr[j]) {
                min = arr[j];
                index = j;
            }
            
        } 
        
        if (index != i) {
            arr[index] = arr[i];
            arr[i] = min;
        }
    }
}

​ 选择排序的时间复杂度也是 O(n*n)，但是选择排序不稳定，在一轮排序中很有可能，例子如下是

1
2
3
4

现在有一个数组: int[] arr = {2,3,12,2,1}
进行第一轮选择时，min = arr[0] = 2， 最后arr[0] 会与arr[4] = 1 交换位置，
结果: int arr[] = {1,3,12,2,2},
此时，两个相同的数字的相对位置发生了变化，所以选择排序是不稳定的。

队列

​ 队列和栈不同的是，栈遵循先进后出的原则， 而队列为先进先出（FIFO），就像排队买东西一样，先到先得。

​ 队列使用链表实现是比较简单的，用数组结构来实现队列。

​ 通过两个指针，一个指向队头（front），一个指向队尾（rear）。当入队时，让rear前移，当出队时，让front前移。如图所示，规定rear指向队尾的下一个元素。front指向队头元素。

如果是这样操作的话，很明显，出队以后，内存空间就使用不了了，这样得多浪费内存，因此，将队列设计成循环队列。大致长这样

初始化的时候，两个指针指向同一位置，当入队时，rear指针后移，即rear指针永远指向队尾元素的下一个，所以，在循环队列中，有一块空间是不存放数据的。

​ 如何确定队列满了还是空了。只要当 front == rear 则说明队列空了；当rear + 1 == front时，就说明队列满了。但是在不断地入队出队操作，rear值肯定越来越大，可以通过mod的方法来保证rear的值。即（rear + 1） % maxSize == front。

如何得到任意时刻队列中的元素个数。用（rear-front+maxSize） % maxSize就可以得到，加上maxSize是为了防止rear的值小于front的值。

栈

​ 栈是一种很常见的数据结构，其特点是先进后出（FILO，first in last out），只可以操作栈顶的元素。

​ 在jdk中，已经封装了Stack，可以拿来即用。api中Stack是通过Vector实现的。是一个线程安全的数组框架。

​ 仿照java api来实现一个栈。。

​

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

class Stack {
    //数组模拟栈
    int[] stack;
    int maxSize;
    int top = -1; //用来指向栈顶元素
    
    public Stack() {}
    
    public Stack(int maxSize) {
        this.maxSize = maxSize;
        stack = new int[maxSize];
    }
    
    /**
    * 栈结构主要有几个方法： 
    * 入栈（压栈）： 即向栈中添加数据
    * 出栈： 删除栈顶元素
    * 查看栈顶元素
    * 判断栈是否空
    * 判断栈是否满
    */
    
    //this stack is empty
    public boolean isEmpty() {
        return top == -1;
    }
    
    //this stack is full
    public boolean isFull() {
        return top == maxSize - 1;
    }
    
    //push data
    public void push(int data) {
        if ( isFull() ) return;
        stack[++top] = data;
    }
    
    //pop and return this data
    public int pop() {
        if(isEmpty()) return;
        return stack[top--];
    }
    
    //peek 
    public int peek() {
        return stack[top];
    }
    
    public void traverse() {
        if (isEmpty()) return;
        for (int i = top; i >= 0; i--) {
            System.out.println(stack[i]);
        }
    }
}

栈的应用比较广泛

​ 在程序函数的调用中，使用到了栈结构，当调用一个函数时，会开辟一块空间，用来存放函数中的变量等，而当函数执行完毕之后，就会销毁这个空间，即出栈。

​ 使用栈来对数学表达式求值等等

​ 主要记录一下，堆内存的结构，以及垃圾回收。

​ 堆由于存放的是对象实例，对象主要是存放数据，所以当一个对象没有使用、或者没有引用指向它时，它就有可能会被垃圾回收器回收。

​ 在jdk1.8之后，堆区主要有三个区域，新生代、老年代、元空间。

​ 新生代包括Eden区(伊甸园区)、 survivor0区（from区）、survivor1区（to区）。

ps: 元空间在jdk1.7之前叫做永久代，元空间中主要存放的是java自带的类信息，如rt.jar包下的类，常用的集合框架等等…

​ 因此，垃圾回收主要发生在前面两个区域。首先要说明的有两点：

1. 对于大部分对象，当它被创建并且在堆中分配内存时，这个对象都是在伊甸园区（后面都说新生代）；
2. 对于大对象会直接进入老年代。像字符串、数组等。这样是为了防止对象复制而降低效率。

gc

大部分的对象使用完毕之后就会被回收，因此在新生代发生gc是十分频繁的。当新生代满了之后，就会发生一次young gc，一次ygc过后，存活下来的对象会被复制进入from区，当新生代发生第二次ygc后，所有存活下来的对象将会被复制到to区，此时，from区会清空，而from区和to区会角色互换。即两者的名字会交换。就是要保证to区是空的。当进入一次幸存者区时，这些对象的年龄就会+1，而当一个对象的年龄达到15岁时，就会进入老年代。

​ Java内存模型，所有的变量都存储在主内存中，而线程拿到的变量都是从主内存中拷贝的副本。线程对所有变量的操作都是在本地内存进行，而不能直接读取主内存。

​ 多个线程访问同一个变量，并且复制到自己的本地内存对变量进行操作，很有可能两个线程使用的数据不一致，要解决这个问题，我们可以把共享变量用关键字volatile来修饰，来保证线程每次读取都是从主内存中读取数据。

volatile

​ 并发编程的三个重要特性： 原子性、可见性、有序性。

​ 原子性： 一个操作或者一系列操作，要么都成功，要么都失败，所有的操作都是一个整体，要么都执行、要么都不执行。synchronized关键字就可以保证原子性。

​ 可见性： 一个线程对共享变量进行修改，其他线程必须能够得到最新的值。即volatile关键字可保证可见性。

​ 顺序性： 编译器会优化代码，书写的代码可能和执行的代码顺序不一样，所以要保证程序的顺序，可用volatile来防止指令重排。

synchronized 和 volatile

​ synchronized保证线程同步，可以修饰类，方法，代码块，修饰类和静态方法则是给类上锁，修饰方法可以给对象上锁，修饰代码块可以指定加锁对象，可以是一个变量、对象，也可以是一个类。而volatile更加轻量级，只能修饰变量。