商汤科技2020-8-20开发笔试A卷

三道题
一：给定一个字符串，找“Good”，字符顺序不可变，每个字符只能用一次

class Solution {
    public int method(char[] chars) {
        if (chars.length < 4)
            return 0;
        int res = 0;
        int numOfG = 0, numOfO = 0;
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == 'G')
                numOfG++;
            if (chars[i] == 'o') {
                if (numOfG > 0)
                    numOfO++;
            }
            if (chars[i] == 'd') {
                if (numOfG > 0 && numOfO >= 2) {
                    res++;
                    numOfG--;
                    numOfO = numOfO - 2;
                }
            }
        }
        return res;
    }
}

二、最常上升子序列，leetcode原题

class SolutionMainTwo {
    public int[][] cur = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    public int r, c;

    public int method(int[][] array, int n, int m) {
        if (n == 0 || m == 0 || array == null)
            return 0;
        r = n;
        c = m;
        int[][] curArray = new int[r][c];
        int ans = 0;
        for (int i = 0; i < r; ++i) {
            for (int j = 0; j < c; ++j) {
                ans = Math.max(ans, methodDFS(array, i, j, curArray));
            }
        }
        return ans;
    }

    private int methodDFS(int[][] matrix, int row, int column, int[][] curArray) {
        if (curArray[row][column] != 0)
            return curArray[row][column];
        ++curArray[row][column];
        for (int[] ints : cur) {
            int newRow = row + ints[0];
            int newColumn = column + ints[1];
            if (newRow >= 0 && newRow < r && newColumn >= 0 && newColumn < c && matrix[newRow][newColumn] > matrix[row][column]) {
                curArray[row][column] = Math.max(curArray[row][column], methodDFS(matrix, newRow, newColumn, curArray) + 1);
            }
        }
        return curArray[row][column];
    }
}

三、大意是求删除区间的个数，可以使得删除后剩下的区间彼此不重叠（好像是这个意思）

class SolutionMainThree {
    /**
     *
     * @param intervals int整型二维数组
     * @return int整型
     */
    public int eraseOverlapIntervals (int[][] intervals) {
        // write code here
        if (intervals.length == 0)
            return 0;
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0]-o2[0];
            }
        });
        int result = 0;
        int cur = 0;
        int len = intervals.length;
        for (int i = 1; i < len; i++) {
            if (intervals[cur][1]>intervals[i][0]){
                if (intervals[cur][1]>intervals[i][1])
                    cur = i;
                result++;
            }else{
                cur = i;
            }
        }
        return result;
    }
}

如果所有大厂的笔试都这么简单就好了