Top 热题

2020年8月份左右
25.链表k个一组反转
3.无重复字符的最长子串
206.反转链表
92.反转链表 II
215.数组中的第K个最大元素

2. 字符串

无重复字符的最长子串

Nr.3
给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。

示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

解题思路:

利用哈希表记录每个出现的字符以其下标，当遇到重复的字符时，先判断重复的字符是否在left左指针的范围内，如果在，left更新到以前重复字符的下一个位置，如果不在，更新重复字符在哈希表中的下标记录，每次比较最大长度。

比如字符串:"abcddbcefga",当遍历到第二个d的时候，left此时在index=0的位置，查表可知被重复的d在index=3，因此left更新到index+1=4的位置，之前的长度到4，是目前最长的；
d在哈希表中更新到4，并开始继续遍历，长度并随之回归到1，之后遇到重复的'b','c','a'都会因为
没有大于left，而不会产生影响, 最终返回长度7(dcbcefga)。

代码:

public static int lengthOfLangestSubString( String str) {
if (str==null || str.length()==0){
    return 0;
}
// 左指针
int left = 0;
int maxLength = 0;
// 字母记录表
HashMap<Character, Integer> CharMap = new HashMap<>();
// 遍历字母
for(int i=0; i<str.length(); i++){
    // 如果有重复的字符，如果是在当前的有效区间内，则更新left
    // 比如: abcddbcdefga 最后一个a，是在哈希表中重复的，如果不判断会导致left更新到2
    if (CharMap.containsKey(str.charAt(i)) && CharMap.get(str.charAt(i)) >= left){
        left = CharMap.get(str.charAt(i)) + 1;
    }
    // 添加新的字符，更新他们的value
    CharMap.put(str.charAt(i), i);
    maxLength = Math.max(maxLength, i-left+1);
}

3.排序

数组的Top-Kth元素

Nr.215
题目描述:

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

解法1: 基于堆排序的选择方法
我们也可以使用堆排序来解决这个问题：建立一个大根堆，做K-1次删除操作后堆顶元素就是我们要找的答案。
或者建立一个容积为K的小根堆，然后再遍历数组，如果比堆顶元素大，则把大的数和堆顶替换掉，这个小根堆的堆顶是这个K个数中最小的，但这个堆也是所有数中最大的K个，因此堆顶就是第K大元素。

public static int findKthLargest(int[] arr, int k){
    if (k<0 || k>arr.length){
        throw new IllegalArgumentException("输入K错误");
    }
    PriorityQueue<Integer> minHeap = new PriorityQueue<>(k, new AscendingComparator());
    for (int i=0; i<k; i++){
        minHeap.offer(arr[i]);
    }
    for (int i=k; i<arr.length; i++){
        if (arr[i] > minHeap.peek()){
            minHeap.poll();
            minHeap.offer(arr[i]);
        }
    }
    return minHeap.peek();
}

也可以自己建立堆结构，进行维护和堆操作

public static void swap (int[] arr, int i, int j){
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
// 解法一： 构建小根堆，再一次遍历数组，比堆顶元素大，就添加更新，最后小根堆里面保存了最大的K个数，堆顶恰好是Kth大数
public static void heapInsert_min(int[] arr, int index){
    // 停止更新时，比父节点大；或者已经是堆顶元素了
    while(arr[index] < arr[(index-1)/2]){
        swap(arr, index, (index-1)/2);
        index = (index-1)/2;
    }
}

public static void heapify_min(int[] arr, int cur, int heapSize){
    // 把数组的第一个元素被更换，从cur=0开始，重新堆化，有效区不变
    int left = 2 * cur + 1;
    // left+1 和 left都是下标，最大不能超过heapSize-1
    while(left < heapSize){
        int smaller = ((left + 1)<heapSize && arr[left] > arr[left+1]) ? left+1 : left;
        if (arr[cur] < arr[smaller]) {
            break;
        }
        swap(arr, cur, smaller);
        cur = smaller;
        left = 2 * cur + 1;
    }
}

public static void main(String[] args) {
    int [] arr = {3, 2, 1, 5, 6, 4};
    int k = 2;
    // 方法一: 小根堆
    int[] minHeap = Arrays.copyOf(arr, k);
    for (int i=0; i<k; i++) {
        heapInsert_min(minHeap, i);
    }
    for (int i=k; i<arr.length; i++) {
        if (minHeap[0] < arr[i]) {
            minHeap[0] = arr[i];
            heapify_min(minHeap, 0, minHeap.length);
        }
    }
    System.out.println("第二大的元素是: " + minHeap[0]);
}

4. 堆与栈

有效的括号

Nr.20
题目链接
类似的题目有三道，链接
题目描述:
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

题目解析:

栈先入后出特点恰好与本题括号排序特点一致，即若遇到左括号入栈，遇到右括号时将对应栈顶左括号出栈，则遍历完所有括号后 stack 仍然为空；
建立哈希表 dic 构建左右括号对应关系：key左括号，value右括号；这样查询 2 个括号是否对应只需 O(1) 时间复杂度；
建立栈 stack，遍历字符串 s 并按照算法流程一一判断。

算法流程:

如果 c 是左括号，则入栈 pushpush；
否则通过哈希表判断括号对应关系，若 stack 栈顶出栈括号stack.pop()与当前遍历括号c不对应，则提前返回false。

解决边界问题：

// 逻辑表达式有短路功能，若第一个为true，栈为空，第二个不会再判断
// 若第一个为false，要判断第二个条件，此时就有前提条件，栈不为空了
if(myStack.isEmpty() || myMap.get(myStack.pop())!=c){
    return false;
}

复杂度分析:
时间复杂度 O(N)：正确的括号组合需要遍历；
空间复杂度 O(N)：哈希表和栈使用线性的空间大小。

代码:

public boolean isValid(String s) {
    // 建立哈希表
    HashMap<Character, Character> myMap = new HashMap<Character, Character>();
    myMap.put('(', ')');
    myMap.put('{', '}');
    myMap.put('[', ']');
    // 利用辅助栈
    Stack<Character> myStack = new Stack<>();
    // 遍历字符串
    for(int i=0; i<s.length(); i++){
        // 当前字符
        char c = s.charAt(i);
        // 判断当前字符是否是开括号，如果是则入栈
        if(myMap.containsKey(c)){
            myStack.push(c);
        }else{
            // 如果闭括号，则判断此时栈是否为空，若为空则返回false
            // 若不为空，则判断弹出字符是否是开括号(栈顶元素)所对应的闭括号
            if(myStack.isEmpty() || myMap.get(myStack.pop())!=c){
                return false;
            }

            //也可以这样写
            if(myStack.isEmpty()){
                    return false;
            }
            if(myMap.get(myStack.pop())!=c){
                    return false;
            }
        }
    }
    // 最后判断栈是否为空
    return myStack.isEmpty();

}