LeetCode 第133场周赛总结

╰半夏微凉° 2023-10-09 09:37 53阅读 0赞

### 1029. 两地调度 ###

公司计划面试 `2N` 人。第 `i` 人飞往 `A` 市的费用为 `costs[i][0]`，飞往 `B` 市的费用为 `costs[i][1]`。

返回将每个人都飞到某座城市的最低费用，要求每个城市都有 `N` 人抵达**。**

**示例：**

输入：[[10,20],[30,200],[400,50],[30,20]]
    输出：110
    解释：
    第一个人去 A 市，费用为 10。
    第二个人去 A 市，费用为 30。
    第三个人去 B 市，费用为 50。
    第四个人去 B 市，费用为 20。
    
    最低总费用为 10 + 30 + 50 + 20 = 110，每个城市都有一半的人在面试

**提示：**

1.  `1 <= costs.length <= 100`
2.  `costs.length` 为偶数
3.  `1 <= costs[i][0], costs[i][1] <= 1000`

> 思路：动态规划，dp\[i\] \[j\] 代表共有 i 个人, 其中 j 个人飞往 A 市的最小花费。

class Solution {
    public:
        int twoCitySchedCost(vector<vector<int>>& costs) {
            int n = costs.size();
            vector<vector<int>> dp(n+1,vector<int>(n+1,INT_MAX));
            dp[0][0] = 0;
            for(int i = 0; i <n; i++)
            { 
                for(int j = 0; j <=i; j++)
                {
                    dp[i+1][j] = min (dp[i+1][j], dp[i][j] + costs[i][0]); //新人飞往A
                    dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j] + costs[i][1]);
                }
            }
            return dp[n][n/2];
        }
    };

### 1030. 距离顺序排列矩阵单元格 ###

给出 `R` 行 `C` 列的矩阵，其中的单元格的整数坐标为 `(r, c)`，满足 `0 <= r < R` 且 `0 <= c < C`。

另外，我们在该矩阵中给出了一个坐标为 `(r0, c0)` 的单元格。

返回矩阵中的所有单元格的坐标，并按到 `(r0, c0)` 的距离从最小到最大的顺序排，其中，两单元格`(r1, c1)` 和 `(r2, c2)` 之间的距离是曼哈顿距离，`|r1 - r2| + |c1 - c2|`。（你可以按任何满足此条件的顺序返回答案。）

**示例 1：**

输入：R = 1, C = 2, r0 = 0, c0 = 0
    输出：[[0,0],[0,1]]
    解释：从 (r0, c0) 到其他单元格的距离为：[0,1]

**示例 2：**

输入：R = 2, C = 2, r0 = 0, c0 = 1
    输出：[[0,1],[0,0],[1,1],[1,0]]
    解释：从 (r0, c0) 到其他单元格的距离为：[0,1,1,2]
    [[0,1],[1,1],[0,0],[1,0]] 也会被视作正确答案。

**示例 3：**

输入：R = 2, C = 3, r0 = 1, c0 = 2
    输出：[[1,2],[0,2],[1,1],[0,1],[1,0],[0,0]]
    解释：从 (r0, c0) 到其他单元格的距离为：[0,1,1,2,2,3]
    其他满足题目要求的答案也会被视为正确，例如 [[1,2],[1,1],[0,2],[1,0],[0,1],[0,0]]。

**提示：**

1.  `1 <= R <= 100`
2.  `1 <= C <= 100`
3.  `0 <= r0 < R`
4.  `0 <= c0 < C`

class Solution {
    public:
            vector<vector<int>>res ;
    
        vector<vector<int>> allCellsDistOrder(int R, int C, int r0, int c0) {
            for(int i = 0; i < R ;i++)
            {
                for(int j = 0; j < C; j++ )
                {
                    res.push_back({i,j});
                }
            }
            
            sort(res.begin(),res.end(),[r0,c0](vector<int> &a, vector<int> &b) {
                return abs(a[0] - r0)+abs(a[1]-c0) <  abs(b[0] - r0)+abs(b[1]-c0);
            });
            return res;
        }
    };

### 1031. 两个非重叠子数组的最大和 ###

给出非负整数数组 `A` ，返回两个非重叠（连续）子数组中元素的最大和，子数组的长度分别为 `L` 和 `M`。（这里需要澄清的是，长为 L 的子数组可以出现在长为 M 的子数组之前或之后。）

从形式上看，返回最大的 `V`，而 `V = (A[i] + A[i+1] + ... + A[i+L-1]) + (A[j] + A[j+1] + ... + A[j+M-1])` 并满足下列条件之一：

*  `0 <= i < i + L - 1 < j < j + M - 1 < A.length`, **或**
 *  `0 <= j < j + M - 1 < i < i + L - 1 < A.length`.

**示例 1：**

输入：A = [0,6,5,2,2,5,1,9,4], L = 1, M = 2
    输出：20
    解释：子数组的一种选择中，[9] 长度为 1，[6,5] 长度为 2。

**示例 2：**

输入：A = [3,8,1,3,2,1,8,9,0], L = 3, M = 2
    输出：29
    解释：子数组的一种选择中，[3,8,1] 长度为 3，[8,9] 长度为 2。

**示例 3：**

输入：A = [2,1,5,6,0,9,5,0,3,8], L = 4, M = 3
    输出：31
    解释：子数组的一种选择中，[5,6,0,9] 长度为 4，[0,3,8] 长度为 3。

**提示：**

1.  `L >= 1`
2.  `M >= 1`
3.  `L + M <= A.length <= 1000`
4.  `0 <= A[i] <= 1000`

> 思路：

class Solution {
    public:
        int s[1005];
        int maxSumTwoNoOverlap(vector<int>& A, int L, int M) {
            int n = A.size();
            s[0] = 0;
            for (int i = 1; i <=n; i++) {
                s[i] = s[i-1] + A[i-1]; 
            }
            int res = 0;
            for (int i = 1; i <= n; i++) {
                for (int j = i+L; j <=n; j++) {
                    if(i+L-1 <= n && j+M-1 <= n) {
                        res = max (res,s[i+L-1] - s[i-1] + s[j+M-1] - s[j-1]);
                    }
                }
            }
           for (int i = 1; i <= n; i++) {
                for (int j = i+M; j <=n; j++) {
                    if(i+M-1 <= n && j+L-1 <= n) {
                        res = max (res,s[i+M-1] - s[i-1] + s[j+L-1] - s[j-1]);
                    }
                }
            }
            return res;
        }
    };

### 1032. 字符流 ###

按下述要求实现 `StreamChecker` 类：

*  `StreamChecker(words)`：构造函数，用给定的字词初始化数据结构。
 *  `query(letter)`：如果存在某些 `k >= 1`，可以用查询的最后 `k`个字符（按从旧到新顺序，包括刚刚查询的字母）拼写出给定字词表中的某一字词时，返回 `true`。否则，返回 `false`。

**示例：**

StreamChecker streamChecker = new StreamChecker(["cd","f","kl"]); // 初始化字典
    streamChecker.query('a');          // 返回 false
    streamChecker.query('b');          // 返回 false
    streamChecker.query('c');          // 返回 false
    streamChecker.query('d');          // 返回 true，因为 'cd' 在字词表中
    streamChecker.query('e');          // 返回 false
    streamChecker.query('f');          // 返回 true，因为 'f' 在字词表中
    streamChecker.query('g');          // 返回 false
    streamChecker.query('h');          // 返回 false
    streamChecker.query('i');          // 返回 false
    streamChecker.query('j');          // 返回 false
    streamChecker.query('k');          // 返回 false
    streamChecker.query('l');          // 返回 true，因为 'kl' 在字词表中。

**提示：**

*  `1 <= words.length <= 2000`
 *  `1 <= words[i].length <= 2000`
 *  字词只包含小写英文字母。
 *  待查项只包含小写英文字母。
 *  待查项最多 40000 个。

class Trie {
        public: 
        bool is_value = false; //结束位
        vector<Trie*> child;
        Trie():child(26,NULL){ //初始化
            
        }
    };
    
    class StreamChecker {
    public:
        vector<char> str;
        Trie *root = new Trie();
        StreamChecker(vector<string>& words) {
            for(auto word:words) {
                reverse(word.begin(),word.end());
                Trie* p = root;
                for(auto w:word) {
                    int t = w - 'a';
                    if(p->child[t]  ==  NULL) {
                        p->child[t] = new Trie();
                    }
                    p = p->child[t];
                }
                p->is_value  = true;
            }
        }
        
        bool query(char letter) {
            str.push_back(letter);
            Trie* p = root;
            for(int i=str.size()-1; i >= 0; i--)
            {
                int t = str[i] - 'a';
                if(p->child[t] == NULL) {
                    return false;
                }
                p = p->child[t];
                if(p->is_value == true) return true;
            }
            return false;
        }
    };
    
    /**
     * Your StreamChecker object will be instantiated and called as such:
     * StreamChecker* obj = new StreamChecker(words);
     * bool param_1 = obj->query(letter);
     */

转载于:https://www.cnblogs.com/lyc1226/p/11306158.html