空中转体一周半

分类

未归档(1) 题解(80)

/ 注册

全部文章（共93篇）

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

寻找两个链表的第一个公共节点，提供两种解法:解法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

题解 | #合并二叉树#

简单直接的版本：把两个树合并到t1。若两个树都存在，直接把和放在t1中，然后再合并子树。合并子树之前进行一下t1的空节点判断即可 import java.util.*; public class Solution { public TreeNode mergeTrees (TreeNode ...

Java

2021-12-22

0 319

题解 | #求解立方根#

解题思路： 1.判断正负。判断输入的数是正数还是符数，设置一个flag表示符号位，flag=0为正，flag=1为负。 2.划分区间。把input的绝对值划分成小于1和大于1的两个区间，如果input小于1，设置二分的初始下界为0，上界为1.input大于1，则设置下届为0，上界为input。 3....

Java

2021-10-25

5 1174

题解 | #输出单向链表中倒数第k个结点#

这个题目用链表就过于复杂了。可以先用字符串读入输入的序列，然后转化成数组，用快慢指针解决问题即可。 import java.util.Scanner; public class Main { public static void main(String[] args) { S...

Java

2021-10-25

1 1070

题解 | #二叉树的最大深度#

递归比较左右子树即可。 import java.util.*; public class Solution { public int maxDepth (TreeNode root) { if(root==null)return 0; if(root.left...

Java

2021-10-22

0 302

题解 | #调整数组顺序使奇数位于偶数前面(二)#

思路很简单，双指针，从数组两头向中间靠近。左边的为奇数指针，右边的为偶数指针。左边指针在没有遇到偶数时，就向右移动，遇到偶数立即停止；右边指针再没有遇到奇数时，向左边移动，遇到奇数时，进行奇偶指针元素交换。交换之后切换到奇数指针工作。这个方法只遍历一遍数组，时间o(n),空间o(1)。 import...

Java

2021-10-19

17 1285