ニュースクラスタ

24971 ワード
コーディングテスト テキストリンク

しょかい


  • 2つの文字列を小文字(または大文字)に変換

  • 各文字列を2文字に分割した後、アルファベットペアの場合のみMapの要素として挿入します.

  • 2枚の地図を比較して交差サイズ/並列サイズを求め,提花類似度を求めた.
  • 交差のサイズ:2つのマッピングの同じキーの最小値
  • のサイズ:2つのマッピング値の合計-交差のサイズ
    • final int INTEGER = 65536;

public int solution(String str1, String str2) {
    String newStr1 = str1.toLowerCase();
    String newStr2 = str2.toLowerCase();

    Map<String, Integer> subStrMap1 = splitStr(newStr1);
    Map<String, Integer> subStrMap2 = splitStr(newStr2);

    int result = compareMaps(subStrMap1, subStrMap2);

    return result;
}//solution() end

    makeMap()


  • 指定された文字列が2文字の文字ペアであるかどうかを決定し、Mapに挿入する方法

  • Mapに複数の集合が含まれているのは,同じ対の英語文字の個数をvalueとして格納するためである.したがって、Mapのキーは英字ペアであり、valueはその英字ペアの個数である.
    (getOrDefault())
    • public Map<String, Integer> makeMap(String str) {
    int length = str.length();

    Map<String, Integer> subStrMap = new HashMap();

    for (int i = 0; i < length-1; i++) {
        String subStr = str.substring(i, i + 2);
        if((subStr.charAt(0)>='a' && subStr.charAt(0)<='z')
                && (subStr.charAt(1)>='a' && subStr.charAt(1)<='z')) {
            subStrMap.put(subStr, subStrMap.getOrDefault(subStr, 0)+1);
        }
    }
    return subStrMap;
}//splitStr() end

    compareMaps()


  • 与えられた2つのMapを比較することによって,交差する個数を求め,和セットの個数を求めて(Jacar類似度*INTEGER)を返す方法

  • 両方のマップが空の場合は、すぐにINTEGERに戻ります.
    • public int compareMaps(Map<String, Integer> map1, Map<String, Integer> map2) {

    if(map1.isEmpty() && map2.isEmpty()) {
        return INTEGER;
    }
    
    //교집합 갯수
    int interSection = 0;
    //합집합 갯수
    int union = 0;

    //두 맵의 key 비교를 위한 keySet
    Set<String> keySet1 = map1.keySet();
    Set<String> keySet2 = map2.keySet();

    //각 맵의 key iterator
    Iterator<String> iterator1 = keySet1.iterator();
    Iterator<String> iterator2;

    //map1의 key 1개에 map2의 key iterator 1번 탐색
    while(iterator1.hasNext()) {
        String keyStr1 = iterator1.next();

        iterator2 = keySet2.iterator();

        while(iterator2.hasNext()) {
            String keyStr2 = iterator2.next();

            if(keyStr1.equals(keyStr2)) {
            	//두 맵의 key가 같다면 각 맵에서의 value의 최솟값이 교집합의 갯수
                interSection += Math.min(map1.get(keyStr1), map2.get(keyStr2));
                //key로 비교하기 때문에 중복된 key가 없어, 같은 key가 나왔다면 그 뒤는 건너뛴다.
                break;
            }//if end
        }//while end
    }//while end

	
    iterator1 = keySet1.iterator();
    iterator2 = keySet2.iterator();

    //각 맵의 value들의 총합
    while(iterator1.hasNext()) {
        union += map1.get(iterator1.next());
    }
    while(iterator2.hasNext()) {
        union += map2.get(iterator2.next());
    }

    //총 합에서 교집합 크기 빼줘야 합집합 크기
    union -= interSection;

    return (interSection * 65536) / union;
}//compareMaps() end
    ここでは、2つの反復器を用いずにcontains()を使用して、2つのマッピングのキーを比較することができます.
    for (String keyStr : keySet1) {
    if(keySet2.contains(keyStr)) {
        interSection += Math.min(map1.get(keyStr), map2.get(keyStr));
    }//if end
}//for end

    別の解釈


    Mapの代わりにListを使用した回答を見た.
    他のプロセスは同じで、2つの文字列で生成された2つのリストを比較して、交差/集合を求めるプロセスは簡潔で、とてもきれいです.
    交差リストと集合リストを手作りし,各サイズで提花類似度を求める.
    public int compareLists(List<String> list1, List<String> list2) {

    if(list1.size()==0 && list2.size()==0) return INTEGER;

    List<String> interSection = new ArrayList<>();
    List<String> union = new ArrayList<>();

    for (String subStr1 : list1) {

        if(list2.remove(subStr1)) {
            //list2에서 같은 요소가 있어 remove에 성공하면 true
            //그리고 해당 요소를 교집합에 추가한다.
            interSection.add(subStr1);
        }
        //list1의 모든 요소를 합집합에 추가한다.
        union.add(subStr1);
    }

    //교집합 요소가 빠진 list2 요소 전부 합집합에 추가한다.
    union.addAll(list2);

    return (INTEGER * interSection.size()) / union.size();
}
    Baekjun-Z[java]
    第2節