leetcode周赛笔记

311单周赛

时间：2022.09.18

【过程】

前两道题很快就写出来了

第三道题，很难受，一种感觉能写出来但是就是写不出来的感觉，还是对于二叉树的递归不够深入

第四道题用常规方法写出来，但是超时...

6181. 最长的字母序连续子字符串的长度

题目

// 比赛写的时候是用栈写的，但是其实只是用到栈的思想，不用栈也是完全可以的
// 抓住 1、连续 2、字母序 3、最大
public int longestContinuousSubstring(String s) {
    int maxLen = 0;
    int need = s.charAt(0); // 下一个需要的字符
    int cnt = 0;
    for(int i = 0; i < s.length(); i++){
        char c = s.charAt(i);
        if(c == need){
            cnt ++;
            need ++;
        } else { // 如果不满足的话，从这个位置重新开始向后寻找
            need = c + 1;
            cnt = 1;
        }
        maxLen = Math.max(maxLen, cnt);
    }
    return maxLen;
}

6182. 反转二叉树的奇数层

题目

【答题】

解题过程中，想过递归和队列两种方式。

但是，递归想的一直都是如何交换节点，所以很快就放弃了

使用队列，想的是在奇数层用遍历将值倒过来，写的过程中不是很顺利

【思路】

核心思想就是交换值，不交换结点

DFS 递归

其实使用DFS递归的过程中只要交换结点的值就可以了，这样就不会影响下面的子节点，只要考虑如何递归能够将一层的结点值倒过来。

运用到二叉树递归的一个技巧，【当递归函数参数只有一个结点难以实现递归时，可以考虑使用两个结点参数的递归函数】

public TreeNode reverseOddLevels(TreeNode root){
    
}

private TreeNode reverseOddLevelsByDFS(TreeNode root){
    dfs(root.left, root.right, 1);
    return root;
}

private void dfs(TreeNode node1, TreeNode node2, int level){
    if(node1 == null) return;
    
	// 如果是奇数层，就交换对应结点的值
    if(level % 2 == 1) {
        int tmp = node1.val;
        node1.val = node2.val;
        node2.val = tmp;
    }
	// 通过两个结点一起递归，且该两个结点是处于对称位置
    dfs(node1.left, node2.right, level+1);
    dfs(node1.right, node2.left, level+1);
}

BFS 迭代

BFS迭代就是借助队列实现层次遍历，如果是奇数层做出对结点值的改变

int[] values;
private TreeNode reverseOddLevelsByBFS(TreeNode root){
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    int level = 0;

    while (!queue.isEmpty()){
        int size = queue.size();

        // 如果队列中放的是奇数层，将这一层的值取出来放在values数组中
        if(level % 2 == 1){
            values = new int[size];
            for (int i = 0; i < size; i++){
                TreeNode node = queue.poll();
                values[i] = node.val;
                queue.offer(node);
            }
        }
        
        // 改造一下常规框架，如果是奇数层，再将结点poll出来之后，根据values数组改变其值
        for (int i = 0; i < size; i++){
            TreeNode node = queue.poll();
            if(level % 2 == 1){ // 如果是奇数层就改变值
                node.val = values[size - i - 1];
            }
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }

        level++;
    }

    return root;
}

6183. 字符串的前缀分数和

题目

在前缀树的基础上，这道题就十分简单了，只需要稍微改造一下前缀树，在插入word的过程中每经过一个结点就+1，然后再提供一个计算word得分的函数

/*
改造 Trie 树 在每一个结点里增加一个 cnt 统计在插入过程中 经过该结点的单词个数
也就是以 到这个结点为至形成的prefix 开始的单词数
 */
public int[] sumPrefixScores(String[] words) {
    Trie root = new Trie();
    for (String word : words) {
        root.insert(word);
    }
    int[] answer = new int[words.length];
    for (int i = 0; i < words.length; i++) {
        answer[i] = root.getScores(words[i]);
    }
    return answer;
}

class Trie {
    public Trie[] children;
    boolean isEnd;
    public int cnt;

    public Trie() {
        children = new Trie[26];
        isEnd = false;
        cnt = 0;
    }

    public void insert(String word) {
        Trie cur = this;
        for (int i = 0; i < word.length(); i++){
            char c = word.charAt(i);
            int idx = c - 'a';
            if(cur.children[idx] == null) {
                cur.children[idx] = new Trie();
            }
            cur.children[idx].cnt ++; // 经过这个结点的单词数++
            cur = cur.children[idx];
        }
        cur.isEnd = true;
    }
	
    // 获得该word的得分
    public int getScores(String word){
        Trie cur = this;
        int score = 0;
        for (int i = 0; i < word.length(); i++){
            char c = word.charAt(i);
            int idx = c - 'a';
            if (cur.children[idx] == null){
                return 0; // 不存在这个word, 对于已存在的word肯定不会出现这个情况
            } else {
                score += cur.children[idx].cnt;
                cur = cur.children[idx];
            }
        }
        return score;
    }

    public boolean search(String word) {
        Trie cur = this;
        for (int i = 0; i < word.length(); i++){
            char c = word.charAt(i);
            int idx = c - 'a';
            if (cur.children[idx] == null){
                return false;
            } else {
                cur = cur.children[idx];
            }
        }
        return cur.isEnd;
    }

    public boolean startsWith(String prefix) {
        Trie cur = this;
        for (int i = 0; i < prefix.length(); i++){
            char c = prefix.charAt(i);
            int idx = c - 'a';
            if(cur.children[idx] == null){
                return false;
            } else {
                cur = cur.children[idx];
            }
        }
        return true;
    }


}

模板: 208. 实现 Trie (前缀树)

题目

/*
Trie的原理: 每一个结点都包含一个指向 size = 26 的数组的引用
插入一个单词就是 从根节点依次向下新增结点 在数组对应位置(对应下标的字符 - 'a') 创建结点Trie
26cha'shu
 */
class Trie {
    public Trie[] children;
    boolean isEnd;

    public Trie() {
        children = new Trie[26];
        isEnd = false;
        cnt = 0;
    }

    public void insert(String word) {
        Trie cur = this;
        for (int i = 0; i < word.length(); i++){
            char c = word.charAt(i);
            int idx = c - 'a';
            if(cur.children[idx] == null) {
                cur.children[idx] = new Trie();
            }
            cur = cur.children[idx];
        }
        cur.isEnd = true;
    }

    public boolean search(String word) {
        Trie cur = this;
        for (int i = 0; i < word.length(); i++){
            char c = word.charAt(i);
            int idx = c - 'a';
            if (cur.children[idx] == null){
                return false;
            } else {
                cur = cur.children[idx];
            }
        }
        return cur.isEnd;
    }

    public boolean startsWith(String prefix) {
        Trie cur = this;
        for (int i = 0; i < prefix.length(); i++){
            char c = prefix.charAt(i);
            int idx = c - 'a';
            if(cur.children[idx] == null){
                return false;
            } else {
                cur = cur.children[idx];
            }
        }
        return true;
    }

}

327单周赛

时间：2023-01-08

在第三道题浪费了太多时间，第四道题比较复杂，思路不清晰。

6284. 使字符串总不同字符的数目相等(第三题)

这道题在做题时把问题想简单了，导致没有考虑全面，通过判题罚时找到漏洞。

其实可以将两个字符串的字符出现情况用两个数组记录下来，然后双重循环即可。

bool isItPossible(string word1, string word2) {
    vector<int> a1(26); vector<int> a2(26);
    for (char c : word1) a1[c-'a'] ++;
    for (char c : word2) a2[c-'a'] ++;
    
    int s1 = 0, s2 = 0;
    for (int i : a1) s1 += i > 0;
    for (int i : a2) s2 += i > 0;
    if (abs(s1 - s2) > 2) return false;

    for (int i = 0; i < 26; i++){
        for (int j = 0; j < 26; j++){
            if (a1[i] > 0 && a2[j] > 0){
                a1[j]++; a1[i]--; a2[j]--; a2[i]++;
                s1 = 0; s2 = 0;
                for (int k : a1) s1 += k > 0;
                for (int k : a2) s2 += k > 0;
                if (s1 == s2) return true;
                a1[j]--; a1[i]++; a2[j]++; a2[i]--;
            }
        }
    }

    return false;
}

6306. 过桥的时间(第四题)

看了题解，核心就是四个堆，因为上面的流程无非就是四个步骤：从桥的左边到右边、从旧仓库取箱子、从桥的右边到左边、从新仓库放箱子，就可以对应这四个步骤建立四个堆。整个过程还是比较复杂的，需要仔细理解。

• ==wait_l==：在桥左边等待的工人
• ==wait_r==：在桥右边等待的工人
• ==box_l==：在新仓库放箱子的工人
• ==box_r==：在旧仓库取箱子的工人

typedef pair<int, int> p;
int findCrossingTime(int n, int k, vector<vector<int>>& time) {
    int size = time.size();
    for(int i = 0; i < size; i ++) time[i].push_back(i);
    // 按照效率从高到低排序 使得下标最大的工人效率最低
    sort(time.begin(), time.end(), [](vector<int>& a, vector<int>& b){
        int prof_a = a[0] + a[2]; int prof_b = b[0] + b[2];
        if (prof_a != prof_b) return prof_a < prof_b;
        return a[4] < b[4];
    });

    priority_queue<int> wait_l, wait_r; // 大顶堆 top()是效率最低的工人
    priority_queue<p, vector<p>, greater<p>> box_l, box_r; // 小顶堆 top()是最快完成box任务的工人

    int cur = 0; // 记录时间

    // 一开始全部在左边等待
    for (int i = 0; i < k; i ++) wait_l.push(i);

    while (true) {
        bool LtoR = n > 0 && !wait_l.empty();
        bool RtoL = !wait_r.empty();

        if (!LtoR && !RtoL) { // 左右两边都没有工人等待
            // 找到box_l和box_r中最快完成任务的工人 更新时间
            int x = INT_MAX;
            if(!box_l.empty()) x = min(x, box_l.top().first);
            if(!box_r.empty()) x = min(x, box_r.top().first);
            cur = x;
        }

        if (RtoL){ // 右边到左边
            int x = wait_r.top(); // 取出右边效率最低的工人x
            wait_r.pop();
            cur += time[x][2]; // 让x工人过桥
            // 检查是否是最后一个工人到达桥左岸
            if (n == 0 && wait_r.empty() && box_r.empty()) return cur;
            box_l.push(p(cur+time[x][3], x)); // 过桥后到新仓库放箱子 放入box_l堆中
        } else if (LtoR) { // 左边到右边
            int x = wait_l.top(); // 取出左边效率最低的工人x
            wait_l.pop();
            cur += time[x][0]; // 让x工人过桥
            box_r.push(p(cur+time[x][1], x)); // 过桥后到旧仓库取箱子 放入box_r堆中
            n--; // 箱子数-1
        }

        while (!box_l.empty()) {
            p worker = box_l.top();
            // 如果在桥上的工人过桥的时间里，有工人能够完成box任务，就将他们放到对应的桥边等待队列中
            if (worker.first > cur) break;
            box_l.pop();
            wait_l.push(worker.second);
        }

        while (!box_r.empty()) {
            p worker = box_r.top();
            // 如果在桥上的工人过桥的时间里，有工人能够完成box任务，就将他们放到对应的桥边等待队列中
            if (worker.first > cur) break;
            box_r.pop();
            wait_r.push(worker.second);
        }
    }
}

类似的题目：

1834. 单线程 CPU