如何用分治法求最大子序和、二叉树最小深度、删除排序链表重复元素？

本文共计981个文字，预计阅读时间需要4分钟。

题目：寻找最大子序列和（数组、分割）

给定一个整数数组nums，找到具有最大和的连续子数组（子数组最少包含一个元素）。返回其最大和。

示例：输入：nums=[-2, 1, -3, 4, -1, 2, 1, -5, 4]输出：6解释：连续子数组[4, -1, 2, 1]的和最大，为6。

具体步骤：

1.初始化最大和为第一个元素。

2.遍历数组，对于每个元素：

a. 计算当前元素和前一个子数组和的和。 b. 比较这两个和，取较大者作为当前最大和。 c. 如果当前和小于0，重置为当前元素。

3.返回最大和。

最大子序和(数组、分治)

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

输入：nums = [1] 输出：1

示例 3：

输入：nums = [0] 输出：0

示例 4：

输入：nums = [-1] 输出：-1

示例 5：

输入：nums = [-100000] 输出：-100000

提示：

• 1 <= nums.length <= 3 * 104
• -105 <= nums[i] <= 105

**进阶：**如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。

解答：

class Solution { public int maxSubArray(int[] nums) { int maxSum = nums[0]; int curSum = 0; for (int n : nums) { curSum += n; if (curSum > maxSum) { maxSum = curSum; } if (curSum < 0) { curSum = 0; } } return maxSum; } }

二叉树的最小深度(树)

给定一个二叉树，找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 **说明：**叶子节点是指没有子节点的节点。

示例 1： 输入：root = [3,9,20,null,null,15,7] 输出：2 示例 2： 输入：root = [2,null,3,null,4,null,5,null,6] 输出：5

提示：

• 树中节点数的范围在 [0, 105] 内
• -1000 <= Node.val <= 1000

解答：

class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } class Solution { public int minDepth(TreeNode root) { if (root == null) { return 0; } if (root.left == null && root.right == null) { return 1; } int min_depth = Integer.MAX_VALUE; if (root.left != null) { int countLeft = 1; countLeft += minDepth(root.left); min_depth = Math.min(countLeft, min_depth); } if (root.right != null) { int countRight = 1; countRight += minDepth(root.right); min_depth = Math.min(min_depth, countRight); } return min_depth; } }

删除排序链表中的重复元素(链表)

存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素 只出现一次 。 返回同样按升序排列的结果链表。

示例 1：

输入：head = [1,1,2] 输出：[1,2]

示例 2：

输入：head = [1,1,2,3,3] 输出：[1,2,3]

提示：

• 链表中节点数目在范围 [0, 300] 内
• -100 <= Node.val <= 100
• 题目数据保证链表已经按升序排列

解答：

public class ListNode { int val; ListNode next; ListNode(int x) { val = x; } } class Solution { public ListNode deleteDuplicates(ListNode head) { if (head == null || head.next == null) { return head; } head.next = deleteDuplicates(head.next); if (head.val == head.next.val) head = head.next; return head; } }

本文内容到此结束了， 如有收获欢迎点赞