算法题目

java 判断二维数组中是否存在某个数

题目：给定一个二维数组，判断其中是否存在某个数 
例如：给定数组{{1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}}，判断7是否存在于数组中

 

public boolean find(int[][] matrix,int rows,int columns,int number){
        if(matrix!=null&&rows>0&&columns>0){
            int row = 0;
            int column = columns-1;
            while(row<rows&&column>=0){
                if(matrix[row][column]==number){
                    return true;
                }
                if(matrix[row][column]>number){
                    column--;
                }else{
                    row++;
                }
            }

        }

        return false;
    }

 

 

 

青蛙跳台阶的算法

 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

    如果n=1，只有一种跳法，那就是1

    如果n=2，那么有两种跳法，2，[1,1]

    如果n=3，那么有三种跳法，[1,1,1],,[1,2],[2,1]

    如果n=4，那么有五种跳法，[1,1,1,1],[1,1,2],[1,2,1],[2,1,1],[2,2]

    如果n=5，那么有八种跳法，[1,1,1,1,1],[1,1,1,2],[1,1,2,1],[1,2,1,1],[2,1,1,1],[2,2,1],[2,1,2],[1,2,2]

    结果为1，2，3，5，8  这不特么是斐波那切数列嘛

 

 递归做法：
    public static int jump(int n){
        if (n==0)
            return 0;
        if (n==1)
            return 1;
        if (n==2)
            return 2;
        return jump(n-1)+jump(n-2);
    }
    非递归做法：
    public static int jump2(int n){
        if (n==0)
            return 0;
        if (n==1)
            return 1;
        if (n==2)
            return 2;
        int n1=1;
        int n2=2;
        int count=2;
        while (count++<=n){
            int tmp=n1;
            n1=n2;
            n2=tmp+n2;
        }
        return n2;
    }

 

 

2、3. 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

    

    f(n) = f(n-1) + f(n-2) + f(n-3) + ... + f(n-(n-1)) + f(n-n)= f(0) + f(1) + f(2) + f(3) + ... + f(n-2)+f(n-1)

    f(n-1) = f(0) + f(1)+f(2)+f(3) + ... + f((n-1)-1) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2)

    so  f(n)=2*f(n-1)

    public int Jump3(int n) {

            if (n <= 1) {

                return 1;

            } else {

                return 2 * Jump3(n - 1);

            }

        }

 

4. 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个m级的台阶总共有多少种跳法。

   先列多项式：

   f(n) =  f(n-1) + f(n-2) + f(n-3) + ... + f(n-m)

   f(n-1) =   f(n-2) + f(n-3) + ... + f(n-m) + f(n-m-1)

   化简得：f(n) = 2f(n-1) - f(n-m-1)

 

public static int Jump4(int n,int m ) {
         //当大于m的时候是上面的公式
         if(n > m){
             return 2*Jump4(n-1, m)-Jump4(n-1-m, m);
         }
         //当小于等于m的时候就是和n级的相同了
         if (n <= 1) {
             return 1;
         } else {
             return 2 * Jump4(n - 1,n);
         }
     }
}

 

 

贪心算法和动态规划算法

贪心算法

与动态规划的区别：贪心算法中，作出的每步贪心决策都无法改变，由上一步的最优解推导下一步的最优解，所以上一部之前的最优解则不作保留。

能使用贪心法求解的条件：是否能找出一个贪心标准。我们看一个找币的例子，如果一个货币系统有三种币值，面值分别为一角、五分和一分，求最小找币数时，可以用贪心法求解；如果将这三种币值改为一角一分、五分和一分，就不能使用贪心法求解。

1、贪心最经典的例子是找钱问题，某国钱币包含1、3、4元，如果要找6元，如何找钱会找的最少？               

贪心的思想是每次都拿最大的，先拿4元，再拿一个1元，再拿一个1元，一共是三张。每次都拿最大的就是贪心，但实际上，只需要两张三元是最优解               

所以说贪心算法不一定能得到最优解，贪心必须在一定条件下得到的才是最优解，比如我国钱币，1、5、10元，大家平时找钱使用贪心法就是最优解。

2、贪心的做法是自顶向下的，而动态规划的解法是自底向上的。               

比如还是找钱问题，动态规划的求解就是找一元如何找的最少，找两元如何找的最少，找三元如何找的最少，并且每次算当前找的最少的钱都使用了之前计算的各自的最优解，从之前所有子集的最优解中找到最优解。               

同时由于每次都记录了每个子问题的最优解，不用每次都重新求子问题的最优解，而是直接使用，就会比暴力解法快很多。

3、         

1）、贪心算法是动态规划的一种特例，贪心算法能解决的问题动态规划一定能解决。动态规划能解决的问题，贪心不一定能够解决               

2）、贪心的复杂度低，动态规划的复杂度高

例：贪心法标准的选择

设有n个正整数，将它们连接成一排，组成一个最大的多位整数。

例如：n=3时，3个整数13，312，343，连成的最大整数为34331213。

又如：n=4时，4个整数7，13，4，246，连成的最大整数为7424613。

输入：n个数

 

输出：连成的多位数

快速排序，什么时候复杂度最大

public void quickSort(int[] num, int st, int ed) {
        if (st >= ed) return;
        int left = st;
        int right = ed;
        int value = num[left];
        while (left < right) {
            while(left < right && num[right] >= value){
                right--;
            }
            num[left] = num[right];
            while(left < right && num[left] < value){
                left++;
            }
            num[right] = num[left];
        }
        int mid = left;
        num[mid] = value;
        quickSort(num, st, mid - 1);
        quickSort(num, mid + 1, ed);
    }

    public static void main(String[] args) {
        QuickSort quickSort = new QuickSort();
        int[] num = {3, 7, 4, 2, 5, 8, 1};
        quickSort.quickSort(num, 0, 6);
        for (int t : num) {
            System.out.println(t);
        }
    }

 

归并排序

import java.util.Arrays;

public class MergeSort {

    public int[] mergeSort(int[] num) {
        if (num.length <= 1) return num;
        int mid = num.length / 2;
        int[] left = Arrays.copyOfRange(num, 0, mid);
        int[] right = Arrays.copyOfRange(num, mid, num.length);
        return mergeArrays(mergeSort(left), mergeSort(right));
    }

    private int[] mergeArrays(int[] mergeSort1, int[] mergeSort2) {
        int[] result = new int[mergeSort1.length + mergeSort2.length];
        int i = 0, j = 0, k = 0;
        while (i < mergeSort1.length && j < mergeSort2.length) {
            if (mergeSort1[i] < mergeSort2[j]) {
                result[k++] = mergeSort1[i++];
            } else {
                result[k++] = mergeSort2[j++];
            }
        }
        while (i < mergeSort1.length) {
            result[k++] = mergeSort1[i++];
        }
        while (j < mergeSort2.length) {
            result[k++] = mergeSort2[j++];
        }
        return result;
    }

    public static void main(String[] args) {
        MergeSort mergeSort = new MergeSort();
        int[] num = {3, 7, 4, 2, 5, 8, 1};
        num = mergeSort.mergeSort(num);
        for (int t : num) {
            System.out.println(t);
        }
    }
}

 

给你一个数组，数组长度为n。请找出数组中第k大的数

public class Solution {
    public int findK(int[] num, int k) {
        return quickSort(num, 0, num.length - 1, k - 1);
    }

    public int quickSort(int[] num, int st, int ed, int k) {
        if (st >= ed) return num[st];
        int value = num[st];
        int left = st;
        int right = ed;
        while (left < right) {
            while (left < right && num[right] >= value) {
                right--;
            }
            num[left] = num[right];
            while (left < right && num[left] < value) {
                left++;
            }
            num[right] = num[left];
        }
        num[left] = value;
        if (left == k) return value;
        else if (left < k) {
            return quickSort(num, left + 1, ed, k);
        } else {
            return quickSort(num, st, left, k);
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] num = {1,8,8,7,4,1,5,1,5,7};
        System.out.println(solution.findK(num, 1));
        System.out.println(solution.findK(num, 2));
 
    }
}

 

1.B+树和B树的区别

B+树的数据都在叶子结点上，而B树的非根非叶节点也是数据节点，所以B+树的查询更稳定。

B+树有两个指针，一个指向root节点，一个指向叶子节点的最左侧，因此其范围查询效率更高，而B树则需要中序遍历B树。

同阶的情况下，B+树节点中的关键字要比B树多一个，并且B+树的中间节点不保存数据，所以磁盘也能够容纳更多结点元素，因此B+树更加矮胖，查询效率也更高。

2.红黑树

红黑树是一个自平衡二叉查找树。时间复杂度O(log n)

• 节点颜色为红或者黑
• 根结点是黑色
• 叶节点（NIL结点，空结点）为黑
• 红节点的孩子为黑（路径上不能有两个连续的红节点）
• 从根到叶子节点路径中的黑节点数相等

3.红黑树和平衡二叉树的区别

平衡二叉树和高度相关，保持平衡的代价更高（多次旋转），因此适用于插入、删除较少，查询较多的场景。

红黑树和高度无关，旋转次数较少，因此适用于插入、删除较多的场景。

动态规划算法

与贪心法的区别：不是由上一步的最优解直接推导下一步的最优解，所以需要记录上一步的所有解 （下例中的F[i][j]就表示第i行的j个解)

能使用动态规划算法的条件：

如果一个问题被划分各个阶段之后，阶段I中的状态只能由阶段I-1中的状态通过状态转移方程得来，与其它状态没有关系，特别是与未发生的状态没有关系，那么这个问题就是“无后效性”的，可以用动态规划算法求解

1。定义阶段：第i行第j列的值a[i][j]

2。定义状态：走到第i行第j列的最大值F[i][j]

3。状态转移方程：F[i][j] = a[i][j]+max(F[i+1][j], F[i+1][j+1])

 

4。定义边界条件：当i = n时，F[i][j] = a[i][j]; 即一开始可以直接得出的局部最优解

 

框架

1.Mybatis动态代理

 

• 构建SqlSessionFactory过程

 

构建主要分为2步：

• 通过XMLConfigBuilder解析配置的XML文件，读出配置参数，包括基础配置XML文件和映射器XML文件；
• 使用Configuration对象创建SqlSessionFactory，SqlSessionFactory是一个接口，提供了一个默认的实现类DefaultSqlSessionFactory。

说白了，就是将我们的所有配置解析为Configuration对象，在整个生命周期内，可以通过该对象获取需要的配置。

• 映射器的动态代理

Mapper映射是通过动态代理来实现的，使用JDK动态代理返回一个代理对象，供调用者访问。

首先看看实现InvocationHandler接口的类，它是执行本代理方法的关键，可以看到，Mapper是一个接口，会生成MapperMethod对象，调用execute方法。

 

总结下映射器的调用过程，返回的Mapper对象是代理对象，当调用它的某个方法时，其实是调用MapperProxy#invoke方法，而映射器的XML文件的命名空间对应的就是这个接口的全路径，会根据全路径和方法名，便能够绑定起来，定位到sql，最后会使用SqlSession接口的方法使它能够执行查询。

• SqlSession的4大对象

 

通过上面的分析，映射器就是一个动态代理对象，进入到了MapperMethod的execute方法，它经过简单的判断就进入了SqlSession的删除、更新、插入、选择等方法，这些方法如何执行是下面要介绍的内容。

Mapper执行的过程是通过Executor、StatementHandler、ParameterHandler和ResultHandler来完成数据库操作和结果返回的，理解他们是编写插件的关键：

• Executor：执行器，由它统一调度其他三个对象来执行对应的SQL；
• StatementHandler：使用数据库的Statement执行操作；
• ParameterHandler：用于SQL对参数的处理；
• ResultHandler：进行最后数据集的封装返回处理；

 

• sql执行的过程
• 在MyBatis中存在三种执行器：
• • SIMPLE：简易执行器，默认的执行器；
  • REUSE：执行重用预处理语句；
  • BATCH:执行重用语句和批量更新，针对批量专用的执行器；

2.Spring IOC是什么？怎么实现的？

IoC(Ioc—Inversion of Control，即“控制反转”)是有专门一个容器来创建这些对象，即由Ioc容器来控制对 象的创建；因为由容器帮我们查找及注入依赖对象，对象只是被动的接受依赖对象，所以是反转.

注入方式：

• 接口注入
• setter
• 构造器注入

 

IOC容器的设计与实现有两种：BeanFactory和ApplicationContext

 

• 实现了BeanFactory接口的简单容器系列，只是实现了容器最基本的功能
• Applic ationContext应用上下文，作为容器的高级形态存在。除了具有基本的功能外，还增加了许多面向框架的特性，同时对应用环境做了许多适配。

3.Spring IOC里面的反射机制怎么实现的？

1.利用传入的参数获取xml文件的流,并且利用dom4j解析成Document对象

2.对于Document对象获取根元素对象<beans>后对下面的<bean>标签进行遍历,判断是否有符合的id.

3.如果找到对应的id,相当于找到了一个Element元素,开始创建对象,先获取class属性,根据属性值利用反射建立对象.

4.遍历<bean>标签下的property标签,并对属性赋值.注意,需要单独处理int,float类型的属性.因为在xml配置中这些属性都是以字符串的形式来配置的,因此需要额外处理.

5.如果属性property标签有ref属性,说明某个属性的值是一个对象,那么根据id(ref属性的值)去获取ref对应的对象,再给属性赋值.

 

6.返回建立的对象,如果没有对应的id,或者<beans>下没有子标签都会返回null

 

Java 反射机制是在运行状态中，对于任意一个类，都能够获得这个类的所有属性和方法，对于任意一个对象都能够调用它的任意一个属性和方法。这种在运行时动态的获取信息以及动态调用对象的方法的功能称为 Java 的反射机制。

 

Class 类与 java.lang.reflect 类库一起对反射的概念进行了支持，该类库包含了 Field,Method,Constructor 类 (每个类都实现了 Member 接口)。这些类型的对象时由 JVM 在运行时创建的，用以表示未知类里对应的成员。

 

通过反射机制创建对象，在创建对象之前要获得对象的构造函数对象，通过构造函数对象创建对应类的实例。

 

 

IOC容器的初始化过程

 

初始化过程分成了三个过程：

• Resource定位
• BeanDefinition的载入
• 向IOC容器注册这些BeanDefinition信息。这个过程是通过BeanDefinitionRegistry接口的实现来完成的。最终注入到HashMap中去，这个hashmap就是持有beandefinition数据的。

 

Spring关于Bean的装配，有下面三种方式：

 

• 在XML中进行显示配置
• 在java中进行显示配置
• 隐式的bean发现机制和自动装配

Redis

1.redis分片，客户端请求怎么处理？

　　Redis的分片是指将数据分散到多个Redis实例中的方法，分片之后，每个redis拥有一部分原数据集的子集。在数据量非常大时，分片能将数据量分散到若干主机的redis实例上，进而减轻单台redis实例的压力。

• 范围分片
• 哈希分片

分片的位置：

• 客户端分片
• 代理分片
• 服务器分片

 2.redis的zset底层实现

　　跳跃表来实现。

　　跳跃表相比于红黑树的优点：

• 存取速度快，节点不需要进行旋转
• 易于实现
• 支持无锁操作

3.redis和mysql的区别

• redis是key-value非关系型数据库，MySQL是关系型数据库
• redis基于内存，也可持久化，MySQL是基于磁盘
• redis读写比MySQL快的多
• redis一般用于热点数据的缓存，MySQL是存储

4.redis加锁

redis为单进程单线程模式，采用队列模式将并发访问变为串行访问，redis本身没有锁的概念，但可以用redis实现分布式锁。

• INCR

Redis Incr 命令将 key 中储存的数字值增一。
如果 key 不存在，那么 key 的值会先被初始化为 0 ，然后再执行 INCR 操作。

• SETNX
• SET：以上两种都没有设置超时时间，SET可以实现超时时间

分布式锁的核心思想是将设置锁和超时时间、删除锁分别作为一个原子操作进行。

5.redis的淘汰策略

• volatile-lru：在设置超时时间的数据中进行lru
• volatile-ttl：在设置超时时间的数据中挑选即将过期
• volatile-random：在设置超时时间的数据中随机挑选
• allkeys-lru：所有数据的lru
• allkeys-random：所有数据的随机
• noeviction：禁止驱逐数据

6.redis无法被命中怎么办？会出现什么问题？

无法被命中：无法直接通过缓存得到想要的数据

解决方案：

• 缓存尽可能聚焦在高频访问且时效性不高的业务热点上。
• 将缓存容量设置为热点数据的容量。
• 缓存预加载。
• 设置合适的缓存淘汰策略。

7.Redis和MySQL复制和分片

	复制	分片
MySQL	三个线程（binlog线程、I/O线程、SQL线程），目的是实现读写分离	水平切分、垂直切分
Redis	使用RDB快照进行复制，发送期间使用缓冲区记录执行的写命令，在RDB快照发送完毕后，发送缓冲区中的写命令	水平切分

 8.Redis是什么？Sorted List是什么？skiplist是什么？怎么实现的？怎么插入一个值？怎么进行查询？和其他数据结构进行对比？

 

9.Redis的hash和Java的map的区别