奇安信笔试

1 题起初想到了132问题，想着用单调栈去解，后来就干脆暴力了，写了个O(n^2logn)时间复杂度的算法，数据都过了。题目也没给数据范围。结束后对代码改了改，时间复杂度O(n^2)

import java.util.Arrays;
import java.util.TreeSet;

public class Solution {
    public static void main(String[] args) {
        int res = new Solution().TeamNums(new int[]{1,6,3,2,5,4});
        System.out.println(res);
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param height int整型一维数组 舞蹈员身高的一维数组
     * @return int整型
     */
    public int TeamNums (int[] height) {
        if (height.length < 3) return 0;
        int ret = work(height);
        int i = 0, j = height.length - 1;
        while(i < j) {
            int tmp = height[i];
            height[i] = height[j];
            height[j] = tmp;
            ++i;
            --j;
        }
        ret += work(height);

        return ret;
    }

    private int work(int[] height) {
        int count = 0;
        TreeSet<Integer> set = new TreeSet<>();
        int[] rank = new int[height.length];
        for (int i = height.length - 1; i >= 0; --i) {
            int idx = Arrays.binarySearch(set.toArray(), height[i]);
            if (idx < 0) {
                idx = -(idx + 1);
                rank[i] = set.size() - idx;  // height[i+1..height.length)中有多少个数比height[i]大
            }
            set.add(height[i]);
        }
        for (int i = 0; i < height.length; ++i) {
            for (int k = height.length - 1; k > i; --k) {
                if (height[k] < height[i]) continue;
                count += rank[k];
            }
        }
        return count;
    }
}

2 题图中链路上节点和的最大值。时间复杂度O(n*m)

public class Solution {
    public static void main(String[] args) {
        int res = new Solution().getMaximumResource(new int[][]{{1,0,7},{2,0,6},{3,4,5},{0,3,0},{9,0,20}});
        System.out.println(res);
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param grid int整型二维数组 为n*m 的二维数组
     * @return int整型
     */
    int n, m;
    public int getMaximumResource (int[][] grid) {
        if (grid.length == 0 || grid[0].length == 0) return 0;
        n = grid.length;
        m = grid[0].length;
        int maxV = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (grid[i][j] != 0) {
                    maxV = Math.max(maxV, dfs(grid, i, j, i, j));
                }
            }
        }
        return maxV;
    }
    static int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int dfs(int[][] grid, int x, int y, int x0, int y0) {
        int ret = grid[x][y];
        grid[x][y] = 0;
        int a = 0, b = 0;
        for (int i = 0; i < 4; ++i) {
            int xx = x + dir[i][0];
            int yy = y + dir[i][1];
            if (xx >= 0 && xx < n && yy >= 0 && yy < m && grid[xx][yy] != 0) {
                int res = dfs(grid, xx, yy, x0, y0);
                if (res >= a) {
                    b = a;
                    a = res;
                } else if (res > b) {
                    b = res;
                }
            }
        }
        return ret + (x == x0 && y == y0 ? a + b: Math.max(a, b));
    }
}

#笔经##奇安信#