哈希表

两数之和

给一个整数数组，找到两个数使得他们的和等于一个给定的数 target。需要实现的函数twoSum需要返回这两个数的下标。

用一个hashmap来记录，key记录target-numbers[i]的值，value记录numbers[i]的i的值，如果碰到一个 numbers[j]在hashmap中存在，那么说明前面的某个numbers[i]和numbers[j]的和为target，i和j即为答案

public int[] twoSum(int[] numbers, int target) {

    HashMap<Integer,Integer> map = new HashMap<>();

    for (int i = 0; i < numbers.length; i++) {
        if (map.containsKey(numbers[i])) {
            return new int[]{map.get(numbers[i]), i};
        }
        map.put(target - numbers[i], i);
    }

    return new int[]{};
}

异位词

string 转 []byte 排序 []byte 存储 map key 是排序后的 value 是原来的

连续数组

给一个二进制数组，找到 0 和 1 数量相等的子数组的最大长度

使用一个数字sum维护到i为止1的数量与0的数量的差值。在loop i的同时维护sum并将其插入hashmap中。对于某一个sum值，若hashmap中已有这个值，则当前的i与sum上一次出现的位置之间的序列0的数量与1的数量相同。

public int findMaxLength(int[] nums) {
    Map<Integer, Integer> prefix = new HashMap<>();
    int sum = 0;
    int max = 0;
    prefix.put(0, -1); // 当第一个0 1数量相等的情况出现时，数组下标减去-1得到正确的长度
    for (int i = 0; i < nums.length; i++) {
        int num = nums[i];
        if (num == 0) {
            sum--;
        } else {
            sum++;
        }
        
        if (prefix.containsKey(sum)) {
            max = Math.max(max, i - prefix.get(sum));
        } else {
            prefix.put(sum, i);
        }
    }
    
    return max;
}

最长无重复字符的子串

用HashMap记录每一个字母出现的位置。设定一个左边界, 到当前枚举到的位置之间的字符串为不含重复字符的子串。若新碰到的字符的上一次的位置在左边界右边, 则需要向右移动左边界

public int lengthOfLongestSubstring(String s) {
    if (s == null || s.length() == 0) {
        return 0;
    }
    HashMap<Character, Integer> map = new HashMap<>();
    int max = Integer.MIN_VALUE;
    int start = -1; // 计算无重复字符子串开始的位置
    int current = 0;
    for (int i = 0; i < s.length(); i++) {
        if (map.containsKey(s.charAt(i))) {
            int tmp = map.get(s.charAt(i));
            if (tmp >= start) { // 上一次的位置在左边界右边, 则需要向右移动左边界
                start = tmp;
            }
        } 
        
        map.put(s.charAt(i), i);
        max = Math.max(max, i - start);
    }
    return max;
}

最多点在一条直线上

给出二维平面上的n个点，求最多有多少点在同一条直线上

class Point {
    int x;
    int y;
    Point() { 
        x = 0; y = 0; 
    }
    Point(int a, int b) { 
        x = a; y = b; 
    }
}

通过HashMap记录下两个点之间的斜率相同出现的次数，注意考虑点重合的情况

public int maxPoints(Point[] points) {
    if (points == null) {
        return 0;
    }
    
    int max = 0;
    for (int i = 0; i < points.length; i++) {
        Map<Double, Integer> map = new HashMap<>();
        int maxPoints = 0;
        int overlap = 0;
        for (int j = i + 1; j < points.length; j++) {
            if (points[i].x == points[j].x && points[i].y == points[j].y) {
                overlap++; // 两个点重合的情况记录下来
                continue;
            }
            double rate = (double)(points[i].y - points[j].y) / (points[i].x - points[j].x);
            if (map.containsKey(rate)) {
                map.put(rate, map.get(rate) + 1);
            } else {
                map.put(rate, 2);
            }
            maxPoints = Math.max(maxPoints, map.get(rate));
        }
        if (maxPoints == 0) maxPoints = 1;
        max = Math.max(max, maxPoints + overlap);
    }
    return max;
}

堆 / 优先队列

前K大的数

// 维护一个 PriorityQueue，以返回前K的数
public int[] topk(int[] nums, int k) {
    int[] result = new int[k];
    if (nums == null || nums.length < k) {
        return result;
    }
    
    Queue<Integer> pq = new PriorityQueue<>();
    for (int num : nums) {
        pq.add(num);
        if (pq.size() > k) {
            pq.poll();
        }
    }
    
    for (int i = k - 1; i >= 0; i--) {
        result[i] = pq.poll(); 
    }
    
    return result;
}

前K大的数II

实现一个数据结构，提供下面两个接口：1.add(number) 添加一个元素 2.topk() 返回前K大的数

public class Solution {
    private int maxSize;
    private Queue<Integer> minheap;
    public Solution(int k) {
        minheap = new PriorityQueue<>();
        maxSize = k;
    }

    public void add(int num) {
        if (minheap.size() < maxSize) {
            minheap.offer(num);
            return;
        }
        
        if (num > minheap.peek()) {
            minheap.poll();
            minheap.offer(num);
        }
    }

    public List<Integer> topk() {
        Iterator it = minheap.iterator();
        List<Integer> result = new ArrayList<Integer>();
        while (it.hasNext()) {
            result.add((Integer) it.next());
        }
        Collections.sort(result, Collections.reverseOrder());
        return result;
    }
}

第K大的数

public int kthLargestElement(int k, int[] nums) {
    if (nums == null || nums.length == 0 || k < 1 || k > nums.length){
        return -1;
    }
    return partition(nums, 0, nums.length - 1, nums.length - k);
}

private int partition(int[] nums, int start, int end, int k) {
    if (start >= end) {
        return nums[k];
    }
    
    int left = start, right = end;
    int pivot = nums[(start + end) / 2];
    
    while (left <= right) {
        while (left <= right && nums[left] < pivot) {
            left++;
        }
        while (left <= right && nums[right] > pivot) {
            right--;
        }
        if (left <= right) {
            swap(nums, left, right);
            left++;
            right--;
        }
    }
    
    if (k <= right) {
        return partition(nums, start, right, k);
    }
    if (k >= left) {
        return partition(nums, left, end, k);
    }
    return nums[k];
}    

private void swap(int[] nums, int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}