/** * 解法一：边界模拟法 * 思路： * 我们想象有一一个矩阵，从第一- 个元素开始，往右到底后再往 * 下到底后再往左到底后再往上，结束这一-圈，进入下一圈螺旋。 * 时间复杂度: O(mn)，相当于遍历整个矩阵. * 空间复杂度: 0(1)，res属于必要空间，没有使用额外辅助空间 */ export function spiralOrder(matrix: number[][]): number[] { const res: number[] = [] if (matrix.length === 0) return res let left ...

/** * 解法一：迭代（双指针） * 思路： * 我们可以设置两个指针，一个当前节点的指针，一个上一个节点的指针(初始为空)。 * 遍历整个链表，每到一个节点，断开当前节点与后面节点的指针，并用临时变量记录后一个节点，然后当前节点指向上一个节点。 * 再轮换当前指针与上-一个指针，让它们进入下一个节点及下一个节点的前序节点。 * 时间复杂度: O(n)，遍历链表一次 * 空间复杂度: 0(1)，无额外空间使用 */ export function ReverseList(head: ListNode | null): ListNode | null { if ...

/** * 解法二：动态规划 * 思路： * 可以用dp数组表示以下标i为终点的最大连续子数组和。 * 每次遇到一个新的数组元素，连续的子数组要么加，上变得更大，要么它本 * 身就更大，因此状态转移为dp[i] = max(dp[i - 1] + array[i], array[i])。 * 遍历数组，每次只要比较取最大值即可。 * 时间复杂度：O(n)，遍历一遍。 * 空间复杂度：O(n)，动态规划辅助数组长度为n */ export function FindGreatestSumOfSubArray(nums: number[]): number { ...

/** * 解法一：回溯 + 递归 * 思路： * 全排列就是对数组元素交换位置，使每--种排列都可能出现。因为题目要求按照字典序排 * 列输出，那毫无疑问第-一个排列就是数组的升序排列，它的字典序最小，后续每个元素与 * 它后面的元素交换一次位置就是一种排列情况，但是如果要保持原来的位置不变，那就不 * 应该从它后面的元素开始交换而是从自己开始交换才能保证原来的位置不变，不会漏情况。 * 时间复杂度: O(n!), n个元素的数组进行全排列 * 空间复杂度: O(n), 递归栈的最大深度为数组长度n，res属于返回必要空间 */ export functio...

/** * 解法一：递归（先序遍历） * 思路： * 既然是检查从根到叶子有没有一-条等于目标值的路径，那肯定需要从根节点遍历到叶子， * 我们可以在根节点每次往下一层的时候，将sum减去节点值，最后检查是否完整等于0.而 * 遍历的方法我们可以选取二叉树常用的递归先序遍历，因为每次进入一个子节点，更新 * sum值以后，相当于对子树查找有没有等于新目标值的路径，因此这就是子问题 * 时间复杂度：O(n)，先序遍历二叉树所有结点 * 空间复杂度：O(n)，最坏情况二叉树化为链表，递归栈空间最大为n */ export function hasPathSum(r...

/** * 解法一：非递归（BFS） * 思路： * （1）首先判断二叉树是否为空，空树没有遍历结果。 * （2）建立辅助队列，根节点首先进入队列。不管层次怎么访问，根节点一定是.第一个，那它肯定排在队伍的最前面。 * （3）每次进入一层，统计队列中元素的个数。因为每当访问完一一层，下一-层作为这一层的子节点， * 一定都加入队列，而再下一层还没有加入，因此此时队列中的 * （4）每次遍历这一层这么多的节点数，将其依次从队列中弹出，然后加入这一行的一维数组中，如果它们有子节点， * 依次加入队列排队等待访问。元素个数就是这-层的元素个数。 * （5）访问完...

/** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * @param a int整型一维数组 * @param n int整型 * @param K int整型 * @return int整型 */ /** * 解法一：快速排序 * 思路：快排，取得升序数组，然后取下标 nums.length - k + 1 对应的值 * 时间复杂度：O(nlogn) * 空间复杂度：最优 O(logn)， 最差 O(n) */ export function findKth(a: number[], n: number, K: numb...

/** * 解法一：双指针 * 思路：待补充 * 时间复杂度：O(n^2) * 空间复杂度：待补充 */ export function threeSum(num: number[]): number[][] { const res: number[][] = [] const len = num.length if (len < 3) return res num.sort((a, b) => a - b) for (let i = 0; i < len - 2; i++) { // 避免重复元素 ...

/** * 解法一：暴力法（嵌套循环） * 思路： * （1）我们需要找出给定数组中两个数字之间的最大差值（即，最大利润）。 * （2）此外，第二个数字（卖出价格）必须大于第一个数字（买入价格）。 * 时间复杂度：O(n^2)。 * 空间复杂度：0(1)，只使用了一个常数变量。 */ function maxProfit(prices: number[]): number { let maxprofit = 0 for (let i = 0; i < prices.length - 1; i++) { for (let j = i + 1;...

/** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * 将给定数组排序 * @param arr int整型一维数组 待排序的数组 * @return int整型一维数组 */ /** * 解法一：快速排序 * 思路： * （1）快速排序的主要思想是通过划分将待排序的序列分成前后两部分，其中前一部分的数据都比后一部分的数据要小， * （2）然后再递归调用函数对两部分的序列分别进行快速排序，以此使整个序列达到有序。 * 时间复杂度：O(nlogn) * 空间复杂度：O(h)，其中 h 为快速排序递归调用的层数。我们需要额外的 O(h) 的...

/** * 解法一：双指针 * 思路： * （1）设置快慢两个指针，初始都指向链表头。 * （2）遍历链表，快指针每次走两步，慢指针每次走一步。 * （3）如果快指针到了链表末尾，说明没有环，因为它每次走两步，所以要验证连续两步是否为 NULL。 * (4）如果链表有环，那快慢双指针会在环内循环，因为快指针每次走两步，因此快指针会在环内追到慢指针，二者相遇就代表有环。 * 时间复杂度: O(n),最坏情况下遍历链表n个节点 * 空间复杂度: O(1)，仅使用了两个指针，没有额外辅助空间 */ export function hasCycle(head: ListNode |...

/** * 解法一：动态规划 * 思路：https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zui-chang-hui-wen-zi-chuan-by-leetcode-solution/ * 时间复杂度：O(n^2)，其中 n 是字符串的长度。动态规划的状态总数为 O(n^2)，对于每个状态，我们需要转移的时间为 O(1)。 * 空间复杂度：O(n^2)，即存储动态规划状态需要的空间。 */ export function getLongestPalindrome(A: string): n...

/** * 解法一：深度优先搜索 * 思路： * （1）从根节点开始，遍历每个节点，如果遇到叶子节点，则将叶子节点对应的数字加到数字之和。 * （2）如果当前节点不是叶子节点，则计算其子节点对应的数字，然后对子节点递归遍历。 * 时间复杂度：O(n)，其中 n 是二叉树的节点个数。对每个节点访问一次。 * 空间复杂度：O(n)，其中 n 是二叉树的节点个数。空间复杂度主要取决于递归调用的栈空间，递归栈的深度等于二叉树的高度， * 最坏情况下，二叉树的高度等于节点个数，空间复杂度为 O(n)。 */ export function sumNumbers(root: TreeNod...

/** * 解法一：递归 * 思路： * （1）最大深度是所有叶子节点的深度的最大值，深度是指树的根节点到任一-叶子节点路径上节点的数量， * （2）因此从根节点每次往下一层深度就会加1。 * （3）因此二叉树的深度就等于根结点这个1层加上左子树和右子树深度的最大值 * 时间复杂度: O(n)，其中n为二叉树的节点数，遍历整棵二叉树 * 空间复杂度: O(n)，最坏情况下，二叉树化为链表，递归栈深度最大为n */ export function maxDepth(root: TreeNode | null): number { if (root == null) ret...