leetcode contest 311

leetcode contest 311

四个都是非常简单的题目，已经严重放水的题目了。

6180. 最小偶倍数

题目

给你一个正整数 n ，返回 2 和 n 的最小公倍数（正整数）。

示例 1：

输入：n = 5
输出：10
解释：5 和 2 的最小公倍数是 10 。

示例 2：

输入：n = 6
输出：6
解释：6 和 2 的最小公倍数是 6 。注意数字会是它自身的倍数。

提示：

• 1 <= n <= 150

地址

https://leetcode.cn/problems/count-days-spent-together/

题意

数学计算

思路

1. $n$ 为偶数则返回 $n$，否则则返回 $n * 2$。
2. 复杂度分析：

• 时间复杂度：$O(1)$。
• 空间复杂度：$O(1)$。

  代码

  class Solution {
  public:
      int smallestEvenMultiple(int n) {
          return (n & 1) ? (n * 2) : n;
      }
  };

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

题目

字母序连续字符串 是由字母表中连续字母组成的字符串。换句话说，字符串 "abcdefghijklmnopqrstuvwxyz" 的任意子字符串都是 字母序连续字符串 。

例如，"abc" 是一个字母序连续字符串，而 "acb" 和 "za" 不是。
给你一个仅由小写英文字母组成的字符串 s ，返回其 最长 的 字母序连续子字符串 的长度。

示例 1：

输入：s = "abacaba"
输出：2
解释：共有 4 个不同的字母序连续子字符串 "a"、"b"、"c" 和 "ab" 。
"ab" 是最长的字母序连续子字符串。

示例 2：

输入：s = "abcde"
输出：5
解释："abcde" 是最长的字母序连续子字符串。

提示：

• 1 <= s.length <= 105
• s 由小写英文字母组成

地址

https://leetcode.cn/problems/length-of-the-longest-alphabetical-continuous-substring/

题意

模拟

思路

1. 直接计算连续的字符串长度即可。
2. 复杂度分析：

• 时间复杂度：时间复杂度为 $O(n)$，$n$ 表示字符串的长度。
• 空间复杂度：空间复杂度为 $O(\log n + \log m)$，$m,n$ 表示运动员和训练师的数量。

  代码

  class Solution {
  public:
      int longestContinuousSubstring(string s) {
          int n = s.size();
          int ans = 1;
          int curr = 1;
          for (int i = 1; i < n; i++) {
              if (s[i] - s[i - 1] == 1) {
                  curr++;
              } else {
                  curr = 1;
              }
              ans = max(ans, curr);
          }
          return ans;
      }
  };

6182. 反转二叉树的奇数层

题目

给你一棵 完美 二叉树的根节点 root ，请你反转这棵树中每个 奇数 层的节点值。

例如，假设第 3 层的节点值是 [2,1,3,4,7,11,29,18] ，那么反转后它应该变成 [18,29,11,7,4,3,1,2] 。
反转后，返回树的根节点。

完美 二叉树需满足：二叉树的所有父节点都有两个子节点，且所有叶子节点都在同一层。

节点的 层数 等于该节点到根节点之间的边数。

示例 1：

输入：root = [2,3,5,8,13,21,34]
输出：[2,5,3,8,13,21,34]
解释：
这棵树只有一个奇数层。
在第 1 层的节点分别是 3、5 ，反转后为 5、3 。

示例 2：

输入：root = [7,13,11]
输出：[7,11,13]
解释： 
在第 1 层的节点分别是 13、11 ，反转后为 11、13 。 

示例 3：

输入：root = [0,1,2,0,0,0,0,1,1,1,1,2,2,2,2]
输出：[0,2,1,0,0,0,0,2,2,2,2,1,1,1,1]
解释：奇数层由非零值组成。
在第 1 层的节点分别是 1、2 ，反转后为 2、1 。
在第 3 层的节点分别是 1、1、1、1、2、2、2、2 ，反转后为 2、2、2、2、1、1、1、1 。

提示：

• 树中的节点数目在范围 [1, 214] 内
• 0 <= Node.val <= 105
• root 是一棵 完美 二叉树

地址

https://leetcode.cn/problems/smallest-subarrays-with-maximum-bitwise-or/

题意

直接模拟

思路

1. 我们直接按照层次来遍历二叉树的每一层，并将奇数层的节点的值和节点本身进行保存，然后将奇数层的节点的值按照要求进行反转之后再填回到节点中即可。
2. 复杂度分析

• 时间复杂度：时间复杂度为 $O(n)$，$n$ 表示节点的数目。
• 空间复杂度：空间复杂度为 $O(n)$，$n$ 表示节点的数目。

  代码

  class Solution {
  public:
      TreeNode* reverseOddLevels(TreeNode* root) {
          queue<TreeNode *> qu;
          qu.emplace(root);
          int level = 1;
          while (!qu.empty()) {
              int sz = qu.size();
              vector<TreeNode *> arr;
              vector<int> nums;
              for (int i = 0; i < sz; i++) {
                  TreeNode *curr = qu.front();
                  qu.pop();
                  if (curr->left && curr->right) {
                      if (level % 2) {
                          nums.emplace_back(curr->left->val);
                          nums.emplace_back(curr->right->val);
                      }
                      arr.emplace_back(curr->left);
                      arr.emplace_back(curr->right);
                      qu.emplace(curr->left);
                      qu.emplace(curr->right);
                  }
              }
              reverse(nums.begin(), nums.end());
              for (int i = 0; i < nums.size(); i++) {
                  arr[i]->val = nums[i];
              }
              level++;
          }
          return root;
      }
  };

6183. 字符串的前缀分数和

题目

给你一个长度为 n 的数组 words ，该数组由 非空 字符串组成。

定义字符串 word 的 分数 等于以 word 作为 前缀 的 words[i]的数目。

例如，如果 words = ["a", "ab", "abc", "cab"] ，那么 "ab" 的分数是 2，因为 "ab" 是 "ab" 和 "abc" 的一个前缀。
返回一个长度为 n 的数组 answer ，其中 answer[i] 是 words[i] 的每个非空前缀的分数 总和 。

注意：字符串视作它自身的一个前缀。

示例 1：

输入：words = ["abc","ab","bc","b"]
输出：[5,4,3,2]
解释：对应每个字符串的答案如下：
- "abc" 有 3 个前缀："a"、"ab" 和 "abc" 。
- 2 个字符串的前缀为 "a" ，2 个字符串的前缀为 "ab" ，1 个字符串的前缀为 "abc" 。
总计 answer[0] = 2 + 2 + 1 = 5 。
- "ab" 有 2 个前缀："a" 和 "ab" 。
- 2 个字符串的前缀为 "a" ，2 个字符串的前缀为 "ab" 。
总计 answer[1] = 2 + 2 = 4 。
- "bc" 有 2 个前缀："b" 和 "bc" 。
- 2 个字符串的前缀为 "b" ，1 个字符串的前缀为 "bc" 。 
总计 answer[2] = 2 + 1 = 3 。
- "b" 有 1 个前缀："b"。
- 2 个字符串的前缀为 "b" 。
总计 answer[3] = 2 。

示例 2：

输入：words = ["abcd"]
输出：[4]
解释：
"abcd" 有 4 个前缀 "a"、"ab"、"abc" 和 "abcd"。
每个前缀的分数都是 1 ，总计 answer[0] = 1 + 1 + 1 + 1 = 4 。

提示：

• 1 <= words.length <= 1000
• 1 <= words[i].length <= 1000
• words[i] 由小写英文字母组成

地址

https://leetcode.cn/problems/sum-of-prefix-scores-of-strings/

题意

trie树

思路

1. 感觉这个是个中等难度的题目，首先利用 trie 树存储所有字符串的前缀的统计次数。对于字符串 $s$ 进行搜索时，我们将在 trie 树中遇到的所有的前缀的统计次数叠加即可，不需要特别复杂的思考的问题。
2. 复杂度分析：

• 时间复杂度：$O(n \times m)$，其中 $n$ 表示的数组的长度，$m$ 表示每个字符串的平均长度。
• 空间复杂度：$O(n \times m)$，其中 $n$ 表示的数组的长度，$m$ 表示每个字符串的平均长度。

代码

struct Trie{
    bool isWord;
    int cnt;
    vector<Trie *> next;
    Trie(){
        this->isWord = false;
        this->next = vector<Trie *>(26, nullptr);
        this->cnt = 0;
    }
};

void insert(Trie * root, string word) {
    Trie *node = root;
    for (auto c : word) {
        if (!node->next[c - 'a']) {
            node->next[c - 'a'] = new Trie();
        }
        node = node->next[c - 'a'];
        node->cnt++;
    }
}

int search(Trie *root, string word) {
    int ans = 0;
    Trie *node = root;
    for (auto c : word) {
        if (!node->next[c - 'a']) {
            return ans;
        }
        node = node->next[c - 'a'];
        ans += node->cnt;
    }
    return ans;
}

class Solution {
public:
    vector<int> sumPrefixScores(vector<string>& words) {
        Trie *root = new Trie();
        for (auto word : words) {
            insert(root, word);
        }
        vector<int> ans;
        for (int i = 0; i < words.size(); i++) {
            ans.emplace_back(search(root, words[i]));
        }
        return ans;
    }
};

#

欢迎关注和打赏，感谢支持！

• 关注我的博客: http://mikemeng.org/
• 关注我的知乎：https://www.zhihu.com/people/da-hua-niu
• 关注我的微信公众号: 公务程序猿