首页 > 试题广场 >

循环单词

[编程题]循环单词
  • 热度指数:10300 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
如果一个单词通过循环右移获得的单词,我们称这些单词都为一种循环单词。 例如:picture 和 turepic 就是属于同一种循环单词。 现在给出n个单词,需要统计这个n个单词中有多少种循环单词。

输入描述:
输入包括n+1行:
第一行为单词个数n(1 ≤ n ≤ 50)
接下来的n行,每行一个单词word[i],长度length(1 ≤ length ≤ 50)。由小写字母构成


输出描述:
输出循环单词的种数
示例1

输入

5
picture
turepic
icturep
word
ordw

输出

2
示例2

输入

4
goran
igor
domagoj
relja

输出

4

说明

并不是必须包含两个或两个以上的不同单词才算一种循环单词!  
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        /**
         * 该解法思想就是,把每个单词所有可能的循环单词都放在一个数据结构中,
         * 可以是List,map,set,数组等等,此处用ArrayList.
         * 然后判断下一个单词是否在表中,不在则加入,并把循环种类加1
         * 在的话,则它与之前的单词是同一种循环单词
         */
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); //第一行为单词个数n(1 ≤ n ≤ 50)
        ArrayList<String> list = new ArrayList<>();
        int count = 0;
        for (int i = 0; i < n; i ++) {
            String s = sc.next(); //输入并存储每行的单词。此处必须调用next()方法,不能是nextLine()方法
            if (!list.contains(s)) {
                count ++;
                list.add(s);

                for (int j = 0; j < s.length() - 1; j ++) {
                    char last = s.charAt(s.length() - 1);
                    s = s.substring(0, s.length() - 1);
                    s = last + s;
                    list.add(s);
                    //以下注释是另一种方法,把可能的循环单词加入list,
                    //思路:把要测试的单词后再重复下这个单词,如:picture ,变成 picturepicture
                    //感谢得闲半生的idea
//                    StringBuffer string = new StringBuffer();
//                    string.append(s);
//                    string.append(s);
//                    String another = string.substring(j, s.length() + j);
//                    list.add(another);
                }
            }
        }
        sc.close();
        System.out.println(count);
    }
}


编辑于 2017-03-12 21:28:31 回复(22)
import collections
a=int(raw_input())
y2=[]
b=[]
for x in range(1,a+1):
    if x<a+1:
        y=raw_input()
        for y1 in y:
            y2.append(y1)
        b.append(y2)
        y2=[]              
for i in range(0,len(b)):
    i_c=collections.deque(b[i])
    for j in range(1,len(b)):
        j_c=collections.deque(b[j])
        while i >= j:
            break
        else:
            for z in range(0,len(b[i])):
                i_c.rotate(z)
                if i_c == j_c:
                     b[j]='@'
                     i_c.rotate(-z)
                else:
                     i_c.rotate(-z)
c=['@']
d=[]
for w in b:
    if w not in c:
        d.append(x)
print len(d)
              

发表于 2017-03-20 20:44:55 回复(0)
import java.util.*;
public class Main {
	public static void main(String args[]) {
		HashSet<String> set = new HashSet<String>();
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		for (int i = 0; i < n; i++) {
			String s = sc.next();
			set.add(calc(s));
		}
		System.out.println(set.size());
	}
	public static String calc(String s) {
		List<String> l = new ArrayList<String>();
		for (int i = 0; i < s.length();/*不是敏感词*/ i++) {
			for (int j = 0; j < s.length(); j++) {
				String tmp = s.substring(j) + s;
				tmp = tmp.substring(0, s.length());
				l.add(tmp);
			}
		}
		Collections.sort(l);
		return l.get(0);
	}
}


编辑于 2017-03-12 19:54:23 回复(3)
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main{

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int count = 0;
        List<String> list = new ArrayList<>();
        for(int i = 0;i < n;i++){
            String string = scanner.next();
            if(list.contains(string) == false){
                count++;
                list.add(string);
                
                for(int j = 0;j < string.length()-1;j++){        //构建循环单词
                    char temp = string.charAt(string.length()-1);
                    string = string.substring(0,string.length()-1);
                    string = temp + string;
                    list.add(string);
                }
            }
            
        }
        System.out.println(count);
    }
}

发表于 2017-12-17 17:00:02 回复(0)
#include <iostream>
#include <string.h>
using namespace std;

string strMove( string str, int n ){
    return str.substr( str.length()-n ) + str.substr( 0, str.length()-n );
}

bool isCircleWord( string str1, string str2 ){
    if( str1.length() == str2.length() ){
        for( int i = 1 ; i < str1.length(); ++i ){
            if( strMove(str1,i) == str2 || str1 == str2 ){
                return true;
            }
        }
    }
    return false;
}

int main()
{
    int n;
    while( cin>>n ){
        if( n == 1 ){
            cout<<1<<endl;
            return 0;
        }

        string a[55];
        for( int i = 0; i < n; ++i ){
            cin>>a[i];
        }

        for( int i = 0; i < n-1; ++i ){
            for( int j = i+1; j < n; ++j ){
                if( isCircleWord(a[i],a[j]) ){
                    a[j] = "!";
                }
            }
        }
        int num = 0;
        for( int i = 0; i < n; ++i ){
            if( a[i][0] != '!' ){
                ++num;
            }
        }
        cout<<num<<endl;
    }
    return 0;
}


发表于 2017-03-13 09:38:25 回复(4)
n = int(raw_input())
word = []
for x in xrange(n):
    word.append(raw_input())
i = n-1
while i >= 0:
    j = len(word) - 1
    while j >= 0:
        if j>=0 and i > j and sorted(word[i]) == sorted(word[j]):
            for x in xrange(len(word[i])):
                if word[i][x:]+word[i][:x] == word[j]:
                    word.remove(word[j])
                    i -= 1 #i从下标最大值开始,移除了一个下标为j的元素,下标前移。
                           #j在后面的语句中下标前移
                    break
        j -= 1
    i -= 1
print len(word)

编辑于 2017-03-19 15:52:31 回复(0)

来个JavaScript版本

var rl = require("readline").createInterface(process.stdin, process.stdout);
var args = [];

rl.on('line', function(data){
    args.push(data);
    if(args.length >= parseInt(args[0] + 1)){
        rl.close();
    }
});

rl.on('close', function(){
    var arr = args.slice(1);
    var res = 0;
    for(var i = 0 ; i < arr.length; i ++){
        for(var j = i + 1; j < arr.length; j ++){
            if(judge(arr[i], arr[j])){
                // 如果两个是循环单词,就把arr[j]移除数组
                arr.splice(j, 1);
                j--;
            }
        }
    }
    res = arr.length;
    console.log(res);
});
// 判断是否互为循环单词
function judge(str1, str2){
    if(str1.split('').sort().join('') == str2.split('').sort().join('')){
        var temp1, temp2;
        for(var i = 0 ; i < str1.length; i ++){
            temp1 = str1.slice(0, i);
            temp2 = str1.slice(i);
            if(str2 == temp2 + temp1){
                return true;
            }
        }
    }
    return false;
}
发表于 2017-03-09 16:56:02 回复(1)
#include<iostream>
#include<map>
#include<string>
using namespace std;
intn;
map<string, int> mp;
intmain() {
    while(scanf("%d", &n) != EOF) {
        string s, tem;
        intans = 0,key=0;
        for(inti = 0; i < n; i++) {
            cin >> s;
            if(mp[s] == 0)
                ans++;
            key = 0;
            for(intj = 0; j < s.length(); j++) {
                tem = s.substr(j, s.length() - j)+ s.substr(0, j);
                mp[tem] = 1;
            }
        }
        cout << ans << endl;
    }
    return0;
}

发表于 2017-03-08 14:59:20 回复(6)
思路:把要测试的单词后再重复下这个单词,如:picture ,变成 picturepicture
然后判断其他要测试的单词是不是这个串的子串(长度要先相等)
#include <string>
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n,num=0;
vector<string> twords;
vector<bool> checks;//判断是否已属于某种循环单词
cin>>n;
for (int i = 0; i < n; i++)
{
string t_w;
cin >> t_w;
twords.push_back(t_w);
checks.push_back(false);
}
for (int j = 0; j < n; j++)
{
if (!checks[j]){
string tt;
tt = twords[j] + twords[j];
for (int k = j + 1; k < n; k++)
{
if (!checks[k]){
if (tt.find(twords[k]) != string::npos&&twords[k].length() == twords[j].length()){ checks[k] = true; }
}
}
num++;
}
}
cout << num << endl;

return 0;
}
编辑于 2017-03-08 14:22:03 回复(11)
#include <bits/stdc++.h>
using namespace std;

int n;

string confirm(string s) {
    vector<string> vStr;
    for (int i = 0; i < (int)s.length(); i++) {
        string temp = s;
        for (int j = 0; j < (int)s.length(); j++) temp[j] = s[(i + j) % s.length()];
        vStr.emplace_back(temp);
    }
    sort(vStr.begin(), vStr.end());
    return vStr[0];
}

int main() {
    set<string> sStr;
    cin >> n;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        sStr.emplace(confirm(s));
    }
    cout << sStr.size() << endl;
    return 0;
}
想问问各位,第10行的操作 temp[j] = s[(i + j) % s.length()]; 做了一件什么事
或者能否解释一下  这个解法的思想?
发表于 2022-06-11 20:56:09 回复(0)
public class Main2 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n =scanner.nextInt();
        String[] data = new String[n];
        for(int i=0;i<n;i++){
            data[i] = scanner.next();
        }
        
        
        List<String> list = new ArrayList<String>();
        list.add(data[0]+data[0]);
        for(int i=1;i<n;i++){
            boolean flag = false;        //list中的字符串是否包含data[i]
            for(int j=0;j<list.size();j++){
                if(list.get(j).length()/2==data[i].length()&&list.get(j).contains(data[i])){
                    flag = true;
                }
            }
            if(!flag)
                list.add(data[i]+data[i]);
        }
        System.out.println(list.size());
        scanner.close();
    }
}
编辑于 2018-05-18 14:28:45 回复(0)
import java.util.*;
public class Main {
    /*
    善用Set会比较简单。
    思路就是如果通过右移char,会与set中的其他元素重复,remove之,最终的set集合大小就是所求的结果
     */
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int n = Integer.parseInt(in.nextLine());
            // 同时使用数组和set来存储输入的字符串
            String[] strings = new String[n];
            HashSet<String> resultSet = new HashSet<>();
            for (int i = 0; i < n; i++) {
                strings[i] = in.nextLine();
                resultSet.add(strings[i]);
            }
            for (int i = 0; i < n; i++) {
                // 用StringBuilder来处理字符串
                StringBuilder sb = new StringBuilder(strings[i]);
                for (int j = 0; j < sb.length(); j++) { // 遍历移动char的方式
                    // 如果set中的该元素还没有被移除,则进入处理,否则直接跳过
                    if (resultSet.contains(strings[i])) {
                        sb.append(sb.charAt(0));
                        sb.deleteCharAt(0);
                        // 删去set中同一种循环单词,同时防止把自己删了=.=
                        if (resultSet.contains(sb.toString()) && !sb.toString().equals(strings[i])) {
                            resultSet.remove(sb.toString());
                        }
                    }
                }
            }
            System.out.println(resultSet.size());
        }
    }
}

发表于 2018-03-03 17:46:27 回复(0)
import java.util.HashSet;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n =sc.nextInt();
        String[] arr = new String[n];
        
        HashSet<String> set = new HashSet<String>();  //创建一个存放单词类型的集合(单词的叠加形式)
        
        int count = 0;
        String str = "";
        for(int i=0;i<n;i++) {
            arr[i]=sc.next();
            boolean boo = true;
            for(String a:set) {
                if(a.contains(arr[i])&& a.length()==arr[i].length()*2) {
                    boo = false;      //集合中已经有了这类单词
                    break;
                }
            }
            if(boo) {        //boo为true说明没有这类单词,将单词叠加存入集合。
            count++;
            str = arr[i]+arr[i];       //单词叠加  例如picturepicture
            set.add(str);
            }
        }
        System.out.println(count);
    }
}

发表于 2018-01-31 16:40:38 回复(0)
import java.util.*;

public class Main{
    public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		ArrayList<String> list = new ArrayList<>();
		for (int i = 0; i < n; i++) {
			list.add(sc.next());
		}
		
		System.out.println(getCycWordNum(list));
	}
	
	/*
	 *1、将列表第一个单词叠加,并在后续列表中遍历是否是当前单词的循环单词
	 */
	public static int getCycWordNum(ArrayList<String> list){
		if(list.size() == 0)
			return 0;
		
		boolean flag = false;
		int count = 0;
		while(!list.isEmpty()){
			String word = list.get(0);
			word = word+word;
			for (int i = 0; i < list.size(); i++) {
				if(word.contains(list.get(i))&&list.get(i).length() == word.length()/2){
					flag = true;
					list.remove(i);
					i--;//remove只有数组数量减少,i为之前的i+1个元素
				}
			}
			if(flag){
				count++;
				flag = false;
			}
		}
		return count;
	}
}

发表于 2017-09-02 12:29:10 回复(0)
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main(){
    vector<string> s;
    int n;
    while(cin>>n){
        string tmp;
        for(int i=0;i<n;i++){
            cin>>tmp;
            s.push_back(tmp);
        }
        vector<string> v;
        for(int i=0;i<s.size();i++){
            int flag=0;
            for(int j=0;j<v.size();j++){
                if(v[j].size()==s[i].size()*2&&v[j].find(s[i])!=string::npos){
                    flag=1;
                    break;
                }
            }
            if(flag==0){
                string t=s[i]+s[i];
                v.push_back(t);
            }
        }
        cout<<v.size()<<endl;
    }
    return 0;
}

发表于 2017-08-24 11:46:29 回复(0)
#include<iostream>
#include<set>
using namespace std;
intmain(){
    intn;
    cin>>n;
    set<string> str_set;
    while(n--){
        string s;
        cin>>s;
        str_set.insert(s);
    }
    for(auto it1=str_set.begin(); it1!=str_set.end(); ++it1){
        string s=*it1+*it1;
        auto it2=it1;
        ++it2;
        while(it2!=str_set.end())
            if(s.find(*it2)!=string::npos&&it2->size()==s.size()/2)
                it2=str_set.erase(it2);
            else
                ++it2;
    }
    cout<<str_set.size();
    return0;
}

发表于 2017-07-30 23:39:02 回复(0)
package 全国统一模拟笔试第一场;

import java.util.ArrayList;
import java.util.Scanner;

public class Main_1 {

	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		while(sc.hasNext())
		{
			int left=sc.nextInt();
			int right=sc.nextInt();
			int n=sc.nextInt();
			int []fishes=new int[n];
			for(int i=0;i<n;i++)
				fishes[i]=sc.nextInt();
			fishes(left, right, fishes);
		}
		sc.close();
	}
	public static void fishes(int left ,int right,int []fishes)
	{	
		ArrayList<Integer> list=new ArrayList<Integer>();		
		boolean flag;
		for(int i=left;i<=right;i++)
		{
			flag=true;
			for(int j=0;j<fishes.length&&flag;j++)
			{
				if((2*i<=fishes[j]&&fishes[j]<=10*i)||(2*fishes[j]<=i&&i<=10*fishes[j]))
				{
					flag=false;					
				}					
			}					
			if(flag)
			{
				list.add(i);
			}
		}
		System.out.println(list.size());
	}
}


发表于 2017-07-19 10:42:42 回复(0)
# encoding=utf8
def f(n, word):
    if n == 1:
        return 1
    _word = []
    ret = 0
    while 1:
        w1 = word.pop()
        l1 = len(w1)
        w1 += w1   # sta=>stasta
        for w2 in word:
            if len(w2) == l1: # 如果两个字符串长度相等
                if w2 in w1:  # 如果w1包含w2
                    pass
                else:
                    _word.append(w2) # 如果w2不是w1的循环单词,重新将w2加入数组
            else:
                _word.append(w2)# 如果w2与w1长度不相等,重新将w2加入数组
        ret += 1
        if len(_word) != 0:
            word = _word[:]
            _word = []
        else:
            break
    if ret == 0:
        ret = n
    return ret
if __name__ == '__main__':
    while 1:
        try:
            n = int(raw_input())
            word = []
            for i in range(n):
                word.append(raw_input())
        except:
            break
        print f(n, word)

发表于 2017-07-10 17:37:32 回复(0)
public class MainTest {
public static void main(String[] args) {
int N=50;
       Scanner sc = new Scanner(System.in);
       N = sc.nextInt(); //第一行为单词个数N
       ArrayList<String> list = new ArrayList<>();
       int count = 0;
       for (int i = 0; i < N; i ++) {
           String s = sc.next(); //输入并存储每行的单词。此处必须调用next()方法
           if (!list.contains(s)) {
               count ++;
               list.add(s);
               for (int j = 0; j < s.length() - 1; j ++) {
                   //以下注释是另一种方法,把可能的循环单词加入list,
                   //思路:把要测试的单词后再重复下这个单词,如:picture ,变成 picturepicture
                   String str= new String();
                   str=s.concat(s);
                   String b= str.substring(j, s.length() + j);
                   list.add(b);
               }
           }
       }
       System.out.println(count);
   }
}

编辑于 2017-06-05 21:24:32 回复(0)
思路:把所有字符串存入到链表中,然后取第一个字符串依次循环右移一位后和链表的其他串相比较,如果重复,就把重复的字符串从链表中去掉,最后链表的长度,就是所求的种数

import java.util.LinkedList;
import java.util.Scanner;

public class Main {

public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
LinkedList<String> list=new LinkedList<String>();
for(int i=0;i<n;i++){
list.add(sc.next());
}
int num=Resolve(list);
System.out.println(num);
}
public static int Resolve(LinkedList<String> list){
int length=list.size();
for(int i=0;i<length;i++){
 String word=list.get(i);
 for(int j=0;j<word.length();j++){
 for(int k=i+1;k<length;k++){
 String str1=Cycle(word,j);
 String str2=list.get(k);
 if( str1.equals(str2)){
 list.remove(k);
 length--;
 }
 }
 
 }
}
for(int m=0;m<list.size();m++){
System.out.println(list.get(m));
}
return list.size();
}
public static String Cycle(String word, int j) {
// TODO Auto-generated method stub
String str1=word.substring(0,word.length()-j);
String str2=word.substring(word.length()-j);
return str2+str1;
}

}

发表于 2017-05-04 20:54:54 回复(0)

热门推荐

通过挑战的用户