Map、List的实际存储格式为数组，只是封装了具体的操作流程。
白话HashMap源码
- 题目
Single Number
Happy Number
Two Sum
Isomorphic Strings
Minimum Index Sum of Two Lists
First Unique Character in a String
Intersection of Two Arrays II
Contains Duplicate II
Group Anagrams
Valid Sudoku
Find Duplicate Subtrees
Jewels and Stones
Longest Substring Without Repeating Characters
4Sum II
Top K Frequent Elements
Insert Delete GetRandom O(1)
Single Number
找出数组中单一的项
Input: [2,2,1]
Output: 1
常规思路就是计数，记录出现次数，发现出现次数为1的项
题目中有这样一句话“every element appears twice except for one”重复项必定出现两次多一次都不行，所以有个非常棒的算法：
异或有个性质，a ^ a = 0 所以
public int singleNumber(int[] nums) {
int res=0;
for(int i=0;i<nums.length;i++){
res =res ^ nums[i];
}
return res;
}
时间复杂度O(n)，空间复杂度O(1)
Happy Number
将整数的各位平方求和，对和重复此操作，直到和为1的整数为Happy Number。
Input: 19
Output: true
Explanation:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12+ 02 + 02= 1
class Solution {
Set<Integer> set=new HashSet<>();
public boolean isHappy(int n) {
if (n == 1) {
return true;
}
set.add(n);
int sum = 0;
while (n != 0) {
int num=n % 10;
sum += num * num;
n = n / 10;
}
if (set.contains(sum)) {
return false;
}
return isHappy(sum);
}
}
解决思路很明确，此题的重点在于寻找循环的出口。
一个整数如果是Happy Number则符合题目所给的条件最终求和得1。如果不是，则会在循环的过程中进入死循环。
记录计算过程中所得和，如果此和出现两次则表明进入死循环且此整数不是Happy Number。
Two Sum
在数组中是否存在两项，其和为指定值。
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1]
class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
for(int i=0;i<nums.length;i++){
map.put(nums[i],i);
}
for(int i=0;i<nums.length;i++){
int tem=target-nums[i];
if (map.containsKey(tem) && map.get(tem) != i) {
return new int[]{i, map.get(tem)};
}
}
return new int[]{};
}
}
map中key为项值，value为数组位置，利用两项和差的关系、map.containsKey，求解。
Isomorphic Strings
判断两字符串，是否为同构字符串
Input: s = "egg", t = "add"
Output: true
class Solution {
public boolean isIsomorphic(String s, String t) {
int m1[] = new int[256];
int m2[] = new int[256];
int n = s.length();
for (int i = 0; i < n; ++i) {
if (m1[s.charAt(i)] != m2[t.charAt(i)]) return false;
m1[s.charAt(i)] = i + 1;
m2[t.charAt(i)] = i + 1;
}
return true;
}
}
两字符串，按顺序记录各自字符出现的次数，如果同构则同位置不同字符出现的次数一样。
Minimum Index Sum of Two Lists
两列表中，每项有不同的权重，求权重最高的共同项
Input:
["Shogun", "Tapioca Express", "Burger King", "KFC"]
["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"]
Output: ["Shogun"]
Explanation: The only restaurant they both like is "Shogun".
class Solution {
public String[] findRestaurant(String[] list1, String[] list2) {
HashMap<String, Integer> map = new HashMap<String, Integer>();
for (int i = 0; i < list1.length; i++) {
map.put(list1[i], i);
}
List<String> res = new ArrayList<String>();
int min = Integer.MAX_VALUE;//此题求的权重不是最大而是最小
for (int i = 0; i < list2.length; i++) {
if (map.containsKey(list2[i])) {//有共同项
int temp = map.get(list2[i]);
if (temp + i < min) {//这两项的权重，符合要求
res.clear();
res.add(list2[i]);
min = temp + i;
}
if (temp + i == min&&!res.contains(list2[i])) {//这两项的权重，也符合要求
res.add(list2[i]);
}
}
}
String[] strings=new String[res.size()];
res.toArray(strings);
return strings;
}
}
key存项，value存权重
First Unique Character in a String
字符串中求出第一个不重复项
s = "leetcode"
return 0
s = "loveleetcode"
return 2
class Solution {
public int firstUniqChar(String s) {
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
for (int i = 0; i < s.length(); i++) {//重复项的value一定大于字符长
if (map.containsKey(s.charAt(i))) {
map.put(s.charAt(i), i + s.length());
} else {
map.put(s.charAt(i), i);
}
}
int min = s.length();
for (Character c : map.keySet()) {
if (map.get(c) < s.length() && map.get(c) < min) {//不重复项，且排序靠前
min = map.get(c);
}
}
return min == s.length() ? -1 : min;
}
}
Intersection of Two Arrays II
求两数组的相交项（不是重复项）
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2]
class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
HashMap<Integer, Integer> hashMap = new HashMap<Integer, Integer>();//key存项，value存出现次数
for (int i = 0; i < nums1.length; i++) {
if (hashMap.containsKey(nums1[i])) {
hashMap.put(nums1[i], hashMap.get(nums1[i]) + 1);
} else {
hashMap.put(nums1[i], 1);
}
}
List<Integer> res = new ArrayList<Integer>();
for (int i = 0; i < nums2.length; i++) {
if (hashMap.containsKey(nums2[i]) && hashMap.get(nums2[i]) >= 1) {//containsKey表示相交，且还存在出现次数
res.add(nums2[i]);
hashMap.put(nums2[i], hashMap.get(nums2[i]) - 1);
}
}
int[] result = new int[res.size()];
for (int i = 0; i < res.size(); i++) {
result[i] = res.get(i);
}
return result;
}
}
Contains Duplicate II
在固定范围内，是否存在两项相同
Input: [1,2,3,1], k = 3
Output: true
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
Set<Integer> set = new HashSet<Integer>();
for(int i = 0; i < nums.length; i++){
if(i > k) set.remove(nums[i-k-1]);//保持set的大小，范围就是set的大小
if(!set.add(nums[i])) return true;
}
return false;
}
}
Group Anagrams
对数组进行分组，此题目的在于找出key，同组数据中找出共性作为key
Input: ["eat", "tea", "tan", "ate", "nat", "bat"]
Output:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]]
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
HashMap<String, List<String>> hashMap = new HashMap<String, List<String>>();
for (String str : strs) {
char[] chars = str.toCharArray();
Arrays.sort(chars);
String key = String.valueOf(chars);
if (!hashMap.containsKey(key)) {
hashMap.put(key, new ArrayList<String>());
}
hashMap.get(key).add(str);
}
return new ArrayList<List<String>>(hashMap.values());
}
}
Valid Sudoku
判断输入的数组是否为数独，数独的条件就是每行每列中1-9的数字不能重复，且3x3的小格内数字不能重复
Input:
[
["5","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]
]
Output: true
class Solution {
public boolean isValidSudoku(char[][] board) {
//每行列格，用set存项，当项重复时则失败
HashMap<Integer, Set<Integer>> row = new HashMap<Integer, Set<Integer>>();
HashMap<Integer, Set<Integer>> colum = new HashMap<Integer, Set<Integer>>();
HashMap<Integer, Set<Integer>> box = new HashMap<Integer, Set<Integer>>();
for (int i = 0; i < 9; i++) {
if (row.get(i) == null) row.put(i, new HashSet<Integer>());
for (int j = 0; j < 9; j++) {
if (colum.get(j) == null) colum.put(j, new HashSet<Integer>());
if (box.get((i / 3) + (j / 3) * 3) == null)//计算小格的逻辑
box.put((i / 3) + (j / 3) * 3, new HashSet<Integer>());
if (board[i][j] == '.') {
continue;
}
if (!row.get(i).add(board[i][j] - '0')) return false;
if (!colum.get(j).add(board[i][j] - '0')) return false;
if (!box.get((i / 3) + (j / 3) * 3).add(board[i][j] - '0')) return false;
}
}
return true;
}
}
Find Duplicate Subtrees
查找树中相同的子树，通过该子树的序列化进行判断，相同的树具有相同的序列化。但子节点为空时，中序遍历可能会有不同子树序列化相同的情况
1
/ \
2 3
/ / \ input
4 2 4
/
4
2
/
4
output
2
/
4
class Solution {
HashMap<String, Integer> trees = new HashMap<String, Integer>();
List<TreeNode> res = new ArrayList<TreeNode>();
public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
preorder(root);
return res;
}
private String preorder(TreeNode root) {
if (root == null) return "#";
StringBuilder s = new StringBuilder();
s.append(root.val + "");
s.append(preorder(root.left));
s.append(preorder(root.right));
if (!trees.containsKey(s.toString())) {
trees.put(s.toString(), 0);
} else {
trees.put(s.toString(), trees.get(s.toString()) + 1);
}
if (trees.get(s.toString()) == 1) {//大于1就重复了，重复的节点只需记录一次
res.add(root);
}
return s.toString();
}
}
Jewels and Stones
在S的字符串中找出包含J字符串字符的数量
Input: J = "aA", S = "aAAbbbb"
Output: 3
class Solution {
public int numJewelsInStones(String J, String S) {
HashMap<Character, Integer> hashMap = new HashMap<>();
for (int i = 0; i < J.length(); i++) {
hashMap.put(J.charAt(i), 0);
}//J相当于过滤器
for (int i = 0; i < S.length(); i++) {//将杂质拿去过滤
if (hashMap.containsKey(S.charAt(i))) {
hashMap.put(S.charAt(i), hashMap.get(S.charAt(i)) + 1);//需要的留下，杂质抛弃
}
}
int sum = 0;
for (Integer i : hashMap.values()) {
sum += i;
}
return sum;
}
}
Longest Substring Without Repeating Characters
找出字符串中不重复的子串长度
Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
class Solution {
public int lengthOfLongestSubstring(String s) {
HashMap<Character, Integer> hashMap = new HashMap<>();
int max = 0;
int start = 0;//不重复字串的起始位置
for (int i = 0; i < s.length(); i++) {
if (hashMap.containsKey(s.charAt(i))) {
start = Math.max(start, hashMap.get(s.charAt(i)) + 1);//新的起始位置为当前重复位置的后一个
}
if ((i - start + 1) > max) {//最长的字串
max = i - start + 1;
}
hashMap.put(s.charAt(i), i);
}
return max;
}
}
4Sum II
4个数组中，各取一项使和为0，有多少中组合
Input:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]
Output:
2
Explanation:
The two tuples are:
(0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
(1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0
class Solution {
public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
HashMap<Integer, Integer> hashMap = new HashMap<>();
for (int i = 0; i < A.length; i++) {
for (int j = 0; j < B.length; j++) {
hashMap.put(A[i] + B[j], hashMap.getOrDefault(A[i] + B[j], 0) + 1);
}
}
int res = 0;
for (int i = 0; i < C.length; i++) {
for (int j = 0; j < D.length; j++) {
if (hashMap.containsKey(-(C[i] + D[j]))) {
res += hashMap.get(-(C[i] + D[j]));
}
}
}
return res;
}
}
如果暴力解的话时间复杂度为O(n4)，此为O(n2)
Top K Frequent Elements
返回数组中前K个出现频率最高的项
Given [1,1,1,2,2,3] and k = 2, return [1,2].
class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {
HashMap<Integer, Integer> hashMap = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
hashMap.put(nums[i], hashMap.getOrDefault(nums[i], 0) + 1);
}//得出各项出现的次数
//反转key为出现次数，value为出现的项 保证了时间却浪费了空间
ArrayList<Integer>[] buckets = new ArrayList[nums.length + 1];
for (Integer key : hashMap.keySet()) {
if (buckets[hashMap.get(key)] == null) {
buckets[hashMap.get(key)] = new ArrayList<>();
}
buckets[hashMap.get(key)].add(key);
}
List<Integer> res = new ArrayList<>();
for (int i = nums.length; res.size() < k && i >= 0; i--) {//由高到低的出现频率循环所有的项，直到满足K
if (buckets[i] != null && buckets[i].size() > 0) {
res.addAll(buckets[i]);
}
}
return res;
}
}
Insert Delete GetRandom O(1)
设计一种数据结构，使其操作的时间复杂度为O(1)。这种数据结构的操作有insert(val)、remove(val)、getRandom
这题的关键在于时间复杂度O(1)，如果只使用map则getRandom实现复杂；如果只使用list则remove会超时，因为list的实现为数组，移除项时，需要将移除项后的所有项向前移动。
public class RandomizedSet {
private List<Integer> list;
private HashMap<Integer,Integer> map;
/** Initialize your data structure here. */
public RandomizedSet() {
list = new ArrayList<>();
map = new HashMap<>();
}
/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
public boolean insert(int val) {
if(map.containsKey(val))return false;
map.put(val,list.size());
list.add(val);
return true;
}
/** Removes a value from the set. Returns true if the set contained the specified element. */
public boolean remove(int val) {
//大体思路：将移除项与最后一项更换位置，减少了list交换的成本一直为O(1)
if (map.containsKey(val)) {
int p = map.get(val);//得到要移除项的位置
int lastV = list.get(list.size() - 1);//得到list的最后一项
list.set(p, lastV);//将最后一项覆盖到移除项的位置上，移除项消除
list.remove(list.size() - 1);//移除最后一项
map.put(lastV, p);//将最后一项的位置换到移除项位置
map.remove(val);//移除项
return true;
}
return false;
}
/** Get a random element from the set. */
public int getRandom() {
Random random=new Random();
int p=random.nextInt(list.size());
return list.get(p);
}
}
/**
* Your RandomizedSet object will be instantiated and called as such:
* RandomizedSet obj = new RandomizedSet();
* boolean param_1 = obj.insert(val);
* boolean param_2 = obj.remove(val);
* int param_3 = obj.getRandom();
*/
