剑指 Offer 41.数据流中的中位数">1、剑指 Offer 41.数据流中的中位数
剑指 Offer 59 - I.滑动窗口的最大值">2、剑指 Offer 59 - I.滑动窗口的最大值
剑指 Offer 16. 数值的整数次方">3、剑指 Offer 16. 数值的整数次方
48. 旋转图像">4、48. 旋转图像
22. 括号生成">5、22. 括号生成
406. 根据身高重建队列">6、406. 根据身高重建队列
240. 搜索二维矩阵 II">7、240. 搜索二维矩阵 II
146. LRU 缓存">8、146. LRU 缓存

1、剑指 Offer 41.数据流中的中位数

2、剑指 Offer 59 - I.滑动窗口的最大值

2.1 题目

给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
示例:

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3 输出: [3,3,5,5,6,7] 解释: 滑动窗口的位置最大值

[1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7

2.2 思路

题目是用到了单调队列实现O（1）时间复杂度求最大值，特别注意滑动窗口left是从1 - k开始滑动，left的起始位置是数组外面，即要保证right是从0开始滑动的。
算法流程：

初始化：双端队列 queue，结果数组 res；

滑动窗口：左边界left的范围是[1- k, nums.length - k] ，右边界right范围是[0, nums.length - 1]；

若 left > 0 且队列queue的首元素 == 被删除元素 nums[left - 1]，则队首元素出队；
删除 queue 内所有 < nums[right] 的元素，以保持队列queue的单调递减；
将 nums[right] 添加至 qeque 尾部；
若已形成窗口（即 left >= 0 ），将窗口最大值（即队列queue首元素）添加至res ；

返回值：返回结果数组 res 。

2.3 代码

class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
  if (nums.length == 0 || k == 0) {
      return new int[0];
  }
  int[] res = new int[nums.length - k + 1];
  // 单调递减队列。res值为每次循环的队列首元素
  LinkedList<Integer> queue = new LinkedList<>();
  for (int right = 0, left = 1 - k; right < nums.length; ++left, ++right) {
      if (left > 0 && queue.peekFirst() == nums[left - 1]) {
          queue.pollFirst();
      }
      while (!queue.isEmpty() && queue.peekLast() < nums[right]) {
          queue.pollLast();
      }
      queue.addLast(nums[right]);
      if (left >= 0) {
          res[left] = queue.peekFirst();
      }
  }
  return res;
}
}

3、剑指 Offer 16. 数值的整数次方

快速幂，真难顶。

3.1 题目

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。
示例 1：

输入：x = 2.00000, n = 10 输出：1024.00000

示例 2：

输入：x = 2.10000, n = 3 输出：9.26100

示例 3：

输入：x = 2.00000, n = -2 输出：0.25000 解释：2-2 = 1/22 = 1/4 = 0.25

3.2 思路

二分法的应用，需要注意一点是n是负数的情况。

3.3 代码

class Solution {
    public double myPow(double x, int n) {
        return n > 0? quick(x, n): 1 / quick(x, n);
    }
    private double quick(double x, int n) {
        if (n == 0) {
            return 1.0;
        }
        double y = quick(x, n / 2);
        return (n & 1) == 0? y * y: y * y * x;
    }
}

4、48. 旋转图像

4.1 题目

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。

4.2 思路

本题必须在原数组上操作，即原地旋转图像。

求矩阵的转置matrixT（注意第二层循环的起始值为j = i）；

沿Y轴对称交换matrixT的列。

4.3 代码

class Solution {
 public void rotate(int[][] matrix) {
     int m = matrix.length, n = matrix[0].length;
     // 求matrix的转置
     for (int i = 0; i < m; ++i) {
         for (int j = i; j < n; ++j) {
             int tmp = matrix[i][j];
             matrix[i][j] = matrix[j][i];
             matrix[j][i] = tmp;
         }
     }
     // y轴镜像交换转置矩阵的列
     int left = 0, right = n - 1;
     while (left < right) {
         for (int i = 0; i < m; ++i) {
             int tmp = matrix[i][left];
             matrix[i][left] = matrix[i][right];
             matrix[i][right] = tmp;
         }
         ++left;
         --right;
     }
 }
}

5、22. 括号生成

5.1 题目

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。
示例 1：

输入：n = 3 输出：[“((()))”,”(()())”,”(())()”,”()(())”,”()()()”]

示例 2：

输入：n = 1 输出：[“()”]

5.2 思路

看上去像回溯，本地用递归……

指定两个变量：
1. leftRemain：剩余左括号数目；
2. rightRemain：剩余右括号数目；

符合要求的字符串，左括号出现的数目=右括号出现的数目=n，只是左括号和右括号出现的顺序有限制。

当leftRemain == 0且rightRemain ==0时，代表符合要求的字符串已出现，此时添加到res，并return；
当leftRemain == rightRemain 时，此时只能添加左括号；
当leftRemain < rightRemain 时，此时有两种情况：
1. 如果还有剩余左括号，添加左括号；
2. 如果没有剩余左括号，添加右括号。
  
  这两种情况都要搜索到，因此不是if-else的关系。
不存在leftRemain > rightRemain 的场景，因为此时已用左括号数目 < 已用右括号数目，这种字符串不是符合要求的字符串，前面的递归如果正确，后面运行到这里是不会允许这种情况出现的。

5.3 代码
```
class Solution {
 private List<String> res = new ArrayList<>();
 public List<String> generateParenthesis(int n) {
     if (n <= 0) {
         return res;
     }
     helper("", n, n);
     return res;
 }
 private void helper(String str, int leftRemain, int rightRemain) {
     if (leftRemain == 0 && rightRemain == 0) {
         res.add(str);
         return;
     }
     // 当剩余左括号数目等于剩余右括号数目时，只能添加左括号
     if (leftRemain == rightRemain) {
         helper(str + "(", leftRemain - 1, rightRemain);
     }
     // 当剩余左括号数目小于剩余右括号数目时，可以添加左括号，也可以添加右括号
     if (leftRemain < rightRemain) {
         // 当还有剩余左括号时，先尝试添加左括号
         if (leftRemain > 0) {
             helper(str + "(", leftRemain - 1, rightRemain);
         }
         // 当剩余左括号用完时，再尝试添加右括号
         helper(str + ")", leftRemain, rightRemain - 1);
     }
 }
}
```
6、406. 根据身高重建队列
妙啊，最好记住答案…….

6.1 题目
假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面正好有 ki 个身高大于或等于 hi 的人。
请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。
示例 1：

输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]] 输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 解释：编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。

示例 2：

输入：people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]] 输出：[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]

6.2 思路

对people数组，先按照hi降序排序，再按照ki升序排序；

遍历重新排序后的people数组，依据people数组中的每个元素的ki，插入到结果list中，注意ki即元素插入到list中的下标。

6.3 代码

class Solution {
 public int[][] reconstructQueue(int[][] people) {
     List<int[]> res = new ArrayList<>();
     Arrays.sort(people, (o1, o2) -> o1[0] == o2[0]? o1[1] - o2[1]: o2[0] - o1[0]);
     for (int[] p: people) {
         res.add(p[1], p);
     }
     return res.toArray(new int[people.length][2]);
 }
}

7、240. 搜索二维矩阵 II

7.1 题目

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

每行的元素从左到右升序排列；
每列的元素从上到下升序排列。

7.2 思路

该题有一种固定解法：

从矩阵的左下角或者右上角作为搜索起点；
当matrix[i][j] > target，则向上搜索一格；
当matrix[i][j] < target，则向右搜索一格；
当matrix[i][j] = target，则返回true；

跳出while循环，则返回false。

7.3 代码

class Solution {
 public boolean searchMatrix(int[][] matrix, int target) {
     int m = matrix.length;
     int n = matrix[0].length;
     int i = m - 1, j = 0;
     while (i >= 0 && i < m && j >= 0 && j < n) {
         if (matrix[i][j] > target) {
             --i;
         } else if (matrix[i][j] < target) {
             ++j;
         } else {
             return true;
         }
     }
     return false;
 }
}

8、146. LRU 缓存

好题！

8.1 题目

请你设计并实现一个满足 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) 的平均时间复杂度运行。
示例：

输入 [“LRUCache”, “put”, “put”, “get”, “put”, “get”, “put”, “get”, “get”, “get”] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]] 输出 [null, null, null, 1, null, -1, null, -1, 3, 4] 解释 LRUCache lRUCache = new LRUCache(2); lRUCache.put(1, 1); // 缓存是 {1=1} lRUCache.put(2, 2); // 缓存是 {1=1, 2=2} lRUCache.get(1); // 返回 1 lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3} lRUCache.get(2); // 返回 -1 (未找到) lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3} lRUCache.get(1); // 返回 -1 (未找到) lRUCache.get(3); // 返回 3 lRUCache.get(4); // 返回 4

8.2 思路

本题有两种思路：

直接使用jdk中封装好的实现了LRU缓存的数据结构：LinkedHashMap，覆写removeEldestEntry方法，将触发LRU缓存的时机和逻辑在这个方法中实现，注意题目中触发LRU的场景是如果插入操作导致关键字数量超过初始容量capacity，则应该逐出最久未使用的关键字；面试官肯定不希望这种解法；
自己定义一个数据结构实现LRU，HashMap + 双向链表。

主要介绍一下第二种解法：

由于get的时间复杂度为O(1)，因此可以引入一个hashMap，从这个map里获取value（map的get方法时间复杂度为O(1))，map的key存放LRU数据结构的key，value存放key对应的双向链表中的node）；
由于put的时间复杂度为O(1)，因此：
1. 不能使用数组，因为数组插入删除会伴随数组中元素的移动，时间复杂度不满足O(1)；
2. 由于插入删除的时间复杂度为O(1)，可以考虑链表，但不能使用单链表，因为单链表的删除操作需要维护一个pre指针，因此使用双向链表；
双向链表是由内部类DLinkedNode的实例组成，在DLinkedNode类里，定义pre和next指针，同时维护key和value；
这里需要注意一个链表题目的小技巧：由于链表在头节点和尾节点做插入和删除操作时需要考虑左和右边是否为null，而在链表中间做插入和删除操作则无需考虑这些，为了统一处理，生成一个仅有指针，没有k-v的伪头节点head和伪尾节点tail，这样链表插入和删除操作无需考虑左右两边是否为null；
注意插入和删除操作时，由于map和双向链表都存有node数据，因此需要结合具体场景考虑是否同时删除和插入这两部分的数据，如果单纯地向到达LRU把节点已到头结点处，则无需更新map；
在写代码中需要合理划分private方法，本题的最佳划分方法为划分以下4个private方法：
1. removeAndHead（DLinkedNode node)：先将node从双向链表中移除，再将node插入到双向链表的头节点处，实现起来为b和c的组合；
2. addHead(DLinkedNode node)：将node插入到双向链表的头节点处；
3. removeNode(DLinkedNode node)：将node从双向链表中移除；
4. DLinkedNode removeTail()：移除双向链表的真正的尾结点（不是伪尾结点tail），并返回尾结点。
需要定义个数相关的成员属性：
1. size：LRUCache中元素的个数；
2. capacity：LRUCache集合的容量。

面试时，可能面试官会问你为什么选择HashMap + 双向链表？为什么不能用数组和单链表？此时要从题目要求的get和put的时间复杂度去介绍。

8.3 代码

直接使用LinkedHashMap：

class LRUCache extends LinkedHashMap<Integer, Integer> {
 private int capacity;
 public LRUCache(int capacity) {
     super(capacity, 0.75f, true);
     this.capacity = capacity;
 }
 public int get(int key) {
     return super.getOrDefault(key, -1);
 }
 public void put(int key, int value) {
     super.put(key, value);
 }
 @Override
 protected boolean removeEldestEntry(Map.Entry<Integer,Integer> eldest) {
     return super.size() > this.capacity;
 }
}

HasMap + 双向链表：

class LRUCache {
 /**
  * 引入hashmap，目的是保证get的时间复杂度为O(1)
  */
 private Map<Integer, DLinkedNode> map;
 /**
  * 集合中元素的数量
  */
 private int size;
 /**
  * 规定的集合初始化时的容量
  */
 private int capacity;
 /**
  * 双向链表头节点，仅有指针没有值
  */
 private DLinkedNode head;
 /**
  * 双向链表尾节点，仅有指针没有值
  */
 private DLinkedNode tail;
 public LRUCache(int capacity) {
     this.size = 0;
     this.capacity = capacity;
     map = new HashMap<>(capacity);
     // 定义没有值的头节点和尾节点，避免头插和删除时考虑左右两边是否为null
     this.head = new DLinkedNode();
     this.tail = new DLinkedNode();
     head.next = tail;
     tail.pre = head;
 }
 public int get(int key) {
     DLinkedNode node = map.get(key);
     if (node == null) {
         return -1;
     } else {
         removeAndHead(node);
         return node.val;
     }
 }
 public void put(int key, int value) {
     DLinkedNode node = map.get(key);
     if (node != null) {
         node.val = value;
         removeAndHead(node);
     } else {
         ++size;
         // 头插到双向链表
         DLinkedNode pNode = new DLinkedNode(key, value);
         addHead(pNode);
         // map里新增k-v
         map.put(key, pNode);
         // 判断是否触发LRU
         if (size > capacity) {
             --size;
             // 移除双向链表的尾结点
             DLinkedNode last = removeTail();
             map.remove(last.key);
         }
     }
 }
 private void removeAndHead(DLinkedNode node) {
     // 先在双向链表中删除当前node
     removeNode(node);
     // 再将最近访问的node移动到双向链表的头节点
     addHead(node);
 }
 private void removeNode(DLinkedNode node) {
     node.pre.next = node.next;
     node.next.pre = node.pre;
 }
 private void addHead(DLinkedNode node) {
     node.pre = head;
     node.next = head.next;
     head.next.pre = node;
     head.next = node;
 }
 private DLinkedNode removeTail() {
     DLinkedNode last = tail.pre;
     removeNode(last);
     return last;
 }
 class DLinkedNode {
     DLinkedNode pre;
     DLinkedNode next;
     int key;
     int val;
     DLinkedNode(){}
     DLinkedNode(int _key, int _val) {
         key = _key;
         val = _val;
     }
 }
}

数据结构和算法

其他