奇安信8月25日笔试

第一题：输出较大面积

x是长，y是宽

例[4,1,2,7]代表4个点(0,4),(1,1),(2,2),(3,7) 点(0,4),(1,1)表示长方形：长(1-0),宽=min(4,1)，面积=1*1=1

输入：[4,1,2,7]

输出：12

public class Main {
    public static int getMaxAreas(int[] arr){
        int res = -1;
        for (int i = 0; i <arr.length ; i++) {
            for (int j = 0; j <arr.length ; j++) {
                if(i!=j){
//                    x是长
                    int x = j-i;
//                    y是宽
                    int y = Math.min(arr[i],arr[j]);
                    res = Math.max(res,Math.abs(x*y));
                }
            }
        }
        return res;
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        s = s.replaceAll("\\[","");
        s = s.replace("]","");
        String[] split = s.split(",");
        int length = split.length;
        int[] arr = new int[split.length];
        for (int i = 0; i <split.length ; i++) {
            arr[i] = Integer.parseInt(split[i]);
        }
        System.out.println(getMaxAreas(arr));
    }
}

第二题：判断城市0到城市4有多少路可以通

输入：[[1,2,3],[3],[3],[4],[]]

输出：3

package QiAnXin;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * 顶点0 到 1 2 3  [1,2,3]
 * 节点1到3        [3]
 * 节点2到3        [3]
 * 节点3到4        [4]
 * 节点4无         []
 * 输入[[1,2,3],[3],[3],[4],[]]
 * 输出 3
 */
//思路：深度优先搜索方式求出做有可能的路径，从0出发，栈记录路径上的点，每次遍历到点n-1，就将栈记录的路径加到答案中
//    本题为有向无环图，不会遍历到重复的点，无需遍历当前点是否遍历过
public class Main01 {
    public int DagaPathNum(int[][] nodes){
//        存放二维节点
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
//        堆栈Deque
        Deque<Integer> stack = new ArrayDeque<Integer>();
//        将指定的元素插入此双端队列的末尾
        stack.offerLast(0);
        dfs(nodes,0,nodes.length-1,ans,stack);
        return ans.size();

    }
//    深度优先搜索
    public void dfs(int[][] graph,int x,int n,List<List<Integer>> ans,Deque<Integer> stack){
        if(x==n){
            ans.add(new ArrayList<Integer>(stack));
            return;
        }
        for (int y:graph[x]) {
            stack.offerLast(y);
            dfs(graph,y,n,ans,stack);
            stack.pollLast();
        }
    }

}

#奇安信笔试#