关于算法:上岸算法-I-LeetCode-Weekly-Contest-218解题报告-上岸算法

No.1 设计 Goal 解析器

解题思路

详情见下方代码注解。

代码展现

class Solution {public String interpret(String command) {command = command.replaceAll("\\(\\)", "o");

        command = command.replaceAll("\\(al\\)", "al");

        return command;

    }

}

No.2 K 和数对的最大数目

解题思路

应用 Map 统计每个数值的呈现次数, 而后匹配即可. 为了防止反复, Map 中贮存大于 k/2 的, 而之后枚举的是小于 k/2 的.

代码展现

class Solution {public int maxOperations(int[] nums, int k) {Map<Integer, Integer> count = new HashMap<>();

        int halfk = 0;

        for (int num : nums) {if (num * 2 > k) {count.put(num, count.getOrDefault(num, 0) + 1);

            } else if (num * 2 == k) {halfk++;}

        }

        Arrays.sort(nums);

        int res = halfk / 2;

        for (int num : nums) {if (num * 2 > k) {break;}

            if (count.getOrDefault(k - num, 0) > 0) {

                res++;

                count.put(k - num, count.get(k - num) - 1);

            }

        }

        return res;

    }

}

No.3 连贯间断二进制数字

解题思路

从 n 到 1 一一拼接计算加和即可. 往一个数字 i 的二进制前拼接一个 0 不影响大小, 拼接一个 1 相当于加上一个 2 的幂.

代码展现

class Solution {

    final int mod = 1000000007;

    public int concatenatedBinary(int n) {

        int res = 0;

        int pow2 = 1;

        for (int i = n; i >= 1; i--) {for (int j = i; j > 0; j >>= 1) {if ((j & 1) == 1) {res = (res + pow2) % mod;

                }

                pow2 = (pow2 << 1) % mod;

            }

        }

        return res;

    }

}

No.4 最小不兼容性

解题思路

解决该题目的通用办法就是深度优先搜寻. 别离枚举每个数字要放到哪个组中.

然而须要加一些优化, 否则会超时.

代码展现

class Solution {

    int res, k, cnt;

    int[] idx, latest, first, nums;

    public int minimumIncompatibility(int[] nums, int k) {if (nums.length == k) {return 0;}

        // 判断无解

        int[] numCnt = new int[17];

        for (int num : nums) {if ((++numCnt[num]) > k) {return -1;}

        }

        Arrays.sort(nums);

        this.k = k;

        this.nums = nums;

        cnt = nums.length / k;

        res = Integer.MAX_VALUE;

        idx = new int[k];

        latest = new int[k];

        first = new int[k];

        dfs(0, 0);

        return res;

    }

    private void dfs(int used, int sum) {if (used == nums.length) {res = Math.min(res, sum);

            return;

        }

        // 优化点

        if (sum >= res) {return;}

        // 枚举 nums[used] 放到哪一组中

        for (int i = 0; i < k; i++) {if (idx[i] < cnt && (idx[i] == 0 || latest[i] != nums[used])) {

                int newSum = sum;

                if (idx[i] == 0) {first[i] = nums[used];

                } else {newSum -= latest[i] - first[i];

                    newSum += nums[used] - first[i];

                }

                idx[i]++;

                int bak = latest[i];

                latest[i] = nums[used];

                dfs(used + 1, newSum);

                idx[i]--;

                latest[i] = bak;

                // 优化点: 第一个数值, 没有必要持续枚举

                if (idx[i] == 0) {break;}

            }

        }

    }

}