206. 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

package com.jiawei.WeekOne;

import com.jiawei.Utils.ListNode;

public class ReverseList {
  public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
      ListNode next = curr.next;
      curr.next = prev;
      prev = curr;
      curr = next;
    }
    return prev;
  }
}

吐槽一句，至今觉得用java写链表这件事十分阴间，底层基本实现的功能还要为了手写而手写，很难受

146. LRU 缓存

请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该逐出最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

// 以下代码是借鉴的b17a大佬的，我自己拿着第一反应就是直接继承LinkedHashMap，但是面试肯定不能这么写，所以学大佬重写了底层
package com.jiawei.WeekOne;

import java.util.HashMap;
import java.util.Map;

public class LRUCache {
  class DLinkedNode {
    int key;
    int value;
    DLinkedNode prev;
    DLinkedNode next;

    public DLinkedNode() {}

    public DLinkedNode(int _key, int _value) {
      key = _key;
      value = _value;
    }
  }

  private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>();
  private int size;
  private int capacity;
  private DLinkedNode head, tail;

  public LRUCache(int capacity) {
    this.size = 0;
    this.capacity = capacity;
    // 使用伪头部和伪尾部节点
    head = new DLinkedNode();
    tail = new DLinkedNode();
    head.next = tail;
    tail.prev = head;
  }

  public int get(int key) {
    DLinkedNode node = cache.get(key);
    if (node == null) {
      return -1;
    }
    // 如果 key 存在，先通过哈希表定位，再移到头部
    moveToHead(node);
    return node.value;
  }

  public void put(int key, int value) {
    DLinkedNode node = cache.get(key);
    if (node == null) {
      // 如果 key 不存在，创建一个新的节点
      DLinkedNode newNode = new DLinkedNode(key, value);
      // 添加进哈希表
      cache.put(key, newNode);
      // 添加至双向链表的头部
      addToHead(newNode);
      ++size;
      if (size > capacity) {
        // 如果超出容量，删除双向链表的尾部节点
        DLinkedNode tail = removeTail();
        // 删除哈希表中对应的项
        cache.remove(tail.key);
        --size;
      }
    } else {
      // 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
      node.value = value;
      moveToHead(node);
    }
  }

  private void addToHead(DLinkedNode node) {
    node.prev = head;
    node.next = head.next;
    head.next.prev = node;
    head.next = node;
  }

  private void removeNode(DLinkedNode node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }

  private void moveToHead(DLinkedNode node) {
    removeNode(node);
    addToHead(node);
  }

  private DLinkedNode removeTail() {
    DLinkedNode res = tail.prev;
    removeNode(res);
    return res;
  }
}

3. 无重复字符的最长子串

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

//没啥好说的，HashSet来做，类似的移动窗口都可以写
package com.jiawei.WeekOne;

import java.util.HashSet;
import java.util.Set;

public class LengthOfLongestSubstring {
  public static int lengthOfLongestSubstring(String s) {
    Set<Character> occ = new HashSet<Character>();
    int n = s.length();
    int rk = -1, ans = 0;
    for (int i = 0; i < n; ++i) {
      if (i != 0) {
        occ.remove(s.charAt(i - 1));
      }
      while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
        occ.add(s.charAt(rk + 1));
        ++rk;
      }
      ans = Math.max(ans, rk - i + 1);
    }
    return ans;
  }

  public static void main(String[] args) {
    String s = "abcabcbb";
    System.out.println("最长无重复字串长度为：" + lengthOfLongestSubstring(s));
  }
}

215. 数组中的第K个最大元素

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

// 我的评价是，谁用sort函数谁就能承包面试官今日份笑点，人面试官又不傻，来你这看你调包呢
// 两个函数，冒泡不需要建树之类的操作，偷懒专用，但是时间复杂度相对高，堆排序是标答
package com.jiawei.WeekOne;

class FindKthLargest {
  public static int findKthLargest(int[] nums, int k) {
    int tmp;
    for (int i = 0; i < k; i++) {
      for (int j = 0; j < nums.length - i - 1; j++) {
        if (nums[j] > nums[j + 1]) {
          tmp = nums[j];
          nums[j] = nums[j + 1];
          nums[j + 1] = tmp;
        }
      }
    }
    return nums[nums.length - k];
  }

  public static int findKthLargestHeap(int[] nums, int k) {
    int heapSize = nums.length;
    buildMaxHeap(nums, heapSize);
    // 建堆完毕后，nums【0】为最大元素。逐个删除堆顶元素，直到删除了k-1个。
    for (int i = nums.length - 1; i >= nums.length - k + 1; --i) {
      // 先将堆的最后一个元素与堆顶元素交换，由于此时堆的性质被破坏，需对此时的根节点进行向下调整操作。
      swap(nums, 0, i);
      // 相当于删除堆顶元素，此时长度变为nums.length-2。即下次循环的i
      --heapSize;
      maxHeapify(nums, 0, heapSize);
    }
    return nums[0];
  }

  public static void buildMaxHeap(int[] a, int heapSize) {
    // 从最后一个父节点位置开始调整每一个节点的子树。数组长度为heasize，因此最后一个节点的位置为heapsize-1，所以父节点的位置为heapsize-1-1/2。
    for (int i = (heapSize - 2) / 2; i >= 0; --i) {
      maxHeapify(a, i, heapSize);
    }
  }

  public static void maxHeapify(int[] a, int i, int heapSize) { // 调整当前结点和子节点的顺序。
    // left和right表示当前父节点i的两个左右子节点。
    int left = i * 2 + 1, right = i * 2 + 2, largest = i;
    // 如果左子点在数组内，且比当前父节点大，则将最大值的指针指向左子点。
    if (left < heapSize && a[left] > a[largest]) {
      largest = left;
    }
    // 如果右子点在数组内，且比当前父节点大，则将最大值的指针指向右子点。
    if (right < heapSize && a[right] > a[largest]) {
      largest = right;
    }
    // 如果最大值的指针不是父节点，则交换父节点和当前最大值指针指向的子节点。
    if (largest != i) {
      swap(a, i, largest);
      // 由于交换了父节点和子节点，因此可能对子节点的子树造成影响，所以对子节点的子树进行调整。
      maxHeapify(a, largest, heapSize);
    }
  }

  public static void swap(int[] a, int i, int j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
  }

  public static void main(String[] args) {
    int nums[] = {3, 2, 1, 5, 6, 4};
    System.out.println(findKthLargestHeap(nums, 4));
  }
}