最大子序和(数组、分治) 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 示例 1： 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]输出：6解释
最大子序和(数组、分治)
给定一个整数数组 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;
}
}
本文内容到此结束了， 如有收获欢迎点赞