栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

算法题笔记

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

算法题笔记

重建二叉树

重建二叉树

    public TreeNode reConstructBinaryTree(int[] pre, int[] vin) {
        if (pre == null || vin == null || pre.length != vin.length) {
            return null;
        }
        return build(pre, 0, pre.length - 1, vin, 0, vin.length - 1);
    }

    private TreeNode build(int[] pre, int pre_start, int pre_end, int[] vin, int vin_start, int vin_end) {
        if (pre_start > pre_end || vin_start > vin_end) {
            return null;
        }
        TreeNode root = new TreeNode(pre[pre_start]);
        for (int j = vin_start; j <= vin_end; j++) {
            if (pre[pre_start] == vin[j]) {
                root.left = build(pre, pre_start + 1, pre_start+ j - vin_start, vin, vin_start, j - 1);
                root.right = build(pre,pre_start+ j - vin_start + 1, pre_end, vin, j + 1, vin_end);
                break;
            }
        }
        return root;
    }
输出斐波那契数列的第 n 项。

斐波那契数列
【剪枝将重复的叶子树用Map集合过滤】

    Map map = new HashMap<>();//过滤

    public int Fibonacci(int n) {
        if (n == 0 || n == 1) {
        return n;
        }
        int pre =0;//找n-1
        if (map.containsKey(n-1)){
            pre = map.get(n-1);
        }else {
            pre = Fibonacci(n-1);
            map.put(n-1,pre);
        }
        int ppre =0;//找n-2
        if (map.containsKey(n-2)){
            ppre =map.get(n-2);
        }else {
            ppre = Fibonacci(n-2);
            map.put(n-2,ppre);
        }
        return ppre+pre;
    }
跳台阶

题目:青蛙跳台阶
DP动态规划

    public static int jumpFloor(int target) {
        if (target == 0){
            return 0;
        }
        if (target <= 2){
            return target;
        }
        int[] dp = new int[target + 1];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= target; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[target];
    }
二进制中1的个数

牛客原题

    public int NumberOf1(int n) {
        int count = 0;
        while (n != 0) {
            int x = n - 1;
            n = n & x;
            count++;
        }
        return count;
    }
合并两个排序的链表

方法一:创建虚拟头节点对两个链表拼接
方法二:递归实现方法一
合并两个排序的 链表

    ListNode dummyHead =new ListNode(0);
    ListNode tail =dummyHead;
    public ListNode Merge(ListNode list1, ListNode list2) {
        build(list1,list2);
        return dummyHead.next;
    }

    private void build(ListNode list1, ListNode list2) {
        if (list1 == null && list2 == null){
            return;
        }
        if (list1 == null) {
            tail.next =list2;
            return;
        }
        if (list2 == null) {
            tail.next = list1;
            return;
        }
        if (list1.val < list2.val){
            tail.next = list1;
            list1 = list1.next;
        }else {
            tail.next = list2;
            list2 =list2.next;
        }
        tail = tail.next;
        build(list1,list2);
    }
树的子结构

[空树不为子结构的情况]牛客原题

    public boolean HasSubtree(TreeNode root1, TreeNode root2) {
        if (root1 == null || root2 == null) {
            return false;
        }
        Boolean isSame = false;
        if (root1.val == root2.val) {
            isSame = isSameChild(root1, root2);//判断子树是否相同
        }
        if (!isSame) {//当前头节点不是,在左子树找
            isSame = HasSubtree(root1.left, root2);
        }
        if (!isSame) {//左子树没有在右子树找
            isSame = HasSubtree(root1.right, root2);
        }
        return isSame;
    }

    private Boolean isSameChild(TreeNode root1, TreeNode root2) {
        if (root2 == null) {//树2遍历结束都没找到不一样的返回真
            return true;
        }
        if (root1 == null) {//树2都没走完,树1走完了返回假
            return false;
        }
        if (root1.val != root2.val) {//判断根节点
            return false;
        }
        return isSameChild(root1.left, root2.left) && isSameChild(root1.right, root2.right);//判断左右子树
    }
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/970756.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号