贝壳813 后端笔试

第一题

题目：n 块田，来回施肥，每次施肥加1，共 m 次
举例：n=3, m=5
[1,0,0] > [1,1,0] > [1,1,1] > [1,2,1] > [2,2,1]
输出 [2,2,1]

数学归纳法 AC

    // 数学归纳法，所以需要去掉一些特殊情况
    public long[] FarmerNN(int n, long m) {
        // write code here
        long[] arr = new long[n];
        // 特殊情况判断
        if (n == 0 || m == 0) return arr;

        if (n == 1) {
            arr[0] = m;
            return arr;
        }

        if (n == 2) {
            Arrays.fill(arr, m / 2);
            if ((m & 1) == 1) arr[0]++;

            return arr;
        }

        if (m < n) {
            for (int i = 0; i < m; i++) {
                arr[i] = 1;
            }

            return arr;
        }

        // 处理除“最后一行”施肥以外的情况
        long cnt = (m - n) / (n - 1);
        int last = (int) ((m - n) % (n - 1));

        for (int i = 1; i <= n - 2; i++) {
            arr[i] = cnt + 1;
        }

        // “最后一行”施肥奇偶分开讨论，这关系到从左开始还是从右开始
        if ((cnt & 1) == 1) {
            arr[0] = (cnt + 1) / 2 + 1;
            arr[n - 1] = arr[0] - 1;

            for (int i = 1; i < last + 1; i++) {
                arr[i]++;
            }

        } else {
            arr[0] = cnt / 2 + 1;
            arr[n - 1] = arr[0];

            for (int i = n - 2; i > n - 2 - last; i--) {
                arr[i]++;
            }

        }

        return arr;
    }

第二题

题目：按字典序从小到大清除字符串 s 中对应字符，清除 k 次
举例：s="caabeefa", k=2
"caabeefa" > "cbeef" > "ceef"
输出 "ceef"

TreeSet 排序加去重 AC

public String NS_String(String s, int k) {
        // write code here
        Set<Character> tab = new TreeSet<>();
        for (int i = 0; i < s.length(); i++) {
            tab.add(s.charAt(i));
        }

        for (char ch : tab) {
            if (k == 0) break;

            s = s.replaceAll(String.valueOf(ch), "");
            k--;
        }

        return s;
    }

第三题

题目：arr[i] ^ arr[j] == t 则区间[i, j]为奇特区间，包含奇特区间的区间也是奇特区间，找出给定区间 a[] 中非奇特子区间的个数
举例：a[]=[1, 2, 4, 8], t = 6
2 ^ 4 == 6, 非奇特区间为[1, 2],[4, 8]
输出 2

我是用DP O(n2)的空间复杂度..爆内存了 70%

    // 算法与最大回文子串类似
    public long section(int[] a, int t) {
        // write code here

        int n = a.length;
        boolean[][] dp = new boolean[n][n];

        int cnt = 0;
        for (int left = n - 2; left >= 0; left--) {
            for (int right = left + 1; right < n; right++) {
                if ((a[left] ^ a[right]) == t) {
                    dp[left][right] = true;
                } else if (dp[left + 1][right - 1] || dp[left][right - 1] || dp[left + 1][right]) {
                    dp[left][right] = true;
                }
                if (!dp[left][right]) cnt++;
            }
        }

        return cnt;
    }