網頁

2018/12/8

LeetCode Jewels and Stones 珠寶與石頭

雖然常在網路上(PTT SOFT_JOB)常聽到要刷LeetCode,但直到今天才來玩看看,下面是我隨便挑的一個演算法(algorithm)的簡單題目,Jewels and Stones 珠寶與石頭

題目如下:

You're given strings J representing the types of stones that are jewels, and S representing the stones you have. Each character in S is a type of stone you have. You want to know how many of the stones you have are also jewels.

The letters in J are guaranteed distinct, and all characters in J and S are letters. Letters are case sensitive, so "a" is considered a different type of stone from "A".

給兩個輸入參數字串分別為JSJ代表珠寶種類,S代表石頭。石頭中的每一個字母(character)代表你擁有的石頭,你想要知道你的石頭中有幾顆是珠寶。

J中的字母是保證唯一的。JS中皆為字母,大小寫敏感,也就是小寫"a"與大寫"A"是不同的,字數皆小餘50個字。

例如

Example 1:

Input: J = "aA", S = "aAAbbbb"
Output: 3

Example 2:

Input: J = "z", S = "ZZ"
Output: 0

一開始直覺想到的解法就是字串轉陣列,跑雙重迴圈來兩兩比較,如果相同則數數加一。

public static int numJewelsInStones(String J, String S) {
    int count = 0;
    for(int n = 0; n < J.length() ; n++) {
        for(int m = 0; m < S.length(); m++) {
            char j = J.charAt(n);
            char s = S.charAt(m);
            if(j == s) {
                count++;
            }
        }
    }
    
    return count;
}

雖然結果正確,但這樣的做法時間複雜度為O(N2),效率不好。


在下面的相關主題看到Hash Map,馬上想到用Map來處理,應該會比較快。

public static int numJewelsInStones(String J, String S) {
    Map<Character, Integer> map = new HashMap<Character, Integer>();
    for(int n = 0; n < J.length(); n++) {
        map.put(J.charAt(n), 1);
    }
    int count = 0;
    for(int m = 0; m < S.length(); m++) {
        Integer c = map.get(S.charAt(m));
        if(c != null) {
            count++;
        }
    }
    return count;
}

或String轉char陣列來用foreach處理。

public static int numJewelsInStones3(String J, String S) {
    System.out.println("numJewelsInStones3");
    Map<Character, Integer> map = new HashMap<Character, Integer>();
    for (char j : J.toCharArray()) {
        map.put(j, 1);
    }
    
    int count = 0;
    for (char s : S.toCharArray()) {
        if (map.get(s) != null) {
            count++;
        }
    }
    return count;
}

或是使用HashSet

public static int numJewelsInStones(String J, String S) {
    
    Set<Character> set = new HashSet<Character>();
    for(int n = 0; n < J.length(); n++) {
        set.add(J.charAt(n));
    }
    int count = 0;
    for(int m = 0; m < S.length(); m++) {
        if(set.contains(S.charAt(m))) {
            count++;
        }
    }
    return count;
}

測試

import org.apache.commons.text.RandomStringGenerator;

public static void main(String[] args) {
    String J = "aAbBcCdDeEfFgG"; // 珠寶種類
    
    char[][] pairs = {{'a','z'},{'A','Z'}}; // 隨機字串範圍
    int length = 10000; // 隨機字串長度
    RandomStringGenerator generator = new RandomStringGenerator.Builder().withinRange(pairs).build();
    String S = generator.generate(length); // 產生 "a - z", "A - Z"隨機字串 
    
    long startTime = System.nanoTime();
    
    int jewelNumber = numJewelsInStones(J, S);
    
    long endTime = System.nanoTime();
    
    System.out.println("Jewel Number:" + jewelNumber);
    System.out.println("Execution Time:" + (endTime - startTime) + " nanosecond");
}

從這題目可以學到,在比較兩個陣列的內容時,應該利用Map來處理,而不要使用雙迴圈。


參考:

沒有留言:

張貼留言