奇安信笔试2021/8/7

第一部分

单选题：操作系统，网络，Linux，数据库，Java基础（Linux指令，操作系统的页啊不会）

第二部分

多选题：范围和第一部分一样，还是有不少不会，操作系统和Linux不会

第三部分

这两题的地址：两道笔试题目

很开心，他是核心代码模式，不用处理输入输出！！！

第一题：

给你一组人，height数组
从这个数组中找三个人，i,j,k这三个人的高度height[i],height[j],height[k]必须逆序或者顺序排列
这三个人可以是多个小组的一部分

输入：[1,5,3,2,4]
输出：3
我们可以组建：（1，3，4）（ 1，2，4 ）（ 5，3，2）

我是暴力破解（这个代码也可以优化，我不知道怎么同时求正序和逆序的人的身高，就是能不能把process和process2的代码合并），想不出动态规划，希望有大佬能在评论区指出更好的思路！！！

/**
 * @author keboom
 * @date 2021/8/7
 */
public class Main1 {

    int res = 0;

    public int TeamNums (int[] height) {
        // write code here
        process(height,0,0,-1);
        process2(height, 0, 0, -1);
        return res;
    }
    // 寻找身高从小到大的人
    private void process(int[] height, int count, int index,int pre) {
        if (index == height.length) {
            return;
        }
        for (int i = index; i < height.length; i++) {
            if (count == 2 && height[i] > pre) {
                res++;
                continue;
            }
            if (pre == -1 || height[i] > pre) {
                process(height, count+1, i+1, height[i]);
            }
        }
    }
    // 寻找身高从大到小的人
    private void process2(int[] height, int count, int index,int pre) {
        if (index == height.length) {
            return;
        }
        for (int i = index; i < height.length; i++) {
            if (count == 2 && height[i] < pre) {
                res++;
                continue;
            }
            if (pre == -1 || height[i] < pre) {
                process2(height, count+1, i+1, height[i]);
            }
        }
    }

    //[1,5,3,2,4]
    public static void main(String[] args) {
        int[] in = {1,5,3,2,4};
        int i = new Main1().TeamNums(in);
        System.out.println(i);
    }
}

第二题：

给你一个网格，你可以从任意位置进入和退出。
你不可以走重复的路
你不可以走0
你可以上下左右走
你进入一个网格则能收集此网格的资源，求你能收集最大的资源数
输入：[[0,6,0],[5,8,7],[0,9,0]]
输出：24
路径：7-8-9

输入：[[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]
输出：28
路径：1-2-3-4-5-6-7

这题我觉得写的还行，如果有更好的算法请评论区指出哈！！！！！！！

/**
 * @author keboom
 * @date 2021/8/7
 */
public class Solution2 {

    boolean[][] isGo;
    int res = 0;
    int[][] skill;
    public int getMaximumResource (int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        isGo = new boolean[row][col];
        skill = new int[][]{{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
        // 那些为0的设置为false
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                isGo[i][j] = grid[i][j] == 0 ? false : true;
            }
        }
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] != 0) {
                    process(grid, i, j, isGo, 0);
                }
            }
        }
        return res;
    }

    private void process(int[][] grid, int i, int j, boolean[][] isGo, int sum) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || !isGo[i][j]) {
            return;
        }
        isGo[i][j] = false;
        sum += grid[i][j];
        res = Math.max(res, sum);
        for (int[] s : skill) {
            int newX = i + s[0];
            int newY = j + s[1];
            process(grid, newX, newY, isGo, sum);
        }
        isGo[i][j] = true;
    }

    //[[0,6,0],[5,8,7],[0,9,0]]
    public static void main(String[] args) {
        int[][] grid = {{0, 6, 0}, {5, 8, 7}, {0, 9, 0}};
        int res = new Solution2().getMaximumResource(grid);
        System.out.println(res);
    }

}