请选择 进入手机版 | 继续访问电脑版

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

[复制链接]
太阳神鹰 发表于 2021-1-1 17:46:41 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
[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
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则


专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )