空中转体一周半

分类

未归档(1) 题解(80)

/ 注册

全部文章（共78篇）

题解 | #缺失的第一个正整数#

时间复杂度O(n),空间复杂度O(n)的做法：开辟一个新的数组arr，长度为nums.length+1，遍历nums数组，如果非负且值小于nums的长度，则把arr[nums[i]]置1。然后遍历辅助数组，找到下标不为1的第一个元素即可。 public class Solution { pu...

Java

2022-01-03

5 857

题解 | #矩阵元素查找#

遍历数组，由于矩阵从上到下，从右到左有序，因此可以从第0行第m-1列开始遍历，若mat[i][j]>x则左移，否则下移，直到找到目标元素。越界则直接返回空数组。时间复杂度O(m+n)。 public class Solution { public int[] findElement(i...

Java

2022-01-01

1 293

题解 | #岛屿数量#

#岛屿数量#解题思路：按行遍历矩阵，遇到‘1’则使用广度优先移除已经参与计数的岛屿。使用递归删除左右上下相邻的grid[i][j]=='1'的格子即可。此方法时间复杂度o(n^2)。 public class Solution { public int solve (char[][] gri...

Java

2021-12-28

0 370

题解 | #输出二叉树的右视图#

#输出二叉树的右视图# 分成两步走:1、递归重建二叉树（参考NC12重建二叉树）时间复杂度O(n),空间O(n)2、层序遍历（使用一个last指针记录每一层的最后一个节点，遍历到每层最后一个节点时，将其加入数组即可)时间复杂度O(n),空间O(n)，总时间复杂度O(n),总空间复杂度O(n) p...

Java

2021-12-28

0 332

题解 | #两个链表生成相加链表#

主要是相加的过程。相加后的结果由当前两位和低位的进位组成。进位初始化为0.为了避免链表中操作的复杂性（翻转、对齐等操作还需要增加额外的代码），可以直接用StringBuilder构造两个序列。依次完成翻转、对齐、相加操作，最后把字符串中的序列还原到链表中即可。 public class Soluti...

Java

2021-12-26

0 339

题解 | #两个链表的第一个公共结点#

寻找两个链表的第一个公共节点，提供两种解法:解法1、使用哈希，把第一个链表的所有节点用哈希保存起来，之后进行第二个链表的扫描，如果第二个链表的某个节点的哈希映射冲突(在map中已经存在)，则该节点为第一个公共节点。空间复杂度O(max(m,n)),事件复杂度O(m+n)(有可能把两个链表都扫描完了)...

Java

2021-12-26

2 406

题解 | #最长公共子串#

注意和最长子序列的区别：最长子序列要求序列可以不连续，子串要求必须连续，中间不能间隔其它字符串。因此，把状态方程改一下即可，dp[i][j]只能来自dp[i-1][j-1],并且用一个max记录当前最长的公共子串。至于最后截取字符串的时候为什么要加个1呢？那是因为公共子串若存在，那么最小值为1，在最...

Java

2021-12-26

0 401

题解 | #按之字形顺序打印二叉树#

该题可以使用队列来完成，与普通的层序遍历不一样，之形层序遍历需要新加两个变量，其一是level表示当前层数，其二是last表示当前层次最后一个节点。每次遍历到最后一个节点时，把层数加1，如果层数是奇数，则直接把当前层次的结果加入res，如果层数是偶数，把当前层次的节点序列逆转即可。事件复杂度O(n)...

Java

2021-12-26

0 336

题解 | #合并两个排序的链表#

采用插入法：首先找出两个链表哪个作为返回链表的表头（节点值较小的那个），然后设置一个前驱pre，根据值的大小比较进行合适的位置插入即可。这个方法记录了每次插入的前驱，每次进行插入时无需遍历链表，因此时间复杂度为O(n) public ListNode Merge(ListNode list1...

Java

2021-12-23

6 913

题解 | #寻找第K大#

基于快排：每次划分之后返回该次划分的基准索引，比较索引和K的大小，K大，则往右继续划分，K小，则往右划分。直到求解为止。该算法不会把快排执行完毕，也就是说数组中还有没有排好序的一些元素。 public class Solution { public int findKth(int[] a, ...

Java

2021-12-23

0 358