Java數(shù)據(jù)結(jié)構(gòu)之Map與Set專篇講解

更新時間：2022年01月27日 16:05:25 作者：/少司命

這篇文章通過實(shí)例面試題目來講解Java中Map和Set之間的關(guān)系，具有很好的參考價值，Map與Set在面試中經(jīng)常會遇到。一起跟隨小編過來看看吧

①只出現(xiàn)一次的數(shù)字

給定一個非空整數(shù)數(shù)組，除了某個元素只出現(xiàn)一次以外，其余每個元素均出現(xiàn)兩次。找出那個只出現(xiàn)了一次的元素。

輸入: [2,2,1]
輸出: 1

首相我們可能會想到用位運(yùn)算直接解決，但我們也可以用hash色條解決。

public int singleNumber(int[] nums) {
        int single = 0;
        for (int num : nums) {
            single ^= num;
        }
        return single;
    }

hashset也已輕松解決這個問題，將整個數(shù)組中的元素放入set,因?yàn)橹怀霈F(xiàn)一次的數(shù)字只有一次，所以我們將多次出現(xiàn)相同的數(shù)字移除

public int singleNumber(int[] nums){
 
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++){
            if (set.contains(nums[i])){
                set.remove(nums[i]);
            }else {
                set.add(nums[i]);
            }
        }
        for (int i = 0; i < nums.length; i++){
            if (set.contains(nums[i])){
                return nums[i];
            }
        }
        return -1;
 
    }

②寶石與石頭

給你一個字符串 jewels 代表石頭中寶石的類型，另有一個字符串 stones 代表你擁有的石頭。 stones 中每個字符代表了一種你擁有的石頭的類型，你想知道你擁有的石頭中有多少是寶石。

字母區(qū)分大小寫，因此 "a" 和 "A" 是不同類型的石頭。

輸入：jewels = "aA", stones = "aAAbbbb"
輸出：3

這道題和第一道題一樣，這里是統(tǒng)計(jì)不同的個數(shù)。因?yàn)橐獏^(qū)分大小寫，所以我們將小寫轉(zhuǎn)大寫，不影響我們做出判斷

 public int numJewelsInStons(String jewels,String stons){
        stons.toUpperCase(Locale.ROOT).toCharArray();
 
        HashSet<Character> set = new HashSet<>();
 
        for (int i = 0; i < jewels.length(); i++){
            set.add(jewels.charAt(i));
        }
 
        int count = 0;
        for (char ch:stons.toCharArray()) {
            if(set.contains(ch)){
                count++;
            }
        }
        return count;
    }

③壞鍵盤打字

舊鍵盤上壞了幾個鍵，于是在敲一段文字的時候，對應(yīng)的字符就不會出現(xiàn)。現(xiàn)在給出應(yīng)該輸入的一段文字、以及實(shí)際被輸入的文字，請你列出肯定壞掉的那些鍵。

輸入
7_This_is_a_test
_hs_s_a_es

輸出

7TI

這道題我們要分兩個set,一個setActual記錄真實(shí)打出的字母，一個setBroken統(tǒng)計(jì)壞掉的字母，判斷條件是符合的字母既不是包含setActual中已經(jīng)存在的，也不是setActual與setBroken相同的字母。主要是同時對比setActual與setBroken。

public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String str1 = scan.nextLine();
        String str2 = scan.nextLine();
 
        HashSet<Character> setActual = new HashSet<>();
        for (char ch:str2.toUpperCase(Locale.ROOT).toCharArray()) {
            setActual.add(ch);
        }
        HashSet<Character> setBroken = new HashSet<>();
        for (char ch: str1.toUpperCase(Locale.ROOT).toCharArray()) {
            if(!setActual.contains(ch) && !setBroken.contains(ch)){
                setBroken.add(ch);
                System.out.print(ch);;
            }
        }
    }

④復(fù)制帶隨機(jī)指針的鏈表

給你一個長度為 n 的鏈表，每個節(jié)點(diǎn)包含一個額外增加的隨機(jī)指針 random ，該指針可以指向鏈表中的任何節(jié)點(diǎn)或空節(jié)點(diǎn)。

構(gòu)造這個鏈表的深拷貝。深拷貝應(yīng)該正好由 n 個全新節(jié)點(diǎn)組成，其中每個新節(jié)點(diǎn)的值都設(shè)為其對應(yīng)的原節(jié)點(diǎn)的值。新節(jié)點(diǎn)的 next 指針和 random 指針也都應(yīng)指向復(fù)制鏈表中的新節(jié)點(diǎn)，并使原鏈表和復(fù)制鏈表中的這些指針能夠表示相同的鏈表狀態(tài)。復(fù)制鏈表中的指針都不應(yīng)指向原鏈表中的節(jié)點(diǎn)。

例如，如果原鏈表中有 X 和 Y 兩個節(jié)點(diǎn)，其中 X.random --> Y 。那么在復(fù)制鏈表中對應(yīng)的兩個節(jié)點(diǎn) x 和 y ，同樣有 x.random --> y 。

輸入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]

輸出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

class Node {
    int val;
    Node next;
    Node random;
 
    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
 
public Node copyRandomList(Node head){
        if (head == null) return null;
        HashMap<Node,Node> map = new HashMap<>();
        Node cur = head;
        while (cur != null){
            Node node = new Node(cur.val);
            map.put(cur,node);
            cur = cur.next;
        }
        cur = head;
        while (cur != null){
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);
 
 
    }

到此這篇關(guān)于Java數(shù)據(jù)結(jié)構(gòu)之Map與Set專篇講解的文章就介紹到這了,更多相關(guān)Java Map Set內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: