当前位置： 首页 > article >正文

面试经典150题——分治

article 2025/2/21 23:46:18

文章目录

  • 1、将有序数组转换为二叉搜索树
    • 1.1 题目链接
    • 1.2 题目描述
    • 1.3 解题代码
    • 1.4 解题思路
  • 2、排序链表
    • 2.1 题目链接
    • 2.2 题目描述
    • 2.3 解题代码
    • 2.4 解题思路
  • 3、建立四叉树
    • 3.1 题目链接
    • 3.2 题目描述
    • 3.3 解题代码
    • 3.4 解题思路
  • 4、合并 K 个升序链表
    • 4.1 题目链接
    • 4.2 题目描述
    • 4.3 解题代码
    • 4.4 解题思路

1、将有序数组转换为二叉搜索树

1.1 题目链接

点击跳转到题目位置

1.2 题目描述

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵
平衡(平衡二叉树是指该树所有节点的左右子树的高度相差不超过1) 二叉搜索树。

提示：

  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • nums 按 严格递增 顺序排列

1.3 解题代码

/**
 * Definition for a binary tree node.
 * public 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 {
    TreeNode build(int[] nums, int left, int right){
        if(left > right){
            return null;
        }
        int mid = (left + right) >> 1;
        TreeNode root = new TreeNode(nums[mid]);
        if(mid == left){
            root.left = null;
            root.right = build(nums, left + 1, right);
        } else if(mid == right){
            root.left = build(nums, left, right - 1);
            root.right = null;
        } else{
            root.left = build(nums, left, mid - 1);
            root.right = build(nums, mid + 1, right);
        }
        return root;
    }

    public TreeNode sortedArrayToBST(int[] nums) {
        int n = nums.length;
        return build(nums, 0, n - 1);
    }
}

1.4 解题思路

  1. 分治本质上是递归，本题就是将数组对半分，中间的数字为根节点，然后对左右子树继续建立成二叉搜索树。

2、排序链表

2.1 题目链接

点击跳转到题目位置

2.2 题目描述

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
提示：

  • 链表中节点的数目在范围 [0, 5 * 104] 内
  • -105 <= Node.val <= 105

2.3 解题代码

/**
 * 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; }
 * }
 */
class Solution {
    
    public ListNode merge(ListNode head1, ListNode head2){
        ListNode dummyHead = new ListNode();
        ListNode head = dummyHead;
        while(head1 != null && head2 != null){
            if(head1.val < head2.val){
                head.next = head1;
                head1 = head1.next;
            } else{
                head.next = head2;
                head2 = head2.next;
            }
            head = head.next;
        }
        if(head1 != null){
            head.next = head1;
        } 
        if(head2 != null){
            head.next = head2;
        }
        return dummyHead.next;
    }


    public ListNode sortList(ListNode head, ListNode tail){
        if(head == null){
            return null;
        }
        if(head.next == tail){
            head.next = null;
            return head;
        }
        ListNode fastNode = head;
        ListNode slowNode = head;
        while(fastNode != tail){
            fastNode = fastNode.next;
            slowNode = slowNode.next;
            if(fastNode != tail){
                fastNode = fastNode.next;
            }
        }
        return merge(sortList(head, slowNode), sortList(slowNode, tail));
    }

    public ListNode sortList(ListNode head) {
        return sortList(head, null);
    }
}

2.4 解题思路

  1. 归并排序的思路，只不过是链表形式。

3、建立四叉树

3.1 题目链接

点击跳转到题目位置

3.2 题目描述

给你一个 n * n 矩阵 grid ，矩阵由若干 0 和 1 组成。请你用四叉树表示该矩阵 grid 。

你需要返回能表示矩阵 grid 的 四叉树 的根结点。

四叉树数据结构中，每个内部节点只有四个子节点。此外，每个节点都有两个属性：

  • val：储存叶子结点所代表的区域的值。1 对应 True，0 对应 False。注意，当 isLeaf 为 False 时，你可以把 True 或者 False 赋值给节点，两种值都会被判题机制 接受 。
  • isLeaf: 当这个节点是一个叶子结点时为 True，如果它有 4 个子节点则为 False 。
    在这里插入图片描述
    我们可以按以下步骤为二维区域构建四叉树：
  1. 如果当前网格的值相同（即，全为 0 或者全为 1），将 isLeaf 设为 True ，将 val 设为网格相应的值，并将四个子节点都设为 Null 然后停止。
  2. 如果当前网格的值不同，将 isLeaf 设为 False， 将 val 设为任意值，然后如下图所示，将当前网格划分为四个子网格。
  3. 使用适当的子网格递归每个子节点。

四叉树格式：

你不需要阅读本节来解决这个问题。只有当你想了解输出格式时才会这样做。输出为使用层序遍历后四叉树的序列化形式，其中 null 表示路径终止符，其下面不存在节点。

它与二叉树的序列化非常相似。唯一的区别是节点以列表形式表示 [isLeaf, val] 。

如果 isLeaf 或者 val 的值为 True ，则表示它在列表 [isLeaf, val] 中的值为 1 ；如果 isLeaf 或者 val 的值为 False ，则表示值为 0 。

3.3 解题代码

/*
// Definition for a QuadTree node.
class Node {
    public boolean val;
    public boolean isLeaf;
    public Node topLeft;
    public Node topRight;
    public Node bottomLeft;
    public Node bottomRight;

    
    public Node() {
        this.val = false;
        this.isLeaf = false;
        this.topLeft = null;
        this.topRight = null;
        this.bottomLeft = null;
        this.bottomRight = null;
    }
    
    public Node(boolean val, boolean isLeaf) {
        this.val = val;
        this.isLeaf = isLeaf;
        this.topLeft = null;
        this.topRight = null;
        this.bottomLeft = null;
        this.bottomRight = null;
    }
    
    public Node(boolean val, boolean isLeaf, Node topLeft, Node topRight, Node bottomLeft, Node bottomRight) {
        this.val = val;
        this.isLeaf = isLeaf;
        this.topLeft = topLeft;
        this.topRight = topRight;
        this.bottomLeft = bottomLeft;
        this.bottomRight = bottomRight;
    }
}
*/

class Solution {
    Node Build(int[][] grid, int r1, int c1, int r2, int c2){
        int row_mid = ((r1 + r2) >> 1);
        int col_mid = ((c1 + c2) >> 1);
        for(int i = r1; i <= r2; ++i){
            for(int j = c1; j <= c2; ++j){
                if(grid[i][j] != grid[r1][c1]){
                    return new Node(true, false, 
                                    Build(grid, r1, c1, row_mid, col_mid), 
                                    Build(grid, r1, col_mid + 1, row_mid, c2),
                                    Build(grid, row_mid + 1, c1, r2, col_mid),
                                    Build(grid, row_mid + 1, col_mid + 1, r2, c2));
                    
                }
            }
        }
        // 如果区域内相同
        return new Node(grid[r1][c1] == 1, true);
    }


    public Node construct(int[][] grid) {
        int n = grid.length;
        return Build(grid, 0, 0, n - 1, n - 1);
    }
}

3.4 解题思路

  1. 分治思想
  2. 如果正方形内所有元素值都相等，则建立节点，该节点为叶子节点，值为该元素值，0为false，1为true。
  3. 如果正方形内存在元素不相等，则当前节点不为叶子节点，将该正方形继续建立四叉树。

4、合并 K 个升序链表

4.1 题目链接

点击跳转到题目位置

4.2 题目描述

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

提示：

  • k == lists.length
  • 0 <= k <= 104
  • 0 <= lists[i].length <= 500
  • -104 <= lists[i][j] <= 104
  • lists[i] 按 升序 排列
  • lists[i].length 的总和不超过 104

4.3 解题代码

/**
 * 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; }
 * }
 */
class Solution { 
    ListNode merge(ListNode head1, ListNode head2){
        ListNode dummyHead = new ListNode();
        ListNode head = dummyHead;
        while(head1 != null && head2 != null){
            if(head1.val < head2.val){
                head.next = head1;
                head1 = head1.next;
            } else{
                head.next = head2;
                head2 = head2.next;
            }
            head = head.next;
        }
        if(head1 != null){
            head.next = head1;
        }
        if(head2 != null){
            head.next = head2;
        }
        return dummyHead.next;
    }

    public ListNode Build(ListNode[] lists, int left, int right){
        if(left == right){
            return lists[left];
        }
        if(left > right){
            return null;
        }
        int mid = (left + right) >> 1;
        return merge(Build(lists, left, mid), Build(lists, mid + 1, right));
    }

    public ListNode mergeKLists(ListNode[] lists) {
        return Build(lists, 0, lists.length - 1);
    }
}

4.4 解题思路

  1. 分治思想。
  2. 将多个链表两两配对，合并成一个更长的链表。

http://www.kler.cn/a/549932.html

相关文章：

  • 产品经理学习——AI产品
  • 青少年编程与数学 02-009 Django 5 Web 编程 10课题、类视图
  • 鸿蒙Next开发-普通函数和箭头函数 this指向的区别以及对UI刷新的影响
  • vue3实战-----集成sass
  • 宝塔面板开始ssl后,使用域名访问不了后台管理
  • 16-使用QtChart创建动态图表：入门指南
  • C语言中printf()函数，格式输出符
  • Web 后端 HTTP协议
  • Flink在指定时间窗口内统计均值，超过阈值后报警
  • 架构设计系列（三）：架构模式
  • 备战蓝桥杯 Day2 枚举 Day3 进制转换
  • FFmpeg源码：av_strlcpy函数分析
  • kamailio中的PV，PV Headers，App Lua，Dialog，UUID,Dianplan等模块的讲解
  • Unity状态机的实现方法二
  • Vue3（3）
  • 【Oracle】层次查询步骤，理解 where 条件执行顺序
  • 项目上传github步骤
  • DeepSeek与医院电子病历的深度融合路径：本地化和上云差异化分析
  • MATLAB图像处理：图像分割方法
  • 【go语言规范】关于接口设计