【算法】算法測(cè)試題1：循環(huán)單詞

dingding199389 發(fā)布于2019-08-23 11:35 / 557人閱讀

摘要：題目描述循環(huán)單詞一個(gè)單詞循環(huán)右移得到另一個(gè)單詞。輸出循環(huán)單詞種數(shù)。注意如果單詞沒(méi)有和任何單詞構(gòu)成循環(huán)單詞，那么也為一種循環(huán)單詞，。

題目描述

循環(huán)單詞：一個(gè)單詞循環(huán)右移得到另一個(gè)單詞。
例如：picture和turepic屬于一種循環(huán)單詞。
給出n個(gè)單詞，統(tǒng)計(jì)有多少種循環(huán)單詞。

輸入

輸入n+1行
第一行為單詞個(gè)數(shù)n（n:[1,50]）
接下來(lái)n行，每一行一個(gè)單詞，小寫(xiě)構(gòu)成。

輸出

循環(huán)單詞種數(shù)。

思路

從第一個(gè)單詞開(kāi)始，遍歷每個(gè)單詞。
每個(gè)沒(méi)有被統(tǒng)計(jì)過(guò)的單詞i都和后面所有沒(méi)有統(tǒng)計(jì)過(guò)的單詞j比較，是否構(gòu)成循環(huán)單詞。
如果構(gòu)成循環(huán)單詞且該循環(huán)單詞沒(méi)有被統(tǒng)計(jì)過(guò)，統(tǒng)計(jì)數(shù)cont+1并且標(biāo)記j為統(tǒng)計(jì)過(guò)use[j]=true;
如果構(gòu)成循環(huán)單詞但是沒(méi)被統(tǒng)計(jì)過(guò)，則標(biāo)記j為統(tǒng)計(jì)過(guò)use[j]=true,不再統(tǒng)計(jì);
如果不夠循環(huán)單詞，則不統(tǒng)計(jì)也不標(biāo)記，不做任何操作。
注意：如果單詞i沒(méi)有和任何單詞構(gòu)成循環(huán)單詞，那么也為一種循環(huán)單詞，count+1。

tips:字符串循環(huán)右移使用substring方法

use[i]記錄第i個(gè)單詞是否被統(tǒng)計(jì)過(guò)
count用來(lái)統(tǒng)計(jì)循環(huán)單詞個(gè)數(shù)
flag表示目前正在訪問(wèn)的這個(gè)循環(huán)單詞是否被統(tǒng)計(jì)過(guò)，如果被統(tǒng)計(jì)過(guò)就不再統(tǒng)計(jì)

javascript解法

while(line=readline()){
    let n = parseInt(line);
    let strArr = new Array();
    let use = [];
    for(let i = 0; i < n; i++){
        strArr[i] = new Array(readline());
        use[i] = false;
    }
    let count = 0;
    let flag = false;
    for(let i = 0; i < n; i++){
        if(!use[i]){    //單詞i沒(méi)有被統(tǒng)計(jì)過(guò)
            use[i] = true;    //標(biāo)記單詞i被統(tǒng)計(jì)過(guò)
            flag = false;     //目前該種循環(huán)單詞沒(méi)有被統(tǒng)計(jì)過(guò)
            for(let j = i+1; j < n; j++){    //和i單詞后面的每個(gè)沒(méi)有被統(tǒng)計(jì)過(guò)的 單詞比較
                if(!use[j]){//只和沒(méi)有被統(tǒng)計(jì)過(guò)的單詞j比較
                    if(same(strArr[i],strArr[j])){//比較i和j是否為循環(huán)單詞
                        if(!flag){//如果這種循環(huán)單詞沒(méi)有統(tǒng)計(jì)，則統(tǒng)計(jì)+1
                            count++;
                            flag = true;
                        }
                        use[j] = true;
                    }
                }
            }
            if(!flag){//單詞i這種循環(huán)單詞沒(méi)有被統(tǒng)計(jì)過(guò)，不和任何單詞構(gòu)成循環(huán)單詞
                count++;
            }
        }
    } 
    print(count);
}
//判斷兩個(gè)單詞是否為循環(huán)單詞
function same(stra, strb){
    //轉(zhuǎn)成字符串類(lèi)型，否則為對(duì)象object類(lèi)型，length=1
    let str1 = new String(stra);
    let str2 = new String(strb);
    if(str1.length != str2.length){//長(zhǎng)度不一樣必然不能構(gòu)成循環(huán)單詞
        return false;
    }
    for(let i = 0; i < str1.length; i++){
        //循環(huán)右移，每次右移一位，比較兩個(gè)單詞是否相等
        //字符串循環(huán)右移使用substring方法
        let str = str1.substring(i)+ str1.substring(0,i);
        if(str == str2){
            return true;
        }
    }
    return false;
}