算法思路总结

Hash

两数之和

核心思想：生成哈希表，对hash再次查找，但是要注意排查同一个元素的使用。

字母异位词分组

核心思想：对每个字符串在遍历时候进行排序，则异位词将变得相同，之后用哈希表记录即可。

1	map精巧的获取方法：map.getOrDefault(test[i], new ArrayList<String>());

最长连续序列

核心思想：找连续序列的起始数字。set去重后，遍历数组判断每个数组是否有前一个数，没有则说明其是起始数字，则往后遍历判断起始数字后面是否存在。

双指针

移动零

核心思想：如果数组没有0，那么快慢指针始终指向同一个位置，每个位置自己和自己交换；如果数组有0，快指针先走一步，此时慢指针对应的就是0，所以要交换。

盛最多水的容器

核心思想：双指针从两头出发，即宽度最大，双指针往中间缩采用边最小的一端往中间缩，贪心算法的思维。

三数之和

核心思想：定一动二，两个从前面遍历，一个从后遍历（三个和偏大的时候向前移动一位）

进行排序
第一个数字从头遍历到尾，第一个数字后面的内容采用双指针进行查找
需要判断数字是否和前面的数字相同，相同则跳过
左边的值从第一个数字下一个位置遍历到最后，而右边的值从数组末尾开始。也要注意数字相同的情况。
当结果偏大，则需要右边向左移动一个。

接雨水

核心思想：一个位置有多高的水取决于：其左右最大的高度中的最小值。

分别求每个位置的最大前缀和最大后缀，求出来后遍历取得最小值再减去当前高度，时间复杂度和空间复杂都是O(N)。
双指针向中间逼近，左指针已知左边的最高值，右指针已知右边的最高值，则选取两侧最高值小的一边（因为肯定高不过小的一侧的最高值）作为水高再减当前高度。然后多次单侧收敛闭合。

滑动窗口

无重复字符的最长子串

核心思想：采用Set来保存子串元素，子串右侧一直右（保证右侧不回退）走直到遇到Set中已经存在的元素，左侧往前上一位并且删除左侧元素，如果右侧元素还在Set中则继续左侧往前上一位。

找到字符串中所有字母异位词

核心思想：创建s和p的数组hash表，初始状态s和p对齐后，p不断往右挪，判断s滑动窗口的p的hash表是否一致。

注意：

初始状态：在hash表中先装入p的长度
s的hash表不断删除首位元素，末尾填入元素，每次操作后进行判断是否与p的hash表相等了。
1
Arrays.equals(sHash,pHash);
初始状态要放在循环外判断，因为2中操作要先操作再判断。
p长度大于s的特殊情况，直接返回空。

子串

和为k的子数组-太妙了

核心思想：前缀和+哈希表。哈希表中记录前面元素的前缀和与该和出现了几次。求一个子串的和 = 前缀和 - 前面某个元素前缀和 = k。则前缀和 - k 去哈希表中找有没有前面某个元素前缀和即可。

注意：

首个元素应该加入{0,1}，即前缀和为0记为1。
先判断是否存在，再加入哈希

滑动窗口最大值

核心思想：单调队列（主要用于处理连续区间上的最值问题，尤其是在滑动窗口场景中非常常见）。单调队列队头位最大值的索引，当滑动窗口时，从队头获取最大值。重点是如何维护单调队列。移动窗口时，要把索引不满足当前窗口的剔除出去。

维护单调队列：

// 维护单调队列，一个元素进来时对比单调队列每个元素，将小于新元素的成员删除
while(!deque.isEmpty() && nums[i] > nums[deque.peekLast()]){
    deque.pollLast();
}
//加入队尾，即确保新加进来的元素永远是在队尾，且队列整体为单调的
deque.offerLast(i);

最小覆盖子串

核心思想：滑动窗口一直向右扩展找到包含t的子串，再左侧收缩直到不满足包含字串，如此循环。两个map，t中包含的字符与个数，滑动窗口滑动过程中包含t中字符的数量，当这两个map相同即过程map跟着t遍历比较里面值都不低于t则说明成功。

注意：

要采用hashmap不能用数组，因为存在大小写

map采用entrySet的迭代遍历

Iterator iter = map.entrySet().interator();
while(iter.hasNext()){
	Map.Entry entry = (Map.Entry)iter.next();
	Character key = (Character)entry.getKey();
	Integer value = (Integer)entry.getValue();
}

普通数组

最大子数组和

核心思想：记录前缀值，如果当前值大于前缀值（包括当前值）则舍弃前缀。再采用一个最大值记录走过的最大值。

合并区间

核心思想：先按照每个区间起始位置排序，如果前一段区间结束位置大于后一段区间起始位置，则需要合并。需要判断合并位置的结束值需要取合并两区间最大值。

// 二维数组排序
Arrays.sort(intervals, (a,b) -> a[0] - b[0]);

// list赋值方法
1. set方法 2. get取出后赋值

// List<int[]> 转 int[][]
res.toArray(new int[res.size()][]);

轮转数组

核心思想：

翻转：k=2 => 1 2 3 4 5 6 7 => 7 6 5 4 3 2 1 => 5 6 7 | 4 3 2 1 => 5 6 7 | 1 2 3 4
环状替换：尚未理解

注意：k = k % n

除自身以外数组的乘积

核心思想：

构造左右前后缀乘积两个数组，结果为左右前缀乘积的乘积。O(N) O(N)
基于上面的思想先构造左前缀乘积到结果数组中，再反方向一遍算右后缀乘积一遍得出结果。

缺失的第一个正数

核心思想：如果数组中含有负数，则缺失的正数一定在[1, nums.length]中。我们对数组进行遍历，对于遍历到的数 x，如果它在 [1,N] 的范围内，那么就将数组中的第 x−1 个位置（注意：数组下标从 0 开始）打上「标记」。在遍历结束之后，如果所有的位置都被打上了标记，那么答案是 N+1，否则答案是最小的没有打上标记的位置加 1。标记的设计：把不在 [1,N] 范围内的数修改成任意一个大于 N 的数（例如 N+1）。这样一来，数组中的所有数就都是正数了，因此我们就可以将「标记」表示为「负号」。

即：最后用数组索引下标表示数值，对应数组元素作为标记。

注意：添加绝对值，虽然第一步删除了负数，但是随着一步步标记会出现负号。

// 将小于长度的数所对应的索引位置的数组元素表示为负
for(int i=0;i<nums.length;i++){
    int num = Math.abs(nums[i]);
    if(num  <= nums.length){
        nums[num - 1] = -Math.abs(nums[num - 1]);
    }
}

矩阵

矩阵置零

核心思想：遍历一遍矩阵用两个数组分别记录横向和纵向是否需要清零。采用矩阵第一列和第一行来充当记录矩阵，需要注意第一个元素是重叠的，需要单独变量进行记录。

注意：最后对首行首列进行处理

螺旋矩阵

核心思想：从外层向内层次遍历，采用四个变量来表示遍历过程。

	row				col
top				left -> right
top->bottom 	right
bottom			right->left
bottom->top		left

注意：

四个角重合的地方进行去重
if(left < right && top < bottom) 主要是为了确保在螺旋遍历时，只有在剩余的矩阵区域不为空时才执行左右和上下边界的反向遍历。这个条件的作用是防止在矩阵的边缘（如一行或一列）时，不会再访问已经遍历过的元素。

旋转图像

核心思想：

翻转的思想：上下翻转，对角线翻转
原地旋转：两层循环，层次为i = n/2，起始点j = i, 终止点为j < n-i-1。顺时针规律：左右交换，交换后的后者 = n-1-后者。

搜索二维矩阵II

核心思想：将这个矩阵旋转45°，看做类似二叉搜索树，从底部开始与target比较，如果target较大则往右上走，target较小则往左上走。

链表

相交链表

核心思想：

翻转链表

核心思想：记录当前节点前后节点信息保证不丢失，再更改当前节点指向前一个。

回文链表

核心思想：翻转后半部分链表，前后两部分进行比较。

注意：

如何不破坏链表，即再翻转一遍恢复链表
寻找中间节点的方法：快慢指针，快指针走完时正好慢指针走到一半，即前半部分最后一个元素，无论奇偶

环形链表

核心思想：快慢指针如果存在环，快指针一定会追上慢指针。

注意：

head和head.next为null要最开始排除
判断相同是ListNode相同

环形链表II

核心思想：快慢指针。slow 指针进入环后，又走了 b 的距离与 fast 相遇。此时，fast 指针已经走完了环的 n 圈，因此它走过的总距离为 a + n(b + c) + b = a + (n + 1)b + nc。根据题意，任意时刻，fast 指针走过的距离都为 slow 指针的 2 倍。因此，我们有a + (n + 1)b + nc = 2(a + b) => a = c + (n - 1)(b + c) 。我们会发现：从相遇点到入环点的距离加上 n−1 圈的环长，恰好等于从链表头部到入环点的距离。最简单的总结：当slow和fast相遇时，再从起点一个指针，这个指针会与slow相遇在起点

fig1

注意：对fast.next进行判空

合并两个有序链表

核心思想：循环中比较两个分支，结果next纳入较小的节点。直到一个分支被添加完后，将剩余的一个分支后面的所有都加入进去。

注意：

创建一个空头节点作为结果的索引，有利于后面的添加。

两数相加

核心思想：两个链表逐次相加，出现进位则要去记录并加到下一轮中。两个列表长度不等，先结束的列表其值默认为0。

注意：

最后一次可能存在进位，需要再往后添加个元素。
头节点要采用一个变量记录。

删除链表的倒数第N个结点

核心思想：快指针先出发n个，慢指针再出发。记录慢指针前一位来进行删除。

注意：

创建一个空头结点，有利于对删除后为空的情况进行处理。

两两交换链表中的节点

核心思想：其实就是设计两个节点前后交换，记录好两节点前面的节点状态和后面的节点状态即可。采用空头节点能减少操作。

K个一组翻转链表

核心思想：

每次翻转前，要确定链表的范围，即是否未翻转的元素还大于k个

for(int i=0;i<k;i++){
    end = end.next;
    if(end==null) return hair.next;
}

记录未翻转前链表的前驱和后继，方便翻转完成后把已翻转部分和未翻转部分连接起来
初始需要两个变量，pre代表待翻转链表的前驱，end代表待翻转链表的末尾

构造翻转函数

// 为什么只需要一个head，因为主函数中将end.next设置为了null，因此这里可以采用curr!=null判断是否到头
private ListNode reverse(ListNode head){
	// 前驱为null
    ListNode pre = null;
    ListNode curr = head;
    while(curr!=null){
        ListNode next = curr.next;
        curr.next = pre;
        pre = curr;
        curr = next;
    }
    // 返回的是需要翻转部分的最后一个元素
    return pre;
}

复制带随机指针的链表

核心思想：采用三个循环：

针对每一个节点都创建一个复制节点，并将原始节点next改为其对应的复制节点，复制节点再连接到下一个原始节点。
将原始节点的随机后继复制到复制节点上，即复制节点之间进行随机连接。
分离原始节点和复制节点，同时更新这两部分的next后继指向。

注意：random赋值为当前节点random节点的下一个，即新的节点。

排序链表

核心思想：采用自底向上的归并算法将链表拆分后采用两两合并有序链表的方式进行排序。首先，遍历一遍计算出链表长度。设定变量并进行循环实现归并的多层操作，即每个子串的大小1,2,4,8,16,...,len。在归并中按照子链表长度分为前后一对进行合并有序链表。

ListNode hair = new ListNode(-1, head);
// subLength从1开始每轮×2，知道子链表长度最接近len
for(int subLength=1;subLength<len;subLength<<=1){
    ListNode pre = hair, curr = hair.next;
    // 每层逐一对每对子链表进行有序合并
    while (curr!=null){
    	// 待合并的第一个子链
        ListNode head1 = curr;
        for(int i=1;i<subLength && curr!=null;i++){
            curr = curr.next;
        }
        // 待合并的第一个子链
        ListNode head2 = curr.next;
        curr.next = null;
        curr = head2;
        for(int i=1;i<subLength && curr!=null&&curr.next!=null;i++){
            curr = curr.next;
        }
		// 合并前使得两个子链最后为null
        ListNode next = null;
        if(curr != null){
            next = curr.next;
            curr.next = null;
        }
        // 合并有序链表
        ListNode merged = merge(head1, head2);
        // 重新首部接回原链表
        pre.next = merged;
        // pre到接回链表的末尾，此时末尾仍然指向null
        while (pre.next!=null){
            pre = pre.next;
        }
        curr = next;
    }
}

LRU缓存

核心思想：哈希表记录key和对应的节点，实现查询O(1)，双向链表实现插入O(1)。插入操作：查询哈希表是否存在，存在则改值并移到链表头；不存在则创建并插入到链表头，判断容量是否满足，不满足删除队尾元素。查询操作：查询哈希表是否存在，存在则移到链表头并返回值；不存在返回-1。

注意：实现两个核心方法：·addToHead和removeNode，其他的方法如移动到头结点，删除队尾节点都可以采用这两个核心方法实现。

合并K个排序链表

核心思想：基于合并两个排序链表，采用归并的思想两两合并。两层循环，第一层循环是归并的层次，第二层循环每层两两合并的选取。

public ListNode mergeKLists(ListNode[] lists) {
	// i表示几个划分，从单个链表两两合并
    for(int i=1;i<lists.length;i<<=1){
        // j表示两两合并的头一个链表
        for(int j=0;j<lists.length - i;j+=i*2){
            lists[j] = merge(lists[j], lists[j+i]);
        }
    }
    return lists.length>0?lists[0]:null;
}

二叉树

中序遍历

核心思想：

构造递归函数，在左右递归调用的中间加入结果集合
采用栈的方式，栈不为空或者root不为null的时候就往左下走。空了之后弹栈加入结果集合，再看弹栈的这个有没有右子树。

二叉树的最大深度

核心思想：

层次遍历，因为队列再删除上一层元素时会加入下一层元素，所以在每层添加前先获取到当前队列的容量，当删除该该容量的数量则说明这一层都弹出了，此时就会记录一层。

深度遍历：关于深度值的传递，直接将深度值作为返回值记录，深度值是对比左右子树传上来的深度。

public int maxDepth(TreeNode root) {
    if(root == null) return 0;
    int leftDept = maxDepth(root.left);
    int rightDept = maxDepth(root.right);
    return Math.max(leftDept, rightDept) + 1;
}

翻转二叉树

核心思想：后续遍历，获取到左右子树返回值后，翻转赋值到当前root。

对称二叉树

核心思想：

递归方法，从第二层开始，输入root的左右子树进行比较。终止条件即左右都为null则为相同。最后要判断的是当前值是否一致，左子树的左侧和右子树的右侧是否传上来的结果相同，左子树的右侧和右子树的左侧传上来的结果是否相同。

private boolean check(TreeNode left, TreeNode right){
    if(left == null && right == null) return true;
    if(left == null || right == null) return false;
    return left.val == right.val && check(left.left, right.right) && check(left.right, right.left);
}

迭代方法，用队列来保存对称位置的节点，每次取出来两个进行比较。

二叉树直径

核心思想：深度优先搜索，左右子树深度之和就是经过当前节点的当前最大直径。采用一个公共变量进行记录这个最大的距离。

private int depth(TreeNode root){
    if (root == null) return 0;
    int left = depth(root.left);
    int right = depth(root.right);
    res = Math.max(left+right, res);
    // 返回的还是最大深度
    return Math.max(left, right) + 1;
}

二叉树层序遍历

核心思想：采用队列记录节点，采用size记录每层的数量

注意：初始root节点判空

将有序数组转换为二叉搜索树

核心思想：二叉搜索树即为递归获取有序数组中值加入树中，采用start和end索引标记起始和结束位置从而找到中间位置。

注意：区间边界的开闭。

验证二叉搜索树

核心思想：从二叉搜索树的特性出发，即左子树都小于根节点，右子树都大于根节点，设置一个左右数值的边界判断根目录是否在这个区间。

private boolean valueCompare(TreeNode root, long  low, long  height){
    if(root == null) return true;
    if(root.val <= low || root.val >= height){
        return false;
    }
    return valueCompare(root.left, low, root.val) && valueCompare(root.right, root.val, height);
}

注意：

测试用例中包含2147483647因此区间设置为Long类型
root和左右边界对比时应该是左右闭区间的或比较，因为有数值相同的情况
1
2
3
if(root.val <= low || root.val >= height){
return false;
}

二叉搜索树中第k小的元素

核心思想：二叉搜索树的中序遍历即为升序序列，采用迭代的方法可以找到结果后提前终止。

注意：二叉树中序遍历迭代方法实现不熟。

二叉树右视图

核心思想：层次遍历记录每层最后一个元素。

二叉树展开为列表

核心思想：因为要按照前序遍历展开，从上到下一遍遍的执行：左子树的最右下角将承接右子树，由此找到左子树的最右侧作为右子树的前驱进行相连。这样从上到下开始被拉伸为一条链。

从前序与中序遍历序列构造二叉树

核心思想：按照前序遍历的顺序不断从中序遍历中找到根节点，并以根节点为中心化分为两侧，以分治法迭代处理。因此中序遍历数组需要规定起始位置和终止位置，前序遍历需要找到左右子树根节点的位置。

1 2	前序遍历性质：节点按照 [ 根节点 \| 左子树 \| 右子树 ] 排序。中序遍历性质：节点按照 [ 左子树 \| 根节点 \| 右子树 ] 排序。

注意：

前序遍历左子树起始位置为根节点索引位置+1，右子树起始位置为根节点+1+左子树的长度，左子树长度可以通过中序遍历中根节点-起始位置得到。
注意区间选择，一般左闭右开。

路径总和III

核心思想：遇到连续区间和的问题先想到前缀和来解决。采用先序遍历累加前缀和记录到Map<Long, Integer>中，Long为前缀和，Integer为前缀和想同的次数，在深度优先遍历时不断算出前面的前缀和，该节点为结尾的路径应满足在Map中查找key值为当前节点值+前缀和 - target，得到有多少个满足的路径。之后再递归调用左右孩子进行计算，最终返回的结果应该是左右孩子返回的路径结果+当前节点路径结果。

注意：

当左右孩子调用完应删除当前节点在map中的记录，因为还有去走其他的路径。
初始化前缀和map时要加入前缀和为0的数量为1的元素，由此可以记录单个节点满足target的情况。

二叉树的最近公共祖先

核心思想：构建一个深度优先遍历，当遇到p、q时则往上传递true，当左右子树两边传递的都是true，或者当前节点为p和q之一并且左右子树有一个传递上来true时，则说明当前节点是最近公共祖先。

注意：

一个节点是另一个节点祖先的情况
往上传递的判断和判断是否为公共祖先的判断是不一样的

二叉树中最大路径和

核心思想：深度优先遍历，获取左右子树最大的路径和，再加上当前节点的值，然后再设计一个公共变量记录最大的值。

注意：

左右子树是否纳入最大和中，需要判断其是否大于零做出正向贡献。
在传递到上一层时，要舍弃到左右子树较小的一边，因为其路径在一条路径序列中至多出现一次，如果不舍弃一边则当前节点重合。

回溯

全排列

核心思想：每一层横向遍历要删除之前已经用过的元素，path.contains(nums[i])。

子集

核心思想：通过一个变量表示每层循环的开始位置，即可以剪枝过滤掉重复的部分。当开始位置大于等于长度时则说明到底了。

电话号码的字母组合

核心思想：将按键映射到map中，根据按键获取到字符串并循环遍历，每一个按键为树的一层。

注意：

StringBuilder对字符串进行操作
处理为空的特殊情况
回溯完要删除sb.deleteCharAt(sb.length() - 1)

组合总和

核心思想：循环遍历每个元素，深层递归来构建组合，并采用sum记录并传递当前的和。当前和大于目标值停止，等于目标和记录。

注意：

横向：去重操作，在同一层中前面使用过的元素，在下一个情况中就将其删去。
纵向：因为元素可以重复使用，因此循环从i开始，下一层循环还可以从i开始。

括号生成

核心思想：需要n个正括号和n个反括号，因此停止条件为open + close >= 2 * n。之后先添加”(“，当close < open时，可以添加”)”。一个回溯递归中包含了两次引用。

private void backtracing(int n, StringBuilder str, int open, int close){
    if(open + close >= n * 2){
        res.add(str.toString());
        return;
    }
    if(open < n){
        str.append ('(');
        backtracing(n, str, open + 1, close);
        str.deleteCharAt(str.length() - 1);
    }
    if(close < open){
        str.append(')');
        backtracing(n, str, open, close + 1);
        str.deleteCharAt(str.length() - 1);
    }
}

单词搜索

核心思想：采用boolean visited数组来标记该位置是否已经经过，采用index来标记当前word需要寻找的字符，采用i和j来标记位置。采用int[][] dirctions = {{0,1},{0,-1},{1,0},{-1,0}};与i和j进行计算来表示上下左右位置，并且需要对边界进行判断是否符合。循环上下左右位置并判断是否visited中是否经过过，没有经过则进行下一轮递归。终止条件：不符合word需要寻找的字符，返回false；index为word最后一位，返回true；回溯上下状态添加与释放：visited数组。

注意：

起始位置是通过循环每一个位置来进入回溯的。
对上下左右位置的操作，采用dirctions数组来标准化，并与i和j操作完后在判断是否符合范围。

分割回文串

核心思想：和组合一样，组合是在横向循环是循环选取字符，而分割是在横向循环时循环选取空隙（第i个位置后面的分割线）。每层将比上一层多加一个分割线。此外每层到下一层会重新创建一个StringBuilder。

注意：

start为开始位置，循环遍历i为结束位置，每次遍历向StringBuilder中加入一个字符，并判断是否符合回文串。

N皇后

核心思想：横向遍历为一行中哪里放”Q”，纵向遍历则为由上到下一行行生成。创建一个二维的char数组来保存，最后存入结果时转换为List。对于是否可以放置”Q”的判断，需要检查列，45°和135°。

注意：

不需要对行进行检查，因为横向遍历就已经明确只能添加一个了。

对角线检查代码，采用多变量多限制的for循环。

 // 检查45度对角线
for (int i=row-1, j=col-1; i>=0 && j>=0; i--, j--) {
    if (chessboard[i][j] == 'Q') {
        return false;
    }
}

二维char数组转为List

public List Array2List(char[][] chessboard) {
    List<String> list = new ArrayList<>();

    for (char[] c : chessboard) {
        list.add(String.copyValueOf(c));
    }
    return list;
}

二维char数组初始化，不初始化会出现\u0000

1
2
3

for (char[] c : chessboard) {
    Arrays.fill(c, '.');
}

二叉搜索

搜索插入位置

核心思想：二分查找，查到返回对应索引，没查到返回mid索引。

注意：

区间统一，左闭右开
mid初始化，mid应在循环最后进行操作。

搜索二维矩阵

核心思想：二分查找，start和end在比较是转换为row和col。

注意：

区间最好为左右闭区间，因为会有[[1]]，其end为1*1-1，若为左闭右开则会出现问题。

在排序数组中查找元素的第一个和最后一个位置

核心思想：与普通的二分查找相比，需要将查找左右位置的判断分开。

当找左边界时，nums[mid]找到为target值时应继续往左侧收缩，即end = mid - 1
当找右边界时，nums[mid]找到为target值时应继续往右侧收缩，即start = mid + 1
ans为记录结果，当向左收缩时，当前 mid 位置的元素可能是目标值的左边界（或者更左侧的位置）；当向右侧收缩时，当前 mid 位置的元素是大于目标值的，因此目标值不可能出现在 mid 右侧，因此继续缩小搜索范围（right = mid - 1）

private int search(int[] nums, int target, boolean lower){
        int left = 0, right = nums.length;
        int res = nums.length;
        while(left < right){
            int mid = (left + right) / 2;
           	// lower相当于一个开关 对相等的情况进行判断
           	// 找到最右边
            if(nums[mid] < target || (nums[mid] == target && !lower)){
                left = mid + 1;
            // 找到最左边    
            }else if(nums[mid] > target || (nums[mid] == target && lower)){
                right = mid;
                res = mid;
            }
        }
        return res;
    }

搜索旋转排序数组

核心思想：因为旋转导致当分为两部分肯定有一部分是无序的，有一部分是有序的。因此需要判断mid分割后，比较端点来判断左右两边哪边是有序的，再判断target在不在有序的一边，不在那肯定在无序的那一边了。

如果start, mid - 1为有序，且target也在区间内，则缩小至start, mid -1，否则target肯定在无序的mid + 1, end这一边。
如果mid + 1, end有序，且target也在区间内，则缩小至mid + 1, end，否在target肯定在无序的start, mid - 1这一边

寻找旋转排序数组中最小值

核心思想：同上一题，旋转后选取中间值后肯定一边有序一边无序，则有序的一边是不包含最小值的，从而不断删减。

nums[start] > nums[mid]时说明最小值在左边，此时右边完全是递增的，因此是可以舍弃掉的。
nums[mid] > nums[end]时说明最小值在右边，此时左边是递增的，因此是可以舍弃掉。

注意：

左右闭区间的情况下，为什么while不包含=。当 low == high 时，数组的最小元素将被找到，low 就是我们要找的最小值的位置，因此不再需要继续比较。
为什么左侧收敛时，end = mid没有-1，如果使用 high = pivot - 1，意味着每次都会排除掉 pivot，这可能会导致错过最小值的情况。例如，如果 pivot 位置正好是最小值，使用 high = pivot - 1 会导致最小值丢失。因此，为了确保我们不丢失任何可能的最小值，high = pivot 可以让我们把 pivot 作为候选之一，不会错过最小值。

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

核心思想：采用一条边界把两个数组划分为左右两个相等的部分，若长度为奇数则让左边部分多出一个数。之后通过边界值去求中位数。在途中主要是找到如此的分界线，此时划分出的左边数字的数量一定是不小于右边的。这个时候就要验证左边的最大值是否小于右边的最小值，如果满足这个条件则说明整体有序，也说明找到了中间的数值。

选取短的数组进行分割，采用递归的方式，注意return

public double findMedianSortedArrays2(int[] nums1, int[] nums2) {
        // 因为是采用二分查找找到分割点，而另一个数组的分割点即可推导出来
        // 由此选择短的数组进行二分查找，有更优的时间复杂度
        if(nums1.length > nums2.length){
            return findMedianSortedArrays2(nums2, nums1);
        }

采用二分查找的方式找的是切割的位置，切割位置满足左边最大值小于右边最小值。
1
2
3
// 切割位置设置
int i = (left + right)/2;
int j = (m + n + 1) / 2 - i;

特殊情况，即分割在头尾的情况

/ 左上最大值
int nums_im1 = (i == 0 ? Integer.MIN_VALUE : nums1[i-1]);
// 右上最小值
int nums_i = (i == m ? Integer.MAX_VALUE : nums1[i]);
// 左下最大值
int nums_jm1 = (j == 0 ? Integer.MIN_VALUE : nums2[j-1]);
// 右下最小值
int nums_j = (j == n ? Integer.MAX_VALUE : nums2[j]);

栈

有效的符号

核心思想：遍历字符串，将正括号压入栈中，反括号则弹栈比较是否为匹配的正括号。

注意：

弹栈前判断是否栈是否为空
最终判断栈不为空则也为不满足

最小栈

核心思想：当栈中压入一个元素时，该元素不弹出则其之前压入的元素肯定还保留在栈中。因此，每个元素入栈时把当前栈的最小值保存下来，无论何时只要栈顶为该元素则最小值即为记录的值。采用一个最小值辅助栈，当压入一个元素时，该元素与辅助栈栈顶元素比较，压入他们之间的最小值。

注意：

在最小值辅助站初始化时，需要提前压入一个MAX_VALUE
如何做到不适用额外空间？

核心思想：栈中采用与最小值的差值进行记录。初始状态：栈中加入0，最小值记为入栈值，即最小值为入栈值，栈中该值与最小值的差值为0。最小值的维护，当需要入栈的值大于最小值，则栈中记录为正的差值；当小于或等于最小值，则栈中记录为负的差值，并更新最小值。弹出元素：弹出的差值为负，则说明当前弹出的元素为当前的最小值，并更新最小值为栈顶元素（差值）加上最小值；差值为正，则差值加上最小值。

字符串解码

核心思想：采用栈的方式保存，分为三种情况：数字、字符或’[‘、其他(‘]’)，数字范围为0-300因此也要循环遍历获取到多位，字符有两种形态一种是带有数字和[]，一种是单独一次的裸字符的形式。当带数字的形式，则逐步加入到栈中，直到]然后将[之后的都取出来并生成对应次数构造出来的字符串再加入到栈中，而裸字符则直接加入到栈中。最终返回栈中所有内容。

注意：

会出现2[abc]ef3[cd]没有数字次数标识的裸字符形式
数字也是会存在多位的

每日温度

核心思想：维护一个从栈底到栈顶的单调递减栈，当每加入一个元素时确保栈中元素都要比其大，因此需要弹出小于他的元素，弹出的过程中即说明当前插入元素比前面元素温度高。

注意：

单调栈中仅保存温度的索引即可，当比较温度时只要在temperatures数组中用索引查询即可

题解讲得有点复杂，不利于理解。。。说白了，这题考的基础模型其实就是：在一维数组中对每一个数找到第一个比自己小的元素。这类“在一维数组中找第一个满足某种条件的数”的场景就是典型的单调栈应用场景。

柱状图中最大的矩形

核心思想：计算最大的矩形需要知道左右第一次遇到比自己小的高度，一般计算距离自己最近的比自己小或大的元素采用单调栈。本题采用单调递减栈（栈顶到栈底），进栈前弹出的都是左边比自己大的→确定左边界；出栈时必定是右边第一次遇到比自己小的→确定右边界。其实就是维护单调递减栈，进入一个比其小的值时，该元素为弹出栈元素右边最近的比自己小的元素；一个元素入栈后，其压在下面的元素即为左边最近的比自己小的元素。可以采用两个数组即left数组和right数组分别记录该元素左右最小元素索引，最终计算(right[i] - left[i] - 1) * heights[i]即为i为索引元素最大矩形。

堆

数组中的第k个最大元素

核心思想：

维护大小为k的小根堆，小根堆即为一个完全二叉树，且根节点为最小值。先向堆中加入k个元素，之后的元素分别与根节点（堆中最小值）进行比较，最终小根堆中存储的为前k个最大值，根节点则为第k个最大元素。JAVA中采用PriorityQueue即可以实现小根堆，并自己维护大小。
1
PriorityQueue<Integer> minHeap = new PriorityQueue<>(k, Comparator.comparingInt(a->a));

基于快速排序的选择

前k个高频元素

核心思想：遍历数组统计频数存入hash表中，遍历hash表构建小根堆并在小根堆存储频数前k个，最终遍历小根堆存入数组输出结果。

注意：

小根堆的创建，比较器的书写尤为重要！！！

PriorityQueue<Integer> heap = new PriorityQueue<>(new Comparator<Integer>(){
        @Override
        public int compare(Integer a, Integer b){
            return freq.get(a) - freq.get(b);
        }
    });

数据流中位数

核心思想：将数据流保存到堆中，并保持堆的有序性。因此建立一个小顶堆和大顶堆，各保存一半的元素。小顶堆A保存较大的一半，长度N/2或N+1/2，大顶堆B保存较大的一半，长度N/2或N-1/2。

函数 addNum(num) ：
- 当 m=n（即 N 为偶数）：需向 A 添加一个元素。实现方法：将新元素 num 插入至 B ，再将 B 堆顶元素插入至 A 。
- 当 m / n（即 N 为奇数）：需向 B 添加一个元素。实现方法：将新元素 num 插入至 A ，再将 A 堆顶元素插入至 B 。
函数 findMedian() ：
- 当 m=n（ N 为偶数）：则中位数为 ( A 的堆顶元素 + B 的堆顶元素 )/2。
- 当 m/=n（ N 为奇数）：则中位数为 A 的堆顶元素。

贪心

买卖股票的最佳时机

核心思想：假如计划在第 i 天卖出股票，那么最大利润的差值一定是在[0, i-1] 之间选最低点买入；所以遍历数组，依次求每个卖出时机的的最大差值，再从中取最大值。

for(int i=0;i<prices.length;i++){
    if(prices[i] < min){
        min = prices[i];
    }else if(prices[i] - min > maxprofit){
        maxprofit = prices[i] - min;
    }
}

跳跃游戏

核心思想：计算并记录跳跃可到达的的最大索引位置，最大索引位置大于数组时则说明可以跳跃到。最大索引位置i + nums[i]。

if(i <= canSkip){
    canSkip = Math.max(canSkip, i + nums[i]);
    if(canSkip >= nums.length - 1){
        return  true;
    }
}

跳跃游戏II

核心思想：在未遍历完当前节点能到达的位置之前，只是记录能够到达的最大位置。当到达该节点能到的位置时，将选取能到最大位置当下一个节点，步数加1。

// 不访问最后一个元素，这是因为在访问最后一个元素之前，我们的边界一定大于等于最后一个位置，否则就无法跳到最后一个位置了
for(int i=0;i<length-1;i++){
    maxPosition = Math.max(maxPosition, i + nums[i]);
    // end为记录的当前节点能到达的最远位置，只有到达最远位置，才会选取maxPosition当做下一个节点
    if(i == end){
        end = maxPosition;
        steps++;
    }
}
return steps;

划分字母区间

核心思想：首先记录每个字符的最后出现位置，遍历字符串一段字符的停止位置为其中包含字符最后出现位置的最大值。

for (int i=0;i<s.length();i++){
	// 每个循环记录end可以保证不断纳入新的字符
    end = Math.max(end, last[s.charAt(i) - 'a']);
    // 当字符类型固定下来，end是不变的，因此i会到达end的时候就是一段字符结束。
    if(i == end){
        res.add(end - start + 1);
        start = i + 1;
    }
}

图论

岛屿的数量

核心思想：主要考察图的遍历，可以采用深度遍历和广度遍历两种方式。

深度遍历：循环遍历二维数组，每达到一个陆地1，将其赋值为2，判断是否为岛屿1，并进行上下左右进行判断是否1，不断深入直到上下左右为水0或者为已遍历过的2。

腐烂的橘子

核心思想：采用图的广度优先遍历，将可遍历到上下左右的位置，并且可以求出到达某一个点的路径距离为多少。首先，先遍历一遍将最开始腐烂的橘子加入到队列中，并记录新鲜橘子的个数。之后，当新鲜橘子数量大于零并且队列中还有元素时，取出队列中元素对其上下左右进行判断，未出边界未变为腐烂时，则将其加入队列中并将其赋值为腐烂的橘子。

所谓广度优先搜索，就是从起点出发，每次都尝试访问同一层的节点，如果同一层都访问完了，再访问下一层，最后广度优先搜索找到的路径就是从起点开始的最短合法路径。

课程表

核心思想：判断一个有向图是否存在环的问题。

广度优先搜索：创建两个核心变量，List<List<Integer>> edges外层以课程编号为索引，内层存放其后置课程，当该课程学完后要释放其后置课程，int[] indeg用于表示以课程编号为索引的前置还未学习的课程，即课程的入度。首先构造edges列表和indeg数组，之后将需要0个前置课程的课程加入到队列中，队列中每弹出一个元素，需要遍历其后置edges列表中的元素，让其indeg值减一，当为0时则加入队列。采用变量记录弹出元素个数，当队列为空时弹出数量与课的总数进行对比得出结果。

实现Trie（前缀树）

核心思想：其可以看成一种有向无环图，但是其实用树的思想。

 private class TrieNode{
    boolean isEnd;
    TrieNode[] next;

    public TrieNode() {
        this.isEnd = false;
        this.next = new TrieNode[26];
    }
}

动态规划

爬楼梯

核心思想：

dp数组含义：dp[i]表示到达该位置有几种方法
dp数组初始化：dp[0] = 1，dp[1] = 1
递推公式：dp[i] = dp[i-1] + dp[i-2]，因为到该层台阶一定是上一层或上两层到达的（迈动1或2步）
遍历方式：按顺序从2开始遍历。

注意：可采用三个变量循环的方式进行计算

杨辉三角

核心思想：从第二层开始，每层的数量与层数相同，每层的第一个和最后一个为1，其余通过上一层进行计算得到。

打家劫舍

核心思想：

dp数组含义：dp[i]表示当前位置及以前可获得的最大金额
dp数组初始化：dp[0] = nums[0]，dp[1] = Math.max(nums[0], nums[1])，因为相邻两家不能同时获得。
递推公式：dp[i] = Math.max(dp[i-2] + nums[i] , dp[i-1])，要么选取当前位置并获得前前一个的dp，要么选取前一个位置不选取当前位置。
遍历方式：按顺序从2开始遍历

注意：

nums长度为0或1或为null
可以采用变量循环的方式计算

完全平方数

核心思想：

dp数组含义：dp[j]表示j数字最少需要dp[i]个完全平方数相加
dp数组初始化：dp[0] = 0，数字0需要0个完全平方数相加，其他位置为n + 1，因为要求的是最少的数量，所以要初始化为最大值
递推公式：d[j] = Math.min(dp[j], dp[j - i*i] + 1)
遍历方式：外层为物品（1到n的平方根的数=>1到i*i<=n），内层为背包（满足的数字，0到n）

零钱兑换

核心思想：

dp数组含义：dp[j]表示总金额j最少需要dp[j]个硬币来凑够
dp数组初始化：dp[0] = 0，0元需要0个硬币，其他位置为amount + 1，因为要求的是最少的数量，所以要初始化为到达不了的最大值
递推公式：dp[j] = Math.min(dp[j]，dp[j - coins[i]] +1)
遍历方式：外层为物品（硬币的币值coins，0到coins.length），内层为背包（实现amount金额最少硬币数，coins[i]到amount）

单词拆分

核心思想：

dp数组含义：boolean类型数组，dp[i]表示字符串从头到i的位置是否正好包含完整的单词个数
dp数组初始化：dp[0] = true，因为其为递推公式开始必须为true，含义为空字符串包含0个完整的单词
递推公式：当字符串[j, i)正好为一个完整的单词时，并且dp[j]已经被标记为包含完整个单词，即在j之前已经是包含完整单词了，[j,i)又发现了新的完整的单词

遍历方式：因为是求排列，即单词需要按顺序组合成字符串的，因此需要外层为背包（字符串，其实是采用外层遍历作为字符截取的右侧），内层为物品（其实不是遍历单词，而是遍历从0到i即字符截取的左侧）

// i作为字符串截取的右边界
for(int i=1;i<=s.length();i++){
	// j作为字符串截取的左边界，但是当前
    for(int j=0;j<i;j++){
        if(dp[j] && wordSet.contains(s.substring(j, i))){
                dp[i] = true;
        }
    }
}

最长递增子序列

核心思想：

dp数组含义：dp[i]为从头到i最长递增子序列长度
dp数组初始化：全部为1，即自己作为子序列的情况
递推公式：选取从[0, i)中，且nums[j] < nums[i]中所记录的最长递增子序列，即Math.max(dp[i], dp[j] + 1)
遍历方式：外层[1, nums.length)，因为第一个数肯定为1在初始化时已经赋值，内层[0, i)即遍历0到i中找到前面满足递推公式条件的最长递增子序列

注意：

最终结果并不在dp数组最后一个元素，而是dp数组的最大值，在外层循环内就可以进行比较获取
数组为0和1长度的情况

乘积最大子数组

核心思想：主要是解决存在负数之间相乘得到最大值的情况

dp数组含义：max[i]表示从头到i最大的连续乘积，min[i]表示从头到i最小的连续乘积
dp数组初始化：其自身为其最小的乘积子数组，因此遍历进行赋值
递推公式：max[i] = Math.max(nums[i] max[i - 1], Math.max(nums[i] min[i - 1], nums[i]))，第一项为前面连续乘积为正数和当前值为正数的情况，第二项为筛选出当前为负值乘以前面连续乘积为负值，如果其中有一个不为负则采用本身值。min[i] = Math.min(nums[i] min[i - 1], Math.min(nums[i] max[i - 1], nums[i]))，同上叙述思路记录前面最小的乘积，主要用于负数之间相乘得到最大值的情况进行最小值记录
遍历方式：一层遍历[1, nums.length)。

注意：

最终结果为max数组中最大值，需要遍历获取
测试用例中包含long类型，因此最大值和最小值要用long类型存储
在对min计算时，当min<Integer.MIN_VALUE时，要将其修正最小乘积值if(min < Integer.MIN_VALUE) min = nums[i];
采用滚动变量对数组进行最大值和最小值进行记录，但是在循环中需要注意在max会在循环中被修改，min再调用时已不是原来的遍历，因此采用临时数值存储后再进行操作和调用。

分割等和子集

核心思想：找数值和相等的两个子集，转化为，找和为总和一半的子集。采用01背包解决。

dp数组含义：dp[j]表示背包数值为j时，能够装的最大数值组合的总和。当能装的最大数值组合的总和正好为总和的一半时则为存在两个相等的子集。
dp数组初始化：dp[0] = 0，全部设置为0即可。
递推公式：dp[j] = Math.max(dp[j], dp[j-nums[i]] + nums[i])，即不采纳当前数值和采纳当前数值哪个更大。
遍历方式：01背包一维数组表示，需要物品在外面，背包在内部，背包倒序遍历。

不同路径

核心思想：

dp数组含义：d[i][j]表示到达i行j列的路径数量
dp数组初始化：dp[0][i]和dp[0][j]即第一行第一列仅有一种方式到达，因此初始化为1。
递推公式：dp[i][j]= dp[i-1][j]+dp[i][j-1]
遍历方式：两层遍历都是从1开始到结尾

注意：

可采用一维数组进行压缩

最小路径和

核心思想：

dp数组含义：dp[i][j]表示到达i行j列的最小路径和
dp数组初始化：dp[0][i]为grid[0][0]-grid[0][1]的累加和，dp[i][0]为grid[0][0]-grid[i][0]的累加和
递推公式：dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
遍历方式：两层遍历都是从1开始到结尾

注意：

可采用一维数组进行压缩，注意每行开始元素需要在遍历中特殊处理

最长回文串

核心思想：

dp数组含义：d[i][j]即字符串从i到j是否为回文串，采用boolean类型数组
dp数组初始化：dp[i][i]全部为true，即为自身回文
递推公式：dp[i][j] => s.charAt(i) == s.charAt(j) && dp[i+1][j-1] == true
遍历方式：外层为j即回文串末尾，内层为i即回文串外层

注意：

采用maxLen在每次确定dp[i][j]后即可计算是否比当前最大长度大，并且记录i的开始位置
i和j相距2

最长公共子序列

核心思想：

dp数组含义：dp[i][j]将表示text1字符串[0,i-1]和text2字符串[0,j-1]的最长公共子序列，为何如此设计参考最长重复子数组，主要是为了减少第一行和第一列的初始化。
dp数组初始化：当i和j为0时，即最长公共子序列长度均为0，由此i和j都从1开始遍历
递推公式：字符相同时则在基础上+1，不相同则继承上或左选取最大值
遍历方式：内外层分别从1开始遍历两个字符串

注意：

dp数组含义，以及为什么采取i-1和j-1进行dp数组含义的设计

编辑距离

核心思想：增加操作和删除操作是等效的，即word1增加和word2减少使其相等是一个操作；替换操作则是在上次操作的基础上加一步。

dp数组含义：dp[i][j]即word1[0,i-1]序列要经过多少步可以和word2[0,j-1]是相同的
dp数组初始化：当i或j为0的时候，即另外一方与空串之间相差的操作步数，即为非空一方的字符串长度
递推公式：当word1.charAt(i-1) == word2.charAt(j-1)时，即字符相同不用再额外添加操作步数，直接继承dp[i-1][j-1]结果；当不相等时，要么若有一边变长，则要么word1删除，要么word2添加，这两个操作都是等效的，即继承dp[i-1][j]和dp[i][j-1]，若长度相同但是字符不同，则进行替换，即继承dp[i][j]，将在这三种情况中选取最小值并进行+1。
遍历顺序：两个字符串从1开始进行遍历

最长有效括号

核心思想：

dp数组含义：dp[i]为以下标i字符结尾的最长有效括号的长度
dp数组初始化：全部为0，

递推公式：

当s[i]=')'且s[i-1] ='('时，dp[i] = dp[i−2]+2。

当s[i]=')'且s[i-1]=')'时，dp[i] = dp[i-1] + 2 + dp[i-dp[i-2]]

// 如果不为反括号即最长默认为0
if (s.charAt(i) == ')') {
	// 分为的两种情况
    if (s.charAt(i - 1) == '(') {
    	// 要保证i-2大于等于0，才能考虑加入前面的有效括号
        dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
        // i - dp[i - 1] > 0，不大于零则说明前面没有能和他匹配的括号了
    } else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
        // 要保证i - dp[i - 1] - 2 > 0，才能考虑加入前面的有效括号
        dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
    }
    maxans = Math.max(maxans, dp[i]);
}

<img src="https://lrblog-img-1304667442.file.myqcloud.com/image-20241210005300789-1749351863409-47.png" alt="image-20241210005300789" style="zoom:25%;" />

遍历顺序：因为要获得i-1的字符来做判断，因此从1开始到字符串长度，在遍历过程中即可比较记录最大值。

技巧

只出现一次的数字

核心思想：采用异或运算。

1	int single ^= num;

注意：也可以用作只出现奇数次的数字

多数元素

核心思想：Boyer-Moore 投票算法，如果我们把众数记为 +1，把其他数记为 −1，将它们全部加起来，显然和大于 0，从结果本身我们可以看出众数比其他数多。

“同归于尽消杀法” ：

由于多数超过50%, 比如100个数，那么多数至少51个，剩下少数是49个。

第一个到来的士兵，直接插上自己阵营的旗帜占领这块高地，此时领主 winner 就是这个阵营的人，现存兵力 count = 1。
如果新来的士兵和前一个士兵是同一阵营，则集合起来占领高地，领主不变，winner 依然是当前这个士兵所属阵营，现存兵力 count++；
如果新来到的士兵不是同一阵营，则前方阵营派一个士兵和它同归于尽。此时前方阵营兵力count —。（即使双方都死光，这块高地的旗帜 winner 依然不变，因为已经没有活着的士兵可以去换上自己的新旗帜）
当下一个士兵到来，发现前方阵营已经没有兵力，新士兵就成了领主，winner 变成这个士兵所属阵营的旗帜，现存兵力 count ++。

就这样各路军阀一直以这种以一敌一同归于尽的方式厮杀下去，直到少数阵营都死光，那么最后剩下的几个必然属于多数阵营，winner 就是多数阵营。（多数阵营 51个，少数阵营只有49个，死剩下的2个就是多数阵营的人）

颜色分类

核心思想：采用两个指针分别用来交换0和1。从左向右遍历，如果找到1，则nums[p1]与nums[i]进行交换，并p1自增；如果找到0，nums[p0]与nums[i]进行交换，当p0<p1时，说明已经将一些连续的1放在头部，而此时p0指的应该是一个为1的值，由此应该让交换完的值为1的nums[i]再和p1交换，使得其放到连续1的末尾，最后p0和p1都要向后移动位置。

下一个排列

核心思想：形式化地描述为：给定若干个数字，将其组合为一个整数。如何将这些数字重新排列，以得到下一个更大的整数。如下需求：①需要左边「较小数」与右边「较大数」交换②要让这个「较小数」尽量靠右，而「较大数」尽可能小。当交换完成后，「较大数」右边的数需要按照升序重新排列。这样可以在保证新排列大于原来排列的情况下，使变大的幅度尽可能小。