重新排列字符串的字符,以形成有效的英文数字表示形式

大晨姑娘_6208

大晨姑娘_6208

2023-09-24

1559人浏览

转载

重新排列字符串的字符,以形成有效的英文数字表示形式

在这个问题中,我们需要重新排列给定字符串的字符,以获得有效的英文数字表示。第一种方法可以是找到字符串的所有排列,提取与数字相关的英文单词,并将它们转换为数字。

另一种解决该问题的方法是从每个单词中找到一个唯一的字符。在本教程中,我们将学习解决给定问题的两种方法。

问题陈述- 我们给出了一个包含小写字符且长度为N的字符串。该字符串以随机顺序包含了[0-9]数字的英文单词表示。我们需要从字符串中提取英文单词,将它们转换为数字,并按升序显示这些数字

示例例子

输入 – str = "zeoroenwot"

输出 – ‘012’

解释– 我们可以从给定的字符串中提取出'zero'、'one'和'two',然后按照数字的增序进行排序。

输入 – str = ‘zoertowxisesevn’

输出 – ‘0267’

Explanation – 我们可以从给定的字符串中提取出“zero”、“two”、“six”和“seven”。

方法一

在这种方法中,我们将使用next_permutation()方法来获取字符串的排列。然后,我们将从每个排列中提取与数字相关的英文单词,并跟踪从任何排列中提取的最大单词总数。根据这一点,我们将形成字符串。

算法

  • 定义countOccurrences()函数,它接受字符串和单词作为参数。它用于计算给定字符串中特定单词的出现次数。

    • 定义变量‘count’,并将其初始化为零。

    • 使用while循环遍历字符串。如果我们在当前位置找到了该单词,则将'count'的值增加1,并将'pos'的值跳过单词的长度。

    • 返回‘count’的值

  • convertToDigits() 函数用于将单词转换为数字

  • 定义名为‘words’的向量,其中包含数字的英文表示。同时,定义‘max_digits’来存储字符串的任意排列中的最大单词数。此外,定义‘digit_freq’映射来存储当我们可以从任意排列中提取最大单词时,每个数字的频率。

  • 使用sort()方法对给定的字符串进行排序。

  • 使用 next_permutations() 方法与 do-while() 循环。在循环中,使用另一个循环来迭代单词向量。

  • 计算当前排列中每个单词的出现次数,并根据此更新'word_freq'映射。同时,将结果值添加到'cnt'变量中。

  • 如果‘cnt’的值大于‘max_digits’,则更新‘max_digits’和‘digit_frequancy’的值。

  • 遍历“digit_freq”映射并将数字转换为字符串。

示例

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

//  function to count the total number of occurrences of a word in a string
int countOccurrences(const string &text, const string &word){
   int count = 0;
   size_t pos = 0;
   while ((pos = text.find(word, pos)) != std::string::npos){
      count++;
      pos += word.length();
   }
   return count;
}
string convertToDigits(string str){
   // defining the words vector
   vector<string> words = {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
   int max_digits = 0;
   map<int int> digit_freq;
   // Traverse the permutations vector
   sort(str.begin(), str.end()); // Sort the string in non-decreasing order
   do{
      string temp = str;
      int cnt = 0;
      map<int int> word_freq;
      // Traverse the words vector
      for (int j = 0; j  max_digits){
         max_digits = cnt;
         digit_freq = word_freq;
      }
   } while (next_permutation(str.begin(), str.end()));
   string res = "";
   // Traverse the digit_freq map
   for (auto it = digit_freq.begin(); it != digit_freq.end(); it++){
      int digit = it->first;
      int freq = it->second;
      // Append the digit to the result string
      for (int i = 0; i <h3>输出</h3>
<pre class="brush:php;toolbar:false;">The string after converting to digits and sorting them in non-decreasing order is 012

时间复杂度 - O(N*N!),因为我们需要找到所有的排列。

happycapy
happycapy

happycapy是一款AI智能体工具,Trickle 团队推出的云端 AI Agent 计算机。

下载

空间复杂度 - O(N),用于存储最终的字符串。

方法二

这种方法是上述方法的优化版本。在这里,我们将从每个单词中取一个唯一的字符,并根据这个字符从给定的字符串中找到确切的单词。

观察

  • 我们在‘zero’中有‘z’个独特的。

  • 我们在‘two’中有‘w’个唯一的。

  • 我们在'four'中有'u'个独特的。

  • 我们在‘六’中有‘x’个独特的。

  • 我们在‘eight’中有‘gg’个独特的。

  • 我们可以从“three”中提取出包含“h”的所有唯一单词,就像我们上面考虑的那样。

  • 我们可以从“one”中取出唯一的“o”,因为我们已经考虑了所有包含“o”的单词。

  • 我们可以从“five”中选择‘f’作为所有包含‘f’的单词,如上所述。

  • 我们在“seven”中有‘v’个独特的。

  • 我们可以从“nine”中取出‘i’作为我们上面考虑过的所有包含‘i’的单词。

算法

  • 定义包含英语单词的'words'向量,并确保按照下面的示例顺序进行,因为我们已经相应地考虑了唯一的单词。同时,定义一个唯一字符的向量及其数字表示

  • 统计每个字符的频率并将其存储在映射中。

  • 遍历唯一字符的数组

  • 如果地图中包含当前唯一的字符,则将其频率值存储在'cnt'变量中。

  • 现在,遍历当前单词。在地图中将单词的每个字符的频率减少'cnt'。

  • 在‘digits’向量中添加一个单词,重复‘cnt’次。

  • 对数字字符串进行排序,并从函数中返回。

示例

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

string convertToDigits(string str){
   // store the words corresponding to digits
   vector<string> words = { "zero", "two", "four", "six", "eight", "three", "one", "five", "seven", "nine" };
   // store the unique characters of the words
   vector<char> unique_chars = {'z',  'w', 'u', 'x', 'g', 'h', 'o', 'f', 'v', 'i'};
   // store the digits corresponding to the words
   vector<int> numeric = {0, 2, 4, 6, 8, 3, 1, 5, 7, 9};
   // to store the answer
   vector<int> digits = {};
   // unordered map to store the frequency of characters
   unordered_map<char int> freq;
   // count the frequency of each character
   for (int i = 0; i <h3>输出</h3>
<pre class="brush:php;toolbar:false;">The string after converting to digits and sorting them in non-decreasing order is 0267

时间复杂度 - O(N),其中N是字符串的长度。

空间复杂度 - O(N),用于存储最终的字符串。

相关文章

PHP速学视频免费教程(入门到精通)
PHP速学视频免费教程(入门到精通)

PHP怎么学习?PHP怎么入门?PHP在哪学?PHP怎么学才快?不用担心,这里为大家提供了PHP速学教程(入门到精通),有需要的小伙伴保存下载就能学习啦!

下载

相关标签:

本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

相关专题

更多
counta和count的区别
counta和count的区别

Count函数用于计算指定范围内数字的个数,而CountA函数用于计算指定范围内非空单元格的个数。本专题为大家提供相关的文章、下载、课程内容,供大家免费下载体验。

2023.11.20

3988

5

sort排序函数用法
sort排序函数用法

sort排序函数的用法:1、对列表进行排序,默认情况下,sort函数按升序排序,因此最终输出的结果是按从小到大的顺序排列的;2、对元组进行排序,默认情况下,sort函数按元素的大小进行排序,因此最终输出的结果是按从小到大的顺序排列的;3、对字典进行排序,由于字典是无序的,因此排序后的结果仍然是原来的字典,使用一个lambda表达式作为key参数的值,用于指定排序的依据。

2023.09.04

1158

7

while的用法
while的用法

while的用法是“while 条件: 代码块”,条件是一个表达式,当条件为真时,执行代码块,然后再次判断条件是否为真,如果为真则继续执行代码块,直到条件为假为止。本专题为大家提供while相关的文章、下载、课程内容,供大家免费下载体验。

2023.09.25

354

5

js 字符串转数组
js 字符串转数组

js字符串转数组的方法:1、使用“split()”方法;2、使用“Array.from()”方法;3、使用for循环遍历;4、使用“Array.split()”方法。本专题为大家提供js字符串转数组的相关的文章、下载、课程内容,供大家免费下载体验。

2023.08.03

1938

5

js截取字符串的方法
js截取字符串的方法

js截取字符串的方法有substring()方法、substr()方法、slice()方法、split()方法和slice()方法。本专题为大家提供字符串相关的文章、下载、课程内容,供大家免费下载体验。

2023.09.04

3224

5

java基础知识汇总
java基础知识汇总

java基础知识有Java的历史和特点、Java的开发环境、Java的基本数据类型、变量和常量、运算符和表达式、控制语句、数组和字符串等等知识点。想要知道更多关于java基础知识的朋友,请阅读本专题下面的的有关文章,欢迎大家来php中文网学习。

2023.10.24

6424

49

字符串介绍
字符串介绍

字符串是一种数据类型,它可以是任何文本,包括字母、数字、符号等。字符串可以由不同的字符组成,例如空格、标点符号、数字等。在编程中,字符串通常用引号括起来,如单引号、双引号或反引号。想了解更多字符串的相关内容,可以阅读本专题下面的文章。

2023.11.24

6629

6

java读取文件转成字符串的方法
java读取文件转成字符串的方法

Java8引入了新的文件I/O API,使用java.nio.file.Files类读取文件内容更加方便。对于较旧版本的Java,可以使用java.io.FileReader和java.io.BufferedReader来读取文件。在这些方法中,你需要将文件路径替换为你的实际文件路径,并且可能需要处理可能的IOException异常。想了解更多java的相关内容,可以阅读本专题下面的文章。

2024.03.22

8154

16

php中定义字符串的方式
php中定义字符串的方式

php中定义字符串的方式:单引号;双引号;heredoc语法等等。想了解更多字符串的相关内容,可以阅读本专题下面的文章。

2024.04.29

12734

11

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
热门推荐
/
最新课程
phpStudy极速入门视频教程
phpStudy极速入门视频教程

共6课时 | 54.7万人学习

独孤九贱(4)_PHP视频教程
独孤九贱(4)_PHP视频教程

共89课时 | 134.3万人学习