牛客题目——盛水最多的容器、字符串的排列

---

题目1——盛水最多的容器

给定一个数组height，长度为n，每个数代表坐标轴中的一个点的高度，height[i]是在第i点的高度，请问，从中选2个高度与x轴组成的容器最多能容纳多少水。
不能倾斜容器；当n小于2时，视为不能形成容器，请返回0；数据保证能容纳最多的水不会超过整型范围，即不会超过2^31-1。

示例
输入：[1,7,3,2,4,5,8,2,7]
输出：49

解题思路

容器的盛水最大水量由左右两板中的最短板控制，最短板×底部的两板距离就可以得到当前容器的容器。但是如果要找最大值，可以利用贪心思想和对撞指针(因为中间可能出现更高的板子)，每次移动最短的指针，贪心思想下较长的一边比较短的一边更可能出现更大容积。

奇安信笔试中第二个编程题：给定一个数组，数组下标为x，数组元素为y，其中两个点构成的矩阵面积为x轴方向的距离*两个点中最小的y，求数组中任意两个点构成的矩阵的最大面积。
这个题的解题思路跟上述相同。

代码实现

import java.util.*;
public class Solution {
    public int maxArea (int[] height) {
        int maxArea = 0;
        int l = 0;
        int r = height.length-1;
        while(l<r){
            int area = Math.min(height[l],height[r])*(r-l);
            maxArea = Math.max(area,maxArea);
            if(height[l]<height[r])
                l++;
            else 
                r--;
        }
        return maxArea;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

题目2——字符串的排列

输入一个长度为n的字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。
例如输入字符串ABC，则输出由该字符A，B，C所能排列出来的所有字符串ABC,ACB,BAC,BCA,CAB,CBA.

示例
输入：“aab”
输出：[“aab”,“aba”,“baa”]

解题思路

递归+回溯
递归是一个函数在其定义中直接或间接调用自身的一种方法，它将一个大问题转化为一个与原问题相似的规模较小的问题来求解。
如果是线型递归，子问题直接回到父问题不需要回溯，但是如果树型递归，父问题有很多分支，子问题需要回到父问题，进入另一个子问题。因此回溯指的是递归过程中从某一分支的子问题回到父问题进入父问题的另一子问题分支。
具体做法如下：

• 先对字符串按照字典排序，获取第一个排列情况；
• 准备一个空串暂存递归过程中组装的排列情况，使用额外的vis访问数组来记录哪些位置的字符被加入了；
• 每次递归从头遍历字符串，获取字符加入：首先根据vis数组判断字符是否加入，加入则继续遍历，否则判断当前加入字符是否跟前一个字符相等且前一个字符已经访问过，符合情况则不加入，否则加入该字符；
• 加入字符后，标记此字符访问过，进入下一层递归；
• 回溯时需要修改vis数组，同时去掉刚刚加入字符串的元素；
• 当临时字符串长度到达原串长度就是一种排列情况。

代码实现

import java.util.*;
public class Solution {
    public void recursion(ArrayList<String> res, char[] s, StringBuffer sbuffer,boolean[] vis){
        if(sbuffer.length() == s.length){
            res.add(sbuffer.toString());
            return;
        }
        for(int i=0;i<s.length;i++){
            //如果该元素已经加入，则不需要加入了
            if(vis[i])
                continue;
            //如果加的字符和前一个字符相同，并且前一个字符已经用过，则不需要加入了
            if(i>0 && s[i] == s[i-1] && !vis[i-1])
                continue;
            vis[i] = true;
            sbuffer.append(s[i]);
            recursion(res,s,sbuffer,vis);
            //回溯
            vis[i] = false;
            sbuffer.deleteCharAt(sbuffer.length()-1);
        }
    }
    public ArrayList<String> Permutation (String str) {
        ArrayList<String> res = new ArrayList<String>();
        if(str == null || str.equals(""))
            return res;
        char[] s = str.toCharArray();
        StringBuffer sbuffer = new StringBuffer();
        boolean[] vis = new boolean[str.length()];
        Arrays.fill(vis,false);
        Arrays.sort(s);
        recursion(res,s,sbuffer,vis);
        return res;
    }
}
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

记录Java一些面试题

抽象类和接口？

抽象类用abstract来修饰，用来捕捉子类的通用性，它不能被实例化，只能用作子类的超类，不能被final和static修饰。
抽象类中不一定包含抽象方法，但是有抽象方法的类一定是抽象类。
如果子类不是抽象类的话，它需要实现父抽象类中所有的抽象方法，非抽象方法可重写也可不重写。

接口是公共的行为的规范标准，只要符合标准规范，就可以通用。
如果一个类实现了某个接口，那么它要实现接口中所有的抽象方法。
接口中的方法被隐式指定为public abstract，变量被隐式指定为public static final。
接口不能有静态代码块(JDK8中引入静态方法)和构造方法。
类之间的继承是单继承，而接口之间可以多继承，相当于多个接口的合并，一个类可以实现多个接口。

1、如果想拥有一些方法，并想让他们中的一些有默认的具体实现，选择抽象类。
2、如果想实现多继承，选择接口；
3、如果基本功能不断变化，选择抽象类，如果使用接口，那么每次变更都需要相应的去改变实现该接口的所有类。
1
2
3

内存泄漏？

内存泄漏：不再被使用的对象不能被回收，造成内存泄漏。
如果长生命周期的对象持有短生命周期的引用，尽管短生命周期的对象不再使用，但是因为长生命周期对象持有它的引用而导致不能被回收，从而导致内存泄漏。

内存泄漏的情况和解决：

• 静态集合类：生命周期与程序一致，容器中的对象在程序结束前不能被释放(可以在退出程序之前，将集合里的东西clear，然后置为null，再退出程序)；
• 数据库、IO连接等连接未关闭：不再使用连接时，需要调用close方法来释放连接，然后垃圾回收器才能回收对应的对象，否则，连接不显示关闭，会造成大量对象无法被回收；
• 变量的作用域不合理：一个变量的定义作用范围大于其使用范围，很有可能造成内存泄漏；
• 内部类持有外部类：内部类被长期引用，即使外部类不再被使用，但内部类持有外部类对象，这个外部类也无法被垃圾回收；
• 改变哈希值：当一个对象被存储进HaseSet集合中以后，就不能修改这个对象中参与哈希运算的字段了，否则修改后的哈希值与最初存进去的哈希值不同，这样无法使用当前对象引用作为参数去检索对象时，将返回找不到对象的结果，也会导致无法从HashSet中单独删除对象，造成内存泄漏；
• 忘记缓存中的对象引用：可以使用WeakHashMap，当key没有引用时，此map会自动丢弃此值；
• 没能及时取消监听器和回调：可以保存它们的引用到WeakHashMap中的键。

Spring的IoC和AOP？

• IoC：控制反转，指的是不需要我们手动创建对象，而是将对象的创建权交给Spring容器去创建，利用了工厂模式将对象交给容器管理，只需要在配置文件中配置相应的bean，以及设置相关的属性，让spring容器来生成并管理类的实例对象，这样降低了代码间的耦合度，使资源管理更加容易。
• AOP：用于将那些与业务无关，但却对多个对象产生影响的公共行为和逻辑，抽取并封装成为一个可重用的模块，这个模块称为“切面”。Sping使用的动态代理，每次运行都是在内存中临时生成一个AOP对象，这个对象包含了目标对象的全部方法，并且在特定切点做了增强处理，然后回调对象的方法。同样是降低了各部分之间的耦合程度，提高了代码可重用性。

Java的4种引用？

• 强引用：通过new创建的对象，只要强引用存在，垃圾回收器将永远不会回收被引用的对象，如果想中断强引用与对象之间的联系，可以显示的将引用赋值为null。
• 软引用：javalang.ref.SoftReference，用来描述一些非必须但仍有用的对象。在内存足够的时候，软引用对象不会被回收，只有在内存不足时，系统则会回收软引用对象。
• 弱引用：java.lang.ref.WeakReference，弱引用的引用强度比软引用要更弱一些，无论内存是否足够，只要JVM开始进行垃圾回收，那些被弱引用关联的对象都会被回收。
• 虚引用：java.lang.ref.PhantomReference，虚引用是最弱的一种引用关系，如果一个对象仅持有虚引用，那么他就和没有任何引用一样，在任何时候都可能被垃圾回收器回收。使用虚引用的目的是为了在对象回收时收到通知，可以用来进行销毁前的一些操作。

https为什么是安全的？

https在http的基础上加入了SSL/TSL协议，通过SSL证书来验证服务器的身份，并且在浏览器和服务器之间的通信进行混合加密(非对称加密解决密钥交换，后续数据传输使用对称加密)。

可防止中间人攻击，确保数据在传输过程中不被窃取、篡改。
但是要比http耗时，并且证书需要付费。

用过哪些JDK自带的命令行工具？

（1）jps：用于显示指定系统内所有HotSpot虚拟机进程，并且能显示虚拟机执行主类。

（2）jstat：用于监视虚拟机各种运行状态信息的工具，可以显示本地或者远程的虚拟机进程类装载、内存、GC、JIT等运行数据。
下图中：每5秒中查看一次id为12524的虚拟机进程的GC情况，一共查询2次。

（3）jmap：将java堆使用情况快照一份导出来供我们查看，用来排查问题。

（4）jhat：和jmap搭配使用，jmap导出的快照文件用jhat打开分析。


（5）jstack：用于生成虚拟机当前时刻线程快照，主要用来定位线程出现长时间停顿的原因，通过jstack可知各线程的调用堆栈情况。

（6）jinfo：用来查看和调整虚拟机各项参数。

Spring用到了哪些设计模式？

• 工厂模式：把创建对象的工作交给工厂，应用有BeanFactory和ApplicationContext等。
• 单例模式：比如线程池、Spring的上下文对象、日志对象等，单例模式好处在于减少了系统的开销和GC线程回收内存的压力。
• 策略模式：封装好一组策略算法，外部客户端根据不同的条件选择不同的策略算法解决问题，比如在Spring中定义了不同的Resource类的实现类。
• 代理模式：Spring AOP主要是基于动态代理实现的，如果要代理的类实现了某个接口，则使用JDK动态代理，没有实现接口则使用Cglib动态代理。
• 模板模式：定义了一个算法的骨架，但是将一些步骤延迟到子类中。一般定义一个抽象类为骨架，子类重写抽象类中的模板方法实现骨架中特定的步骤。Spring中的事务管理器就是运用模板模式的设计。模板方法使得子类可以不改变一个算法的结构即可重定义该算法的某些特定步骤的实现方式。
• 适配器模式与责任链模式：能够使接口不兼容的对象相互合作，将一个类的接口转换为客户期望的另外一个接口。Spring AOP中使用Advice通知来增强被代理类的功能，每个Advice都有对应的拦截器(拦截请求并作相应的处理)，Spring需要将每个Advice都封装成对应的拦截器类型返回给容器。将通知类转换为拦截类之后，就添加到拦截器集合中，然后就用到了责任链模式。