25. K 个一组翻转链表

206. 反转链表

  1. /**
  2.  * Definition for singly-linked list.
  3.  * public class ListNode {
  4.  *     int val;
  5.  *     ListNode next;
  6.  *     ListNode() {}
  7.  *     ListNode(int val) { this.val = val; }
  8.  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  9.  * }
  10.  */
  11. class Solution {
  12.     public ListNode reverseKGroup(ListNode list, int k) {
  13.         // list可以看作是由若干个包含k个结点的子链表和一个不足k个结点的子链表组成
  14.         ListNode head = new ListNode(); // 1、头结点
  15.         head.next = list;
  16.         ListNode left = head, right = head; // 2、子链表的前驱结点和后继结点
  17.         ListNode start, end; // 3、子链表的首结点与尾结点
  18.         while (true) {
  19.             for (int i = 0; i < k && right != null; i++) { // 4、判断下一个子链表是否包含k个结点
  20.                 right = right.next; // right指向子链表的第1个结点时，i=1
  21.             } // right指向子链表的第k个结点时，i=k，循环结束，但第k个结点未必存在
  22.             if (right == null) { // 下一个子链表不足k个结点，翻转完毕
  23.                 break;
  24.             }
  25.             start = left.next; // 确定首结点
  26.             end = right; // 确定尾结点
  27.             right = right.next; // 确定后继结点
  28.             end.next = null; // 5、将子链表的尾结点与母表断开，以便于翻转
  29.             left.next = reverseList(start); // 6、返回子链表翻转后的首结点，即子链表原来的尾结点
  30.             start.next = right; // 7、将翻转后的子链表的尾结点(即子链表原来的首结点)与母表连接
  31.             left = start; // 确定前驱结点
  32.             right = start; // 8、复位right，以继续翻转下一个子链表
  33.         }
  34.         return head.next;
  35.     }
  37.     public ListNode reverseList(ListNode head) {
  38.         // 1、同时记录相邻的三个结点prev、curr和next，初始时prev为null，curr为head
  39.         // 2、改变curr.next，使其指向prev
  40.         // 3、"滑动窗口"右移一位，prev指向curr，curr指向next，curr不为null时，next指向next.next
  41.         // 4、终止条件是curr为null，即curr指向链表末尾结点的下一个位置时结束
  42.         head = iteration(head); // 方法一：迭代法
  43.         // head = recursion(null, head); // 方法二：递归法
  44.         return head;
  45.     }
  47.     public ListNode iteration(ListNode head) {
  48.         ListNode prev = null;
  49.         ListNode curr = head;
  50.         while (curr != null) {
  51.             ListNode next = curr.next;
  52.             curr.next = prev;
  53.             prev = curr;
  54.             curr = next;
  55.         }
  56.         return prev;
  57.     }
  59.     public ListNode recursion(ListNode prev, ListNode curr) {
  60.         if (curr == null) {
  61.             return prev;
  62.         }
  63.         ListNode next = curr.next;
  64.         curr.next = prev;
  65.         return recursion(curr, next);
  66.     }
  67. }

215. 数组中的第K个最大元素（待补）

  1. class Solution {
  2.     public int findKthLargest(int[] nums, int k) {
  3.         int target = nums.length - k; // 数组排序后第k大元素的位置
  4.         int left = 0;
  5.         int right = nums.length - 1;
  6.         while (true) {
  7.             int index = partition(nums, left, right);
  8.             if (index == target) {
  9.                 return nums[index];
  10.             } else if (index < target) { // 基准位置小于目标位置时，对基准的右侧排序
  11.                 left = index + 1;
  12.             } else { // 基准位置大于目标位置时，对基准的左侧排序
  13.                 right = index - 1;
  14.             }
  15.         }
  16.     }
  18.     public int partition(int[] nums, int left, int right) {
  19.         int pivot = nums[left];
  20.         while (left < right) {
  21.             while (left < right && pivot <= nums[right]) {
  22.                 right--;
  23.             }
  24.             nums[left] = nums[right];
  25.             while (left < right && pivot >= nums[left]) {
  26.                 left++;
  27.             }
  28.             nums[right] = nums[left];
  29.         }
  30.         nums[left] = pivot;
  31.         return left;
  32.     }
  33. }

912. 排序数组（待补）

  1. class Solution {
  2.     public int[] sortArray(int[] nums) {
  3.         bubbleSort(nums); // 冒泡排序
  4.         // quickSort(nums, 0, nums.length - 1); // 快速排序
  5.         // dumpSort(nums); // 堆排序
  6.         return nums;
  7.     }
  9.     public void bubbleSort(int[] nums) {
  10.         for (int i = 1; i < nums.length; i++) {  // 最多进行(arr.length-1)轮冒泡
  11.             boolean flag = false;  // 若本轮有元素交换，则置为true，若本轮结束后仍为false，则说明上一轮过后数组已有序
  12.             for (int j = 0; j < nums.length - i; j++) {
  13.                 if (nums[j] > nums[j + 1]) {  // 稳定排序，O(n2)
  14.                     nums[j] = nums[j] + nums[j + 1];
  15.                     nums[j + 1] = nums[j] - nums[j + 1];
  16.                     nums[j] = nums[j] - nums[j + 1];
  17.                     flag = true;
  18.                 }
  19.             }
  20.             if (!flag) {
  21.                 break;
  22.             }
  23.         }
  24.     }
  26.     public void quickSort(int[] nums, int left, int right) {
  27.         if (left < right) {
  28.             // 最理想的划分是平均划分O(nlog2(n))，即分成两个规模为n/2的问题，最差划分是最大程度的不对称划分O(n2)，即排序表基本有序或基本无序
  29.             int pivot = partition(nums, left, right); // pivot：基准、支点、枢轴、中心点
  30.             quickSort(nums, left, pivot - 1);
  31.             quickSort(nums, pivot + 1, right);
  32.         }
  33.     }
  35.     public int partition(int[] nums, int left, int right) {
  36.         int pivot = nums[left]; // 直接取首元素为基准，即严蔚敏教材的算法，也可以随机选取基准以尽量避免最差的划分，此时称为随机快速排序
  37.         while (left < right) {
  38.             while (left < right && pivot <= nums[right]) { // 必须是<=和>=，如果是<和>，那么当首尾元素等大时，会陷入死循环
  39.                 right--;
  40.             }
  41.             nums[left] = nums[right]; // 将小于基准的元素与基准交换位置
  42.             while (left < right && pivot >= nums[left]) { // 快排不稳定，比如{2,1,2,1}
  43.                 left++;
  44.             }
  45.             nums[right] = nums[left]; // 将大于基准的元素与基准交换位置
  46.         }
  47.         nums[left] = pivot; // 将基准放在它的最终位置上
  48.         return left; // 返回基准的最终位置，该位置左侧的元素均 ≤ 基准，该位置右侧的元素均 ≥ 基准
  49.     }
  51.     public void dumpSort(int[] nums) {
  53.     }
  54. }

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

  1. class Solution {
  2.     public int lengthOfLongestSubstring(String s) {
  3.         HashMap<Character, Integer> hashMap = new HashMap<>(); // key为s中的字符，value是字符在s中的最新位置
  4.         int len = s.length();
  5.         int maxLen = 0;
  6.         int start = 0;
  7.         for (int end = 0; end < len; end++) { // [start,end]为不重复子串
  8.             char c = s.charAt(end);
  9.             if (hashMap.containsKey(c)) {
  10.                 // start = map.get() + 1; // 输入"abba"时出错，即start指针不能往回走，必须一直向后走
  11.                 start = Math.max(hashMap.get(c) + 1, start); // 前一个重复字符的下一个位置是新的不重复子串的起始位置
  12.             }
  13.             maxLen = Math.max(maxLen, end - start + 1);
  14.             hashMap.put(c, end);  // 利用put()的覆盖写性质，巧妙地从映射表中“除去了”前一个重复字符
  15.             // map中会冗余存储开头的一部分字符，但除了这些冗余，其他字符都是新的不重复子串的字符
  16.         }
  17.         return maxLen;
  18.     }
  19. }

146. LRU 缓存

  1. /**
  2.  * Your LRUCache object will be instantiated and called as such:
  3.  * LRUCache obj = new LRUCache(capacity);
  4.  * int param_1 = obj.get(key);
  5.  * obj.put(key,value);
  6.  */
  7. class LRUCache {
  8.     class DLinkedNode { // 双向链表，实现LRU(Least Recently Used，最近最少使用)
  9.         int k;
  10.         int v;
  11.         DLinkedNode prev;
  12.         DLinkedNode next;
  14.         public DLinkedNode() {
  15.         }
  17.         public DLinkedNode(int key, int value) {
  18.             k = key;
  19.             v = value;
  20.         }
  21.     }
  23.     private HashMap<Integer, DLinkedNode> cache = new HashMap<>(); // 哈希表，使存取复杂度为O(1)
  24.     private int capacity; // 容量
  25.     private int size = 0; // 大小
  26.     private DLinkedNode head = new DLinkedNode(); // 头结点，不保存数据
  27.     private DLinkedNode tail = new DLinkedNode(); // 尾结点，不保存数据
  29.     public LRUCache(int capacity) {
  30.         this.capacity = capacity;
  31.         head.next = tail; // 初始时首尾相连
  32.         tail.prev = head;
  33.     }
  35.     public int get(int key) {
  36.         DLinkedNode node = cache.get(key);
  37.         if (node == null) { // key不存在于缓存中，返回-1
  38.             return -1;
  39.         } else { // key存在于缓存中，返回其值
  40.             removeNode(node); // 先将最近访问结点从链表中删除
  41.             addToHead(node); // 再将最近访问结点移至链表首部
  42.             return node.v;
  43.         }
  44.     }
  46.     public void put(int key, int value) {
  47.         DLinkedNode node = cache.get(key);
  48.         if (node == null) { // key不存在于缓存中，新增结点
  49.             node = new DLinkedNode(key, value);
  50.             cache.put(key, node);
  51.             addToHead(node); // 新增结点也是最近访问结点，将其移至链表首部
  52.             if (size > capacity) { // LRU缓存的大小达到容量上限，删除最近最少使用结点
  53.                 cache.remove(tail.prev.k);
  54.                 removeNode(tail.prev);
  55.             }
  56.         } else { // key存在于缓存中，更新其值
  57.             node.v = value;
  58.             removeNode(node);
  59.             addToHead(node);
  60.         }
  61.     }
  63.     private void removeNode(DLinkedNode node) {
  64.         node.prev.next = node.next;
  65.         node.next.prev = node.prev;
  66.         size--;
  67.     }
  69.     private void addToHead(DLinkedNode node) {
  70.         node.prev = head;
  71.         node.next = head.next;
  72.         head.next.prev = node;
  73.         head.next = node;
  74.         size++;
  75.     }
  76. }
  1. class LRUCache extends LinkedHashMap<Integer, Integer> {
  2.     private int capacity;
  4.     public LRUCache(int capacity) {
  5.         super(capacity, 0.75F, true);
  6.         this.capacity = capacity;
  7.     }
  9.     public int get(int key) {
  10.         return super.getOrDefault(key, -1);
  11.     }
  13.     public void put(int key, int value) {
  14.         super.put(key, value);
  15.     }
  17.     @Override
  18.     protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
  19.         return size() > capacity;
  20.     }
  21. }

image.png
image.png
image.png