关于leetcode:LeetCode-Weekly-Contest-254解题报告

作为子字符串呈现在单词中的字符串数目

签到题，枚举、统计即可。

class Solution {public int numOfStrings(String[] patterns, String word) {
        int cnt = 0;
        for (String p : patterns) {if (word.contains(p)) {cnt++;}
        }
        return cnt;
    }
}

结构元素不等于两相邻元素平均值的数组

依照一大一小的程序重排数组即可，这样一个数字相邻的数字要么都比它大，要么都比它小。

class Solution {public int[] rearrangeArray(int[] nums) {Arrays.sort(nums);
        LinkedList<Integer> list = new LinkedList<>();
        for (int num : nums) {list.add(num);
        }
        int[] res = new int[nums.length];
        for (int i = 0; i < res.length; i++) {if (i % 2 == 0) {res[i] = list.pollFirst();} else {res[i] = list.pollLast();}
        }
        return res;
    }
}

数组元素的最小非零乘积

最终肯定是若干个 1、1 个 $2^p – 1$、若干个 $2^p – 2$，并且 $2^p – 2$ 的数量和 1 的数量相等。

即最终后果是 $(2^p – 2)^{(2^{p-1} – 1)} * (2^p – 1)$

应用疾速幂计算即可。

class Solution {public int minNonZeroProduct(int p) {if (p == 1) {return 1;}
        // 2^(p-1) - 1 个 1
        // (2^p - 2)^(2^(p-1) - 1) * (2^p - 1)
        long mod = (long) 1e9 + 7;
        long a = (pow(2, p, mod) + mod - 2) % mod;
        a = pow2(a, 2, p - 1, 1, mod);
        long c = (pow(2, p, mod) + mod - 1) % mod;
        return (int) (a * c % mod);
    }

    private long pow2(long a, long x, long y, long z, long mod) {// calc a^(x^y - z) % mod
        // x = 2, z = 1 or 0
        if (y <= 2) {long p = pow(x, y, mod) - z;
            return pow(a, p, mod);
        }
        if (z == 0) {return pow(pow2(a, x, y - 1, z, mod), 2, mod);
        } else {long t = pow2(a, x, y - 1, z, mod);
            long t2 = pow2(a, x, y - 1, z - 1, mod);
            return t * t2 % mod;
        }
    }

    long pow(long a, long b, long p) {if (b == 0) {return 1;}
        if (b == 1) {return a % p;}
        long t = pow(a, b / 2, p);
        t = t * t % p;
        if (b % 2 == 0) {return t;}
        return t * a % p;
    }
}

你能穿过矩阵的最初一天

二分答案，而后 BFS 判断可达性。

class Solution {public int latestDayToCross(int row, int col, int[][] cells) {
        int l = 0, r = cells.length;
        while (l + 1 < r) {int m = (l + r) / 2;
            if (check(row, col, cells, m)) {l = m;} else {r = m;}
        }
        return check(row, col, cells, r) ? r : l;
    }

    private boolean check(int row, int col, int[][] cells, int m) {final int[] dx = {0, 0, 1, -1};
        final int[] dy = {1, -1, 0, 0};
        boolean[][] mp = new boolean[row][col];
        for (int i = 0; i < m; i++) {int[] cell = cells[i];
            mp[cell[0] - 1][cell[1] - 1] = true;
        }
        boolean[][] vis = new boolean[row][col];
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < col; i++) {if (!mp[0][i]) {queue.add(0);
                queue.add(i);
                vis[0][i] = true;
            }
        }
        while (!queue.isEmpty()) {int x = queue.poll();
            int y = queue.poll();
            if (x == row - 1) {return true;}
            for (int i = 0; i < 4; i++) {int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx < 0 || ny < 0 || nx >= row || ny >= col || mp[nx][ny] || vis[nx][ny]) {continue;}
                vis[nx][ny] = true;
                queue.add(nx);
                queue.add(ny);
            }
        }
        return false;
    }
}