二分查找和哈希表-习题解析-week04

二分查找
- 704.二分查找（简单）标准二分查找">704.二分查找（简单）标准二分查找
- 374.猜数字大小（简单）">374.猜数字大小（简单）
- 744.寻找比目标字母大的最小字母（简单）">744.寻找比目标字母大的最小字母（简单）
- 35.搜索插入位置（简单）">35.搜索插入位置（简单）
- 34.在排序数组中查找元素的第一个和最后一个位置（中等）">34.在排序数组中查找元素的第一个和最后一个位置（中等）
- 面试题10.05.稀疏数组搜索（简单）">面试题10.05.稀疏数组搜索（简单）
- 33.搜索旋转排序数组（中等）无重复数据">33.搜索旋转排序数组（中等）无重复数据
  - 二分法
- 153.寻找旋转排序数组中的最小值（中等）无重复数据">153.寻找旋转排序数组中的最小值（中等）无重复数据
- 852.山脉数组的峰顶索引（简单）峰值二分">852.山脉数组的峰顶索引（简单）峰值二分
- 162.寻找峰值（中等）峰值二分">162.寻找峰值（中等）峰值二分
- 367.有效的完全平方数（简单）二分答案">367.有效的完全平方数（简单）二分答案
- 69. x的平方根（简单）二分答案">69. x的平方根（简单）二分答案
  - 二分法
- 74.搜索二维矩阵（中等）二维转一维，二分查找">74.搜索二维矩阵（中等）二维转一维，二分查找
- 658. 找到 K 个最接近的元素（中等）">658. 找到 K 个最接近的元素（中等）
  - 二分法+双指针
- 875. 爱吃香蕉的珂珂（中等）二分答案">875. 爱吃香蕉的珂珂（中等）二分答案
- 81. 搜索旋转排序数组 II（中等）有重复数据">81. 搜索旋转排序数组 II（中等）有重复数据
- 154. 寻找旋转排序数组中的最小值 II （困难）有重复数据">154. 寻找旋转排序数组中的最小值 II （困难）有重复数据
哈希表
- 两数之和（简单）">两数之和（简单）
  - 哈希表
- 15.三数之和（中等）">15.三数之和（中等）
  - 哈希表
  - 排序+头尾双指针
160.相交链表（简单）">160.相交链表（简单）
141.环形链表（简单）">141.环形链表（简单）
面试题02.01.移除重复节点（中等）">面试题02.01.移除重复节点（中等）
面试题16.02.单词频率（简单）">面试题16.02.单词频率（简单）
面试题01.02.判定是否互为字符重排（简单）">面试题01.02.判定是否互为字符重排（简单）
剑指Offer 03.数组中重复的数字（简单）">剑指Offer 03.数组中重复的数字（简单）
- 哈希表
- 数组原地交换
242.有效的字母异位词（简单）">242.有效的字母异位词（简单）
- 哈希表（两个哈希表，减少遍历次数）
49.字母异位词分组（中等）">49.字母异位词分组（中等）
- 哈希表
136.只出现一次的数字（简单）">136.只出现一次的数字（简单）
- 哈希表
- 异或运算
349.两个数组的交集（简单）">349.两个数组的交集（简单）
- 哈希表
1122.数组的相对排序（中等）">1122.数组的相对排序（中等）
- 哈希表
- 首尾双指针+排序
706.设计哈希映射（简单）">706.设计哈希映射（简单）
- 超大数组
- 链地址法
146. LRU 缓存机制（中等）标准的LRU">146. LRU 缓存机制（中等）标准的LRU
- 哈希表+双向链表
面试题16.21.交换和（中等）">面试题16.21.交换和（中等）

二分查找

704.二分查找（简单）标准二分查找

class Solution {
    public int search(int[] nums, int target) {
        int low = 0, high = nums.length -1;
        while(low <= high) {
            int mid = low + (high - low) / 2;
            if(nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return -1;
    }
}

374.猜数字大小（简单）

解题思路：二分法

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        return bisection(0, n);
    }
    public int bisection(int low, int high) {
        while(low <= high) {
            int mid = low + (high - low) / 2;
            int guessRes = guess(mid);
            if(guessRes == 0) {
                return mid;
            } else if(guessRes == -1) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return 0;
    }
}

744.寻找比目标字母大的最小字母（简单）

解题思路：

class Solution {
    public char nextGreatestLetter(char[] letters, char target) {
        int size = letters.length, low = 0, high = size - 1;
        while(low <= high) {
            int mid = low + (high - low) / 2;
            char midChar = letters[mid];
            if(midChar <= target) {
                if(mid == high || letters[mid + 1] > target) {
                    // 循环数组
                    return letters[(mid + 1) % size];
                }
                low = mid + 1;
            } else{
                high = mid - 1;
            }
        }
        return letters[0];
    }
}

35.搜索插入位置（简单）

class Solution {
    public int searchInsert(int[] nums, int target) {
        int size = nums.length, low = 0, high = size - 1;
        while(low <= high) {
            int mid = low + (high - low) / 2;
            if(nums[mid] == target) {
                return mid;
            } else if(nums[mid] < target) {
                if(mid == size - 1 || nums[mid + 1] > target) {
                    return mid + 1;
                }
                low = mid + 1;
            } else {
                if(mid == 0 || nums[mid - 1] < target) {
                    return mid;
                }
                high = mid - 1;
            }
        }
        return -1;
    }
}

34.在排序数组中查找元素的第一个和最后一个位置（中等）

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int low = 0, high = nums.length - 1, size = nums.length;
        while(low <= high) {
            int mid = low + (high - low) / 2;
            if(nums[mid] == target) {
                int s = 0, e = 0, i = mid;
                while(i >= 0 && nums[i] == target) {
                    i--;
                }
                // 本身多减了一次
                s = i + 1;
                i = mid;
                while(i < size && nums[i] == target) {
                    i++;
                }
                // 多加了一次
                e = i - 1;
                return new int[] {s, e};
            } else if (nums[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return new int[]{-1, -1};
    }
}

面试题10.05.稀疏数组搜索（简单）

class Solution {
    public int findString(String[] words, String s) {
        int low = 0, high = words.length - 1, size = words.length;
        while(low <= high) {
            int mid = low + (high - low) / 2;
            // 遇到空字符串，往后遍历
            while(mid > low && "".equals(words[mid])){
                mid--;
            }
            if(words[mid].compareTo(s) == 0) {
                return mid;
            } else if (words[mid].compareTo(s) < 0) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }
}

33.搜索旋转排序数组（中等）无重复数据

二分法

解题思路：

class Solution {
    public int search(int[] nums, int target) {
        int low = 0, high = nums.length - 1;
        while(low <= high) {
            int mid = low + (high - low) / 2;
            if(nums[mid] == target) {
                return mid;
            } else if(nums[mid] > target) {
                // 向右遍历探测有无小于等于target的值
                int i = mid;
                while(i <= high && nums[i] > target) {
                    i++;
                }
                // 右侧找到比target小的值，判断target在不在[i, high] 这个区间
                if(i <= high && nums[i] <= target && nums[high] >= target){
                    low = i;
                } else {
                    high = mid - 1;
                }
            } else {
                // 向左遍历探测有无大于等于target的值
                int i = mid;
                while(i >= low && nums[i] < target) {
                    i--;
                }
                // 左侧找到比target大的值，判断target在不在[low, i] 这个区间内
                if(i >= low && nums[low] <= target && nums[i] >= target) {
                    high = i;
                } else {
                    low = mid + 1;
                }
            }
        }
        return -1;
    }
}

153.寻找旋转排序数组中的最小值（中等）无重复数据

class Solution {
    public int findMin(int[] nums) {
        int low = 0, high = nums.length - 1, size = nums.length;
        if(size== 1) {
            return nums[0];
        }
        while(low <= high) {
            int mid = low + (high - low) / 2;
            if((mid == 0 && nums[mid] < nums[mid + 1]) 
                || (mid == size -1 && nums[mid] < nums[mid - 1]) 
                || (mid > 0 && mid < size - 1 && nums[mid] < nums[mid - 1] && nums[mid] < nums[mid + 1])){
                return nums[mid];
            }
            if(mid < size && nums[mid] < nums[mid + 1]) {
                // 向右探测有无降序元素
                if(nums[high] <= nums[mid]) {
                    low = mid + 1;
                }else {
                    high = mid - 1;
                }
            } else {
                low = mid + 1;
            } 
        }
        return -1;
    }
}

852.山脉数组的峰顶索引（简单）峰值二分

class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int length = arr.length, low = 0, high = length - 1;
        while(low <= high) {
            int mid = low + (high - low) / 2;
            if(mid > 0 && mid < length - 1 && arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1]) {
                return mid;
            }
            if(arr[mid] <= arr[mid + 1]) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }
}

162.寻找峰值（中等）峰值二分

class Solution {
    public int findPeakElement(int[] nums) {
        int low = 0, high = nums.length -1;
        if(nums.length == 1) {
            return 0;
        }
        while(low <= high) {
            int mid = low + (high - low) / 2;
            if((mid == nums.length -1 && nums[mid] > nums[mid - 1]) 
                || (mid == 0 && nums[mid] > nums[mid + 1])
                || (mid > 0 && mid < nums.length - 1 && nums[mid] > nums[mid - 1] && nums[mid] > nums[mid + 1])) {
                return mid;
            }
            if(nums[mid] < nums[mid + 1]) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }
}

367.有效的完全平方数（简单）二分答案

class Solution {
    public boolean isPerfectSquare(int num) {
        long low = 0, high = num;
        while(low <= high) {
            long mid = low + (high - low) / 2;
            // 使用 long 防止溢出
            long sqrt = mid * mid;
            if(sqrt == num) {
                return true;
            } 
            if(sqrt > num) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return false;
    }
}

69. x的平方根（简单）二分答案

二分法

class Solution {
    public int mySqrt(int x) {
        int low = 0, high = x, res = -1;
        while(low <= high) {
            int mid = low + (high - low) / 2;
            if((long)mid * mid <= x) {
                res = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return res;
    }
}

74.搜索二维矩阵（中等）二维转一维，二分查找

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int r = matrix.length, c = matrix[0].length;
        for(int i = 0; i < r; i++) {
            if(target >= matrix[i][0] && target <= matrix[i][c - 1]) {
                return bisection(matrix[i], target);
            }
        }
        return false;
    }
    private boolean bisection(int[] nums, int target) {
        int low = 0, high = nums.length - 1;
        while(low <= high) {
            int mid = low + (high - low) / 2;
            if(nums[mid] == target) {
                return true;
            } else if(nums[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return false;
    }
}

658. 找到 K 个最接近的元素（中等）

二分法+双指针

class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int low = 0, high = arr.length - 1, mid = 0;
        int left = -1, right = -1;
        while(low <= high) {
            mid = low + (high - low) / 2;
            if(arr[mid] == x) {
               left = right = mid; 
               if(mid == 0) {
                   right = k - 1;
               } else if (mid == arr.length -1) {
                   left = mid - k + 1; 
               } else {
                   int[] range = findK(arr, mid, k, x);
                   left = range[0];
                   right = range[1];
               }
               break;
            } else if(arr[mid] < x) {
                low = mid  + 1;
            } else {
                high = mid - 1;
            }
        }
        if(low > high) {
            int[] range = findK(arr, low, k, x);
            left = range[0];
            right = range[1];
        }
        List<Integer> res = new ArrayList<>();
        for(int i = left; i <= right; i++) {
            res.add(arr[i]);
        }
        return res;
    }
    private boolean compare(int[] arr, int a, int b, int x) {
        if(a < 0) {
            return false;
        }
        if(b > arr.length - 1) {
            return true;
        }
        return Math.abs(arr[a] - x) <= Math.abs(arr[b] - x);
    }
    private int[] findK(int[] arr, int mid, int k, int x) {
        int left = Math.max(0, mid - k - 1), right = Math.min(arr.length - 1, mid + k - 1);
        while(right - left > k - 1) {
            if(compare(arr, left, right, x)){
                right--;
            } else {
                left++;
            }
        }
        return new int[]{left, right};
    }
}

875. 爱吃香蕉的珂珂（中等）二分答案

81. 搜索旋转排序数组 II（中等）有重复数据

154. 寻找旋转排序数组中的最小值 II （困难）有重复数据

哈希表

两数之和（简单）

哈希表

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

15.三数之和（中等）

哈希表

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> resList = new ArrayList<>();
        Map<Integer, Integer> map = new HashMap<>();
        Arrays.sort(nums);
        int size = nums.length;
        if(size < 3 || nums[0] > 0) {
            return resList;
        }
        for(int i = 0; i < size; i++) {
            map.put(nums[i], i);
        }
        for(int i = 0; i < size; i++) {
            if(i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            for(int j = i + 1; j < size; j++) {
                if(i != j - 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                int target = -(nums[i] + nums[j]);
                if(map.containsKey(target)) {
                    int idx = map.get(target);
                    if(idx > j) {
                        List<Integer> list = new ArrayList<>();
                        list.add(nums[i]);
                        list.add(nums[j]);
                        list.add(nums[idx]);
                        resList.add(list);
                    }
                }
            }
        }
        return resList;
    }
}

排序+头尾双指针

解题思路：

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        if(nums == null || nums.length < 3 || nums[0] > 0) {
            return result;
        }
        int size = nums.length;
        for(int i = 0; i < size; i++) {
            if(i != 0 && nums[i] == nums[i -1]) {
                continue;
            }
            int target = -nums[i];
            int head = i + 1, tail = size - 1;
            while(head < tail) {
                int sum = nums[head] + nums[tail];
                if((target == sum)) {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[head]);
                    list.add(nums[tail]);
                    result.add(list);
                    head++;
                    tail--;
                    // 去除左侧重复的元素
                    while(head < tail  && nums[head] == nums[head - 1]) {                                                                          
                        head++;
                    }
                    // 去除右侧重复的元素
                    while(head < tail && nums[tail] == nums[tail + 1]){
                        tail--;
                    }
                } else if(sum > target){
                    tail--;
                } else {
                    head++;
                }
            }
        }
        return result;
    }
}

160.相交链表（简单）

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null) {
            return null;
        }
        Map<ListNode, ListNode> map = new HashMap<>();
        ListNode tmp = headA;
        while(tmp != null) {
            map.put(tmp, tmp);
            tmp = tmp.next;
        }
        while(headB != null) {
            if(map.containsKey(headB)) {
                return headB;
            }
            headB = headB.next;
        }
        return headB;
    }
}

141.环形链表（简单）

public class Solution {
    public boolean hasCycle(ListNode head) {
        Map<ListNode, Integer> map = new HashMap<>();
        while(head != null) {
            if(map.containsKey(head)) {
                return true;
            }
            map.put(head, 1);
            head = head.next;
        }
        return false;
    }
}

面试题02.01.移除重复节点（中等）

class Solution {
    public ListNode removeDuplicateNodes(ListNode head) {
        Map<Integer, Boolean> map = new HashMap<>();
        ListNode newHead = new ListNode(-1), tmp = head, pre = newHead;
        newHead.next = tmp;
        while(tmp != null) {
            if(map.containsKey(tmp.val)) {
                pre.next = tmp.next;
                tmp = tmp.next;
                continue;
            }
            map.put(tmp.val, true);
            pre = tmp;
            tmp = tmp.next;
        }
        pre.next = null;
        return head;
    }
}

面试题16.02.单词频率（简单）

class WordsFrequency {
    Map<String, Integer> map;
    public WordsFrequency(String[] book) {
        map = new HashMap<>(book.length);
        for(String val : book) {
            if(map.containsKey(val)) {
                map.put(val, map.get(val) + 1);
            } else {
                map.put(val, 1);
            }
        }
    }
    public int get(String word) {
        if(!map.containsKey(word)) {
            return 0; 
        }
        return map.get(word);
    }
}

面试题01.02.判定是否互为字符重排（简单）

class Solution {
    public boolean CheckPermutation(String s1, String s2) {
        if(s1 == null && s2 == null) {
            return true;
        }
        if(s1.length() != s2.length()) {
            return false;
        }
        Map<Character, Integer> map = new HashMap<>();
        for(int i = 0; i < s1.length(); i++) {
            Character key = s1.charAt(i);
            if(map.containsKey(key)) {
                map.put(key, map.get(key) + 1);
            } else {
                map.put(key, 1);
            }
        }
        for(int i = 0; i < s2.length(); i++) {
             Character key = s2.charAt(i);
             if(!map.containsKey(key)) {
                 return false;
             }
             map.put(key, map.get(key) - 1);
        }
        for(Map.Entry<Character,Integer> entry : map.entrySet()) {
            if(entry.getValue() != 0) {
                return false;
            }
        }
        return true;
    }
}

剑指Offer 03.数组中重复的数字（简单）

哈希表

class Solution {
    public int findRepeatNumber(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int val : nums) {
            if(map.containsKey(val)) {
                return val;
            }
            map.put(val, val);
        }
        return -1;
    }
}

数组原地交换

解题思路：

class Solution {
    public int findRepeatNumber(int[] nums) {
        int i = 0;
        while(i < nums.length) {
            if(nums[i] == i) {
                i++;
                continue;
            }
            if(nums[nums[i]] == nums[i]) {
                return nums[i];
            }
            int t = nums[i];
            nums[i] = nums[t];
            nums[t] = t;
        }
        return -1;
    }
}

时间复杂度：O(n)
空间复杂度：O(1)

242.有效的字母异位词（简单）

哈希表（两个哈希表，减少遍历次数）

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        char[] s1 = s.toCharArray();
        char[] t1 = t.toCharArray();
        char[] counters = new char[26];
        char[] countert = new char[26];
        for (int i = 0; i < s1.length; i++) {
            counters[s1[i] - 'a']++;
            countert[t1[i] - 'a']++;
        }
        for (int i = 0; i < counters.length; i++) {
            if (counters[i] != countert[i]) {
                return false;
            }
        }
        return true;
    }
}

时间复杂度：O(n)
空间复杂度：O(2n) => O(n)

49.字母异位词分组（中等）

哈希表

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> hashMap = new HashMap<>();
        List<List<String>> result = new ArrayList<>();
        for(String str : strs) {
            String key = getKey(str);
            List<String> list = hashMap.getOrDefault(key, new ArrayList<>());
            list.add(str);
            hashMap.put(key, list);
        }
        for(Map.Entry<String, List<String>> entry : hashMap.entrySet()) {
            result.add(entry.getValue());
        }
        return result;
    }
    // 字母异位词的共性：每个字母的个数都是一致的。利用这个特性构造通用的组合key => 字母+出现的次数
    private String getKey(String str) {
        int[] map = new int[26];
        for(int i = 0; i < str.length(); i++) {
            map[str.charAt(i) - 'a']++;
        }
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < map.length; i++) {
            if(map[i] != 0) {
                sb.append((char)(i + 'a')).append(map[i]);
            }
        }
        return sb.toString();        
    }
}

时间复杂度：O(n)
空间度复杂度：O(n)

136.只出现一次的数字（简单）

哈希表

class Solution {
    public int singleNumber(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int val : nums) {
            if(map.containsKey(val)) {
                map.put(val, map.get(val) + 1);
            } else {
                map.put(val, 1);
            }
        }
        for(Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if(entry.getValue() == 1) {
                return entry.getKey();
            }
        }
        return -1;
    }
}

时间复杂度：O(n)
空间复杂度：O(n)

异或运算

class Solution {
    public int singleNumber(int[] nums) {
        // 异或运算
        // 1. 0与任意数 a 异或，其结果都是 a
        // 2. 任意数和自身异或，结果都为 0
        // 3. 异或运算满足交换律和结合律
        int single = 0;
        for(int val : nums) {
            single ^= val;
        }
        return single;
    }
}

时间复杂度：O(n)
空间复杂度：O(1)

349.两个数组的交集（简单）

哈希表

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set = new HashSet<>();
        Set<Integer> resSet = new HashSet<>();
        for(int i = 0; i <nums1.length; i++) {
            set.add(nums1[i]);
        }
        for(int i = 0; i < nums2.length; i++) {
            if(set.contains(nums2[i])) {
                resSet.add(nums2[i]);
            }
        }
        int[] res = new int[resSet.size()];
        int i = 0;
        Iterator<Integer> iterator = resSet.iterator();
        while(iterator.hasNext()) {
            res[i++] = iterator.next();
        }
        return res;
    }
}

1122.数组的相对排序（中等）

哈希表

解题思路：

class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        Map<Integer, Integer> map = new HashMap<>();
        // 初始化 map
        for(int val : arr2) {
            map.put(val, 0);
        }
        // 扫描 arr1 统计 arr2 中每个数字在 arr1 中出现的次数
        for(int val : arr1) {
            if(map.containsKey(val)) {
                int oldCount = map.get(val);
                map.put(val, oldCount + 1);
            }
        }
        int[] result = new int[arr1.length];
        int k = 0;
        for(int key : arr2) {
            int count = map.get(key);
            while(count > 0) {
                result[k++] = key;
                count--;
            }
        }
        Arrays.sort(arr1);
        for(int v : arr1) {
            if(!map.containsKey(v)) {
                result[k++] = v;
            }
        }
        return result;
    }
}

首尾双指针+排序

class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        if(arr1.length == 0 || arr2.length == 0) {
            return arr1;
        }
        int flag = 0;
        for(int i = 0; i < arr2.length; i++) {
            int target = arr2[i];
            int head = flag, tail = arr1.length - 1;
            while(head <= tail) {
                if(arr1[tail] == target) {
                    int t = arr1[tail];
                    arr1[tail] = arr1[head];
                    arr1[head] = t;
                    head++;
                } else {
                    tail--;
                }
            }
            flag = head;
        }
        int[] tmp = Arrays.copyOfRange(arr1, flag, arr1.length);
        Arrays.sort(tmp);
        for(int i = 0; i < tmp.length; i++) {
            arr1[i + flag] = tmp[i];
        }
        return arr1;
    }
}

706.设计哈希映射（简单）

超大数组

class MyHashMap {
    private int[] map;
    /** Initialize your data structure here. */
    public MyHashMap() {
        map = new int[1000001];
        Arrays.fill(map, -1);
    }
    /** value will always be non-negative. */
    public void put(int key, int value) {
        map[key] = value;
    }
    /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
    public int get(int key) {
        return map[key];
    }
    /** Removes the mapping of the specified value key if this map contains a mapping for the key */
    public void remove(int key) {
        map[key] = -1;
    }
}
/**
 * Your MyHashMap object will be instantiated and called as such:
 * MyHashMap obj = new MyHashMap();
 * obj.put(key,value);
 * int param_2 = obj.get(key);
 * obj.remove(key);
 */

链地址法

解题思路：

基于数组实现哈希表
自定义计算hash的函数：取模运算。

基于链地址法解决哈希冲突。 ```java class MyHashMap {

class Node {

 int key;
 int value;
 public Node(int key, int value) {
     this.key = key;
     this.value = value;
 }

}

private int BASE = 769;

private LinkedList[] data;

/* Initialize your data structure here. / public MyHashMap() {

 data = new LinkedList[BASE];

}

/* value will always be non-negative. / public void put(int key, int value) {

 int idx = hash(key);
 if(data[idx] == null) {
     LinkedList<Node> list = new LinkedList<>();
     list.add(new Node(key, value));
     data[idx] = list;
 } else {
     for(Object n : data[idx]) {
         Node node = (Node) n;
         if(node.key == key) {
             node.value = value;
             return;
         }
     }
     data[idx].addLast(new Node(key, value));
 }

}

/* Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key / public int get(int key) {

 int idx = hash(key);
 if(data[idx] == null) {
     return -1;
 }
 for(Object n : data[idx]) {
     Node node = (Node) n;
     if(node.key == key) {
         return node.value;
     }
 }
 return -1;

}

/* Removes the mapping of the specified value key if this map contains a mapping for the key / public void remove(int key) {

 int idx = hash(key);
 if(data[idx] != null) {
     Iterator<Node> it = data[idx].iterator();
     while(it.hasNext()) {
         Node node = it.next();
         if(node.key == key) {
             data[idx].remove(node);
             return;
         }
     }
 }

}

private int hash(int key) {

 return key % BASE;

} }

/**

Your MyHashMap object will be instantiated and called as such:
MyHashMap obj = new MyHashMap();
obj.put(key,value);
int param_2 = obj.get(key);
obj.remove(key); */ ```

146. LRU 缓存机制（中等）标准的LRU

哈希表+双向链表

class LRUCache {
    private static class DLNode {
        int key, value;
        DLNode prev, next;
        public DLNode() {
        }
        public DLNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    private int capacity, size;
    private DLNode head, tail;
    private DLNode[] cache = new DLNode[30001];
    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        head = new DLNode();
        tail = new DLNode();
        head.next = tail;
        tail.prev = head;
    }
    public int get(int key) {
        DLNode node = cache[key];
        if (node == null) {
            return -1;
        }
        removeNode(node);
        insertNode(node);
        return node.value;
    }
    private void removeNode(DLNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    private void insertNode(DLNode node) {
        node.next = head.next;
        head.next.prev = node;
        node.prev = head;
        head.next = node;
    }
    public void put(int key, int value) {
        DLNode node = cache[key];
        if (node == null) {
            insertNode(cache[key] = new DLNode(key, value));
            size++;
            if (size > capacity) {
                DLNode last = tail.prev;
                removeNode(last);
                cache[last.key] = null;
                size--;
            }
        } else {
            node.value = value;
            removeNode(node);
            insertNode(node);
        }
    }
}

面试题16.21.交换和（中等）

class Solution {
    public int[] findSwapValues(int[] array1, int[] array2) {
        // 假设 s1 为 array1 的总和，s2 为 array2 的总和，a 为 array1 要交换的值，b 为 array2 要交换的值
        // s1 - a + b = s2 -b + a => b = (s2 - s1) / 2 + a
        // s2 - s1 为奇数时，则不存在符合的值。
        HashSet<Integer> set = new HashSet<>();
        int s1 = 0, s2 = 0;
        for(int val : array1) {
            s1 += val;
        }
        for(int val : array2) {
            s2 += val;
            set.add(val);
        }
        for(int val : array1) {
            // 
            if(((s2 - s1) & 1) == 1) {
                return new int[0];
            }
            int target = val + (s2 - s1) / 2;
            if(set.contains(target)) {
                return new int[]{val, target};
            }
        }
        return new int[0];
    }
}

二分查找

704.二分查找（简单） 标准二分查找

374.猜数字大小（简单）

744.寻找比目标字母大的最小字母（简单）

35.搜索插入位置（简单）

34.在排序数组中查找元素的第一个和最后一个位置 （中等）

面试题10.05.稀疏数组搜索（简单）

33.搜索旋转排序数组（中等）无重复数据

二分法

153.寻找旋转排序数组中的最小值（中等） 无重复数据

852.山脉数组的峰顶索引（简单）峰值二分

162.寻找峰值（中等）峰值二分

367.有效的完全平方数（简单）二分答案

69. x的平方根（简单）二分答案

二分法

74.搜索二维矩阵（中等） 二维转一维，二分查找

658. 找到 K 个最接近的元素（中等）

二分法+双指针

875. 爱吃香蕉的珂珂（中等）二分答案

81. 搜索旋转排序数组 II（中等）有重复数据

154. 寻找旋转排序数组中的最小值 II （困难） 有重复数据

哈希表

两数之和 （简单）

哈希表

15.三数之和（中等）

哈希表

排序+头尾双指针

160.相交链表（简单）

141.环形链表（简单）

面试题02.01.移除重复节点（中等）

面试题16.02.单词频率 （简单）

面试题01.02.判定是否互为字符重排（简单）

剑指Offer 03.数组中重复的数字 （简单）

哈希表

数组原地交换

242.有效的字母异位词（简单）

哈希表（两个哈希表，减少遍历次数）

49.字母异位词分组（中等）

哈希表

136.只出现一次的数字（简单）

哈希表

异或运算

349.两个数组的交集 （简单）

哈希表

1122.数组的相对排序（中等）

哈希表

首尾双指针+排序

706.设计哈希映射（简单）

超大数组

链地址法

146. LRU 缓存机制 （中等）标准的LRU

哈希表+双向链表

面试题16.21.交换和（中等）

704.二分查找（简单）标准二分查找

34.在排序数组中查找元素的第一个和最后一个位置（中等）

153.寻找旋转排序数组中的最小值（中等）无重复数据

74.搜索二维矩阵（中等）二维转一维，二分查找

154. 寻找旋转排序数组中的最小值 II （困难）有重复数据

两数之和（简单）

面试题16.02.单词频率（简单）

剑指Offer 03.数组中重复的数字（简单）

349.两个数组的交集（简单）

146. LRU 缓存机制（中等）标准的LRU