前言

──是啊。我留下了美梦般的回忆，不过时间到了。

整体评价

t2设计题不错，不过放水了， t3的构造题考验思维，t4经典的状压DP

整体还不错，^_^

1. 字符串中第二大的数字

1796. 字符串中第二大的数字

一般求第K大的题都挺麻烦的，幸好这题是t1.

这边用了slot桶，然后贪心倒序求第二大。

时间复杂度为 $O (n)$

Java

class Solution {
    
    public int secondHighest(String s) {
        int[] hash = new int[10];
        for (char c: s.toCharArray()) {
            if (c >= '0' && c <= '9') {
                hash[c - '0']++;
            }
        }
        int seen = 0;
        for (int i = 9; i >= 0; i--) {
            if (hash[i] > 0) {
                seen++;
                if (seen == 2) {
                    return i;
                }
            }
        }
        return -1;
    }
    
}

2. 设计一个验证系统

1797. 设计一个验证系统

这题一度想用树状数组维护没过期的token数了，不过数据范围实在太大了.

最后用了Brute Force Algorithm.

值得一提的是，这边用了 LinkedHashMap, 就是那个著名的LRU底层数据结构。

Java

class AuthenticationManager {

    // 数据太大，不能用BIT
    
    private int timeToLive;
    LinkedHashMap<String, Integer> tokenMap = new LinkedHashMap<String, Integer>();
    
    public AuthenticationManager(int timeToLive) {
        this.timeToLive = timeToLive;
    }
    
    public void generate(String tokenId, int currentTime) {
        tokenMap.put(tokenId, currentTime + this.timeToLive);
    }
    
    public void renew(String tokenId, int currentTime) {
        long at = tokenMap.getOrDefault(tokenId, -1);
        if (at > currentTime) {
            tokenMap.put(tokenId, currentTime + timeToLive);
        }
    }
    
    public int countUnexpiredTokens(int currentTime) {
        int ans = 0;
        Iterator<Map.Entry<String, Integer>> iter = tokenMap.entrySet().iterator();
        while (iter.hasNext()) {
            Map.Entry<String, Integer> e = iter.next();
            if (e.getValue().intValue() <= currentTime) {
                iter.remove();
            } else {
                ans++;
            }
        }
        
        return ans;
    }
    
}

3. 你能构造出连续值的最大数目

1798. 你能构造出连续值的最大数目

非常不错的思维题，然后联想到集合的扩展，类似并查集在数组中扩展过程。

想到了贪心解, 满足条件的集合尝试扩展自己的边界，需要满足集合 $s u m (S) + 1 >= n$ , 那这个n可以合并到这个集合中去.

Java

class Solution {
    
    public int getMaximumConsecutive(int[] coins) {
    
        Arrays.sort(coins);

        int acc = 0;
        for (int i = 0; i < coins.length; i++) {
            if (acc + 1 >= coins[i]) {
                acc += coins[i];
            } else {
                return acc + 1;
            }
        }
        
        return acc + 1;
        
    }
    
}

4. N 次操作后的最大分数和

1799. N 次操作后的最大分数和

这题的N范围 $1 \leq N \leq 7$ , 数组最多为14，所以很容易联想到暴力dfs, 或者状压DP

最终采用状压DP，也没写记忆化搜索。

Java

class Solution {

    int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    // 状压DP
    public int maxScore(int[] nums) {

        // 经典状压题
        int m = nums.length;
        int range = (1 << m);
        int[] opt = new int[range];

        Arrays.fill(opt, -Integer.MAX_VALUE / 4);

        opt[0] = 0;
        for (int i = 1; i < range; i++) {

            List<Integer> arr = new ArrayList<>();
            for (int j = 0; j < m; j++) {
                if ((i & (1 << j)) != 0) {
                    arr.add(j);
                }
            }

            if (arr.size() % 2 == 1) continue;

            int last = 0;
            for (int j = 0; j < arr.size(); j++) {
                for (int k = j + 1; k < arr.size(); k++) {
                    last = (1 << arr.get(j)) | (1 << arr.get(k));

                    int other = i - last;
                    opt[i] = Math.max(
                        opt[i], 
                        opt[other] + arr.size() / 2 * gcd(nums[arr.get(j)], nums[arr.get(k)])
                    );
                }
            }

        }

        return opt[range - 1];
    }

}