18年360春招笔试题

一共三道题，最后一道为选答题(反正我是在指定时间里做不出来的，出的问题太多了，调了一个小时)

1. 茉莉有一个画板，画板可以抽象成100行，每行100个像素点的正方形，茉莉在画板上画画，她一共画了n次，每次将一个矩形涂上颜色，茉莉想知道一共有多少个像素点被她涂过颜色，若一个像素点被涂了k次，那么认为有k个像素点被涂过颜色。
2. 茉莉邀请她的朋友参加周末的派对，茉莉买了3种颜色的气球，现在她要用这些气球来装饰餐桌，每个餐桌只用恰好3个气球装饰，要求3个气球的颜色不能完全一样，可以是2种或者3种，茉莉想知道这些气球最多能装饰多少张餐桌。
3. 给你一个图，0节点连接着一个联通块a，1节点连接着一个联通块b，ab仅由01这条边相连，现在我们定义奇异路劲为恰好经过0-1这条边一次的路劲，其他边可以经过任意次，且路径不带方向，1-2-3与3-2-1认为是两条路径，重边也算多条路径，在这个图中有无数奇异路径，问第k短的奇异路径长度是多少？

画板

主要是输入数据如何存储，以便后面的遍历，搞了有10来分钟，不然很快就写完了

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * @author pengsong
 * @date 18/3/31 下午7:57
 */

public class QH36001 {
    //直接计算矩形的面积相加就可以了
    public static void getNumber(List<List<Integer>> lists){
        int i=0;
        int res=0;
        while (i<lists.size()){
            for(int j=0;j<lists.get(i).size();j+=4){
                res+=(lists.get(i).get(j+2)-lists.get(i).get(j+0)+1)*(lists.get(i).get(j+3)-lists.get(i).get(j+1)+1);
            }
            i++;
            System.out.println(res);
            res=0;
        }
    }
    /*
    输入
    第一行一个数 T
    对于每组数据，第一行一个整数n
    接下来n行，每行4个整数x1，y1，x2，y2

    输出
    对于每组数据，输出一行，表示茉莉一共涂了多少个像素点
     */
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int t;
        t=scanner.nextInt();
        int []n=new int[t];
        List<List<Integer>> lists=new ArrayList<>();
        for(int i=0;i<t;i++){
            n[i]=scanner.nextInt();
            ArrayList<Integer> list=new ArrayList<>();
            for(int j=0;j<n[i];j++){
                list.add(scanner.nextInt());
                list.add(scanner.nextInt());
                list.add(scanner.nextInt());
                list.add(scanner.nextInt());
            }
            lists.add(list);
        }
        scanner.close();
        getNumber(lists);
        //System.out.println();
    }
}

派对

我的想法是先取3个，然后再取两个，不知道对不对，帮别人做的

import java.util.Scanner;

/**
 * @author pengsong
 * @date 18/3/31 下午8:24
 */
public class QH36002 {
    /*
    在选两种颜色中最大装饰餐桌数量的时候，同样选取最小的，也就是最多只能装饰最小的个数的数量
    而且要满足最小的个数乘以3小于等于总的气球个数
     */
    public static int getNum(int i,int j){
        int res=Math.min(i,j);
        while (res*3>i+j)res--;
        return res;
    }

    /*
    我的想法是，先选3种颜色的情况，然后再选2种情况的颜色，将其相加作为最大的装饰餐桌数
     */
    public static int theMaxNumber(int r,int g,int b){
        int res=0;
        int min=Math.min(Math.min(r,g),b);
        res+=min;
        r-=min;
        g-=min;
        b-=min;
        if(r==0)res+=getNum(g,b);
        else if(g==0)res+=getNum(r,b);
        else res+=getNum(r,g);
        return res;
    }

    public static void getMax(int[][]rgb){
        for(int i=0;i<rgb.length;i++){
            System.out.println(theMaxNumber(rgb[i][0],rgb[i][1],rgb[i][2]));
        }
    }
    /*
    输入
    第一行一个数T，表示数据数组
    对于每组数据，第一行3个整数，r，g，b分别表示三种颜色的气球个数
    输出
    对于每组数组，输出一行，一个整数表示最多能够装饰的餐桌数
     */
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int t;
        t=scanner.nextInt();
        int [][]rgb=new int[t][3];
        for(int i=0;i<t;i++){
            rgb[i][0]=scanner.nextInt();
            rgb[i][1]=scanner.nextInt();
            rgb[i][2]=scanner.nextInt();
        }
        scanner.close();
        getMax(rgb);
    }
}

奇异路径

这个题目是一道选答题，图的问题一般是不会涉及的，还算比较简单吧，属于直接告诉思路型。
这道题我开始用DFS做，也能做，但是如果出现环的问题，就跳不出来了。
这里跳出条件是如果当前节点要走的下一个节点和当前节点的前一个节点相同，表明此时这条路径可以终止。用一个boolean类型来记录当前路径是否已经经过了0-1边，终止的时候判断该布尔值，如果为true，则算一条路径。然后将所有的路径全部走完，将长度存在一个数组中，最后对这个数组排序，找出第k小的值返回。
代码如下：

import java.util.*;

/**
 * @author pengsong
 * @date 18/3/31 下午8:42
 */

public class QH36003 {
    /*
    这个算法写的有点问题，需要满足图中不能出现环，如果有环的话，就会不停的循环，走出不去
    按理说应该使用BFS做的，我却用DFS做了
     */
    public static void getLength(Map<Integer,ArrayList<Integer>>map,int key,int step,boolean flag,ArrayList<Integer>res,int preNode){
        for(int j=0;j<map.get(key).size();j++){
            int value=map.get(key).get(j);
            if(value==preNode){
                if(flag==true)res.add(step);
                continue;
            }
            if((key==0&&value==1)||(key==1&&value==0))flag=true;
            getLength(map,value,step+1,flag,res,key);
            if((key==0&&value==1)||(key==1&&value==0))flag=false;
        }
    }
    /*
    遍历map的key节点作为路劲的第一个节点
    使用res记录走到头的路径
     */
    public static void theKLength(Map<Integer,ArrayList<Integer>> map,int k){
        ArrayList<Integer> res=new ArrayList<>();
        for(int key:map.keySet()){
            getLength(map,key,0,false,res,-1);
        }
        Collections.sort(res);
//        for(int i=0;i<res.size();i++) System.out.println(res.get(i));
        System.out.println(res.get(k-1));
    }

    /*
    输入
    第一行三个整数n，m，k表示有n个节点，0~n-1，有m条边，问第k长？
    接下来有m行u，v表示边，保证0-1边只出现一次，保证ab联通块只通过0-1相连

    输出
    一行表示答案
     */
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int n,m,k;
        n=scanner.nextInt();
        m=scanner.nextInt();
        k=scanner.nextInt();
        Map<Integer,ArrayList<Integer>> map=new HashMap<>();//使用map来存储每个节点所连接的其他节点
        for(int i=0;i<m;i++){
            int key=scanner.nextInt();
            int value=scanner.nextInt();
            if(map.containsKey(key))map.get(key).add(value);
            else {
                ArrayList<Integer> list=new ArrayList<>();
                list.add(value);
                map.put(key,list);
            }
        }
        scanner.close();
        for(int i=0;i<n;i++){
            if(!map.containsKey(i)){
                map.put(i,new ArrayList<>());
            }
        }
        //完善map的对应关系
        for(int key:map.keySet()){
            for(int j=0;j<map.get(key).size();j++){
                int value=map.get(key).get(j);
                if(!map.get(value).contains(key))map.get(value).add(key);
            }
        }
//        for(int key:map.keySet()){
//            System.out.print(key+":");
//            for(int j=0;j<map.get(key).size();j++){
//                System.out.print(map.get(key).get(j)+",");
//            }
//            System.out.println();
//        }
        //theKLength(map,k);
        getLengthBFS(map,k);
    }
}

这是一个很普通很笨的方法，这道题已经暗示了第k小的路径，表明需要用BFS写，将上面的DFS改写为下面的BFS，BFS的原理就是对n种可能的走法同时向前前进一步，正好符合该题意图，每次走一步，然后判断是否该路径终止，如果终止，继续判断是否满足奇异，如果满足则作为一条路径，用一个变量来记录，当这个变量的值达到k的时候，就是第k小的路径，因为BFS每次出去的路径都是当前最小的路径。
代码如下：

    public static void getLengthBFS(Map<Integer,ArrayList<Integer>>map,int k){
        int step=0;
        int res=0;
        ArrayList<Integer> curNode=new ArrayList<>();
        ArrayList<Integer> preNode=new ArrayList<>();
        ArrayList<Boolean> flag=new ArrayList<>();
        for(int key:map.keySet()){
            curNode.add(key);
            preNode.add(-1);
            flag.add(false);
        }
        while (curNode.size()>0){
            int size=curNode.size();
            for (int i=0;i<size;i++){
                for(int val:map.get(curNode.get(i))){
                    if(val==preNode.get(i)){
//                        System.out.println("----"+preNode.get(i)+"----"+curNode.get(i));
                        if(flag.get(i)==true){
                            res++;
                            if(res==k){
                                System.out.println(step);
                                return;
                            }
                        }
                    }else {
                        boolean f=flag.get(i);
                        if((curNode.get(i)==0&&val==1)||(curNode.get(i)==1&&val==0))f=true;
                        curNode.add(val);
                        preNode.add(curNode.get(i));
                        flag.add(f);
                    }
                }
            }
            for(int i=0;i<size;i++){
//                System.out.println("----"+curNode.get(0)+"****"+preNode.get(0)+"****"+flag.get(0)+"----");
                curNode.remove(0);
                preNode.remove(0);
                flag.remove(0);
            }
//            System.out.println("res="+res);
//            System.out.println(curNode.size()+","+preNode.size()+","+flag.size());
            step++;
        }
    }