牛客网刷题总结（一）

1.运动员排名

一架飞机载着5位运动员从奥林匹克运动会归来，这5位运动员在某个项目中排名第一到第五。他们说了下面这些话：
A:”我不是最后一名。”
B:”C是第三名。”
C：”A的排名在E后面。”
D:”E是第二名。”
E:”D不是第一名。”
处于谦虚或其他什么原因，金牌和银牌的得主都说了谎。那三个成绩相对较差的运动员倒说了真话。 他们的排名到底怎样？

解析：

A分析：
    A说本人不是最后一名，假如A说了假话，则A是最后一名，但是最后一名说的是真话，矛盾。所以A说的是真话，排在3-5位。

再分析相互纠缠的D和E：
    假设D说了真话，那么E就是第二名，E就是说的假话，那么D就是第一名，但是第一名应该说假话，矛盾。所以D说了假话，D应该排在1-2位。

再来分析B和C：
    假设B说了真话，那么C就是第三名，C说的就是真话，由于A也是说的真话，那么3-5位的排序只能是 C E A，但是A不是最后一位，矛盾。所以B说的是假话，排位在1-2位。

综合来看：
    D B说了假话，那么A C E就是说了真话，对A C E进行排序就是：E A C。由E 对 D B进行排序就是：B D。所以真正的排名就是：B D E A C。

2.集合特性

1	说出ArrayList,Vector, LinkedList的存储性能和特性？

解析

ArrayList和Vector都是使用数组方式存储数据，此数组元素数大于实际存储的数据以便增加和插入元素，它们都允许直接按序号索引元素，但是插入元素要涉及数组元素移动等内存操作，所以索引数据快而插入数据慢，Vector由于使用了synchronized方法（线程安全），通常性能上较ArrayList差，而LinkedList使用双向链表实现存储，按序号索引数据需要进行前向或后向遍历，但是插入数据时只需要记录本项的前后项即可，所以插入速度较快。

3.说明errorPage的作用

正常页面中<%@page errorpage=”error.jsp”%>

错误页面<%@page iserrorpage=”true”%>

有一内置对象:exception

4.sleep( ) 和 wait( ) 有什么区别?

1
2

sleep是线程类（Thread）的方法，导致此线程暂停执行指定时间，给执行机会给其他线程，但是监控状态依然保持，到时后会自动恢复。调用sleep不会释放对象锁。
wait是Object类的方法，对此对象调用wait方法导致本线程放弃对象锁，进入等待此对象的等待锁定池，只有针对此对象发出notify方法（或notifyAll）后本线程才进入对象锁定池准备获得对象锁进入运行状态。

5.forward和redirect的区别？

1
2
3

forward: 转发，在下一个页面中,request保留上一个页面中的request的所有值

redirect: 跳转，不传递request对象。

6.矩阵判断数字

给定如下的n*n的数字矩阵，每行从左到右是严格递增， 每列的数据也是严格递增

1  2  3

3  5  6

4  8  9

现在要求设计一个算法， 给定一个数k 判断出k是否在这个矩阵中。描述算法并且给出时间复杂度（不考虑载入矩阵的消耗）

解析

答案：算法思想：沿着对角线查找，获得i,使得k位于a[i][i]与a[i+1][i+1]之间。k只可能存在于a[i][i]对应的右上角矩阵 和a[i+1][i+1]对应的左下角矩阵。使用递归法继续查找即可。
时间复杂度 O(n)
int searchK(int_arr[][], int n, int startlow, int startclm, int k) {
 int downtemp=0;
 int i=0;
 while(int_arr[startlow+i][startclm+i]<k||i<n)
 i++;
 if (i==n)
 return 0;
 else if(arr[i][i]==k)
 reuturn 1;
 else
return searchK(int_arr,n,startlow,startclm+i,k)+searchK(int_arr,n,startlow+i,startclm,k); 
}

7.数据库

问题描述:

已知关系模式:S (SNO,SNAME) 学生关系。SNO 为学号，SNAME 为姓名

C (CNO,CNAME,CTEACHER) 课程关系。CNO 为课程号，CNAME 为课程名，CTEACHER 为任课教师

SC(SNO,CNO,SCGRADE) 选课关系。SCGRADE 为成绩

1.      找出没有选修过“李明”老师讲授课程的所有学生姓名
2.      列出“1”号课成绩比“2”号课成绩高的所有学生的学号及其“1”号课和“2”号课的成绩

解析

 Select SNAME FROM S Where NOT
EXISTS( Select * FROM SC,C Where SC.CNO=C.CNO AND CNAME='李明'   AND SC.SNO=S.SNO)

Select S.SNO,S.SNAME,SC.[1号课成绩],SC.[2号课成绩]  FROM S,( Select SC1.SNO,[1号课成绩]=SC1.SCGRADE,[2号课成绩]=SC2.SCGRADE   FROM SC SC1,C C1,SC SC2,C C2 Where
SC1.CNO=C1.CNO AND C1.NAME='1' AND SC2.CNO=C2.CNO AND C2.NAME='2'   AND SC1.SCGRADE>SC2.SCGRADE  )SC Where S.SNO=SC.SNO

8.请使用内部类实现线程设计4个线程，其中两个线程每次对j增加1，另外两个线程对j每次减少1。

public class Solution {
     
     
    class InnerSolu{
        int j = 5;
         
        void fun(){
            int[] var = {0};
            var[0] = j;
             
            for(int i=0; i< 4; i++){
                int[] index = {0};
                index[0] = i;
                if (i<2){
                    new Thread(() -> {
                        var[0] = var[0] + 1;
                        System.out.println(index[0]+" "+var[0]);
                    }).start();
                } else {
                    new Thread(() -> {
                        var[0] = var[0] - 1;
                        System.out.println(index[0]+" "+var[0]);
                    }).start();
                }
            }
        }
    }
     
    public static void main(String[] args){
        Solution solution = new Solution();
        Solution.InnerSolu innerSolu = solution.new InnerSolu();
        innerSolu.fun();
    }
     
}

9.请你说明一下TreeMap的底层实现？

1	TreeMap是一个有序的key-value集合，基于红黑树(Red-Black tree)实现。该映射根据其键的自然顺序进行排序，或者根据创建时提供的Comparator进行排序

10.

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

解析

class Solution {
public:
    bool Find(vector<vector<int> > array,int target) {
        bool flag=false;
        int row=0;
        int col=array.size()-1;
        if(row<array.size() && col>0){
            while(row<array.size() && col>=0){
                if(array[row][col]==target){
                    flag=true;
                     break;
                }
                else if (array[row][col]>target)
                    col--;
                    else
                    row++;
            }
        }
        return flag;
    }
};