Java复习第四天

一、代码题

1.相同的树

(1)题目

给你两棵二叉树的根节点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

(2)思路实现

a.题目实现

如果两个节点都为空，则它们是相同的。
如果其中一个节点为空而另一个不为空，则它们不同。
如果两个节点的值不同，则它们不同。
如果两个节点的值相同，则递归地检查它们的左子树和右子树是否相同。

b.代码实现

定义一个递归函数 isSameTree，接受两个 TreeNode 类型的参数 p 和 q。
首先检查两个节点是否都为空，如果是，则返回 true。
然后检查其中一个节点是否为空而另一个不为空，如果是，则返回 false。
接着检查两个节点的值是否相同，如果不同，则返回 false。
最后递归地检查两个节点的左子树和右子树是否相同，只有当两者都返回 true 时，才返回 true。

(3)代码实现

package com.thor.test;

public class Demo {
    public static void main(String[] args) {
        //示例 1: 输入:p=[1,2,3]，q=[1,2,3] 输出:true
        TreeNode p1 = new TreeNode(1, new TreeNode(2), new TreeNode(3));
        TreeNode q1 = new TreeNode(1, new TreeNode(2), new TreeNode(3));
        System.out.println(new TreeNode.Solution().isSameTree(p1,q1));
        //示例 2: 输入:p =[1,2]，q=[1,null,2] 输出:false
        TreeNode p2 = new TreeNode(1, new TreeNode(2), null);
        TreeNode q2 = new TreeNode(1, null, new TreeNode(2));
        System.out.println(new TreeNode.Solution().isSameTree(p2,q2));
        //示例 3: 输入:p=[1,2,1]，q =[1,1,2] 输出:false
        TreeNode p3 = new TreeNode(1, new TreeNode(2), new TreeNode(1));
        TreeNode q3 = new TreeNode(1, new TreeNode(1), new TreeNode(2));
        System.out.println(new TreeNode.Solution().isSameTree(p3,q3));
    }

}
class TreeNode {
    int val;//节点值
    TreeNode left;//左子节点
    TreeNode right;//右子节点
    
    TreeNode() {}//无参构造
    TreeNode(int val) {this.val = val;}//有参构造

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }//有参构造

    static 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 false;
            }
            //递归低检查两个节点的左子树和右子树是否相等
            return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
        }
    }
}

2.对称二叉树

(1)题目

你一个二叉树的根节点root，检查它是否轴对称。

示例1: 输入:root=[1,2,2,3,4,4,3] 输出:true
示例 2: 输入:root=[1,2,2,null,3,null,3] 输出:false

(2)思路实现

a.题目实现

如果树为空，则它是对称的。
定义一个辅助函数 isMirror，用于检查两个子树是否互为镜像。
在 isMirror 函数中，首先检查两个节点是否都为空，如果是，则它们是对称的。
然后检查其中一个节点为空而另一个不为空，如果是，则它们不对称。
接着检查两个节点的值是否相同，如果不同，则它们不对称。
最后递归地检查一个节点的左子树和另一个节点的右子树是否互为镜像，以及一个节点的右子树和另一个节点的左子树是否互为镜像

b.代码实现

定义一个递归函数 isSymmetric，接受一个 TreeNode 类型的参数 root。
如果 root 为空，则返回 true。
调用辅助函数 isMirror，传入 root 的左子树和右子树。
定义辅助函数 isMirror，接受两个 TreeNode 类型的参数 p 和 q。
在 isMirror 函数中，首先检查两个节点是否都为空，如果是，则返回 true。
然后检查其中一个节点为空而另一个不为空，如果是，则返回 false。
接着检查两个节点的值是否相同，如果不同，则返回 false。
最后递归地检查一个节点的左子树和另一个节点的右子树是否互为镜像，以及一个节点的右子树和另一个节点的左子树是否互为镜像。

(3)代码实现

package com.thor.test;

public class Demo {
    public static void main(String[] args) {
        // 示例 1
        TreeNode root1 = new TreeNode(1,
                new TreeNode(2, new TreeNode(3), new TreeNode(4)),
                new TreeNode(2, new TreeNode(4), new TreeNode(3))
        );
        System.out.println(new Solution().isSymmetric(root1)); // 输出: true

        // 示例 2
        TreeNode root2 = new TreeNode(1,
                new TreeNode(2, null, new TreeNode(3)),
                new TreeNode(2, null, new TreeNode(3))
        );
        System.out.println(new Solution().isSymmetric(root2)); // 输出: false
    }
}

class TreeNode {
    int val; // 节点值
    TreeNode left; // 左子节点
    TreeNode right; // 右子节点
    TreeNode() {
    } // 无参构造
    TreeNode(int val) {
        this.val = val;
    } // 有参构造
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    } // 有参构造
}
class Solution {
    public boolean isSymmetric(TreeNode root) {
        // 如果树为空，则它是对称的
        if (root == null) {
            return true;
        }
        // 调用辅助函数检查左子树和右子树是否互为镜像
        return isMirror(root.left, root.right);
    }
    private boolean isMirror(TreeNode p, TreeNode q) {
        // 如果两个节点都为空，则它们是对称的
        if (p == null && q == null) {
            return true;
        }
        // 如果其中一个节点为空而另一个不为空，则它们不对称
        if (p == null || q == null) {
            return false;
        }
        // 如果两个节点的值不同，则它们不对称
        if (p.val != q.val) {
            return false;
        }
        // 递归地检查一个节点的左子树和另一个节点的右子树是否互为镜像
        // 以及一个节点的右子树和另一个节点的左子树是否互为镜像
        return isMirror(p.left, q.right) && isMirror(p.right, q.left);
    }
}

二、集合

1.简介

2.ArrayList

(1)注意：声明的时候，最好采用多态的形式，就是父类引用指向子类对象

原因：关于可重复，有序操作的方法，都是在接口中已经定义好了;利于多态

(2)代码

List list =new ArrayList();
//增
list.add(1);
list.add(2);
list.add(3);
list.add(1);
//查
for (int i = 0; i < list.size(); i++) {
	System.out.println(list.get(i));
}

(3)单元测试——@Test

@Test
public void f01() {
	List list = new ArrayList();
	//增
	list.add(1);
	list.add(2);
	list.add(3);
	list.add(1);
	for (int i = 0; i < list.size(); i++) {
		System.out.println(list.get(i));
	}
}
@Test
public void f02() {
	List list = new ArrayList();
	//增
	list.add(1);
	list.add(2);
	list.add(3);
	list.add(1);
	//删
	list.remove(1);
	for (int i = 0; i < list.size(); i++) {
		System.out.println(list.get(i));
	}
}
@Test
public void f03() {
	List list = new ArrayList();
	//增
	list.add(1);
	list.add(2);
	list.add(3);
	list.add(1);
	//改
	list.set(0, 4);
	for (int i = 0; i < list.size(); i++) {
		System.out.println(list.get(i));
	}
}

3.LinkedList

(1)代码

@Test
public void f01() {
	List list = new LinkedList();
	//增
	list.add(1);
	list.add(2);
	list.add(3);
	list.add(1);
	for (int i = 0; i < list.size(); i++) {
		System.out.println(list.get(i));
	}
}
@Test
public void f02() {
	List list = new LinkedList();
	//增
	list.add(1);
	list.add(2);
	list.add(3);
	list.add(1);
	//删
	list.remove(1);
	for (int i = 0; i < list.size(); i++) {
		System.out.println(list.get(i));
	}
}
@Test
public void f03() {
	List list = new LinkedList();
	//增
	list.add(1);
	list.add(2);
	list.add(3);
	list.add(1);
	//改
	list.set(0, 4);
	for (int i = 0; i < list.size(); i++) {
		System.out.println(list.get(i));
	}
}

(2)特殊方法

4.List、ArrayList、LinkedList 区别

List	增	删	改	查
ArrayList	慢	慢	快	快
LinkedList	快	快	慢	慢

相同点:二者都是有序的，父类为List

不同点:二者的底层结构不一样。

ArrayList的底层数据结构的数组结构，数组结构有个特点是查询快，因为它里面有索引，但是增加和删除慢，因为增加的时候需要考虑扩容机制。

LinkedList的底层数据结构是链表结构，链表结构增加和删除快，因为它们内部都有一个节点保存其地址值。但是查询慢，因为它们没有对应的索引操作

5.练习题

题目：如何存储多条狗狗信息，获取狗狗总数，逐条打印出各条狗狗信息 ?

package com.thor.test;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;
import java.util.Objects;

public class Demo {
    @Test
    public void f01() {
        List list = new ArrayList();
        //增
        list.add(new Dog("欧欧","雪纳瑞"));
        list.add(new Dog("豆豆","泰迪"));
        list.add(new Dog("花花","金毛"));
        list.add(new Dog("美美","哈士奇"));
        System.out.println("共计有"+list.size()+"条狗");
        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }
    }
}
class Dog{
    private String name;
    private String strain;

    @Override
    public String toString() {
        return "Dog{" +
                "name='" + name + '\'' +
                ", strain='" + strain + '\'' +
                '}';
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Dog dog = (Dog) o;
        return Objects.equals(name, dog.name) && Objects.equals(strain, dog.strain);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, strain);
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public String getStrain() {
        return strain;
    }

    public void setStrain(String strain) {
        this.strain = strain;
    }

    public Dog(String name, String strain) {
        this.name = name;
        this.strain = strain;
    }
}

6.Set

Set 入门案例

Set 不能重复，无序;遍历用增强 for，因为无序，没有索引。
代码

@Test
public void f01() {
	Set set = new HashSet();
	//增
	set.add("中国");
	set.add("美国");
	set.add("中国");
	set.add("日本");
	set.add("韩国");
	System.out.println(set.size());
	for (Object o : set) {
		System.out.println(o);
	}
}

7.Map

Map 入门案例
Map 是双列集合
新增是(key value 结构)，key 不能重复，value 可以重复
新增和修改用的是同一个方法——put
代码

@Test
public void f01() {
	Map map = new HashMap();
	map.put("China","中国");
	map.put("American","美国");
	map.put("England","英国");
	map.put("Japan","日本");
	map.put("China1","中国");
	System.out.println(map.size());
	//查
	Set set = map.keySet();
	//增强for
	for (Object key : set) {
		Object value = map.get((String) key);
		System.out.println(key+ " : "+ value);
	}
}

8.迭代器——Iterator

所有的增强 for 循环，底层实际上是依赖于迭代器Iterator

(1)有序

@Test
public void f01() {
	ArrayList<Integer> list = new ArrayList<>();
	list.add(1);
	list.add(2);
	list.add(3);
	list.add(4);
	System.out.println("\n遍历方式1");
	for (int i = 0; i < list.size(); i++) {
		System.out.println(list.get(i)+" ");
	}
	System.out.println("\n遍历方式2");
	for (Integer i : list) {
		System.out.println(i + " ");
	}
	System.out.println("\n遍历方式3");
	Iterator<Integer> iterator = list.iterator();
	while(iterator.hasNext()){
		System.out.println(iterator.next()+" ");
	}
}

(2)无序

@Test
public void f01() {
	Set<Integer> set = new HashSet<>();
	set.add(1);
	set.add(2);
	set.add(6);
	set.add(4);
	System.out.println("\n遍历方式1");
	for (Integer i : set) {
		System.out.println(i + " ");
	}
	System.out.println("\n遍历方式2");
	Iterator<Integer> iterator = set.iterator();
	while (iterator.hasNext()) {
		System.out.println(iterator.next() + " ");
	}
}

9.Collections 集合框架工具类

@Test
    public void f01() {
        List<Integer> list = new ArrayList<>();
        for (int i = 1; i < 11; i++) {
            list.add(i);
        }
        //洗牌
        Collections.shuffle(list);
        System.out.println("洗牌的结果为:" + list + " ");
    }
    @Test
    public void f02() {
        List<Integer> list = new ArrayList<>();
        for (int i = 1; i < 11; i++) {
            list.add(i);
        }
        //洗牌
        Collections.reverse(list);
        System.out.println("洗牌反转后的结果为:" + list + " ");
    }
    @Test
    public void f03() {
        List<Integer> list = new ArrayList<>();
        for (int i = 1; i < 11; i++) {
            list.add(i);
        }
        //洗牌
        Collections.addAll(list,11,12);
        System.out.println("洗牌追加后的结果为:" + list + " ");
    }