藍橋杯-算法訓練-字串統計-Java

2019-11-14 08:50:37

字體：大中小

來源：轉載

供稿：網友

藍橋杯-算法訓練-字串統計-java

問題描述

　　給定一個長度為n的字符串S，還有一個數字L，統計長度大于等于L的出現次數最多的子串（不同的出現可以相交），如果有多個，輸出最長的，如果仍然有多個，輸出第一次出現最早的。

輸入格式

　　第一行一個數字L。　　第二行是字符串S。　　L大于0，且不超過S的長度。　

輸出格式

一行，題目要求的字符串。　　輸入樣例1：　　4 　　bbaabbaaaaa 　　輸出樣例1：　　bbaa 　　輸入樣例2：　　2 　　bbaabbaaaaa 　　輸出樣例2：　　aa

數據規模和約定

n<=60 S中所有字符都是小寫英文字母。

提示

枚舉所有可能的子串，統計出現次數，找出符合條件的那個

思考

道題用HashMap來保存枚舉的字串,key值保存字串-value值保存字串所出現的次數；通過for循環并使用subString()方法枚舉所有符合要求的字串maxStr記錄出現次數最多的字串，maxValue記錄其出現的次數

代碼

package com.test;import java.util.HashMap;import java.util.Map;import java.util.Scanner;public class ALGO_87 { public static void main(String[] args) { Scanner scanner = new Scanner(System.in) ; int l = 0; String s = "" ; if(scanner.hasNext()){ //輸入數字l與字符串s l = scanner.nextInt() ; s = scanner.next() ; } Map<String,Integer> map = new HashMap<String,Integer>() ; //使用map中key保存字符串 value保存字符串出現的次數 int maxValue = 0 ; //保存字符串的出現次數的最大值 String maxStr = "" ; //保存出現次數最多的字符串 for(int i = 0 ; i < s.length() - l + 1 ; i ++){ for(int j = i + l ; j < s.length() ; j ++){ String str = s.substring(i,j) ; //枚舉截取長度大于等于l的字符串 if(map.containsKey(str)){ //若該字符串之前出現過則map(key,value)中value值+1 int value = map.get(str) ; value ++ ; if(value > maxValue){ maxValue = value ; maxStr = str ; }else if(value == maxValue){ //若該字符串出現的次數與當前出現次數最多的字符串相等，則比較兩個字符串的長度，取字符串長的 if(maxStr.length() < str.length()){ maxStr = str ; } } map.put(str, value) ; }else{ //若該字符串之前并未出現過則添加，并初始化value值為0 map.put(str, 0) ; } } } System.out.PRintln(maxStr); //輸出出現次數最多的字符串 }}

上一篇：Qt實現的gbk/utf8無bom文本轉碼小工具

下一篇：對于CRITICAL_SECTION用法的介紹和理解