1. 数组
列题 448，找到所有数组中消失的数字。给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。
- 可以直接用 hash;
- 这种确定数值范围的题可以考虑用数值作为数组下标是否有用。这道题没有使用额外空间，在原数组上做的修改，稍微会绕一点。
public List<Integer> findDisappearedNumbers(int[] nums) {
List<Integer> res = new ArrayList<>();
int n = nums.length;
for (int num : nums) {
//将数值作为数组下标，值为当前值+n
// %n 是为了防止数组范围超限
nums[(num- 1) % n ] += n;
}
for (int i = 1; i <= n; i++) {
//值不大于n的元素对应的下标即为缺失值
if (nums[i-1] <= n ) {
res.add(i);
}
}
return res;
}
例题48，旋转图像。给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
- 由外向内一层一层旋转；
- 注意 for 循环中 i、j 的范围，如果是 0 到 n，那么循环一次则恢复到原先图像。
public void rotate(int[][] matrix) {
//设置为长度减一，后续下标就无需减一
int n = matrix.length-1;
for(int i = 0; i <= n-i; i++) {
for (int j = i; j <= n-i-1; j++) {
int tmp = matrix[i][j];
matrix[i][j] = matrix[n-j][i];
matrix[n-j][i] = matrix[n-i][n-j];
matrix[n-i][n-j] = matrix[j][n-i];
matrix[j][n-i] = tmp;
}
}
}
例题 769，最多能完成排序的块。给定一个长度为 n 的整数数组 arr ，它表示在 [0, n - 1] 范围内的整数的排列。我们将 arr 分割成若干 块 (即分区)，并对每个块单独排序。将它们连接起来后，使得连接的结果和按升序排序后的原数组相同。返回数组能分成的最多块数量。arr 中每个元素都 不同。
- 很巧妙的思路。
- 记录当前元素之前最大的元素，如果最大元素等于当前下标，则可分割一次；
- 因为如果最大元素大于当前下标，那么表示后面必然存在一个小于下标的数需要划分到当前组；另外最大元素不可能小于当前下标。
public int maxChunksToSorted(int[] arr) {
int count = 0;
int max = 0;
for (int i = 0; i < arr.length; i++) {
if(arr[i] > max) {
max = arr[i];
}
if (max == i) {
count ++;
}
}
return count;
}
2. 栈和队列
例题 232，用栈实现队列。请你仅使用两个栈实现先入先出队列。
- 需要使用两个栈才能实现一个队列，通过一个栈进行入栈操作；一个栈用来弹出。
class MyQueue {
private Stack<Integer> in; //入栈用这个
private Stack<Integer> out; //出栈用这个
public MyQueue() {
in = new Stack<>();
out = new Stack<>();
}
public void push(int x) {
in.push(x);
}
public int pop() {
//需要out全部空了，才能从in转移到out
if (out.isEmpty()) {
while (!in.isEmpty()) {
out.push(in.pop());
}
}
return out.pop();
}
public int peek() {
if (out.isEmpty()) {
while (!in.isEmpty()) {
out.push(in.pop());
}
}
return out.peek();
}
public boolean empty() {
return in.isEmpty() && out.isEmpty();
}
}
例题 225. 用队列实现栈。请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
- Java中队列可以通过 LinkedList 实现，offer 表示插入队尾，poll 表示删除第一个元素。
- 用队列实现栈的思想和用栈实现队列的思想有些不一样，因为即使用两个队列进行倒腾，顺序一直都是先进先出，不会改变。因此这里用两个队列是用来做相互备份的。
class MyStack {
private Queue<Integer> out;
private Queue<Integer> in;
public MyStack() {
out = new LinkedList<>();
in = new LinkedList<>();
}
public void push(int x) {
//插入队尾
in.offer(x);
while(!out.isEmpty()) {
in.offer(out.poll());
}
Queue<Integer> tmp = out;
out = in;
in = tmp;
}
public int pop() {
return out.poll();
}
public int top() {
return out.peek();
}
public boolean empty() {
return out.isEmpty() && in.isEmpty();
}
}
例题 155，最小栈。设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
- 方法一，用两个栈，一个栈用于存储最小元素。
class MinStack {
private Stack<Integer> stack;
private Stack<Integer> minS;
public MinStack() {
stack = new Stack<>();
minS = new Stack<>();
}
public void push(int val) {
stack.push(val);
//注意是小于等于
if (minS.isEmpty() || val <= minS.peek()) {
minS.push(val);
}
}
public void pop() {
//这里不能用==，只能用equals
if (stack.peek().equals(minS.peek())) {
minS.pop();
}
stack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return minS.peek();
}
}
- 方法二，一个栈，每个元素是一个数组，数组中第一位是入栈的元素，第二位是当前栈中最小的元素。
class MinStack {
private Stack<int[]> stack;
public MinStack() {
stack = new Stack<>();
}
public void push(int val) {
if (stack.isEmpty()) {
stack.push(new int[]{val, val});
} else {
stack.push(new int[]{val, Math.min(val, stack.peek()[1])});
}
}
public void pop() {
stack.pop();
}
public int top() {
return stack.peek()[0];
}
public int getMin() {
return stack.peek()[1];
}
}
例题20，有效的括号。给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。左括号必须以正确的顺序与右括号闭合。
- 将左括号当作入栈操作，右括号当作出栈操作，看入栈出栈是否匹配。
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
char[] arr = s.toCharArray();
for(int i = 0; i < arr.length; i++) {
if (arr[i] == '(') {
stack.push(')');
} else if (arr[i] == '{') {
stack.push('}');
} else if (arr[i] == '[') {
stack.push(']');
} else if (!stack.isEmpty() && arr[i] == stack.peek()) {
stack.pop();
} else {
return false;
}
}
return stack.isEmpty();
}
3. 单调栈
单调栈是通过构造一个单调递增或者递减的栈，来处理需要进行大小比较的问题。
例题739，每日温度。给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指在第 i 天之后，才会有更高的温度。如果气温在这之后都不会升高，请在该位置用 0 来代替。
- 构造一个单调栈，栈中存储温度数组的下标，即日期。如果栈为空，或者当前日期的温度小于栈顶日期的温度，则推入栈中；否则，弹出栈顶元素，循环该过程直到栈为空或栈顶元素小于当前日期。
- 在构造单调栈的过程中，即可计算结果。
public int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length;
int[] res = new int[n];
//存储温度数组下标，维护一个单调递减的栈
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]) {
res[stack.peek()] = i - stack.peek();
stack.pop();
}
stack.push(i);
}
return res;
}
- 这道题还可以不用栈，直接从后往前计算，避免计算重复值，速度更快。
public int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length;
int[] res = new int[n];
for (int i = n-2; i >= 0; i--) {
//j=j+res[j] 即利用了已经计算了的结果
for(int j = i+1; j < n; j=j+res[j]) {
if (temperatures[j] > temperatures[i]) {
res[i] = j - i;
break;
}
if (res[j] == 0) {
break;
}
}
}
return res;
}
例题503，下一个更大元素 II。给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。如果不存在，则输出 -1 。
- 更高温度的变种题，最小栈解决，这道题由于是循环数组，直接走两遍数组即可；
- 注意栈中存储的是数组下标。
public int[] nextGreaterElements(int[] nums) {
Stack<Integer> stack = new Stack();
int[] res = new int[nums.length];
Arrays.fill(res, -1);
int size = nums.length;
for (int i = 0; i < 2 * size; i++) {
while (!stack.isEmpty() && nums[i % size] > nums[stack.peek()]) {
res[stack.peek()] = nums[i % size];
stack.pop();
}
stack.push(i % size);
}
return res;
}
4. 哈希表
哈希表，又称散列表，使用 O(n) 空间复杂度存储数据，通过哈希函数映射位置，从而实现
近似 O(1) 时间复杂度的插入、查找、删除等操作。
一般用于判断元素是否存在的用 hashset；需要同时存储 key 和 value 的就用 hashmap，可以用来统计频率，记录内容等等。
例题 128，最长连续序列。给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
- 最简单想到的就是排序，然后按序遍历。但是排序最优时间复杂度为O(nlogn)，因此排除这种做法；
- 再一种最容易想到的做法是遍历数组，判断当前元素 i 后一个元素 i+1、i+2…… 是否存在在数组中。要判断一个元素是否在数组中，遍历的方法时间复杂度为 O(n)，但如果使用hash表，就可以达到 O(1) 的复杂度。
- 因此将数组中的元素全都存入hashset，然后遍历各元素，对每个元素判断它前一个后一个有没有，更新连续序列的长度。
public int longestConsecutive(int[] nums) {
HashSet<Integer> set = new HashSet<>();
for (int num : nums) {
set.add(num);
}
int maxLen = 0;
for (int num : nums) {
if (set.remove(num)) {
int curLen = 1;
int i = 1;
while (set.remove(num-i)) {
i++;
curLen ++;
}
i=1;
while (set.remove(num+i)) {
i++;
curLen ++;
}
if (curLen > maxLen) {
maxLen = curLen;
}
}
}
return maxLen;
}
5. 前缀和与积分图
通过在初始化时构造特殊的数据结构，从而使得后续求某些结果的复杂度降低。
例题 303，区域和检索 - 数组不可变。给定一个整数数组 nums，处理以下类型的多个查询:计算索引 left 和 right （包含 left 和 right）之间的 nums 元素的 和 ，其中 left <= right。
- 构造前缀和数组即可。
class NumArray {
private int[] myNum;
/**
初始化数组为前缀和数组
*/
public NumArray(int[] nums) {
myNum = new int[nums.length];
myNum[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
myNum[i] = myNum[i-1] + nums[i];
}
}
public int sumRange(int left, int right) {
return myNum[right] - (left > 0 ? myNum[left-1] : 0);
}
}
例题 304，二维区域和检索 - 矩阵不可变。给定一个二维矩阵 matrix，计算其子矩形范围内元素的总和，该子矩阵的 左上角 为 (row1, col1) ，右下角 为 (row2, col2) 。
- 本题与上题相比增加了一维，但思路不变，需要找到累计和之间的关系。
- 构造一个矩阵sumMatrix，该矩阵存储的是从(0,0)到当前位置所有元素之和。构造时可以使用动态规划 sumMatrix[i][j] = sumMatrix[i-1][j] + sumMatrix[i][j-1] - sum[i-1][j-1] + matrix[i][j]。
- 两位置之间的所有元素之和为sumMatrix[row2][col2] - sumMatrix[row1-1][col2] - sumMatrix[row2][col1-1] + sumMatrix[row1-1][col1-1]
class NumMatrix {
private int[][] sumMatrix;
/**
构造一个矩阵sumMatrix，该矩阵存储的是从(0,0)到当前位置所有元素之和
构造时可以使用动态规划 sumMatrix[i][j] = sumMatrix[i-1][j] + sumMatrix[i][j-1] - sum[i-1][j-1] + matrix[i][j];
*/
public NumMatrix(int[][] matrix) {
//避免考虑边界元素，增大一行一列
sumMatrix = new int[matrix.length + 1][matrix[0].length + 1];
for (int i = 1; i < matrix.length+1; i++) {
for(int j = 1; j < matrix[0].length + 1; j++) {
sumMatrix[i][j] = sumMatrix[i-1][j] + sumMatrix[i][j-1] - sumMatrix[i-1][j-1] + matrix[i-1][j-1];
}
}
}
/**
两位置之间的所有元素之和为sumMatrix[row2][col2] - sumMatrix[row1-1][col2] - sumMatrix[row2][col1-1] + sumMatrix[row1-1][col1-1]
*/
public int sumRegion(int row1, int col1, int row2, int col2) {
//sumMatrix 比 matrix 大1行1列，需要+1
return sumMatrix[row2+1][col2+1] - sumMatrix[row1][col2+1] - sumMatrix[row2+1][col1] + sumMatrix[row1][col1];
}
}
例题 560. 和为 K 的子数组。给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的连续子数组的个数 。
- 先计算数组的前缀和，然后双层for循环统计两数之差等于k的个数。时间复杂度为 O(n^2).
public int subarraySum(int[] nums, int k) {
//计算数组的累计和，然后双层for循环统计两数之差等于k的个数
int n = nums.length;
int[] sum = new int[n+1];
for(int i = 1; i < n+1; i++) {
sum[i] = sum[i-1] + nums[i-1];
}
int s = 0;
for (int i = 0; i < n+1; i++) {
for (int j = i+1; j < n+1; j++) {
if (sum[j] - sum[i] == k) {
s += 1;
}
}
}
return s;
}
- 前缀和 + 哈希表 优化；
- 遍历数组时，用一个哈希表统计从起始元素开始各个前缀和出现的频率。首先需要初始化前缀和为 0 的出现频率为 1；
- 前缀和为 k 的连续子数组出现的个数其实就等于 sum - k 前缀和出现的个数。这是因为 sum 表示从 0 到当前元素的前缀和，sum-k 表示从 0 到某个元素 j 的连续子数组的前缀和，则必然存在对应的元素 j 到当前元素的连续子数组的和为k，因此 map.get(sum-k) 就等于前缀和为 k 的子数组个数。（有点难理解，可以画个坐标轴图看看就知道了）
public int subarraySum(int[] nums, int k) {
int n = nums.length;
//统计出现的各个前缀和的次数
Map<Integer, Integer> map = new HashMap<>();
//统计前缀和
int sum = 0;
int count = 0;
map.put(0, 1);
for (int i = 0; i < n; i++) {
sum += nums[i];
//map.get(sum-k)表示以当前元素结尾的满足要求的数组个数
//因为sum表示从0到当前元素的前缀和，sum-k表示从0到某个元素j的连续子数组的前缀和，则必然存在元素j到当前元素的连续子数组的和为k，其个数就等于前缀和为sum-k的子数组个数
count += map.get(sum - k) == null ? 0 : map.get(sum - k);
if (map.get(sum) == null) {
map.put(sum, 1);
} else {
map.put(sum, map.get(sum) + 1);
}
}
return count;
}
6. 滑动窗口
例题697，数组的度。给定一个非空且只包含非负数的整数数组 nums，数组的 度 的定义是指数组里任一元素出现频数的最大值。你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。
- 先遍历一遍数组找到最大频度；
- 然后通过滑动窗口找到满足最大频度的最短连续子数组；
- 滑动窗口是先移动右边界找到满足条件的子数组，再缩短左边界找到最短子数组。
public int findShortestSubArray(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
int maxFreq = 0;
for (int num : nums) {
if (map.get(num) == null) {
map.put(num, 1);
} else {
map.put(num, map.get(num) + 1);
}
if (maxFreq < map.get(num)) {
maxFreq = map.get(num);
}
}
//开始利用滑动窗口求最短子数组
int left = 0;
int right = 0;
map = new HashMap();
int res = nums.length;
while (right < nums.length) {
if (map.get(nums[right]) == null) {
map.put(nums[right], 1);
} else {
map.put(nums[right], map.get(nums[right]) + 1);
}
//找到了频度相等的数组，移动左边界将其缩至最短
while (map.get(nums[right]) == maxFreq) {
res = Math.min(res, right - left + 1);
//移动左边界相应元素的频度会减小
map.put(nums[left], map.get(nums[left]) - 1);
left ++;
}
//继续移动右边界，因为可能存在频度相等的数
right++;
}
return res;
}
例题594. 最长和谐子序列。和谐数组是指一个数组里元素的最大值和最小值之间的差别正好是 1 。现在，给你一个整数数组 nums ，请你在所有可能的子序列中找到最长的和谐子序列的长度。（子序列无需连续）
- 先排序，排序不影响这道题的结果。
- 然后再用两个指针模拟滑动窗口进行计数。
public int findLHS(int[] nums) {
Arrays.sort(nums);
int left = 0;
int res = 0;
for(int right = 0; right < nums.length; right++) {
//超过1需要移动左边界
while (nums[right] - nums[left] > 1) {
left ++;
}
//刚好等于1时计算长度
if (nums[right] - nums[left] == 1) {
res = Math.max(res, right - left + 1);
}
//小于1时仅移动右边界，其他什么都不做
}
return res;
}
例题3，无重复字符的最长子串。给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。（子串必须连续）
- 双指针模拟滑动窗口，再加一个指针遍历窗口内的数据判断是否重复。
public int lengthOfLongestSubstring(String s) {
int left = 0;
int right = 0;
int tmp = 0;
int res = 0;
char[] arr = s.toCharArray();
while (right < arr.length) {
tmp = left;
while (tmp < right) {
if (arr[tmp] == arr[right]) {
left = tmp + 1;
break;
}
tmp++;
}
res = Math.max(res, right - left + 1);
right++;
}
return res;
}
注：感觉上述两题其实也可以用动态规划来做。但是动态规划子序列或子串的题不一定能用滑动窗口来做。首先，子序列的题由于结果可以不连续，因此一般不能用滑动窗口来做（例题594例外，因为它通过排序使之变成连续的了）；而子串的题可以先考虑用滑动窗口试试。但是如果涉及到两个数组求公共的题，一般是用动态规划来做。
7. 其他
例题 287，寻找重复数。给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。
- 由于数组范围在[1,n]内，因此很容易想到可通过元素值当下标进行遍历；
- 判断重复元素最简单的方法就是使用哈希表来进行判断，但是这道题不让使用额外空间；另一种方法是通过元素值当下标遍历，修改遍历到的数组元素，如果有重复的则会发现数组元素已被修改。但是这道题不允许修改数组。
- 由于存在重复元素，相当于链表中存在环。我们可以通过快慢指针找环来判断重复元素。
public int findDuplicate(int[] nums) {
int slow = 0;
int fast = 0;
slow = nums[slow];
fast = nums[nums[fast]];
while(slow != fast) {
slow = nums[slow];
fast = nums[nums[fast]];
}
slow = 0;
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
例题313，超级丑数。超级丑数 是一个正整数，并满足其所有质因数都出现在质数数组 primes 中。给你一个整数 n 和一个整数数组 primes ，返回第 n 个 超级丑数 。题目数据保证第 n 个超级丑数 在 32-bit 带符号整数范围内。
- 优先队列内部维护的是一个最小堆，加入队列中的元素自动按最小堆排列；
- 所有的丑数都是由 primes 中的元素相乘得来，这里初始化一个优先队列，将生成的丑数加入到队列中，poll 出堆顶元素，循环 n 次，则能获取到第 n 个丑数。
public int nthSuperUglyNumber(int n, int[] primes) {
PriorityQueue<Long> queue = new PriorityQueue<>();
long res = 1;
for (int i = 1; i < n; i++) {
for (int prime : primes) {
queue.add(res * prime);
}
res = queue.poll(); //弹出首个，也就是最小的
//防止队列中出现相同的元素
while (!queue.isEmpty() && res == queue.peek()) {
res = queue.poll();
}
}
return (int)res;
}
例题 870，优势洗牌。给定两个大小相等的数组 nums1 和 nums2，nums1 相对于 nums 的优势可以用满足 nums1[i] > nums2[i] 的索引 i 的数目来描述。返回 nums1 的任意排列，使其相对于 nums2 的优势最大化。
- 其实就是田忌赛马；nums1的最小值要是不能大于nums2的最小值，那么就让它对应nums2的最大值；
- 对nums1 进行排序，对nums2 进行带下标的排序。遍历nums1，判断它能否大于nums2 当前最小值。用两个指针判断应该将nums1[i] 放在哪个位置。
public int[] advantageCount(int[] nums1, int[] nums2) {
int len = nums1.length;
int[] res = new int[len];
int[][] newNums2 = new int[len][2];
for (int i = 0; i < len; i++) {
newNums2[i][0] = nums2[i];
newNums2[i][1] = i;
}
Arrays.sort(nums1);
Arrays.sort(newNums2, (a, b) -> a[0] - b[0]);
int left = 0;
int right = len-1;
for (int i = 0; i < nums1.length; i++) {
//如果nums1的最小值能大于nums2的最小值
if (nums1[i] > newNums2[left][0]) {
res[newNums2[left][1]] = nums1[i];
left ++;
} else {
//否则直接将其与nums2的最大值匹配
res[newNums2[right][1]] = nums1[i];
right --;
}
}
return res;
}
