/** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 给定数组的最长严格上升子序列的长度。 * @param arr int整型一维数组 给定的数组 * @return int整型 */ /** * 解法一：动态规划 * 思路： * （1） * 时间复杂度：O(n^2)，其中 nn 为数组 nums 的长度。 * 空间复杂度：O(n)O(n)，需要额外使用长度为 nn 的 dpdp 数组。 */ export function LIS(arr: number[]): number { if (arr.length == ...

/*class ListNode { * val: number * next: ListNode | null * constructor(val?: number, next?: ListNode | null) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } * } */ /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * ...

/** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * @param n int整型 * @return string字符串一维数组 */ export function generateParenthesis(n: number): string[] { const res: string[] = [] resursion(0, 0, '', res, n) return res } function resursion(left: number, right: number, temp: string, res: ...

/** * 解法一：深度优先 * 思路： * （1）当我们遇到矩阵的某个元素为1时，首先将其置为了0 * （2）然后查看与它相邻的上下左右四个方向，如果这四个方向相邻元素为1，则进入该元素 * （3）进入该元素之后我们发现又回到了刚刚的子问题，又是把这一片相邻区域的 1 全部置为 0 ，因此可以用递归实现。 * 时间复杂度：O(nm)，其中m、n为矩阵的长和宽，需要遍历整个矩阵，每次dfs搜索需要经过每个值为1的元素， * 但是最坏情况下也只是将整个矩阵变成0，因此相当于最坏遍历矩阵2次 * 空间复杂度：0(nm)，最坏情况下整个矩阵都是1，递归栈深度为 *...

/** * 解法一：循环 * 思路： * （1）从数组首尾开始，每次取中点值。 * （2）如果中间值等于目标即找到了，可返回下标，如果中点值大于目标， * 说明中点以后的都大于目标，因此目标在中点左半区间，如果中点值小于目标，则相反。 * （3）根据比较进入对应的区间，直到区间左右端相遇，意味着没有找到。 * 时间复杂度：O(log2n)，对长度为n的数组进行二分，最坏情况就是取2的对数 * 空间复杂度：0(1)，无额外空间 */ export function search(nums: number[], target: number): number { con...

/** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * @param number int整型 * @return int整型 */ /** * 解法一：递归（超时） * 思路：满足斐波那契数列公式，最简单的肯定是递归 * 时间复杂度：O(2^n)，每个递归会调用两个递归，因此会成二的指数级增长 * 空间复杂度： */ export function jumpFloor(number: number): number { if (number <= 1) return 1 return jumpFloor(...

/** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * @param numbers int整型一维数组 * @param target int整型 * @return int整型一维数组 */ /** * 解法一：双层循环（不可用，运行超时） * 思路：详情看以下代码 * 时间复杂度：O(n^2)，双层循环 * 空间复杂度：O(1) * 注意：如果这里的 nums 是有序的话，优化嵌套循环，可以考虑 “双指针” */ // export function twoSum(numbers: number[], target: ...

/** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * @param s string字符串 * @return bool布尔型 */ /** * 解法一：栈 * 思路： *（1）左括号，压栈 *（2）右括号，则判断栈顶是否匹配（是否出栈）否则直接 return false * (3) 最后 return stack.length === 0 * 时间复杂度：O(n)，其中 n 为字符串长度 * 空间复杂度：O(n)，最坏情况下栈空间记录整个字符串长度的右括号 */ function isMatch(left: string...

/** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * 计算两个数之和 * @param s string字符串 表示第一个整数 * @param t string字符串 表示第二个整数 * @return string字符串 */ /** * 解法一：模拟法（双尾指针法） * 思路：模拟我们日常加法进位过程，详细过程看代码 * 时间复杂度：O(n)，其中 n 为较长字符的长度，遍历字符串 * 空间复杂度：O(1)，常数级空间 */ export function solve(s: string, t: string): string ...

/** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * @param arr int整型一维数组 the array * @return int整型 */ /** * 解法一：滑动窗口（reduce累加器） * 此题与leetcode 003 题类似 * 思路： * （1）先判断数组 arr 的长度，如果 arr.length <= 1 直接返回 arr.length * （2）使用数组的 reduce 累加器，滑动窗口过程处理（详细过程看以下代码） * （3）返回最长无重复子数组的长度 maxLen * 时间复杂度：O(...

/** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * 验证IP地址 * @param IP string字符串 一个IP地址字符串 * @return string字符串 */ /** * 解法一：正则 * 时间复杂度：O(n)，正则默认 O(n) * 空间复杂度：O(n) */ export function solve(IP: string): string { const arrIPv4: any[] = IP.split('.') const arrIPv6: any[] = IP.split(':') c...

/** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * @param strs string字符串一维数组 * @return string字符串 */ /** * 解法一：遍历查找 * 时间复杂度：O(mn),其中 m 为数组中最短的字符串的长度，n 为字符串数组的长度 * 空间复杂度：O(1)，没有使用额外的辅助空间 */ export function longestCommonPrefix(strs: string[]): string { if (strs.length === 0) return '' f...

/** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * @param s string字符串 * @param n int整型 * @return string字符串 */ /** * 解法一：正则 * 时间复杂度：O(n) * 空间复杂度：O(n) */ export function trans(s: string, n: number): string { let res: string = '' if (s.length === 0 || n === 0) return res // 翻...

/** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 比较版本号 * @param version1 string字符串 * @param version2 string字符串 * @return int整型 */ /** * 解法一：分割截取 * 思路： *（1）先根据.号分割成字符串数组，获取两个数组中的最大长度值， *（2）按顺序遍历比较，详细过程看以下代码 * 时间复杂度：O(max(n, m)) * 空间复杂度：O(max(n, m)) */ export function compare(version1: ...