哈希表（Hash Table，也叫散列表），是根據(jù)鍵（Key）而直接訪問在內(nèi)存存儲位置的數(shù)據(jù)結(jié)構(gòu)。也就是說，它通過計算一個關(guān)于鍵值的函數(shù)，將所需查詢的數(shù)據(jù)映射到表中一個位置來訪問記錄，這加快了查找速度。這個映射函數(shù)稱做哈希函數(shù)，存放記錄的數(shù)組稱做哈希表。

哈希表是使用 O(1)O(1) 時間進行數(shù)據(jù)的插入刪除和查找，但是哈希表不保證表中數(shù)據(jù)的有序性，這樣在哈希表中查找最大數(shù)據(jù)或者最小數(shù)據(jù)的時間是 O(N)O(N) 實現(xiàn)。

463. 島嶼的周長

給定一個包含 0 和 1 的二維網(wǎng)格地圖，其中 1 表示陸地 0 表示水域。

網(wǎng)格中的格子水平和垂直方向相連（對角線方向不相連）。整個網(wǎng)格被水完全包圍，但其中恰好有一個島嶼（或者說，一個或多個表示陸地的格子相連組成的島嶼）。

島嶼中沒有“湖”（“湖” 指水域在島嶼內(nèi)部且不和島嶼周圍的水相連）。格子是邊長為 1 的正方形。網(wǎng)格為長方形，且寬度和高度均不超過 100 。計算這個島嶼的周長。

示例 :
輸入:
[[0,1,0,0],
[1,1,1,0],
[0,1,0,0],
[1,1,0,0]]

輸出: 16

題解：

class Solution {
    public int islandPerimeter(int[][] grid) {
        //思路：每個島嶼，如果四周都沒有島，那么它對周長的貢獻就是4，
        // 遍歷二維數(shù)組，對每個島查詢上下左右相鄰有沒有島嶼，有島嶼對周長貢獻-1，所有累加起來就是總周長

        int totalEdge = 0;
        for (int i = 0; i < grid.length; i++) {
            int[] row = grid[i];  //當前行數(shù)組
            //遍歷當前行，值為1的為島嶼進行判斷
            for (int j = 0; j < row.length; j++) {
                if (row[j] == 1) {
                    //當前點為島嶼，位置為 grid[i][j]

                    //上
                    if (i != 0) {  //非第一行
                        if (grid[i - 1][j] != 1) {
                            //上一行對應位置沒有島嶼，+1
                            totalEdge++;
                        }

                    } else {
                        totalEdge++;
                    }
                    //右
                    if (j != row.length-1) {  //非該行最后一個位置
                        //不是最后一個
                        if (row[j+1] != 1) {
                            totalEdge++;
                        }
                    } else {
                        totalEdge++;
                    }
                    //下
                    if (i != grid.length-1) {  //非最后一行
                        if (grid[i + 1][j] != 1) {
                            //下一行對應位置沒有島嶼，+1
                            totalEdge++;
                        }
                    } else {
                        totalEdge++;
                    }
                    //左
                    if (j != 0) {  //非該行第一個位置
                        //不是第一個
                        if (row[j-1] != 1) {
                            totalEdge++;
                        }
                    } else {
                        totalEdge++;
                    }
                }
            }
        }

        return totalEdge;
    }
}

500. 鍵盤行

給定一個單詞列表，只返回可以使用在鍵盤同一行的字母打印出來的單詞。鍵盤如下圖所示。

示例：
輸入: ["Hello", "Alaska", "Dad", "Peace"]
輸出: ["Alaska", "Dad"]

題解：

class Solution {
    public String[] findWords(String[] words) {
        //思路：創(chuàng)建3個字符串，分別記錄3行鍵盤所包含的字母字符
        //遍歷words數(shù)組，遍歷單詞字符，記錄每個字符出現(xiàn)的鍵盤行數(shù)，用set存儲各個行數(shù)值，如果最終只有一個值，那么表明在鍵盤的同一行

        String[] enChar = new String[] {"qwertyuiopQWERTYUIOP", "asdfghjklASDFGHJKL", "zxcvbnmZXCVBNM"};
        ArrayList<String> result = new ArrayList<>();
        for (int i=0;i<words.length;i++) {
            //遍歷words
            Set<Integer> record = new HashSet<>();  //用set存字符所在enchar位置，如果全部相等，最終set長度為1，否則大于1
            for (int j=0;j<words[i].length();j++) {
                //遍歷每個單詞
                for (int k=0;k<enChar.length;k++) {
                    //遍歷鍵盤每一行字符串
                    String wordChar = String.valueOf(words[i].charAt(j));
                    if (enChar[k].contains(wordChar)) {
                        record.add(k);
                    }
                }
            }
            if (record.size() == 1) {
                result.add(words[i]); //記錄該滿足條件字符串
            }

        }

        return result.toArray(new String[result.size()]);
    }
}

771. 寶石與石頭

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

J 中的字母不重復，J 和 S中的所有字符都是字母。字母區(qū)分大小寫，因此"a"和"A"是不同類型的石頭。

示例 1:
輸入: J = "aA", S = "aAAbbbb"
輸出: 3

示例 2:

輸入: J = "z", S = "ZZ"
輸出: 0

題解：

class Solution {
        public int numJewelsInStones(String J, String S) {
        int totalCount = 0;
        //遍歷J中的每種寶石，將S中有寶石的各種數(shù)量累加起來
        for (int i=0;i<J.length();i++) {
            Character jeuwls = J.charAt(i);
            String restStr = S.replaceAll(String.valueOf(jeuwls), ""); //將珠寶字符替換掉
            int count = S.length() - restStr.length();  //長度變短數(shù)為該字符出現(xiàn)在字符串中的次數(shù)
            totalCount += count;  //累加每種寶石數(shù)量
        }

        return totalCount;
    }
}

349. 兩個數(shù)組的交集

給定兩個數(shù)組，編寫一個函數(shù)來計算它們的交集。

示例 1：
輸入：nums1 = [1,2,2,1], nums2 = [2,2]
輸出：[2]

示例 2：
輸入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
輸出：[9,4]

題解：

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        HashSet<Integer> jiaoji = new HashSet<>();
        for (int i=0;i<nums1.length;i++) {
            for (int j=0;j<nums2.length;j++) {
                if (nums1[i] == nums2[j]) {
                    jiaoji.add(nums1[i]);
                    break;
                }
            }
        }

        int[] jiaojiArray = new int[jiaoji.size()];
        int pos = 0;
        Iterator iterator = jiaoji.iterator();
        while (iterator.hasNext()) {
            jiaojiArray[pos] = (int) iterator.next();
            pos++;
        }

        return jiaojiArray;
    }
}

1207. 獨一無二的出現(xiàn)次數(shù)

給你一個整數(shù)數(shù)組 arr，請你幫忙統(tǒng)計數(shù)組中每個數(shù)的出現(xiàn)次數(shù)。

如果每個數(shù)的出現(xiàn)次數(shù)都是獨一無二的，就返回 true；否則返回 false。

示例 1：
輸入：arr = [1,2,2,1,1,3]
輸出：true
解釋：在該數(shù)組中，1 出現(xiàn)了 3 次，2 出現(xiàn)了 2 次，3 只出現(xiàn)了 1 次。沒有兩個數(shù)的出現(xiàn)次數(shù)相同。

示例 2：
輸入：arr = [1,2]
輸出：false

示例 3：
輸入：arr = [-3,0,1,-3,1,1,1,-3,10,0]
輸出：true

題解：

class Solution {
    public boolean uniqueOccurrences(int[] arr) {
        //思路：存儲每一個數(shù)字出現(xiàn)的次數(shù)，判斷這些次數(shù)是否都不相等
        Map<Integer, Integer> record = new HashMap<>();
        for (int num : arr) {
            if (!record.containsKey(num)) {
                record.put(num, 1);
            } else {
                record.put(num , record.get(num) + 1);
            }
        }

        //遍歷map，將value值存入set去判斷是否有相同值，如果有，則false，否則返回true
        Set<Map.Entry<Integer, Integer>> entries = record.entrySet();
        Set<Integer> set = new HashSet<>();
        for (Map.Entry<Integer, Integer> entry : entries) {
            if (!set.add(entry.getValue())) {
                //添加失敗，說明有相同值
                return false;
            }
        }
        return true;
    }
}

1160. 拼寫單詞

給你一份『詞匯表』（字符串數(shù)組） words 和一張『字母表』（字符串） chars。
假如你可以用 chars 中的『字母』（字符）拼寫出 words 中的某個『單詞』（字符串），那么我們就認為你掌握了這個單詞。

注意：每次拼寫（指拼寫詞匯表中的一個單詞）時，chars 中的每個字母都只能用一次。
返回詞匯表 words 中你掌握的所有單詞的 長度之和。

示例 ：
輸入：words = ["cat","bt","hat","tree"], chars = "atach"
輸出：6
解釋：
可以形成字符串 "cat" 和 "hat"，所以答案是 3 + 3 = 6。

題解：

class Solution {
    public int countCharacters(String[] words, String chars) {
        int enLength = 26;
        StringBuilder stringBuilder = new StringBuilder();
        //解決方案：將每個字符串維護一張長度為26的int數(shù)組，存儲a-z26個字母各自出現(xiàn)的次數(shù)
        int[] charsArray = new int[enLength];
        for (int i=0;i<chars.length();i++) {
            charsArray[chars.charAt(i) - 'a'] += 1; //chars.char(i)-'a' 表示當前字符在a-z數(shù)組的序號，如c-'a'=2為c在字母表中序號
        }

        //給words數(shù)組中每個字符串創(chuàng)建一張字母表
        a : for (String str : words) {
            int[] strArray = new int[enLength];
            for (int i=0;i<str.length();i++) {
                strArray[str.charAt(i) - 'a'] += 1;
            }

            //核心判斷：因為chars 中的每個字母都只能用一次，所有chars中每種字母次數(shù)不能比word中的小，不然就重復使用了
            for (int i=0;i<enLength;i++) {
                if (strArray[i] > charsArray[i]) {
                    continue a;
                }
            }

            //順利執(zhí)行到此，表明滿足條件，添加單詞記錄
            stringBuilder.append(str);
        }

        return stringBuilder.length();
    }

}

1002. 查找常用字符

給定僅有小寫字母組成的字符串數(shù)組 A，返回列表中的每個字符串中都顯示的全部字符（包括重復字符）組成的列表。例如，如果一個字符在每個字符串中出現(xiàn) 3 次，但不是 4 次，則需要在最終答案中包含該字符 3 次。

你可以按任意順序返回答案。

示例 1：
輸入：["bella","label","roller"]
輸出：["e","l","l"]

示例 2：
輸入：["cool","lock","cook"]

輸出：["c","o"]

題解：

class Solution {
    public List<String> commonChars(String[] A) {
        //思路：取出數(shù)組第一個字符串，遍歷該字符串字符，遍歷其他字符串，用indexof去找當前字符，如果沒找到，則該字符為不常用
        //如果找到了，刪除該字符串，找到一輪遍歷完成，那么該字符為常用字符

        String compareStr = A[0];
        List<String> strArray = new ArrayList<>();
        a : for (int i=0;i<compareStr.length();i++) {
            char ch = compareStr.charAt(i);
            for (int j=1;j<A.length;j++) {
                int pos = A[j].indexOf(ch);
                if (pos == -1) {
                    //未找到
                    continue a;
                } else {
                    //找到需要刪去
                    A[j] = strRemoveChar(A[j], pos);
                }
            }
            //ch字符在每個字符串都找到，屬于常用字符串
            strArray.add(String.valueOf(ch));
        }
        return strArray;
    }

        /**
     * 刪除字符串指定位置的字符
     * @param string
     * @param pos
     * @return
     */
    public String strRemoveChar(String string, int pos) {
        return string.substring(0, pos) + string.substring(pos+1);
    }
}

811. 子域名訪問計數(shù)

一個網(wǎng)站域名，如"discuss.leetcode.com"，包含了多個子域名。作為頂級域名，常用的有"com"，下一級則有"leetcode.com"，最低的一級為"discuss.leetcode.com"。當我們訪問域名"discuss.leetcode.com"時，也同時訪問了其父域名"leetcode.com"以及頂級域名 "com"。

給定一個帶訪問次數(shù)和域名的組合，要求分別計算每個域名被訪問的次數(shù)。其格式為訪問次數(shù)+空格+地址，例如："9001 discuss.leetcode.com"。

接下來會給出一組訪問次數(shù)和域名組合的列表cpdomains 。要求解析出所有域名的訪問次數(shù)，輸出格式和輸入格式相同，不限定先后順序。

示例 1:
輸入:
["9001 discuss.leetcode.com"]
輸出:
["9001 discuss.leetcode.com", "9001 leetcode.com", "9001 com"]
說明:
例子中僅包含一個網(wǎng)站域名："discuss.leetcode.com"。按照前文假設(shè)，子域名"leetcode.com"和"com"都會被訪問，所以它們都被訪問了9001次。

題解：

class Solution {
    public List<String> subdomainVisits(String[] cpdomains) {
        //思路：分別計算各種域名訪問的次數(shù)，從三級域名到二級到一級，分別計算二級和一級訪問的總數(shù)
        //用Map來存各種域名訪問的次數(shù)

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

        for (String str : cpdomains) {
            record(record, str);
        }

        ArrayList<String> datas = new ArrayList<>();
        Set<Map.Entry<String, Integer>> entries = record.entrySet();
        for (Map.Entry<String, Integer> entry : entries) {
            datas.add(entry.getValue() + " " + entry.getKey());
        }

        return datas;
    }

    private void record(Map<String, Integer> record, String ip) {
        String[] data = ip.split(" ");
        int count = Integer.parseInt(data[0]);  //ip訪問次數(shù)
        String fullIp = data[1];  //ip全稱

        //從該ip獲得所有個子ip地址
        putValue(record, fullIp, count);

        getSubIp(record, fullIp, count);

    }

    /**
     * 遞歸獲取所有子域名
     * @param record
     * @param fullIp
     * @param count
     */
    private void getSubIp(Map<String, Integer> record, String fullIp, int count) {
        int pos = fullIp.indexOf(".");
        if (pos != -1) {
            //有子域名
            fullIp = fullIp.substring(pos+1);

            putValue(record, fullIp, count);

            getSubIp(record, fullIp, count);
        }
    }

    private void putValue(Map<String, Integer> record, String fullIp, int count) {
        if (!record.containsKey(fullIp)) {
            record.put(fullIp, count);
        } else {
            record.put(fullIp, record.get(fullIp)+count);
        }
    }
}

575. 分糖果

給定一個偶數(shù)長度的數(shù)組，其中不同的數(shù)字代表著不同種類的糖果，每一個數(shù)字代表一個糖果。你需要把這些糖果平均分給一個弟弟和一個妹妹。返回妹妹可以獲得的最大糖果的種類數(shù)。

示例 1:
輸入: candies = [1,1,2,2,3,3]
輸出: 3
解析: 一共有三種種類的糖果，每一種都有兩個。
最優(yōu)分配方案：妹妹獲得[1,2,3],弟弟也獲得[1,2,3]。這樣使妹妹獲得糖果的種類數(shù)最多。

題解：

class Solution {
    public int distributeCandies(int[] candies) {
        //思路：遍歷candies存入map中，判斷map的長度，如果長度<=candies.length/2，則妹妹糖果種類為map長度，如果長度>candies.length/2，則為
        //candies.length/2

        Map<Integer, Integer> record = new HashMap<>();
        for (int candy : candies) {
            if (!record.containsKey(candy)) {
                record.put(candy, 1);
            } else {
                record.put(candy, record.get(candy) + 1);
            }
        }

        if (record.size() <= candies.length/2) {
            return record.size();
        } else {
            return candies.length/2;
        }
    }
}

884. 兩句話中的不常見單詞

給定兩個句子 A 和 B 。 （句子是一串由空格分隔的單詞。每個單詞僅由小寫字母組成。）
如果一個單詞在其中一個句子中只出現(xiàn)一次，在另一個句子中卻沒有出現(xiàn)，那么這個單詞就是不常見的。

返回所有不常用單詞的列表。
您可以按任何順序返回列表。

示例 1：
輸入：A = "this apple is sweet", B = "this apple is sour"
輸出：["sweet","sour"]

題解：

class Solution {
    public String[] uncommonFromSentences(String A, String B) {

        String result = get(A, B) + get(B, A);
        System.out.println(result);
        if (result.length() == 0) {
            return new String[]{};
        } else {
            return result.split(" ");
        }
    }

    private String get(String A, String B) {
        StringBuilder stringBuilder = new StringBuilder();
        String[] arrayA = A.split(" ");
        String[] arrayB = B.split(" ");

        a : for (int i=0;i<arrayA.length;i++) {
            //如果B中包含字符串，則不是不常見單詞
            for (String strB : arrayB) {
                if (strB.equals(arrayA[i])) {
                    continue a;
                }
            }

            //如果B中不包含，還需要判斷arrayA中該字符串是否重復

            for (int j=0;j<arrayA.length;j++) {
                if (i != j) {  //避免自己與自己再匹配
                    if (arrayA[j].equals(arrayA[i])) {
                        continue a;
                    }
                }
            }

            stringBuilder.append(arrayA[i] + " ");
        }

        return stringBuilder.toString();
    }
}

389. 找不同

給定兩個字符串 s 和 t，它們只包含小寫字母。
字符串 t 由字符串 s 隨機重排，然后在隨機位置添加一個字母。
請找出在 t 中被添加的字母。

示例:
輸入：
s = "abcd"
t = "abcde"

輸出：
e

解釋：
'e' 是那個被添加的字母。

題解：

class Solution {
    public char findTheDifference(String s, String t) {
        //思路：將s、t字符串分別將字符存入map中，字符為key，存入次數(shù)為value，遍歷t的map，如果存在t中key在s中不存在，則該key為被添加的字母
        //如果t中的value與s中對應keyvalue不相等，則該key也為被添加的字母


        Map<Character, Integer> mapS = record(s);
        Map<Character, Integer> mapT = record(t);

        Set<Map.Entry<Character, Integer>> entries = mapT.entrySet();
        for (Map.Entry<Character, Integer> entry : entries) {
            if (!mapS.containsKey(entry.getKey())) {
                return entry.getKey();
            }

            if (entry.getValue() != mapS.get(entry.getKey())) {
                return entry.getKey();
            }
        }

        throw new IllegalArgumentException("不存在該字母");
    }

    private Map<Character, Integer> record(String s) {
        Map<Character, Integer> mapS = new HashMap<>();
        for (int i=0;i<s.length();i++) {
            char ch = s.charAt(i);
            if (!mapS.containsKey(ch)) {
                mapS.put(ch, 1);
            } else {
                mapS.put(ch, mapS.get(ch)+1);
            }
        }
        return mapS;
    }
}