樊轶群的个人网站

import java.util.HashSet;
import java.util.Set;

// 0753. Cracking the Safe
class Solution {
    public String crackSafe(int n, int k) {
        if (n == 1 && k == 1) {
            return "0";
        }
        StringBuilder ans = new StringBuilder();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n - 1; ++i) {
            sb.append("0");
        }
        String start = sb.toString();
        Set<String> visited = new HashSet<>();
        dfs(start, k, visited, ans);
        ans.append(start);
        return ans.toString();
    }

    public void dfs(String start, int k, Set<String> visited, StringBuilder ans) {
        for (int i = 0; i < k; ++i) {
            String nbr = start + i;
            if (!visited.contains(nbr)) {
                visited.add(nbr);
                dfs(nbr.substring(1), k, visited, ans);
                ans.append(i);
            }
        }
    }
}

学习笔记：
这又是一道超级困难题，普通深搜似乎是难以通过的，得剪枝。
这其实是求一个de Bruijn序列，和汉密尔顿圈、欧拉回路都有关系。
这个需要等以后有空了才能去研究了。

// 1806. Minimum Number of Operations to Reinitialize a Permutation
class Solution {
    public int reinitializePermutation(int n) {
        int[] perm = new int[n];
        for (int i = 0; i < n; ++i) {
            perm[i] = i;
        }
        int ans = 0;
        while (true) {
            ++ans;
            int[] arr = new int[n];
            for (int i = 0; i < n; ++i) {
                if ((i & 1) == 0) {
                    arr[i] = perm[i >> 1];
                } else {
                    arr[i] = perm[(n >> 1) + (i - 1 >> 1)];
                }
            }
            if (isReinitialized(n, arr)) {
                break;
            }
            perm = arr;
        }
        return ans;
    }

    private boolean isReinitialized(int n, int[] arr) {
        for (int i = 0; i < n; ++i) {
            if (arr[i] != i) {
                return false;
            }
        }
        return true;
    }
}

学习笔记：
这道题是一道中等题，如果是数学算法，我觉得算是困难题了可以。
主要这道题用n^2的模拟算法也给过，我时间紧迫就先写了一个模拟算法的了。
这个其实就是一个循环次数的问题，还有寻找面向答案的编程、还有数学算法可以使用。

// 2185. Counting Words With a Given Prefix
class Solution {
    public int prefixCount(String[] words, String pref) {
        int ans = 0;
        for (String word : words) {
            if (word.startsWith(pref)) {
                ++ans;
            }
        }
        return ans;
    }
}

学习笔记：
这是一道简单题。判断一个字符串是否为另一个字符串的前缀。
考察的是对于startsWith函数的使用。
遍历用一圈就可以了。

// 1658. Minimum Operations to Reduce X to Zero
class Solution {
    public int minOperations(int[] nums, int x) {
        int n = nums.length;
        int left = -1;
        int window = 0;
        while (window < x) {
            ++left;
            if (left == n) {
                return -1;
            }
            window += nums[left];
        }
        int minOp = 9999999;
        if (window == x) minOp = left + 1;
        int right = n;
        while (left >= -1 && left < right) {
            while (window > x && left >= 0) {
                window -= nums[left];
                --left;
            }
            if (window == x) {
                int op = left + 1 + n - right;
                minOp = Math.min(minOp, op);
            }
            --right;
            if (right < 0) break;
            window += nums[right];
        }
        return minOp == 9999999 ? -1 : minOp;
    }
}

学习笔记：
这是一道滑动窗口的题目，总体难度中等，很符合中等题该有的难度。
就是窗口是左半边加右半边的，维护起来有点恶心。
还有各种边界情况，容易产生漏算漏考虑导致的报错。

// 2180. Count Integers With Even Digit Sum
class Solution {
    public int countEven(int num) {
        int ans = 0;
        for (int i = 1; i <= num; ++i) {
            if (isEvenDigitsSum(i)) {
                ++ans;
            }
        }
        return ans;
    }

    private boolean isEvenDigitsSum(int n) {
        int oddEven = 0;
        while (n > 0) {
            if (n % 10 % 2 == 1) ++oddEven;
            n /= 10;
        }
        return oddEven % 2 == 0;
    }
}

学习笔记：
困难题之后果然又是一道简单题。
今天的题目就是统计奇数偶数的位数相关的。
转成String来做也是比较合理的，用%和/组合运算也是更高效的算法。

// 1803. Count Pairs With XOR in a Range
class Solution {
    private Trie root;
    private static final int HIGH_BIT = 14;

    public int countPairs(int[] nums, int low, int high) {
        return countPairsLessThanOrEqualsX(nums, high) - countPairsLessThanOrEqualsX(nums, low - 1);
    }

    public int countPairsLessThanOrEqualsX(int[] nums, int x) {
        root = new Trie();
        int res = 0;
        addNode(nums[0]);
        for (int i = 1; i < nums.length; ++i) {
            res += get(nums[i], x);
            addNode(nums[i]);
        }
        return res;
    }

    public void addNode(int num) {
        Trie current = root;
        for (int k = HIGH_BIT; k >= 0; --k) {
            int bit = (num >> k) & 1;
            if (current.son[bit] == null) {
                current.son[bit] = new Trie();
            }
            current = current.son[bit];
            ++current.belowSum;
        }
    }

    public int get(int num, int x) {
        Trie current = root;
        int sum = 0;
        for (int k = HIGH_BIT; k >= 0; k--) {
            int r = (num >> k) & 1;
            if (((x >> k) & 1) != 0) {
                if (current.son[r] != null) {
                    sum += current.son[r].belowSum;
                }
                if (current.son[r ^ 1] == null) {
                    return sum;
                }
                current = current.son[r ^ 1];
            } else {
                if (current.son[r] == null) {
                    return sum;
                }
                current = current.son[r];
            }
        }
        sum += current.belowSum;
        return sum;
    }
}

class Trie {
    Trie[] son = new Trie[2];
    int belowSum;

    public Trie() {
        belowSum = 0;
    }
}

学习笔记：
这是一道超级困难题，用到了字典树，位运算。
我也看了解法后理解了思路，但是写不出来。后来看到了代码后跟着代码继续理解了两遍，把代码半默写了一遍。之后有时间还是要好好再研究研究这道题。

// 1802. Maximum Value at a Given Index in a Bounded Array
class Solution {
    public int maxValue(int n, int index, int maxSum) {
        int left = 1;
        int right = maxSum + 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (valid(mid, n, index, maxSum)) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left - 1;
    }

    public boolean valid(int mid, int n, int index, int maxSum) {
        int left = index;
        int right = n - index - 1;
        long sum = mid + cal(mid, left) + cal(mid, right);
        return sum <= maxSum;
    }

    public long cal(int big, int length) {
        if (length + 1 < big) {
            int small = big - length;
            return (long) (big - 1 + small) * length / 2;
        } else {
            int ones = length - (big - 1);
            return (long) big * (big - 1) / 2 + ones;
        }
    }
}

学习笔记：
这是一道二分搜索的题目，用到的是搜索右边界的二分搜索。
然后再逐个尝试的时候，用到了贪心算法。

// 2042. Check if Numbers Are Ascending in a Sentence
class Solution {
    public boolean areNumbersAscending(String s) {
        String[] words = s.split(" ");
        int previous = 0;
        for (String word : words) {
            try {
                int current = Integer.parseInt(word);
                if (current <= previous) {
                    return false;
                } else {
                    previous = current;
                }
            } catch (Exception e) {

            }
        }
        return true;
    }
}

学习笔记：
这道题的话简陋的做法就是这样。
尝试将字符串切割后转为整数，能转就比较，不能转的话会有异常。
如果打印异常的话会20ms，不打印不处理只需要3ms。
看来打印异常还是挺耗时的。

import java.util.PriorityQueue;

// 1801. Number of Orders in the Backlog
class Solution {
    public int getNumberOfBacklogOrders(int[][] orders) {
        final long MOD = 1000000007L;
        PriorityQueue<Order> backlog0 = new PriorityQueue<>(((o1, o2) -> (o2.price - o1.price)));
        PriorityQueue<Order> backlog1 = new PriorityQueue<>(((o1, o2) -> (o1.price - o2.price)));
        for (int[] order : orders) {
            int price = order[0];
            int amount = order[1];
            if (order[2] == 0) {
                while (amount > 0 && !backlog1.isEmpty() && price >= backlog1.peek().price) {
                    if (amount >= backlog1.peek().amount) {
                        amount -= backlog1.poll().amount;
                    } else {
                        backlog1.peek().amount -= amount;
                        amount = 0;
                    }
                }
                if (amount > 0) {
                    backlog0.offer(new Order(price, amount));
                }
            } else {
                while (amount > 0 && !backlog0.isEmpty() && price <= backlog0.peek().price) {
                    if (amount >= backlog0.peek().amount) {
                        amount -= backlog0.poll().amount;
                    } else {
                        backlog0.peek().amount -= amount;
                        amount = 0;
                    }
                }
                if (amount > 0) {
                    backlog1.offer(new Order(price, amount));
                }
            }
        }
        long ans = 0L;
        while (!backlog0.isEmpty()) {
            ans = (ans + backlog0.poll().amount) % MOD;
        }
        while (!backlog1.isEmpty()) {
            ans = (ans + backlog1.poll().amount) % MOD;
        }
        return (int) ans;
    }
}

class Order {
    int price;
    int amount;

    public Order(int price, int amount) {
        this.price = price;
        this.amount = amount;
    }
}

学习笔记：
今天这道题目就是考察两个优先队列，分别是最大堆和最小堆。
描述了很多，做题的时候发现描述多写代码就按描述来就可以了。
有一种在做模拟算法的感觉。

// 2351. First Letter to Appear Twice
class Solution {
    public char repeatedCharacter(String s) {
        boolean[] existed = new boolean[123];
        for (char c : s.toCharArray()) {
            if (existed[c]) {
                return c;
            } else {
                existed[c] = true;
            }
        }
        return ' ';
    }
}

学习笔记：
新的一年，第一题特别简单，考察的是哈希表，但我偏偏不用，哈哈哈。