与树相关的一些问题。

参考文章：

优先级队列（堆）

【算法笔记】二分查找 && 二分答案

数据结构 -栈和队列(Java实现)

第3章栈、队列、数组和矩阵

双指针（java）

算法题 - 求数组的子集合

优先队列（堆）

队列是一种先进先出(FIFO)的数据结构，但有些情况下，操作的数据可能带有优先级，一般出队列时，可能需要优先级高的元素先出队列，该场景下，使用队列显然不合适，比如：在手机上玩游戏的时候，如果有来电，那么系统应该优先处理打进来的电话；初中那会班主任排座位时可能会让成绩好的同学先挑座位。

这种情况下，数据结构应该提供两个最基本的操作，一个是返回最高优先级对象，一个是添加新的对象。这种数据结构就是优先级队列(Priority Queue)。

PriorityQueue常用接口

PriorityQueue的特性

Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列，PriorityQueue是线程不安全的，PriorityBlockingQueue是线程安全的，此处主要介绍PriorityQueue。

关于PriorityQueue的使用要注意：

  1. 使用时必须导入 PriorityQueue 所在的包，即：import java.util.PriorityQueue;

  2. PriorityQueue 中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出 ClassCastException 异常

  3. 不能插入 null 对象，否则会抛出 NullPointerException

  4. 没有容量限制，可以插入任意多个元素，其内部可以自动扩容。优先级队列的扩容说明：

    1. 如果容量小于64时，是按照oldCapacity的2倍方式扩容的
    2. 如果容量大于等于64，是按照oldCapacity的1.5倍方式扩容的
    3. 如果容量超过MAX_ARRAY_SIZE，按照MAX_ARRAY_SIZE来进行扩容

  5. 插入和删除元素的时间复杂度为O（logN）

  6. PriorityQueue 底层使用了堆数据结构

  7. PriorityQueue 默认情况下是小堆，即每次获取到的元素都是最小的元素

优先级队列的构造

构造器 功能介绍+H4:021H4:H4:013
PriorityQueue() 创建一个空的优先级队列，默认容量是11
PriorityOueue(int initialCapacity) 创建一个初始容量为initialCapacity的优先级队列
注意：initialCapacity不能小于1，否则会抛lllegalArgumentException异常
PriorityQueue(Collection<? extends E> c) 用一个集合来创建优先级队列 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
 static void TestPriorityQueue(){
    // 创建一个空的优先级队列，底层默认容量是11
    PriorityQueue<Integer> q1 = new PriorityQueue<>();
    // 创建一个空的优先级队列，底层的容量为initialCapacity
    PriorityQueue<Integer> q2 = new PriorityQueue<>(100);

    // 用ArrayList对象来构造一个优先级队列的对象
    // q3中已经包含了三个元素
    ArrayList<Integer> list = new ArrayList<>();
    list.add(4);list.add(3);list.add(2);list.add(1);
    PriorityQueue<Integer> q3 = new PriorityQueue<>(list);
    System.out.println(q3.size());
    System.out.println(q3.peek());
}

注意：默认情况下，PriorityQueue队列是小堆，如果需要大堆需要用户提供比较器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 用户自己定义的比较器：直接实现Comparator接口，然后重写该接口中的compare方法即可
class IntCmp implements Comparator<Integer>{
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2-o1;
    }
}
public class TestPriorityQueue {
    public static void main(String[] args) {
        PriorityQueue<Integer> p = new PriorityQueue<>(new IntCmp());
        // 或者Lambda 写法
        // PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a,b) -> b - a);
        p.offer(4); p.offer(3); p.offer(2);  p.offer(1); p.offer(5);
        System.out.println(p.peek());
    }
 }

插入/删除/获取优先级最高的元素

函数名 功能介绍
boolean offer(E e) 插入元素e，插入成功返回true，如果e对象为空，抛出NulIPointerException异常，时间复杂度
注意：空间不够时候会进行扩容
E peek() 获取优先级最高的元素，如果优先级队列为空，返回null
E poll()) 移除优先级最高的元素并返回，如果优先级队列为空，返回null
int size() 获取有效元素的个数
void clear() 清空
boolean isEmpty() 检测优先级队列是否为空，空返回true 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
static void TestPriorityQueue2(){
    int[] arr = {4,1,9,2,8,0,7,3,6,5};
    // 一般在创建优先级队列对象时，如果知道元素个数，建议就直接将底层容量给好
    // 否则在插入时需要不多的扩容
    // 扩容机制：开辟更大的空间，拷贝元素，这样效率会比较低
    PriorityQueue<Integer> q = new PriorityQueue<>(arr.length);
    for (int e: arr) {
        q.offer(e);
    }
    System.out.println(q.size());   // 打印优先级队列中有效元素个数
    System.out.println(q.peek());   // 获取优先级最高的元素

    // 从优先级队列中删除两个元素之后，再次获取优先级最高的元素
    q.poll();
    q.poll();
    System.out.println(q.size());   // 打印优先级队列中有效元素个数
    System.out.println(q.peek());   // 获取优先级最高的元素

    // 将优先级队列中的有效元素删除掉，检测其是否为空
    q.clear();
    if(q.isEmpty()){
        System.out.println("优先级队列已经为空!!!");
    } else{
        System.out.println("优先级队列不为空");
    }
}

堆的应用

PriorityQueue的实现

用堆作为底层结构封装优先级队列

堆排序

堆排序即利用堆的思想来进行排序，总共分为两个步骤：

  1. 建堆：升序，建大堆；降序，建小堆

  2. 利用堆删除思想来进行排序

建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。

Top-k问题

TOP-K问题：即求数据集合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。

比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都 不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：

  1. 用数据集合中前K个元素来建堆 前k个最大的元素，则建小堆前k个最小的元素，则建大堆

  2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素

将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

案例

例题参见 数组中的第K个最大元素

二分查找

二分查找，也称为折半查找（Binary Search），是一种在有序数组中高效查找特定元素的搜索算法，时间复杂度为O(log⁡n)O(logn)，通过不断缩小搜索范围实现快速定位。它的基本思想是将目标值与数组中间的元素进行比较，如果目标值小于中间元素，则在数组的左半部分继续查找，否则在右半部分查找，不断缩小搜索范围，直到找到目标值或确定目标值不存在为止。

算法原理

二分查找的核心思想是分治策略，具体步骤如下

  1. 有序数组前提：仅适用于已排序的数组，利用顺序性快速排除无效区间。
  2. 中间元素比较：每次取中间位置元素与目标值比较，若相等则返回位置:
  3. 缩小搜索范围
    1. 若目标值小于中间元素，则在左半区间继续查找;
    2. 若目标值大于中间元素，则在右半区间继续查找。
  4. 终止条件：当搜索区间缩小至空(即左边界超过右边界)时，判定元素不存在。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int binarySearch(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;  // 防止整数溢出
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

代码关键点：

  • 循环条件：left <= right确保单个元素时仍能执行判断。
  • 中间值计算：使用mid = left + (right - left) / 2避免整数溢出风险。

时间复杂度与空间复杂度

  • 时间复杂度：O(log⁡n)O(logn)，每次迭代将搜索范围减半。
  • 空间复杂度：迭代实现为O(1)O(1)，递归实现因调用栈深度为O(log⁡n)O(logn)。

案例

例题参见 寻找两个正序数组的中位数

栈&矩阵&队列

矩阵（Matrix）

概念

矩阵是一个多维数组，其元素以行和列的形式排列。在计算机内存中，矩阵通常被实现为向量中的向量。一个3x3的矩阵有9个位置，每个位置可以通过一对索引（行号和列号）来访问。例如，一个元素 M 可能位于 [0][0] 的位置，而另一个元素 O 可能位于 [2][2] 的位置。矩阵可以是任意维度的，比如四维矩阵、五维矩阵等，但它们通常用于处理复杂的科学计算和图形渲染。

矩阵是数据科学、图像处理、机器学习、计算机图形学等领域最基础、最常用的数据结构之一。在现实世界中，数据往往以二维或多维数组的形式存在。

矩阵转置（Transpose）

矩阵转置（Transpose）是指将矩阵的行与列互换，通常记作 $A^T$。例如，$A$ 为 $m×n$ 矩阵，则 $A^T$ 为 $n×m$ 矩阵，满足 $A^T[i][j] = A[j][i]$。重要性如下：

  • 数据变换：在高效存储或算法实现时，经常需要将行主序（row-major）与列主序（column-major）格式互换；
  • 线性代数：在求解矩阵方程、特征值分解等算法中，转置操作会频繁出现；
  • 并行加速：对大规模矩阵做转置时，合理的分块策略和优化手段能大幅提升缓存命中率和并行效率。

栈（Stack）

概念

栈是一种特殊的列表，其添加和删除元素的操作仅限于一端，即栈顶。栈的基本操作包括入栈（push）和出栈（pop），遵循后进先出（LIFO）或先进后出（FILO）的原则。栈在程序中用于存储函数调用的上下文、保存局部变量、实现递归函数等。

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据在栈顶。

基本操作

方法 功能
new Stack() 创建一个新的空白的栈
push(a) 将元素a插入栈中，实现压栈
pop() 将栈顶元素进行出栈
peek() 获取栈顶元素
int size() 获取栈中元素的个数
boolean isEmpty() 判断栈中元素是否为空

队列（Queue）

概念

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出，

入队列：进行插入操作的一端称为队尾

出队列：进行删除操作的一端称为队头

基本操作

在Java中，Queue是个接口，底层是通过链表实现的。

方法 功能
boolean offer(E e) 入队列
E poll() 出队列
peek() 获取队头元素
int size() 获取队列中有效元素个数
boolean isEmpty() 检测队列是否为空

注意：Queue是个接口，在实例化时必须实例化LinkedList的对象，因为LinkedList实现了Queue接口。

循环队列

解决假溢出的方法就是后面满了，就再从头开始，也就是头尾相接的循环。我们把队列的这种头尾相接的顺序存储结构称为循环队列。当队首指针**Q->front = maxsize-1**后，再前进一个位置就自动到0，这可以利用除法取余运算（%）来实现。

  • 初始时：Q->front = Q->rear=0
  • 队首指针进1：Q->front = (Q->front + 1) % MAXSIZE
  • 队尾指针进1：Q->rear = (Q->rear + 1) % MAXSIZE
  • 队列长度：(Q->rear - Q->front + MAXSIZE) % MAXSIZE

判断队列为空的条件是：Q->front == Q->rear

为了区分队列还是队满的情况，有三种处理方式： (重点是第一种)

  1. 牺牲一个单元来判断队空还是队满,入队时少用一个单元. 约定以“队头指针在队尾指针的下一位置作为队满的标志”
    • 队满条件： (Q->rear + 1)%Maxsize == Q->front
    • 队空条件： Q->front == Q->rear
    • 队列中元素的个数： (Q->rear - Q ->front + Maxsize)% Maxsize
  2. 使用计数的方法来判断队列是否已满
  3. 增设一个boolean flag标记,以区分队满还是队空,flag等于false,若因删除导致 Q->front == Q->rear ，则为队空；flag 等于 true 时，若因插入导致 Q ->front == Q->rear ，则为队满

案例

例题参见 最大矩形、柱状图中最大的矩形

双指针

概念

双指针算法通过维护两个指针（索引或节点引用）在数据结构中协同移动，以优化时间复杂度。其核心在于减少不必要的遍历次数，将原本需要嵌套循环的问题转化为单次遍历，时间复杂度通常从 O(n²) 降低至 O(n) 或 O(n log> n)，适用于数组、链表、字符串等线性结构 。

核心特点

双指针协同：两指针根据规则同步或异步移动，覆盖问题解空间。
单调性依赖：多数问题需数据结构具备有序性或其他规律，例如排序后的数组或特定约束的子串。
高效性：通过剪枝或跳过无效区间，避免重复计算。

分类与应用场景

快慢指针

原理：两个指针以不同速度移动，常用于 链表操作 和 循环检测。
应用场景：

  • 链表环检测：快指针每次移动两步，慢指针移动一步，若相遇则存在环 。
  • 链表中点查找：快指针到末尾时，慢指针指向中点 。
  • 删除重复元素：慢指针标记唯一元素位置，快指针遍历数组（如有序数组去重）

对撞指针（左右指针）

原理：两指针从两端向中间移动，适用于 有序数组查找 或 对称性问题。
应用场景：

  • 两数之和：在排序数组中找和为目标值的两个数（指针调整方向基于当前和与目标值的比较） 。
  • 盛水容器：计算最大容积时，移动高度较小的指针以寻求更大可能 。
  • 反转数组/字符串：交换左右指针元素直至相遇

滑动窗口

原理：维护动态窗口，通过调整窗口边界寻找最优解，常用于 子串/子数组问题。
应用场景：

  • 最小覆盖子串：窗口覆盖目标字符集时收缩左边界以优化长度 。
  • 最长无重复子串：右指针扩展窗口，左指针在重复时跳跃 。

案例

例题参见 好子数组的最大分数

枚举

例题参见 超级回文数

模拟

例题参见 螺旋矩阵

子集合

例题参见 求数组的子集合

算法题

数组中的第K个最大元素

题目链接：LeetCode_215. 数组中的第K个最大元素

问题描述：
给定整数数组 nums 和整数 k，请返回数组中第 **k** 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

1
2
输入: [3,2,1,5,6,4], k = 2
输出: 5

示例 2:

1
2
输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

提示：

  • 1 <= k <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4
1
2
3
4
5
6
7
8
9
10
11
12
13
public int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);
    for (int i = 0; i < k; i++) {
        minHeap.offer(nums[i]);
    }
    for (int i = k; i < nums.length; i++) {
        if (nums[i] > minHeap.peek()) {
            minHeap.poll();
            minHeap.offer(nums[i]);
        }
    }
    return minHeap.peek();
}

寻找两个正序数组的中位数

题目链接：LeetCode_4. 寻找两个正序数组的中位数

**问题描述：
**给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：

1
2
3
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

示例 2：

1
2
3
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

提示：

  • nums1.length == m
  • nums2.length == n
  • 0 <= m <= 1000
  • 0 <= n <= 1000
  • 1 <= m + n <= 2000
  • -10^6 <= nums1[i], nums2[i] <= 10^6

思路：
两个有序数组的长度分别为m和n，由于两个数组长度之和 m+n 的奇偶不确定，因此需要分情况来讨论，对于奇数的情况，直接找到最中间的数即可，偶数的话需要求最中间两个数的平均值。

为简化代码，不分情况讨论，使用一个小技巧：分别找第 (m+n+1) / 2 个，和 (m+n+2) / 2 个，然后求其平均值即可，这对奇偶数均适用。假如 m+n 为奇数的话，那么其实 (m+n+1) / 2 和 (m+n+2) / 2 的值相等，相当于两个相同的数字相加再除以2，还是其本身。

定义一个函数用于在两个有序数组中找到第K个元素，下面重点来看如何实现找到第 K 个元素。

  1. 首先，为了避免产生新的数组从而增加时间复杂度，使用两个变量 i 和 j 分别来标记数组 nums1 和 nums2 的起始位置。
  2. 然后，处理边界问题，比如当某一个数组的起始位置大于等于其数组长度时，说明其所有数字均已经被淘汰了，相当于一个空数组了，那么实际上就变成了在另一个数组中找数字，直接就可以找出来了。还有如果 K=1 ，那么只要比较 nums1 和 nums2 的起始位置 i 和 j 上的数字就可以了。
  3. 难点在于一般的情况怎么处理？因为需要在两个有序数组中找到第K个元素，为了加快搜索的速度，要使用二分法，对 K 二分，意思是要分别在 nums1 和 nums2 中查找第 K/2 个元素，注意这里由于两个数组的长度不定，所以有可能某个数组没有第 K/2 个数字，所以需要先检查数组中到底存不存在第 K/2 个数字，如果存在就取出来，否则就赋值上一个整型最大值。如果某个数组没有第 K/2 个数字，那么淘汰另一个数字的前K/2个数字。有没有可能两个数组都不存在第 K/2 个数字呢，这道题里是不可能的，因为K是给的m+n的中间值，所以必定至少会有一个数组是存在第K/2个数字的。
  4. 最后就是二分法的核心，比较这两个数组的第 K/2 小的数字 midVal1 和 midVal2 的大小，如果第一个数组的第 K/2 个数字小的话，那么说明要找的数字肯定不在 nums1 中的前 K/2 个数字，所以可以将其淘汰，将 nums1 的起始位置向后移动 K/2 个，并且此时的K也自减去K/2，调用递归。反之，淘汰nums2中的前K/2个数字，并将 nums2 的起始位置向后移动 K/2 个，并且此时的 K 也自减去K/2，调用递归。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int left = (m + n + 1) / 2;
        int right = (m + n + 2) / 2;
        return (findKth(nums1, 0, nums2, 0, left) + findKth(nums1, 0, nums2, 0, right)) / 2.0;
    }
    // i: nums1的起始位置 j: nums2的起始位置,k 表示 第 k 个元素
    public int findKth(int[] nums1, int i, int[] nums2, int j, int k){
        if( i >= nums1.length) { // nums1为空数组
            return nums2[j + k - 1];
        }
        if( j >= nums2.length) { // nums2为空数组
            return nums1[i + k - 1];
        }
        if(k == 1){
            return Math.min(nums1[i], nums2[j]);
        }
        int midVal1 = (i + k / 2 - 1 < nums1.length) ? nums1[i + k / 2 - 1] : Integer.MAX_VALUE;
        int midVal2 = (j + k / 2 - 1 < nums2.length) ? nums2[j + k / 2 - 1] : Integer.MAX_VALUE;
        if(midVal1 < midVal2) { // 淘汰 nums1的前 k/2个
            return findKth(nums1, i + k / 2, nums2, j , k - k / 2);
        }else{ // 淘汰 nums2的前 k/2个
            return findKth(nums1, i, nums2, j + k / 2 , k - k / 2);
        }        
    }
}

最大矩形

题目链接：85. 最大矩形

问题描述：给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

示例 1：

1
2
3
输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：6
解释：最大矩形如上图所示。

示例 2：

1
2
输入：matrix = [["0"]]
输出：0

示例 3：

1
2
输入：matrix = [["1"]]
输出：1

提示：

  • rows == matrix.length
  • cols == matrix[0].length
  • 1 <= row, cols <= 200
  • matrix[i][j] 为 '0' 或 '1'
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public int maximalRectangle(char[][] matrix) {
    if (matrix.length == 0) {
        return 0;
    }
    int m = matrix.length, n = matrix[0].length, area = 0, min;
    int[][][] dp = new int[m + 1][n + 1][2];
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (matrix[i - 1][j - 1] == '1') {
                if (j != 1 && matrix[i - 1][j - 2] == '1') {
                    dp[i][j][0] = dp[i][j - 1][0] + 1;
                } else {
                    dp[i][j][0] = 1;
                }
                if (i != 1 && matrix[i - 2][j - 1] == '1') {
                    dp[i][j][1] = dp[i - 1][j][1] + 1;
                } else {
                    dp[i][j][1] = 1;
                }
                min = dp[i][j][0];
                for (int k = 1; k <= dp[i][j][1]; k++) {
                    min = Math.min(min, dp[i - k + 1][j][0]);
                    area = Math.max(area, min * k);
                }
            }
        }
    }
    return area;
}

柱状图中最大的矩形

题目链接：84. 柱状图中最大的矩形

问题描述：给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例 1：

1
2
输入：heights = [2,1,5,6,2,3]
输出：10

示例 2：

1
2
输入： heights = [2,4]
输出： 4

提示：

  • 1 <= heights.length <=10^5
  • 0 <= heights[i] <= 10^4

思路：使用单调增栈可以 O(1) 的获取柱体 i 左边第一个比它小的柱体，因为对于栈中的柱体来说，栈中的下一个柱体就是其「左边第一个小于自身的柱体」。遍历每个柱体，若当前的柱体 i 高度大于等于栈顶柱体的高度，就直接将当前柱体入栈，否则若当前柱体 i 高度小于栈顶柱体的高度，说明 i 是栈顶柱体的「右边第一个小于栈顶柱体的柱体」，以栈顶柱体为高的矩形的左右宽度边界就确定了，那么就可以将栈顶柱体出栈来计算以其为高的矩形的面积了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int largestRectangleArea(int[] heights) {
    // 在柱体数组的头和尾加了两个高度为 0 的柱体
    int[] tmp = new int[heights.length + 2];
    System.arraycopy(heights, 0, tmp, 1, heights.length); 
    Deque<Integer> stack = new ArrayDeque<>();
    int area = 0;
    for (int i = 0; i < tmp.length; i++) {
        while (!stack.isEmpty() && tmp[i] < tmp[stack.peek()]) {
            int h = tmp[stack.pop()]; // 栈顶柱体高度，注意是出栈
            area = Math.max(area, (i - stack.peek() - 1) * h); // 栈顶元素计算左右宽度边界
        }
        stack.push(i);
    }
    return area;
}

好子数组的最大分数

题目链接：LeetCode_1793. 好子数组的最大分数

问题描述：
给你一个整数数组 nums （下标从 0 开始）和一个整数 k 。一个子数组 (i, j) 的 分数 定义为 min(nums[i], nums[i+1], ..., nums[j]) * (j - i + 1) 。一个 好 子数组的两个端点下标需要满足 i <= k <= j 。请你返回 好 子数组的最大可能 分数 。

示例 1：

1
2
3
输入：nums = [1,4,3,7,4,5], k = 3
输出：15
解释：最优子数组的左右端点下标是 (1, 5) ，分数为 min(4,3,7,4,5) * (5-1+1) = 3 * 5 = 15 。

示例 2：

1
2
3
输入：nums = [5,5,4,5,4,1,1,1], k = 0
输出：20
解释：最优子数组的左右端点下标是 (0, 4) ，分数为 min(5,5,4,5,4) * (4-0+1) = 4 * 5 = 20 。

提示：

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 2 * 10^4
  • 0 <= k < nums.length

思路：判断左右指针对应的数组值哪个比较大，移动到大的一端即可

1
2
3
4
5
6
7
8
9
10
11
12
13
public int maximumScore(int[] nums, int k) {
    int n = nums.length, ret = nums[k];
    for (int i = k, j = k, mn = nums[k]; i > 0 || j < n - 1; ) {
        // mn 表示 Math.min(nums[i], nums[i+1], ..., nums[j]) 
        if (j == n - 1 || i > 0 && nums[i-1] > nums[j+1]) {
            mn = Math.min(mn, nums[--i]);
        } else {
            mn = Math.min(mn, nums[++j]);
        }
        ret = Math.max(ret, mn * (j - i + 1));
    }
    return ret;
}

超级回文数

题目链接：LeetCode_906. 超级回文数

问题描述：
如果一个正整数自身是回文数，而且它也是一个回文数的平方，那么我们称这个数为 超级回文数 。现在，给你两个以字符串形式表示的正整数 left 和 right ，统计并返回区间 [left, right] 中的 超级回文数 的数目。

示例 1：

1
2
3
4
输入：left = "4", right = "1000"
输出：4
解释：4、9、121 和 484 都是超级回文数。
注意 676 不是超级回文数：26 * 26 = 676 ，但是 26 不是回文数。

示例 2：

1
2
输入：left = "1", right = "2"
输出：1

提示：

  • 1 <= left.length, right.length <= 18
  • left 和 right 仅由数字（0 - 9）组成。
  • left 和 right 不含前导零。
  • left 和 right 表示的整数在区间 [1, 10^18 - 1] 内。
  • left 小于等于 right 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public int superpalindromesInRange(String left, String right) {
    int sum = 0;
    for(int a = Integer.parseInt("1"+"0".repeat(
            String.valueOf((int)Math.sqrt(Double.parseDouble(left))).length() - 1),3); ; a++){
        String check = Integer.toString(a,3);
        if(!new StringBuffer(check).reverse().toString().equals(check)) {
            continue;
        }
        if(Integer.parseInt(check) < (int)Math.sqrt(Double.parseDouble(left))) {
            continue;
        }
        if(Integer.parseInt(check) > (int)Math.sqrt(Double.parseDouble(right))) {
            break;
        }
        if(check.chars().map(b -> ((char)b - '0') * ((char)b - '0')).sum() < 10) {
            sum++;
        }   
    }
    if(left.length() == 1 && Integer.parseInt(left) <= 9 
            && (right.length() > 1 || Integer.parseInt(right) >= 9)) {
        sum++;
    } 
    return sum;
}

螺旋矩阵

题目链接：54. 螺旋矩阵

问题描述：给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

示例 1：

1
2
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

示例 2：

1
2
输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]

提示：

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 10
  • -100 <= matrix[i][j] <= 100

思路：模拟矩形的顺时针旋转，所以核心依然是依然是坚持循环不变量，按照左闭右开的原则。模拟顺时针画矩阵的过程:

  • 填充上行从左到右
  • 填充右列从上到下
  • 填充下行从右到左
  • 填充左列从下到上

由外向内一圈一圈这么画下去。

设置四个边界，注意状态改变后要增加条件限制，比如后面两个for循环，这个解题是比较好记的，注意每次都是左开右闭就可以了，不要随意更改，其实就是二分查找的区间不变量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public List<Integer> spiralOrder(int[][] matrix) {
    List<Integer> result = new ArrayList<>();
    int left = 0, top = 0;
    int right = matrix[0].length-1;
    int bottom = matrix.length-1 ;
    while(left <= right && top <= bottom) {
        for(int i = left; i <= right; i++) { // 上行从左到右
            result.add(matrix[top][i]);
        }
        top++;
        for(int i = top; i <= bottom; i++) { // 右列从上到下
            result.add(matrix[i][right]);
        }
        right--;
        for(int i = right; i >= left && top <= bottom; i--) { // 下行从右到左
            result.add(matrix[bottom][i]);
        }
        bottom--;
        for(int i = bottom; i >= top && left <= right; i--) { // 左列从下到上
            result.add(matrix[i][left]);
        }
        left++;
    }
    return result;
}

求数组的子集合

题目一：给出一个数组 list = [1,2,3,4,5,6]，求此数组的所有子集合
输出：[1]，[1,2]，[1,2,3]…

题目二：给出一个数组 list = [1,2,3,4,5,6]，求此数组的所有子集合中和为6的子集
输出：[6，[2,4]，[1,5]，[1,2,3]

解题思路：
方式一：递归
方式二：全排列方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// 递归方式 求数组的子集合，子数组
public static void main(String[] args) {
    int[] list = {1,2,3,4,5,6}; // 测试数组
    List<List<Integer>> resultList = new ArrayList<>(); // 保存结果集
    List<Integer> subList = new ArrayList<>();
    subList(list, 0, resultList, subList); // 递归调用
    // 求数组的子集
    System.out.println("数组的所有子集合：");
    for (List<Integer> sub : resultList) {
        System.out.println(Arrays.toString(sub.toArray()));
    }
    // 求各个子集中 和 为6的集合
    System.out.println("输出和为：6");
    for (List<Integer> sub : resultList) {
        int sum = sub.stream().reduce(0, Integer::sum);
        if (sum == 6) {
            System.out.println(Arrays.toString(sub.toArray()));
        }
    }
}
// 递归
public static void subList(int[] list , int index, 
        List<List<Integer>> resultList, List<Integer> subList) {
    resultList.add(new ArrayList<>(subList));
    int size = list.length ;
    for (int i = index; i < size; ) {
        subList.add(list[i]);
        subList(list, ++i, resultList, subList);
        subList.remove(subList.size() - 1);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 求数组的子集合，子数组 方式二：全排列方式
public static void main(String[] args) {
    int[] list = {1,2,3,4,5,6}; // 测试数组
    List<List<Integer>> resultList = new ArrayList<>(); // 保存结果集 
    // 全排列 循环
    int size = list.length ;
    for (int i = 0; i < size; i++) {
        resultList.add(new ArrayList<>(Arrays.asList(list[i])));  // 保存单个
        for (int j = i+1; j < size; j++) {
            List<Integer> subList = new ArrayList<>();
            subList.add(list[i]);
            for (int k = j; k < size; k++) {
                subList.add(list[k]);
                resultList.add(new ArrayList<>(subList)); // 重新保存一个数组
            }
        }
    }
    System.out.println("数组的所有子集合：");
    for (List<Integer> sub : resultList) {
        System.out.println(Arrays.toString(sub.toArray()));
    }
    System.out.println("输出和为：6");
    for (List<Integer> sub : resultList) {
        int sum = sub.stream().reduce(0, Integer::sum);
        if (sum == 6) {
            System.out.println(Arrays.toString(sub.toArray()));
        }
    }
}