奇安信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();
}
}
}
