算法进阶——滑动窗口的最大值

2 月 6 日
阅读 2 分钟
194
例如,如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3,那么一共存在6个滑动窗口,他们的最大值分别为{4,4,6,6,6,5}; 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个: {[2,3,4],2,6,2,5,1}, {2,[3,4,2],6,2,5,1}, {2,3,[4,2,6],2,5,1}, {2,3,4,[2,6,2],5,1}, {2,3,4,2,[6,2,5],1}, {2,3,4,2,6,[2,5,1]}。

算法进阶——数据流中的中位数

1 月 22 日
阅读 2 分钟
107
如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流,使用GetMedian()方法获取当前读取数据的中位数。

算法进阶——按之字形顺序打印二叉树

1 月 9 日
阅读 3 分钟
88
题目给定一个二叉树,返回该二叉树的之字形层序遍历,(第一层从左向右,下一层从右向左,一直这样交替)。数据范围:0≤n≤1500,树上每个节点的val满足∣val∣<=1500要求:空间复杂度:O(n),时间复杂度:O(n)例如:给定的二叉树是{1,2,3,#,#,4,5}该二叉树之字形层序遍历的结果是[[1],[3,2],[4,5]]示例1 {代码...} 示例2...

算法进阶——求二叉树的层序遍历

2023-12-28
阅读 2 分钟
65
题目给定一个二叉树,返回该二叉树层序遍历的结果,(从左到右,一层一层地遍历)。例如:给定的二叉树是{3,9,20,#,#,15,7},该二叉树层序遍历的结果是[[3],[9,20],[15,7]]提示:0 <= 二叉树的结点数 <= 1500示例1 {代码...} 示例2 {代码...} 思路利用辅助队列,通过bfs(广度优先)算法遍历二叉树,按层次顺序记录...

算法进阶——删除有序链表中重复的元素

2023-12-06
阅读 2 分钟
133
题目给出一个升序排序的链表,删除链表中的所有重复出现的元素,只保留原链表中只出现一次的元素。例如:给出的链表为1→2→3→3→4→4→5, 返回1→2→5。给出的链表为1→1→1→2→3, 返回2→3。数据范围:链表长度0≤n≤10000,链表中的值满足∣val∣≤1000要求:空间复杂度O(n),时间复杂度O(n)进阶:空间复杂度O(1),时间复杂度O(n)示例...

算法进阶——链表中环的入口节点

2023-11-20
阅读 3 分钟
170
题目给一个长度为n链表,若其中包含环,请找出该链表的环的入口结点,否则,返回null。数据范围:1<=结点值<=10000要求:空间复杂度O(1),时间复杂度O(n)例如,输入{1,2},{3,4,5}时,对应的环形链表如下图所示:可以看到环的入口结点的结点值为3,所以返回结点值为3的结点。输入描述:输入分为2段,第一段是入环前...

算法进阶——旋转数组

2023-11-10
阅读 1 分钟
89
一个数组A中存有 n 个整数,在不允许使用另外数组的前提下,将每个整数循环向右移 M( M >=0)个位置,即将A中的数据由(A0 A1 ……AN-1 )变换为(AN-M …… AN-1 A0 A1 ……AN-M-1 )(最后 M 个数循环移至最前面的 M 个位置)。如果需要考虑程序移动数据的次数尽量少,要如何设计移动的方法?

算法进阶——数组中只出现一次的两个数字

2023-10-26
阅读 2 分钟
58
题目一个整型数组里除了两个数字只出现一次,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。数据范围:数组长度2≤n≤1000,数组中每个数的大小0<val≤1000000要求:空间复杂度O(1),时间复杂度 O(n)提示:输出时按非降序排列。示例1 {代码...} 示例2 {代码...} 思路第一个知识点是:任何一个数字异或它...

算法进阶——数组中的逆序对

2023-10-23
阅读 3 分钟
151
在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P mod 1000000007

算法进阶——丑数

2023-10-18
阅读 2 分钟
169
把只包含质因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第 n个丑数。

算法进阶——最小的K个数

2023-10-13
阅读 2 分钟
90
给定一个长度为 n 的可能有重复值的数组,找出其中不去重的最小的 k 个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4(任意顺序皆可)。

算法进阶——字符串的排列

2023-10-11
阅读 2 分钟
161
输入一个长度为 n 字符串,打印出该字符串中字符的所有排列,你可以以任意顺序返回这个字符串数组。例如输入字符串ABC,则输出由字符A,B,C所能排列出来的所有字符串ABC,ACB,BAC,BCA,CBA和CAB。

每日一题——二叉搜索树的最近公共祖先

2023-08-22
阅读 2 分钟
652
对于该题的最近的公共祖先定义:对于有根树T的两个节点p、q,最近公共祖先LCA(T,p,q)表示一个节点x,满足x是p和q的祖先且x的深度尽可能大。在这里,一个节点也可以是它自己的祖先.

每日一题——判断是不是平衡二叉树

2023-08-21
阅读 2 分钟
670
输入一棵节点数为 n 二叉树,判断该二叉树是否是平衡二叉树。在这里,我们只需要考虑其平衡性,不需要考虑其是不是排序二叉树平衡二叉树(Balanced Binary Tree),具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。样例解释:

每日一题——螺旋矩阵

2023-08-20
阅读 2 分钟
864
题目给定一个m x n大小的矩阵(m行,n列),按螺旋的顺序返回矩阵中的所有元素。数据范围:0≤n,m≤10,矩阵中任意元素都满足 ∣val∣≤100要求:空间复杂度 O(nm) ,时间复杂度 O(nm)示例1 {代码...} 示例2 {代码...} 思路首先排除矩阵为空的情况的特殊情况。设置矩阵的四个边界值,开始准备螺旋遍历矩阵,遍历的截止点是左...

每日一题——买卖股票的最好时机(一)

2023-08-19
阅读 2 分钟
1.1k
题目假设你有一个数组prices,长度为n,其中prices[i]是股票在第i天的价格,请根据这个价格数组,返回买卖股票能获得的最大收益。1.你可以买入一次股票和卖出一次股票,并非每天都可以买入或卖出一次,总共只能买入和卖出一次,且买入必须在卖出的前面的某一天。2.如果不能获取到任何利润,请返回0。3.假设买入卖出均无...

每日一题——连续子数组的最大和

2023-08-18
阅读 1 分钟
887
题目输入一个长度为n的整型数组array,数组中的一个或连续多个整数组成一个子数组,子数组最小长度为1。求所有子数组的和的最大值。数据范围:1<=n<=2×\(10^5\) −100<=a[i]<=100要求:时间复杂度为 O(n),空间复杂度为 O(n)示例1 {代码...} 示例2 {代码...} 思路这题属于动态规划,可以使用状态转移方程求得子...

每日一题——不同路径的数目(一)

2023-08-17
阅读 1 分钟
677
一个机器人在m×n大小的地图的左上角(起点)。机器人每次可以向下或向右移动。机器人要到达地图的右下角(终点)。可以有多少种不同的路径从起点走到终点?

每日一题——二叉树的镜像

2023-08-16
阅读 1 分钟
715
题目操作给定的二叉树,将其变换为源二叉树的镜像。数据范围:二叉树的节点数 0≤n≤1000 , 二叉树每个节点的值 0≤val≤1000要求: 空间复杂度 O(n) 。本题也有原地操作,即空间复杂度 O(1) 的解法,时间复杂度 O(n)比如:源二叉树镜像二叉树参数说明:二叉树类,二叉树序列化是通过按层遍历,#代表这这个节点为空节点,举...

每日一题——合并二叉树

2023-08-15
阅读 2 分钟
583
题目已知两颗二叉树,将它们合并成一颗二叉树。合并规则是:都存在的结点,就将结点值加起来,否则空的位置就由另一个树的结点来代替。例如:两颗二叉树是:Tree 1Tree 2合并后的树为数据范围:树上节点数量满足 0≤n≤500,树上节点的值一定在32位整型范围内。进阶:空间复杂度 O(1) ,时间复杂度 O(n)参数说明:二叉树类...

每日一题——对称的二叉树

2023-08-14
阅读 3 分钟
260
题目给定一棵二叉树,判断其是否是自身的镜像(即:是否对称)例如: 下面这棵二叉树是对称的下面这棵二叉树不对称。数据范围:节点数满足 0≤n≤1000,节点上的值满足 ∣val∣≤1000要求:空间复杂度 O(n),时间复杂度 O(n)参数说明:二叉树类,二叉树序列化是通过按层遍历,#代表这这个节点为空节点,举个例子: {代码...} ...

每日一题——二叉树中和为某一值的路径

2023-08-13
阅读 3 分钟
336
题目给定一个二叉树root和一个值 sum ,判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径。该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点叶子节点是指没有子节点的节点路径只能从父节点到子节点,不能从子节点到父节点总节点数目为n例如:给出如下的二叉树,sum=22,返回true,因为存在一条路...

每日一题——二叉树的最大深度

2023-08-12
阅读 1 分钟
193
二叉树的深度就等于根节点这个1层加上左子树和右子树深度的最大值,即\(root_d\)=max(\(left_d\), \(right_d\))+1。而每个子树我们都可以看成一个根节点,使用递归即可求的深度。

每日一题——最长公共前缀

2023-08-11
阅读 2 分钟
243
题目给你一个大小为 n 的字符串数组 strs ,其中包含n个字符串 , 编写一个函数来查找字符串数组中的最长公共前缀,返回这个公共前缀。数据范围:0≤n≤5000, 0≤len(\(strs_i\))≤5000进阶:空间复杂度 O(1),时间复杂度 O(n∗len)示例1 {代码...} 示例2 {代码...} 思路以第一个字符串为基准,与其他字符串进行比较。从第一...

每日一题——合并两个有序的数组

2023-08-10
阅读 1 分钟
270
题目给出一个有序的整数数组 A 和有序的整数数组 B ,请将数组 B 合并到数组 A 中,变成一个有序的升序数组数据范围:0≤n,m≤100,∣\(A_i\)∣<=100,∣\(B_i\)∣<=100注意:1.保证 A 数组有足够的空间存放 B 数组的元素, A 和 B 中初始的元素数目分别为 m 和 n,A的数组空间大小为 m+n。2.不要返回合并的数组,将数组...

每日一题——字符串变形

2023-08-09
阅读 2 分钟
301
首先这个字符串中包含着一些空格,就像"Hello World"一样,然后我们要做的是把这个字符串中由空格隔开的单词反序,同时反转每个字符的大小写。

每日一题——最小花费爬楼梯

2023-08-08
阅读 2 分钟
275
给定一个整数数组 cost ,其中 cost[i] 是从楼梯第i 个台阶向上爬需要支付的费用,下标从0开始。一旦你支付此费用,即可选择向上爬一个或者两个台阶。

每日一题—— 数组中出现次数超过一半的数字

2023-08-07
阅读 1 分钟
273
给一个长度为 n 的数组,数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。

每日一题——两数之和

2023-08-06
阅读 2 分钟
304
给出一个整型数组 numbers 和一个目标值 target,请在数组中找出两个加起来等于目标值的数的下标,返回的下标按升序排列。(注:返回的数组下标从1开始算起,保证target一定可以由数组里面2个数字相加得到)

每日一题——跳台阶

2023-08-05
阅读 1 分钟
306
题目一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法(先后次序不同算不同的结果)。数据范围:1≤n≤40要求:时间复杂度:O(n) ,空间复杂度: O(1)示例1 {代码...} 示例2 {代码...} 思路一只青蛙一次可以跳1阶或2阶,直到跳到第n阶,也可以看成这只青蛙从n阶往下跳,到0阶,...