关于leetcode:上岸-I-LeetCode-Weekly-Contest-215解题报告

No.1设计有序流

解题思路

依照题意编码即可.

代码展现

class OrderedStream {

    private final String[] strings;
    private int ptr;

    public OrderedStream(int n) {
        strings = new String[n];
        ptr = 0;
    }

    public List<String> insert(int id, String value) {
        id--;  // 数组下标从 0 开始
        strings[id] = value;
        List<String> res = new ArrayList<>();
        for (; ptr < strings.length && strings[ptr] != null; ptr++) {
            res.add(strings[ptr]);
        }
        return res;
    }
}

No.2确定两个字符串是否靠近

解题思路

解读、剖析失去两个字符串靠近的条件:

1. 字符集雷同
2. 每种字符呈现的次数形成的序列雷同

代码展现

class Solution {
    public boolean closeStrings(String word1, String word2) {
        int[] cnt1 = new int[26];
        for (int i = 0; i < word1.length(); i++) {
            cnt1[word1.charAt(i) - 'a']++;
        }
        int[] cnt2 = new int[26];
        for (int i = 0; i < word2.length(); i++) {
            cnt2[word2.charAt(i) - 'a']++;
        }
        // 字符集雷同
        for (int i = 0; i < 26; i++) {
            // 字符 i 若在 word1 中呈现, 那么在 word2 中也必须呈现
            if (cnt1[i] + cnt2[i] != 0 && cnt1[i] * cnt2[i] == 0) {
                return false;
            }
        }
        // 次数序列雷同
        Arrays.sort(cnt1);
        Arrays.sort(cnt2);
        for (int i = 0; i < 26; i++) {
            if (cnt1[i] != cnt2[i]) {
                return false;
            }
        }
        return true;
    }
}

No.3将x减到0的最小操作数

解题思路

两根指针, 详见正文.

代码展现

class Solution {
    public int minOperations(int[] nums, int x) {
        // 预处理出前缀和与后缀和, 不便后续计算
        int[] prefixSum = new int[nums.length];
        int[] suffixSum = new int[nums.length];
        prefixSum[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            prefixSum[i] = prefixSum[i - 1] + nums[i];
        }
        suffixSum[nums.length - 1] = nums[nums.length - 1];
        for (int i = nums.length - 2; i >= 0; i--) {
            suffixSum[i] = suffixSum[i + 1] + nums[i];
        }
        // 两根指针 left 和 right
        int res = nums.length + 1;
        int left = 0, right = 0;
        // [0, left) + [right, nums.length)
        for (; left < nums.length; left++) {
            while (right < nums.length && calcSum(left, right, prefixSum, suffixSum) > x) {
                right++;
            }
            if (calcSum(left, right, prefixSum, suffixSum) == x) {
                int len = left + nums.length - right;
                res = Math.min(res, len);
            }
        }
        return res > nums.length ? -1 : res;
    }
    private int calcSum(int left, int right, int[] prefixSum, int[] suffixSum) {
        // [0, left) + [right, nums.length)
        return (left > 0 ? prefixSum[left - 1] : 0) +
                (right < suffixSum.length ? suffixSum[right] : 0);
    }
}

No.4最大化网格幸福感

解题思路

深度优先搜寻 (回溯).

实质上就是枚举每一个格子是调配内向的人, 还是外向的人, 还是不调配.

下述代码展现思路, 能够计算出正确答案, 然而会超出工夫限度.

进一步优化能够将 grid 进行压缩并且记忆化, 方可通过.

代码展现
class Solution {

private int res;

public int getMaxGridHappiness(int m, int n, int introvertsCount, int extrovertsCount) {
    res = 0;
    dfs(0, 0, m, n, new byte[m][n], introvertsCount, extrovertsCount);
    return res;
}

private void dfs(int x, int y, int m, int n, byte[][] grid, int introvertsCount, int extrovertsCount) {
    if (y == n) {
        x++;
        y = 0;
    }
    if (x == m || introvertsCount + extrovertsCount == 0) {
        res = Math.max(calc(grid), res);
        return;
    }
    // 优化点: 就算剩下的人都取最大幸福值也不如以后答案优良, 进行搜寻.
    if (introvertsCount * 120 + extrovertsCount * 120 + calc(grid) <= res) {
        return;
    }
    if (extrovertsCount > 0) {
        grid[x][y] = 2;
        dfs(x, y + 1, m, n, grid, introvertsCount, extrovertsCount - 1);
        grid[x][y] = 0;
    }
    if (introvertsCount > 0) {
        grid[x][y] = 1;
        dfs(x, y + 1, m, n, grid, introvertsCount - 1, extrovertsCount);
        grid[x][y] = 0;
    }
    dfs(x, y + 1, m, n, grid, introvertsCount, extrovertsCount);
}

private int calc(byte[][] grid) {
    int[] dx = {1, -1, 0, 0};
    int[] dy = {0, 0, 1, -1};
    int res = 0;
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {
            if (grid[i][j] == 0) {
                continue;
            }
            res += grid[i][j] == 1 ? 120 : 40;
            int inc = grid[i][j] == 1 ? -30 : 20;
            for (int k = 0; k < 4; k++) {
                int x = i + dx[k];
                int y = j + dy[k];
                if (x < 0 || y < 0 || x >= grid.length || y >= grid[0].length) {
                    continue;
                }
                if (grid[x][y] > 0) {
                    res += inc;
                }
            }
        }
    }
    return res;
}

}