算法合集

合并两个升序数组，空间复杂度要求为O(1)

移除数组中的指定值，并且让剩余元素集中在前列。

删除非严格递增排列的数组nums中的重复项，采用双指针法解答

删除有序数组中的重复项2，利用了双指针以及指针-1、指针-2位置的含义进行解答。

判断当前字符串是不是回文串，比较简单。

这题的最佳解法用到了概率统计，利用随机选取的期望把空间复杂度降到了O(1)。

栈的经典题目，括号匹配

将数组的元素依次向右移动k个位置。

判断一个串是否是主串的子序列，可以用简单的双指针或者动态规划进行解答。

这题要求得到二叉树的最大深度，可以采用深度搜索或广度搜索两种方式解答

买卖股票的最佳时机，本质是用的动态规划的思想，用之前的结果和当前的状态进行递推。

该题是买卖股票的最佳时机的进阶题，可以采用简单的贪心算法解答，也可以采用动态规划的思路

合并区间，将数组排序后进行合并即可

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。用贪心法即可解答

跳跃游戏I的进阶题，这次要得到到达n-1的位置的最小次数。

给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。 根据维基百科上 h 指数的定义：h 代表“高引用次数

需要实现一个数据结构，能够O(1)时间插入、删除和获取随机元素。需要组合哈西表和顺序表两种数据结构才能实现，

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

该解法的关键点是需要认识到，如果x最远只能到达y，那么x到y之间的加油站也到达不了y+1。所以x到y之间的点就都可以被排除。所以下一次检查从y+1开始就可以。时间复杂度为O(n)

这题可以用贪心算法解答，只要遍历两边，分别得到满足左规则和右规则的两个数组即可。最终该解法的时间复杂度为O(n)，空间复杂度也为O(n)。

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。和发糖果有点相似，都是得到满足左右规则的数组，然后让同时满足。还通过动态规划优化得到数组的过程。

罗马数字转整数，一般字符顺序是从大到小，需要特殊处理左边字符小于右边字符的情况。

将整数转换成罗马数字。是找零问题和罗马数字转整数的结合，用贪心解题即可

给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。

编写一个函数来查找字符串数组中的最长公共前缀。这题主要有两种思路，一种是逐个比较，时间复杂度是O(mn)。另一种是按字典排序后，直接比较第一个字符串和最后一个，时间复杂度时O(mnlogn)。

给你一个字符串 s ，请你反转字符串中 单词的顺序。主要是利用到了字符串中常用的方法。

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。可以用暴力法或者KMP求解。

给定一个单词数组 words 和一个长度 maxWidth ，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。

给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。

给定一个长度为 n 的整数数组 height 。有n条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线，使得它们与x轴共同构成的容器可以容纳最多的水

这题可以看作是两数之和II的进阶题，将三数之和问题转化为两数之和问题后，再求解。难点在于三个去重时机。

给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其总和大于等于 target 的长度最小的 子数组，并返回其长度。如果不存在，则返回0

给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。可以用map和滑动窗口进行解决。

串联所有单词的子串，用滑动窗口解决，比较困难。

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

这题通过hashmap简化了查找的过程，从而使得一次遍历即可完成检查。

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

这题主要的目标还是降低空间复杂度，简单的做法需要复制矩阵以免影响计算。进阶做法可以通过定义新状态来防止状态污染的同时又降低空间复杂度。

这题比较简单，涉及重复查找的题型都可以考虑用hashmap简化查找操作

该题用哈希表实现映射即可。

这题同样是使用哈希表实现一对一的映射，用两个哈希表即可实现。

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的 字母异位词。

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。用哈希表存储差值，遍历nums看看有没有符合差值的。

编写一个算法来判断一个数 n 是不是快乐数。

给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

汇总区间

在一个无重叠的升序区间列表中插入一个新区间。

这题排序以后依次求出交集即可，交集的数量即是答案。

用split方法按照/进行切割，然后将目录名存入栈，碰到..就出栈，碰到.与空则不做操作。

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

逆波兰表达式求值，也就是后缀表达式求值，使用栈进行处理即可。

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

给你一个链表的头节点 head ，判断链表中是否有环。

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。 请你将两个数相加，并以相同形式返回一个表示和的链表。

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。这题可以两次遍历或者用栈解决，一次遍历可以用快慢指针解决。

给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。 你应当 保留 两个分区中每个节点的初始相对位置。

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。可以通过深搜（先/中/后序遍历）或广搜（层次遍历）解决。

给你一个二叉树的根节点 root ， 检查它是否轴对称。

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

给定一个二叉树，填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL 。

展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。 展开后的单链表应该与二叉树 先序遍历 顺序相同。

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 tr

计算从根节点到叶节点生成的 所有数字之和 。

实现一个二叉搜索树迭代器类BSTIterator ，表示一个按中序遍历二叉搜索树（BST）的迭代器

给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（k 从 1 开始计数）。

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' 组成，捕获 所有 被围绕的区域

给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。

用图来表示节点的除法。

这题是经典的拓扑排序题目。

课程表II，除了要判断是否有环，还需要返回课程学习的顺序

这题首先要将变化过程抽象为图的遍历过程。求A到C的最少变化次数，就是找图的两点间最短路径。无权图就可以通过广度优先遍历进行求解，有权图可以通过Dijkstra求解。

Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。

请你设计一个数据结构，支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。

回溯其实就是带选择的DFS

这题的核心思路在于让之后选择的数字比之前选择的都大（升序），就可以避免重复结果。

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。

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

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树。

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

给你一个 n * n 矩阵 grid ，矩阵由若干 0 和 1 组成。请你用四叉树表示该矩阵 grid 。

给定一个长度为 n 的环形整数数组 nums ，返回 nums 的非空 子数组 的最大可能和 。

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

从一个递增的二维数组中查找目标。这题只需要把二维数组下标转一维数组下标，然后进行二分查找即可。

峰值元素是指其值严格大于左右相邻值的元素。 给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

升序数组旋转后查找指定值。

查找经过旋转的升序数组的最小值。

给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。

颠倒给定的 32 位有符号整数的二进制位。

给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。

给你两个整数 left 和 right ，表示区间 [left, right] ，返回此区间内所有数字 按位与 的结果（包含 left 、right 端点）。

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

给定一个三角形 triangle ，找出自顶向下的最小路径和。

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。 说明：每次只能向下或者向右移动一步。

带障碍的机器人移动，求机器人到达左下角的路径总数。

给你一个字符串 s，找到 s 中最长的 回文 子串。

给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。

在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性： 每行的元素从左到右升序排列。 每列的元素从上到下升序排列。

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

给定一个正整数 n，编写一个函数，获取一个正整数的二进制形式并返回其二进制表达式中 设置位 的个数（也被称为汉明重量）。