C ++中字长的最大乘积

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一个称为单词的字符串数组，找到length（word [i]）* length（word [j]）的最大值，其中两个单词将不共享公共字母。我们可以假设每个单词仅包含小写字母。如果不存在这两个词，则返回0。因此，如果输入类似于[“ abcw”，“ baz”，“ foo”，“ bar”，“ xtfn”，“ abcdef”]，则输出将为16因为两个词可以是“ abcw”，“ xtfn”。

为了解决这个问题，我们将遵循以下步骤-

  • 定义一个名为的方法getRev()，它将x作为输入

  • ret：= 0

  • 当我在0到25的范围内

    • 如果x /（2 ^ i）是偶数，则ret：= ret OR 2 ^ i

  • 返回ret

  • 从主要方法中，执行以下操作-

  • 创建一个映射mn：=单词数组的大小

  • 对于i，范围为0至n – 1

    • 键：=键或2 ^（s [j] –'a'的ASCII）

    • s：= words [i]，key：= 0

    • 对于范围在0到s大小之间的j

    • m [i]：=键

  • ret：= 0

  • 对于我来说，范围是0到字数-1

    • 如果m [i]和m [j] = 0，则ret：=单词[i]的最大大小*单词[j]的大小

    • 对于范围i + 1的单词大小– 1

  • 返回ret

例子（C ++）

让我们看下面的实现以更好地理解-

#include <bits/stdc++.h&g;
using namespace std;
class Solution {
   public:
   int getRev(int x){
      int ret = 0;
      for(int i = 0; i <= 25 ; i++){
         if(!((x >> i) & 1)){
            ret |= (1 << i);
         }
      }
      return ret;
   }
   int maxProduct(vector<string>& words) {
      unordered_map <int, int> m;
      int n = words.size();
      for(int i = 0; i < n; i++){
         string s = words[i];
         int key = 0;
         for(int j = 0; j < s.size(); j++){
            key |= 1 << (s[j] - 'a');
         }
         m[i] = key;
      }
      int ret = 0;
      for(int i = 0; i < words.size(); i++){
         for(int j = i + 1; j < words.size(); j++){
            if((m[i] & m[j]) == 0){
               //cout << i << " " << j << endl;
               ret = max(ret, (int)words[i].size() * (int)words[j].size());
            }
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<string> v = {"abcw","baz","foo","bar","xtfn","abcdef"};
   cout << (ob.maxProduct(v));
}

输入值

["abcw","baz","foo","bar","xtfn","abcdef"]

输出结果

16

以上是 C ++中字长的最大乘积 的全部内容， 来源链接： utcz.com/z/338465.html

回到顶部