第 204 场周赛回顾

前言

第一次打比赛，熟悉一下难度和赛制。

第一题：重复至少 K 次且长度为 M 的模式

题解一：模拟

从头开始一次匹配，找到符合要求的就返回true。

class Solution {
    public boolean containsPattern(int[] arr, int m, int k) {
        boolean ans = false;
        int[] pattern = new int[m];
        int[] other = new int[m];
        int count;
        for (int i = 0; i < arr.length - m; ++i) {
            pattern = Arrays.copyOfRange(arr, i, i + m);
            count = 1;
            for (int j = i + m; j <= arr.length - m; j += m) {
                other = Arrays.copyOfRange(arr, j, j + m);
                if (Arrays.equals(pattern, other)) {
                    ++count;
                } else {
                    break;
                }
            }
            if (count >= k) {
                ans = true;
                break;
            }
        }
        return ans;
    }
}

第二题：乘积为正数的最长子数组长度

题解一：

思路。

class Solution {
    public int getMaxLen(int[] nums) {
        List<Integer> list;
        List<Integer> indexList;
        int max = 0;
        int i = 0;
        // 跳过0
        while ((i < nums.length) && (nums[i] == 0)) {
            ++i;
        }
        for (; i < nums.length;) {
            list = new LinkedList<>();
            while ((i < nums.length) && (nums[i] != 0)) {
                list.add(nums[i]);
                ++i;
            }
            if ((i < nums.length) && (nums[i] == 0)) {
                ++i;
            }
            if (list.isEmpty()) {
                continue;
            }
            indexList = new ArrayList<>(list.size());
            int index = 0;
            for (Iterator<Integer> iter = list.iterator(); iter.hasNext(); ++index) {
                int e = iter.next();
                if (e < 0) {
                    indexList.add(index);
                }
            }
            if (indexList.size() % 2 == 0) {
                max = Math.max(list.size(), max);
                continue;
            }
            if (indexList.size() == 1) {
                max = Math.max(list.size() - indexList.get(0) - 1, max);
                max = Math.max(indexList.get(0), max);
                continue;
            }
            // 第一个负数的下标
            int first = indexList.get(0);
            // 最后一个负数的下标
            int last = indexList.get(indexList.size() - 1);
            max = Math.max(last, max);
            max = Math.max(list.size() - first - 1, max);
        }
        return max;
    }
}

第三题：使陆地分离的最少天数

题解一：

思路。

第四题：将子数组重新排序得到同一个二叉查找树的方案数

题解一：

思路。