4 篇
分治题目专区
分治的思路核心是“把大问题切成一模一样的小问题”,再把每个小问题的解拼回来。
题目描述 给定一个整数数组 nums,元素已经按升序排列。要求把它转换成一棵 平衡 二叉搜索树(任意节点左右子树高度差不超过 1)。 由于答案不唯一,只要满足 BST 性质并且高度平衡即可。 思路 升序数组其实就是 BST 的中序遍历结果。这就好办啦——既然中序遍历能唯一还原中序顺序,那么任意挑一个元素当根、左半边递归
题目描述 给定一个链表的头节点 head,要求把链表按照 升序 排列,并返回排序后的新头节点。 进阶要求是时间复杂度 O(n log n),并且尽量使用常数级额外空间。 思路 链表不像数组能随机访问下标,所以适合数组的快排在链表上写起来不优雅。这里用 归并排序:分治三步走——把链表对半切,分别递归排序两半,再把两条有序
题目描述 给你一个 n * n 矩阵 grid,矩阵由若干 0 和 1 组成。请你用四叉树表示该矩阵 grid,并返回根节点。 四叉树每个节点有两个属性: val:叶子节点所代表区域的值(1 对应 True,0 对应 False);非叶子节点的 val 任意。 isLeaf:当前节点是叶子时为 True,否则为 Fa
题目描述 给你一个链表数组,每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中,返回合并后的链表。 思路 K 条链表一起排队?咱用分治抢先一步~ 最最直觉的写法是:拿第 1 条和第 2 条 merge,再拿结果跟第 3 条 merge……一路串糖葫芦下来。可这么干每多合并一条就要把已合好的长链表