53. 最大子序和+21. 合并两个有序链表

[21. 归并两个有序链表]

形貌:

1. 将两个升序链表归并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

复制代码

示例I/O

1. 输入：1->2->4, 1->3->4输出：1->1->2->3->4->4

复制代码

(归并)

1. 思路雷同于归并排序,只需将两个头遍历即可,每次取较小的插入进原链表中去

复制代码

Code

1. /** * 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 mergeTwoLists(ListNode l1, ListNode l2) {        ListNode p,q,newHead,r,s;        p = l1;        q = l2;        newHead =r= new ListNode();        newHead.next=null;        while(p!=null && q!=null){            if((p.val) < (q.val)){                s = new ListNode(p.val,null);                r.next = s;                r = s;                p = p.next;            }else{                s = new ListNode(q.val,null);                r.next = s;                r = s;                q = q.next;            }        }        while(p!=null)        {            s = new ListNode(p.val,null);            r.next = s;            r = s;            p = p.next;        }        while(q!=null)        {            s = new ListNode(q.val,null);            r.next = s;            r = s;            q = q.next;        }        r.next = null;        return newHead.next;    }}

复制代码

[53. 最大子序和]

题目形貌:

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

复制代码

示例I/O

1. 输入: [-2,1,-3,4,-1,2,1,-5,4]输出: 6表明: 连续子数组 [4,-1,2,1] 的和最大，为 6。

复制代码

(动态规划)

比较简单的动态规划,只需找到状态方程即可
Code

1. class Solution {    public int maxSubArray(int[] nums) {        int length = nums.length;        //动态规划： 状态转移方程：dp[i] = max(dp[i-1] + nums[i], nums[i])        int[] dp = new int[length];        dp[0] = nums[0];        int res = dp[0];        for (int i = 1; i < nums.length; i++) {            dp[i] = Math.max(dp[i-1] + nums[i], nums[i]);            res = Math.max(res,dp[i]);        }        return res;    }}

复制代码

来源：https://blog.csdn.net/storm_55/article/details/111996448
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！