精华内容
下载资源
问答
  • 题目: 给出一个长度不超过200,而且全部小写英文字母组成的字符串(该字符串必须每行20个字母的方式输入)。要求将此字符串分成k份(1<k<=40),输出最大的包含单词个数。...3.单词由...

    题目:
    给出一个长度不超过200,而且全部小写英文字母组成的字符串(该字符串必须每行20个字母的方式输入)。要求将此字符串分成k份(1<k<=40),输出最大的包含单词个数。限制条件如下:
    1.每份中包含的单词可以部分重叠。
    2.当选用一个单词后,其第一个字母不能再用。例如字母串this中可包含this和is,选用this之后就不能包含th,因为t开头的单词已经包含在内了。
    3.单词由一个不超过6个单词的字典给出。
    输入第一行为一个正整数n(0<n<=5),表示测试数据组数。每组的第一行有两个正整数p、k。p表示子串的行数,k表示分成k个部分。再接下来有一行有一个正整数s,表示词典中单词个数(1<s<=6)。接下来的s行为词典内容,每行均有一个单词。输出n行,每行一个整数,分别对应每组测试数据的相应结果。

    思路:

    说明题中“给出一个长度不超过200,...(该字符串必须每行20个字母的方式输入)”听起来有些莫名其妙,因此不考虑这个,直接输入一行待匹配的字符串。然后关于测试数据,我也默认只有一组测试数据,如果需要按照题目输入几组测试数据的话,写一个while循环一组一组的测试即可。)

    学习了一阵子动态规划,条件反射先定义一个二维数组dp[][],本题dp[i][j]的含义为将输入字符串的前 i+1个字符组成的子字符串划分为 j 份后最大包含单词的个数。动态转移方程为:dp[i][j] = dp[m][j-1] + ([m+1,i] 区间中包含的单词个数)。

    [m+1,i] 区间中包含的单词个数可以这样求:先将该部分字符串提取出来赋给substr变量,再将substr传入match_and_count函数,进行统计。而match_and_count函数的思路可以参考我的上一篇博客:c++ 求字符串中最大的包含单词个数

    另外将区间[0,i]的子字符串分为1份(不划分)时的dp[i][0]是可以提前用match_and_count函数求得的。

    如果理解不了动态转移方程:dp[i][j] = dp[m][j-1] + ([m+1,i] 区间中包含的单词个数) ,可以看一下我的这一篇博客:程序基本算法习题解析 动态规划-乘积最大:设有一个长度为N的数字串,要求选手使用K个乘号将它分成K+1个部分,找出一种分法,使得这K+1个部分的乘积最大。

    最后就是需要注意遍历时各层循环变量的取值范围。

    代码如下:

    // Chapter14_6.cpp : Defines the entry point for the application.
    // 统计单词个数
    // 给出一个长度不超过200,而且全部小写英文字母组成的字符串(该字符串必须每行20个字母的方式输入)。
    // 要求将此字符串分成k份(1<k<=40),输出最大的包含单词个数。限制条件如下:
    // 1.每份中包含的单词可以部分重叠。
    // 2.当选用一个单词后,其第一个字母不能再用。例如字母串this中可包含this和is,选用this之后就不能
    // 包含th,因为t开头的单词已经包含在内了。
    // 3.单词由一个不超过6个单词的字典给出。
    // 输入第一行为一个正整数n(0<n<=5),表示测试数据组数。
    // 每组的第一行有两个正整数p、k。p表示子串的行数,k表示分成k个部分。
    // 再接下来有一行有一个正整数s,表示词典中单词个数(1<s<=6)。
    // 接下来的s行为词典内容,每行均有一个单词。
    // 输出n行,每行一个整数,分别对应每组测试数据的相应结果。
    
    #include "stdafx.h"
    #include<iostream>
    #include<string>
    using namespace std;
    
    const int max_dic = 6; //定义字典中所能存放的单词个数
    const int maxN = 200; //字符串最大的长度
    const int maxK = 40; //划分的最大份数
    string str; //原字符串(输入的需要匹配的字符串)
    int p; //字典中单词的个数
    int k; //要划分的份数
    int maxlength; //字典中最长单词的长度
    string dic[max_dic]; //字典
    
    //声明函数
    int max_length(string *str,int n); //求字典中最长单词的长度函数
    int match_and_count(string &substr); //求字典中最长单词的长度函数
    
    int main()
    {
    	//dp[i][j]表示将输字符串的前i+1个字符组成的子字符串划分为j份后最大包含单词的个数
    	int dp[maxN+1][maxK+1]; 
    	memset(dp,0,sizeof(dp));
    	int i,j; //循环变量
    	int count = 0; //计数变量
    	//输入
    	cout << "输入需要匹配的字符串:" << endl;
    	cin >> str;
    	cout << "输入需要划分的份数:";
    	cin >> k;
    	cout << "输入字典中的单词个数:";
    	cin >> p;
    	cout << "输入字典中的单词:" << endl;
    	for(i=0;i<p;i++)
    		cin >> dic[i];
    	//输入的字符串的长度
    	int stringLength = str.length();
    	//求字典中最长单词的长度
    	maxlength = max_length(dic,p);
    	//将区间[0,i]的子字符串分为1份(不划分)时的dp[i][0]
    	//求子字符串
    	string substr = ""; //substr为区间[m,i]之间的子字符串
    	for(i=0;i<stringLength;i++)
    	{
    		substr = substr + str[i]; 
    		dp[i][1] = match_and_count(substr);
    	}
    	//动态规划思想求dp[i][j]
    	//i的取值范围是[0,stringLength)
    	for(i=0;i<stringLength;i++)
    	{
    		//j的取值范围是[1,k],但是j=1时的dp[i][j]值之前单独求过了,因此这里j从2开始
    		for(j=2;j<=k;j++)
    		{
    			//要保证字符串长度大于划分的份数
    			if(i>=j)
    			{
    				count = 0; //对于每个dp[i][j],count需要初始化为0
    				for(int m=0;m<i;m++)
    				{
    					//求子字符串
    					substr = ""; //substr为区间[m+1,i]之间的子字符串
    					for(int l=m+1;l<=i;l++)
    						substr = substr + str[l]; 
    					//求substr中最大包含的单词数
    					count = match_and_count(substr);
    					//动态转移方程
    					dp[i][j] = dp[m][j-1] + count;
    				}
    			}
    		}
    	}
    	cout << "最大的包含单词个数为:" << dp[stringLength-1][k] << endl;
    	system("pause");
    	return 0;
    }
    
    //求字典中最长单词的长度函数
    int max_length(string *str,int n)
    {
    	int max = str[0].length();
    	for(int i=1;i<n;i++)
    	{
    		if(str[i].length() > max)
    			max = str[i].length();
    	}
    	return max;
    }
    
    //匹配和计数函数
    int match_and_count(string &substr)
    {
    	int subcount = 0; //函数中的计数变量
    	int i;
    	//left:切片的起始位置,right:切片的终止位置
    	int left = 0,right = 0;
    	//切片的起始位置移动到原字符串的末尾为止
    	while(left < substr.length())
    	{
    		//left加1和right加1的标志变量,flag=0表示未找到匹配,right加1;flag=1表示找到匹配,left加1
    		int flag = 0; 
    		//遍历不同长度的子字符串
    		for(right=left;right<= left+maxlength;right++)
    		{
    			//求子字符串
    			string temp = "";
    			for(i=left;i<=right;i++)
    				temp = temp + substr[i]; 
    			//与字典中的单词进行比对
    			for(i=0;i<p;i++)
    			{
    				//若匹配到一个单词
    				if(temp == dic[i])
    				{
    					subcount++; //计数变量加1
    					flag = 1; //flag置1(目的是退出外for循环)
    					break;
    				}
    			}
    			if(flag == 1)
    				break;
    		}
    		//从下个字符开始进行匹配
    		left++;
    	}
    	return subcount;
    }
    

    运行结果如下:

    展开全文
  • python在单词表中查找包含所有元音字母aeiou的单词并打印 python单词表中查找所有的元音字母aeiou: 方法一: def claen(word): return word.strip().lower() def lookUpWord(word): newword = "" f...

    python在单词表中查找包含所有元音字母aeiou的单词并打印

    python单词表中查找所有的元音字母aeiou:
    方法一:

     def claen(word):
                return word.strip().lower()
             
     def lookUpWord(word):
           newword = ""
           for char in word:
               if char in 'aeiou':
                   newword += char
               return newword
               
    if __name__ == '__main__':
        try:
           with open(r'dictionary.txt') as f:
               for word in f:
                   word = claen(word)
                   wordstr = lookUpWord(word)
                   if wordstr == 'aeiou':
                      print(word)
         finally:
            f.close()
    

    方法二:

    def claen(word):
                return word.strip().lower()
            
     def lookupword(word):
         vowelsInWord = ""
         for char in word:
             if char in 'aeiou':
                vowelsInWord +=char
             return vowelsInWord
                
    if __name__ == '__main__':        
    	 try:
             with open(r'dictionary.txt') as f:
                  for word in f:
                      word = claen(word)
                      if len(word) < 5:
                          continue
                      vowelStr = lookupword(word)
                      if vowelStr == 'aeiou':
                         print(word)
        finally:
           f.close()
    

    程序运行截图:
    在这里插入图片描述

    展开全文
  • 第一个单词前,最后一个单词后也可能有0到多个空格。 比如:" abc xyz" 包含两个单词,"ab c xyz " 包含3个单词。 如下的程序解决了这个问题,请填写划线部分缺失的代码。 注意:只填写划线...

    2015届蓝桥杯B组1:

    输入一个字符串,求它包含多少个单词。单词间以一个或者多个空格分开。
    第一个单词前,最后一个单词后也可能有0到多个空格。
    比如:" abc    xyz" 包含两个单词,"ab   c   xyz    "  包含3个单词。

    如下的程序解决了这个问题,请填写划线部分缺失的代码。

    注意:只填写划线部分的代码,不要填写任何多余的内容。比如已经存在的小括号,注释或说明文字等。


    int get_word_num(char* buf)
    {
        int n = 0;   
        int tag = 1;
        char* p = buf;
        
        for(;*p!=0 && *p!=13 && *p!=10;p++){
            if(*p==' ' && tag==0) tag=1;
            if( *p!=' ' && tag==1 ) { n++; tag=0; }   //填空
        }
        
        return n;
    }

    int main()
    {
        char buf[1000];
        fgets(buf,1000,stdin);
        
        printf("%d\n", get_word_num(buf));
        return 0;
    }

    当前一位是空格,但后一位不是空格时就代表一个单词出现,n++。

     

     

    展开全文
  • 输入一个字符串,帮忙统计字符串里面的每个单词出现的次数,以及非法单词的次数。非法单词的定义为:包含数字(0-9)的单词 输入一个字符串,长度小于1000,输入的字符仅包含(0-9,a-z,A-Z, . , : ! )及空格。 ...

    深信服2018秋招笔试题:

    输入一个字符串,帮忙统计字符串里面的每个单词出现的次数,以及非法单词的次数。非法单词的定义为:包含数字(0-9)的单词

    输入一个字符串,长度小于1000,输入的字符仅包含(0-9,a-z,A-Z, . , : ! )及空格。

    输出按单词的字母进行排序,每行为 :

    单词    单词出现次数

    最后一行输出非法单词个数


    实例1:

    输入:

    wow! Is wonderful!

    输出:

    Is 1

    wonderful 1

    wow 1

    0


    实例2:

    输入:

    abc bcd2 fe fe a3xd

    输出:

    abc 1

    fe 2

    2


    代码如下:

    #include<iostream>
    #include<map>
    #include<string>
    #include<vector>
    
    using namespace std;
    int main()
    {
    	string str;
    	map<string, int>temp;
    	getline(cin, str);
    	int plow = 0, phigh = 0;
    	string s = "";
    	while (phigh < str.length())
    	{
    		if (str[phigh] == ' ')
    		{
    			phigh++;
    			plow = phigh;
    			temp[s]++;
    			s = "";
    			continue;
    
    		}
    		else
    		{
    			s = s + str[phigh];
    			if (phigh == str.length() - 1) temp[s]++;
    			phigh++;
    		}
    
    	}
    	vector<string>res;
    	auto j = temp.begin();
    	while(j != temp.end())
    	{
    		string tmp = j->first;
    		int len = tmp.size();
    		for (int i = 0; i < len; i++)
    		{
    			if (!(tmp[i] >= 65 && tmp[i] <= 90 || tmp[i] >= 97 && tmp[i] <= 122))
    			{
    				if (tmp[i] >= 48 && tmp[i] <= 57)
    				{
    					res.push_back(tmp);
    					j = temp.erase(j);
    					j--;
    					break;
    				}
    
    			}
    			else if (tmp[len-1] == 44 || tmp[len-1] == 46 || tmp[len-1] == 58 || tmp[len-1] == 33) {
    				string new_tmp(tmp.begin(), tmp.end() - 1);
    				int b = j->second;
    				temp.insert(make_pair(new_tmp, b));
    				j = temp.erase(j);
    				j--;
    				break;
    			}
    		}
    		j++;
    	}
    	for (auto s = temp.begin(); s != temp.end(); s++)
    	{
    		cout << s->first << " " << s->second << endl;
    	}
    	cout << res.size() << endl;
    
    	system("pause");
        return 0;
    }
    

    主要是对问题的仔细分析!然后就是注意细节,特别是迭代器的失效问题,位置变换等问题!

    展开全文
  • 单词拆分 给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。 说明: 拆分时可以重复使用字典中的单词。 你可以假设字典中没有重复的单词。...
  • 首先,使用Ctrl+H,然后勾选正则表达式(Regular expression),在find what里输入:^.*prompt.*$,中间prompt可以是要替换的单词或字符。
  • HDU2082_找单词【多重背包】

    千次阅读 2014-10-20 10:43:19
    题目大意:每个单词都有一个值,从A、B…到Z的值分别为1、2…到26 现在给你26个字母每个字母的个数,问:能找到多少个字母总价值 的单词数。(单词排列顺序无关,ACM和CMA和AMC都视为同一个单词) 思路:很多人都是用...
  • 单词接龙

    千次阅读 2014-07-10 20:50:03
    单词接龙:是指一组单词序列,任何两个相邻的单词满足前一个单词的尾字母和后一个单词的首字母相同。  接龙长度:接龙中所有单词长度之和。  如单词:tea, cat, dog, aid, fish 可以形成单词接龙:...
  • 给定一个句子(只包含字母和空格), 将句子中的单词位置反转,单词用空格分割, 单词之间只有一个空格,前后没有空格。
  • 参考内容: ... 2. 严蔚敏 -数据结构 ... 树中的每个节点一般不是直接包含关键字,而是包含组成关键字的符号(当然叶子节点除外,叶子节点可能包含整个单词以及词频,非叶节点也可包含单词和词频)。根据存
  • 这个弄了很久,其实特简单,但思路很容易被绕,分析过程不...的所有单词。 var reg = /\b[\w]*is[\w]*\b/g; var result = "This is a dictionary.".match(reg); for(var i=0; i&lt;result.length;i...
  • linux查找当前目录下包含某一单词的所有文件并进行替换
  • 数组查找操作:定义一个长度为10 的一维字符串数组,在每一个元素存放一个单词;然后运行时从命令行输入一个单词,程序判断数组是否包含有这个单词,包含这个单词就打印出“Yes”,不包含就打印出“No”。 import ...
  • 内大2018专硕:输入一个长度不大于100的字符串(由空格和组成),输出串中包含的单词个数,如果不存在单词则输出0。 package neida; import java.io.*; import java.io.BufferedReader; import java.io....
  • //**********************************...//输入一行文本,其中包含多个单词,找出最长的单词长度 //**************************************************** #include #include #include #include void main() { c
  • 单词替换

    千次阅读 2019-01-31 13:51:58
    【小韦同学@题解-字符串】 题目: 描述 输入一个字符串,以回车结束...该字符串由若干个单词组成,单词之间用一个空格隔开,所有单词区分大小写。现需要将其中的某个单词替换成另一个单词,并输出替换之后的字符串。
  • python之字符串练习2:将句子中的单词位置反转 1)题目描述 > 给定一个句子(只包含字母和空格), 将句子中的单词位置反转,单词用 空格分割, 单词之间只有一个空格,前后没有空格。 比如: (1) “hello xiao ...
  • 1.给定一个仅包含大小写字母和空格 ’ ’ 的字符串 s,返回其最后一个单词的长度。 如果字符串从左向右滚动显示,那么最后一个单词就是最后出现的单词。 如果不存在最后一个单词,请返回 0 。 说明:一个单词是指仅...
  • 这个是为了匹配某单词,无后缀。 然后用(?:)的循环语句廓上,循环0次,就搞定了 (?:(?!单词).)* eg: /(http:\/\/[^'"(),\\s\r\n!\x80-\xff](?:(?!http:|https:).)+)/i 转载于:...
  • 给定一个仅包含大小写字母和空格 ’ ’ 的字符串,返回其最后一个单词的长度。 如果不存在最后一个单词,请返回 0 。 说明:一个单词是指由字母组成,但不包含任何空格的字符串。 class Solution { public: ...
  • #include &lt;stdio.h&gt; #include &lt;string.h&gt; #include &lt;stdlib.h&gt; #include &lt;ctype.h&gt; int main(){ int value = 0; int maxvalue = 0;... g...
  • 单词全排列

    千次阅读 2014-04-09 14:34:47
    如何对一个包含n个字母的单词进行全排列? 1,对右边
  • 统计单词

    千次阅读 2018-02-08 12:15:39
    编一个程序,读入用户输入的,以“.”结尾的一行文字,统计一共有多少个单词,并分别输出每个单词含有多少个字符。 (凡是以一个或多个空格隔开的部分就为一个单词) 输入描述: 输入包括1行字符串,以“.”结束,...
  • 单词拆分

    千次阅读 2019-05-25 13:20:47
    给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。 说明: 拆分时可以重复使用字典中的单词。 你可以假设字典中没有重复的单词。 示例 1: ...
  • printf("最长的单词的长度为:%d\n",count); } 方法3 #include #define N 81 void main() { char string[N]; int i,m=0,word=1,t=0,n; char c; gets(string); for(i=0;(c=string[i])!='\0';++i) { ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 408,984
精华内容 163,593
关键字:

包单词