哈希表理論基礎

[LeetCode] 242. 有效的字母異位詞

[LeetCode] 242. 有效的字母異位詞 文章解釋

[LeetCode] 242. 有效的字母異位詞 視頻解釋

題目:

給定兩個字符串 s 和 t ，編寫一個函數來判斷 t 是否是 s 的字母異位詞。

注意：若?s 和 t?中每個字符出現的次數都相同，則稱?s 和 t?互為字母異位詞。

示例?1:

輸入: s = "anagram", t = "nagaram"
輸出: true

示例 2:

輸入: s = "rat", t = "car"
輸出: false

提示:

• 1 <= s.length, t.length <= 5 * 104
• s 和 t?僅包含小寫字母

進階:?如果輸入字符串包含 unicode 字符怎么辦？你能否調整你的解法來應對這種情況？

自己看到題目的第一想法

??? 因為前一晚先看了視頻, 加上之前自己實現過, 所以印象挺深的.

看完代碼隨想錄之后的想法

??? 使用數組做哈希表, 哈希表的索引為字母在 26 個字母表的位置, 這樣可以提高搜索的速度.

// 方案一: 這個方案對于 characterCount 中的數據做的剪發操作會比方案二多不少
// 因此在大量隨機輸入的情況下效率沒有方案二高
class Solution {public boolean isAnagram(String s, String t) {if (s == null || t == null || s.length() != t.length()) {return false;}int[] characterCount = new int[26];for (int i = 0; i < s.length(); i++) {characterCount[s.charAt(i) - 'a']++;characterCount[t.charAt(i) - 'a']--;}for (int i = 0; i < characterCount.length; i++) {if (characterCount[i] != 0) {return false;}}return true;}
}

// 方案二
class Solution {public boolean isAnagram(String s, String t) {if (s == null || t == null || s.length() != t.length()) {return false;}int[] characterCount = new int[26];for (int i = 0; i < s.length(); i++) {characterCount[s.charAt(i) - 'a']++;}for (int i = 0; i < t.length(); i++) {characterCount[t.charAt(i) - 'a']--;if (characterCount[t.charAt(i) - 'a'] < 0) {return false;}}return true;}
}

自己實現過程中遇到哪些困難

??? 如果按照視頻里的解法, 效率好像會稍微低一些, 將判斷是否異位詞的邏輯修改成每次對第二個字符串中的字符, 每減一就判斷一次, 這樣可以減少一些減法操作, 效率提升了一些.

[LeetCode] 349. 兩個數組的交集

[LeetCode] 349. 兩個數組的交集 文章解釋

[LeetCode] 349. 兩個數組的交集 視頻解釋

題目:

給定兩個數組?nums1?和?nums2 ，返回 它們的交集 。輸出結果中的每個元素一定是 唯一 的。我們可以 不考慮輸出結果的順序 。

示例 1：

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

示例 2：

輸入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
輸出：[9,4]
解釋：[4,9] 也是可通過的

提示：

• 1 <= nums1.length, nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 1000

自己看到題目的第一想法

??? 兩個 for 循環, 再將相等的數據放到 Set 集合里.

看完代碼隨想錄之后的想法

??? 通過 Set 保存一個數組的數據, 再通過另一個遍歷另一個數組將同時出現在被遍歷數組和 Set 中的數字, 保存到結果中并返回.

class Solution {public int[] intersection(int[] nums1, int[] nums2) {Set<Integer> comparedSource = new HashSet<>();for (int i = 0; i < nums1.length; i++) {comparedSource.add(nums1[i]);}List<Integer> result = new ArrayList<>();for (int i = 0; i < nums2.length; i++) {if (comparedSource.remove(nums2[i])) {result.add(nums2[i]);}}int[] resultArray = new int[result.size()];for (int i = 0; i < result.size(); i++) {resultArray[i] = result.get(i);}return resultArray;}
}

自己實現過程中遇到哪些困難

??? Java 的 List<Integer> 轉為 int[] 沒找到合適的 API.

[LeetCode] 202. 快樂數

[LeetCode] 202. 快樂數 文章說明

題目:

編寫一個算法來判斷一個數 n 是不是快樂數。

「快樂數」?定義為：

• 對于一個正整數，每一次將該數替換為它每個位置上的數字的平方和。
• 然后重復這個過程直到這個數變為 1，也可能是 無限循環 但始終變不到 1。
• 如果這個過程 結果為?1，那么這個數就是快樂數。

如果 n 是 快樂數 就返回 true ；不是，則返回 false 。

示例 1：

輸入：n = 19
輸出：true
解釋：(左邊的數表示底數, 右邊的數表示指數, 1^2則表示1的平方)
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

示例 2：

輸入：n = 2
輸出：false

提示：

• 1 <= n <= 231 - 1

自己看到題目的第一想法

??? 1. 為什么一個整數的每個位置的數平方后, 再把這些平方值相加. 最終不是得到1, 就是得到一個循環的過程呢? 算了, 題目這么說就這么信吧!

??? 2. 既然會出現循環, 那就不能讓程序出現死循環. 所以我要記錄住每個數字拆解后出現的序列(這里就是愚蠢的開始), 如果后續再出現這個序列, 我就要終止比對. 如果出現需要判斷一個對象是否出現在列表里, 就要考慮用哈希表! 我懂! 每個序列有長度, 我把相同長度的序列放在Map的同一個索引下, 與是愚蠢的 List<Integer, List<List<Integer>>> 出現了. 當然后面就越寫越奇怪, 越寫越亂.

??? 3. 在第2步的愚蠢之下, 迎來了意思曙光. 不管是 212、 122 還是 221, 如果出現循環的話, 最終一定會回到2^2+1^1+2^2=5, 所以只要5重復出現, 就表示循環了. 所以我要記錄的只是所有數的平方和是否重復出現就可以了... 這么簡單的道理我到底在復雜些什么?

看完代碼隨想錄之后的想法

??? 如我看到題目的第一想法的第3步, 基本沒有太多差別了. 算法的精妙就在于, 一旦想明白, 就會覺得豁然開朗以及否定自我. 為什么我會如此愚蠢呢, 這么簡單的事情都沒想到.

class Solution {public boolean isHappy(int n) {Set<Integer> squareSum = new HashSet<>();while ((n = getNumber(n)) != 1) {if (!squareSum.add(n)) {return false;}}return true;}private int getNumber(int number) {int result = 0;int currentNumber;while (number > 0) {currentNumber = number - (number/10)*10;result += currentNumber * currentNumber;number /= 10;}return result;}
}

自己實現過程中遇到哪些困難

??? 想明白了就很簡單了, 沒有遇到判斷條件不確定等問題.

[LeetCode] 1. 兩數之和

[LeetCode] 1. 兩數之和 文章解釋

[LeetCode] 1. 兩數之和 視頻解釋

題目:

給定一個整數數組 nums?和一個整數目標值 target，請你在該數組中找出 和為目標值 target? 的那?兩個?整數，并返回它們的數組下標。

你可以假設每種輸入只會對應一個答案。但是，數組中同一個元素在答案里不能重復出現。

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

示例 1：

輸入：nums = [2,7,11,15], target = 9
輸出：[0,1]
解釋：因為 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

輸入：nums = [3,2,4], target = 6
輸出：[1,2]

示例 3：

輸入：nums = [3,3], target = 6
輸出：[0,1]

提示：

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• 只會存在一個有效答案

進階：你可以想出一個時間復雜度小于 O(n2) 的算法嗎？

自己看到題目的第一想法?

??? 嗯... 雖然看了視頻, 依舊會看到之前自己的解答. 果然是爽循環 O(n^2) 的暴力解法.

看完代碼隨想錄之后的想法

??? x + y = z, 已知 z 和 y 的條件下, x 可知. 所以問題退化成尋找 x 是否在數組中出現. 當需要判斷一個對象是否在數組中出現的時候, 考慮哈希表. 這里需要返回對應數字的下表, 因此需要用 Map, 將數字和數字所在的下標做一個映射.

class Solution {public int[] twoSum(int[] nums, int target) {Map<Integer, Integer> existsNumbers = new HashMap<>();int[] result = new int[2];for (int i = 0; i < nums.length; i++) {if (existsNumbers.containsKey(target - nums[i])) {result[0] = existsNumbers.get(target - nums[i]);result[1] = i;return result;} else {existsNumbers.put(nums[i], i);}}return result;}
}

自己實現過程中遇到哪些困難

??? 無