- ???? 作者：烧洋芋的土豆
- ???? 内容：使用Java语言刷Leetcode算法题第四天
- ???? 技术交流：分享日常学习知识,平常遇到的问题,一些学习资料,一起学习,一起进步。
( )
???? 88. 合并两个有序数组
给你两个按非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。请你合并nums2到nums1 中，使合并后的数组同样按 非递减顺序 排列。
注意： 最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
示例 1：
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 输出：[1,2,2,3,5,6] 解释：需要合并 [1,2,3] 和 [2,5,6] 。 合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。
示例 2：
输入：nums1 = [1], m = 1, nums2 = [], n = 0 输出：[1] 解释：需要合并 [1] 和 [] 。 合并结果是 [1] 。
示例 3：
输入：nums1 = [0], m = 0, nums2 = [1], n = 1 输出：[1] 解释：需要合并的数组是 [] 和 [1] 。 合并结果是 [1] 。 注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。
提示：
- nums1.length == m + n
- nums2.length == n
- 0 <= m, n <= 200
- 1 <= m + n <= 200
- -109 <= nums1[i], nums2[j] <= 109
方法一：快速排序模式
代码和结果图如下：
public static void merge(int[] nums1, int m, int[] nums2, int n) {
for (int i = 0; i != n; i++) {
nums1[m+i]=nums2[i];
}
Arrays.sort(nums1);
List<Integer> collect = Arrays.stream(nums1).boxed().collect(Collectors.toList());
System.out.println(collect);
}
复杂分析度：
- 时间复杂度:O(m+n)log(m+n)) 排序长度为m+n,套用快速排序的时间复杂度,平均为O(m+n)log(m+n))
- 空间复杂度:O(log(m+n)) 排序序列长度为m+n 套用快速排序的空间复杂度,平均为O(log(m+n))
方法二：逆向双指针
代码和结果图如下：
int p1 = m-1, p2 = n-1;
int tail=m+n-1;
int cur;
while (p1>=0 ||p2>=0){
if(p1 ==-1){
cur=nums2[p2--];
}else if(p2 == -1){
cur=nums1[p1--];
} else if(nums1[p1]>nums2[p2]){
cur=nums1[p1--];
}else {
cur=nums2[p2--];
}
nums1[tail--]=cur;
}
List<Integer> collect = Arrays.stream(nums1).boxed().collect(Collectors.toList());
System.out.println(collect);
复杂分析度：
- 时间复杂度:O(m+n) 因为数组是有序的,指针移动单调递减,最多移动m+n次,时间复杂度为O(m+n)
- 空间复杂度:O(1) 直接对数组原地修改,不需要额外的空间
???? 94. 二叉树的中序遍历
给定一个二叉树的根节点 root ，返回它的中序遍历 。
注意：
不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1：
输入：root = [1,null,2,3] 输出：[1,3,2]
示例 2：
输入：root = [] 输出：[]
示例 3：
输入：root = [1] 输出：[1]
提示：
- 树中节点数目在范围 [0, 100] 内
- -100 <= Node.val <= 100
代码和结果图如下：
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list=new ArrayList<>();
//判断是否是空树
if(root == null){
return list;
}
Stack<Object> stack=new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
Object obj = stack.pop();
//第一次出栈
if(obj instanceof TreeNode){
TreeNode node=(TreeNode) obj;
if(node.right!=null){
stack.push(node.right);
}
stack.push(node.val);
if(node.left!=null){
stack.push(node.left);
}
}
//第二次出栈
else{
list.add((Integer) obj);
}
}
return list;
}
}
???? 100. 相同的树
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例 1：
输入：p = [1,2,3], q = [1,2,3] 输出：true
示例 2：
输入：p = [1,2], q = [1,null,2] 输出：false
示例 3：
输入：p = [1,2,1], q = [1,1,2] 输出：false
提示:
- 两棵树上的节点数目都在范围 [0, 100] 内
- -104 <= Node.val <= 104
代码和结果图如下：
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p ==null && q==null){
return true;
}
if(p ==null ||q==null){
return false;
}
if(p.val==q.val){
return isSameTree(p.left,q.left)&& isSameTree(p.right,q.right);
}
return false;
}
}
???? 101. 对称二叉树
给你一个二叉树的根节点 root ， 检查它是否轴对称。
示例 1：
输入：root = [1,2,2,3,4,4,3] 输出：true
示例 2：
输入：root = [1,2,2,null,3,null,3] 输出：false
提示：
- 树中节点数目在范围 [1, 1000] 内
- -100 <= Node.val <= 100
代码和结果图如下：
解析:
相当于照镜子,看是否相同,因为刚好是反向的
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
public boolean isSymmetric(TreeNode root) {
return isMirror(root, root);
}
public boolean isMirror(TreeNode t1, TreeNode t2) {
if (t1 == null && t2 == null) return true;
if (t1 == null || t2 == null) return false;
return (t1.val == t2.val)
&& isMirror(t1.right, t2.left)
&& isMirror(t1.left, t2.right);
}
???? 104. 二叉树的最大深度
给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例 ：
给定二叉树 [3,9,20,null,null,15,7]，
返回它的最大深度 3 。
代码和结果图如下：
class Solution {
public int maxDepth(TreeNode root) {
return root == null ? 0 : Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
}
???? 总结
这几道算法题主要是采用Java基础知识和一些方法来实现的,这是刷算法题的第四天,期待我们后续越来越长,坚持下来就是胜利。