精华内容
下载资源
问答
  • 点击上方蓝设为星标东哥带你手把手撕力扣????点击下方卡片即可搜索????最大子数组问题前文讲过 经典动态规划:最长递增子序列 套路非常相似,代表着一类比较特殊动态规划问题思...

    点击上方蓝字设为星标

    东哥带你手把手撕力扣????

    点击下方卡片即可搜索????

    最大子数组问题和前文讲过的 经典动态规划:最长递增子序列 的套路非常相似,代表着一类比较特殊的动态规划问题的思路:

    title

    思路分析

    其实第一次看到这道题,我首先想到的是滑动窗口算法,因为我们前文说过嘛,滑动窗口算法就是专门处理子串/子数组问题的,这里不就是子数组问题么?

    但是,稍加分析就发现,这道题还不能用滑动窗口算法,因为数组中的数字可以是负数

    滑动窗口算法无非就是双指针形成的窗口扫描整个数组/子串,但关键是,你得清楚地知道什么时候应该移动右侧指针来扩大窗口,什么时候移动左侧指针来减小窗口。

    而对于这道题目,你想想,当窗口扩大的时候可能遇到负数,窗口中的值也就可能增加也可能减少,这种情况下不知道什么时机去收缩左侧窗口,也就无法求出「最大子数组和」。

    解决这个问题需要动态规划技巧,但是dp数组的定义比较特殊。按照我们常规的动态规划思路,一般是这样定义dp数组:

    nums[0..i]中的「最大的子数组和」为dp[i]

    如果这样定义的话,整个nums数组的「最大子数组和」就是dp[n-1]。如何找状态转移方程呢?按照数学归纳法,假设我们知道了dp[i-1],如何推导出dp[i]呢?

    如下图,按照我们刚才对dp数组的定义,dp[i] = 5,也就是等于nums[0..i]中的最大子数组和:

    那么在上图这种情况中,利用数学归纳法,你能用dp[i]推出dp[i+1]吗?

    实际上是不行的,因为子数组一定是连续的,按照我们当前dp数组定义,并不能保证nums[0..i]中的最大子数组与nums[i+1]是相邻的,也就没办法从dp[i]推导出dp[i+1]

    所以说我们这样定义dp数组是不正确的,无法得到合适的状态转移方程。对于这类子数组问题,我们就要重新定义dp数组的含义:

    nums[i]为结尾的「最大子数组和」为dp[i]

    这种定义之下,想得到整个nums数组的「最大子数组和」,不能直接返回dp[n-1],而需要遍历整个dp数组:

    int res = Integer.MIN_VALUE;
    for (int i = 0; i < n; i++) {
        res = Math.max(res, dp[i]);
    }
    return res;
    

    依然使用数学归纳法来找状态转移关系:假设我们已经算出了dp[i-1],如何推导出dp[i]呢?

    可以做到,dp[i]有两种「选择」,要么与前面的相邻子数组连接,形成一个和更大的子数组;要么不与前面的子数组连接,自成一派,自己作为一个子数组。

    如何选择?既然要求「最大子数组和」,当然选择结果更大的那个啦:

    // 要么自成一派,要么和前面的子数组合并
    dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
    

    综上,我们已经写出了状态转移方程,就可以直接写出解法了:

    int maxSubArray(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;
        int[] dp = new int[n];
        // base case
        // 第一个元素前面没有子数组
        dp[0] = nums[0];
        // 状态转移方程
        for (int i = 1; i < n; i++) {
            dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
        }
        // 得到 nums 的最大子数组
        int res = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            res = Math.max(res, dp[i]);
        }
        return res;
    }
    

    以上解法时间复杂度是 O(N),空间复杂度也是 O(N),较暴力解法已经很优秀了,不过注意到dp[i]仅仅和dp[i-1]的状态有关,那么我们可以进行「状态压缩」,将空间复杂度降低:

    int maxSubArray(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;
        // base case
        int dp_0 = nums[0];
        int dp_1 = 0, res = dp_0;
    
        for (int i = 1; i < n; i++) {
            // dp[i] = max(nums[i], nums[i] + dp[i-1])
            dp_1 = Math.max(nums[i], nums[i] + dp_0);
            dp_0 = dp_1;
            // 顺便计算最大的结果
            res = Math.max(res, dp_1);
        }
    
        return res;
    }
    

    最后总结

    虽然说动态规划推状态转移方程确实比较玄学,但大部分还是有些规律可循的。

    今天这道「最大子数组和」就和「最长递增子序列」非常类似,dp数组的定义是「以nums[i]为结尾的最大子数组和/最长递增子序列为dp[i]」。因为只有这样定义才能将dp[i+1]dp[i]建立起联系,利用数学归纳法写出状态转移方程。

    经典动态规划:戳气球问题

    经典动态规划:0-1背包问题的变体

    BFS 算法框架套路详解

    历史文章摘要目录,建议收藏

    _____________

    公众号:labuladong

    B站:labuladong

    知乎:labuladong

    fucking-algorithm 项目在 Github 上已破 42k star,即将出版,公众号后台回复关键词「pdf」限时免费下载,回复「进群」可加入刷题群。东哥手把手带你撕 LeetCode,感受支配算法的快感

    展开全文
  • 重点放在客户—服务器机制上,介绍了客户-服务器机制应用程序用于网络通信套接接口,分析了分布式程序客户端服务器两部分算法,讨论了客户端服务器设计及遵循模式。本书在并发处理上也花费了相当...
  • 对于python列表理解可以C语言里面数组进行比较性记忆与对照,它们比较相似,对于python里面列表定义可以直接用方括号里加所包含对象方法,并且python列表是比较强大,它包含了很多不同类型数据:...
    59f124af2c1f6077317613eb1ee8dd17.png

    对于python列表的理解可以和C语言里面的数组进行比较性的记忆与对照,它们比较相似,对于python里面列表的定义可以直接用方括号里加所包含对象的方法,并且python的列表是比较强大的,它包含了很多不同类型的数据:整型数字,浮点型,字符串以及对象等。接下来将介绍如何向列表里面加元素、删减列表中的一些元素、 获取列表里面的特定元素、列表分片、常用的列表操作符、其他常见列表操作函数。

    5c7c33d631c3d0beaeb0b6b4ac2fa98f.png

    4、列表分片

    对于列表分片的含义需要明白,列表分片就是指将列表里面的一些列元素(不仅仅是某一个元素)进行获取或者得到:temp=List[A:B] 表示将m列表里从索引号位置为A开始的元素到B-1处元素之间的列表获取赋给temp。

    temp = List[1:3]print(temp)
    df184680fda6ef0a41454cd3074c2e35.png

    5、常用的列表操作符

    首先定义两个列表list1和list2。

    list1 = [1,2,3,4,5,6,7,8,9]list2 = [98,76,54,32,1]
    d35e5b3963c285fd637d4d9977034a58.png

    1)+:它主要实现的是多个列表之间的拼接常见的列表操作符

    list3 = list1 + list2print(list3)
    8e7eb2771735df946e8a275d47ed17b5.png

    2)*:主要实现的是列表的复制和添加

    list3 = list1*3
    5061f7c1d2dd60d5e992ba49fe7c95a7.png

    3)比较>,<:>

    list1 > list2
    5f10bed6d3912e17ee6d3bd73b9dd283.png

    4)and等:;逻辑运算符,可以进行列表之间的逻辑判断

    list1 > list2 and list2 > list3
    f8d90d98e7131162b773b20dc0e9d4ca.png

    6、其他常见列表操作函数

    1)count(A):输出元素A在列表list3里面出现的次数。

    list3.count(1)
    6ce4de5928e8ad071189d99cf982d094.png

    2)index(A):输出元素A在列表m里面的索引位置号list3.index(A,a,b):对于列表list3里面包含多个元素A时,输出在列表list3索引号a-b之间的特定索引号。

    list3.index(1)
    a4a69dc5a319d22269f404194286613b.png

    3)reverse():将列表list3进行前后的翻转,前变后,后变前。

    list3.reverse()print(list3)
    f3a5de0f18674e891d58786447e382e4.png

    4)sort():将列表list3里面地数据进行从小到大的排列。

    list3.sort()print(list3)
    06fe2f23f38023661472a615323b2b6c.png

    5)sort(reverse=True):将列表list3里面地数据进行从大到小的排列。

    list3.sort(reverse=True)print(list3)
    dde76ba8b3417f55432eed1eb601f127.png
    展开全文
  • 对于python列表理解可以C语言里面数组进行比较性记忆与对照,它们比较相似,对于python里面列表定义可以直接用方括号里加所包含对象方法,并且python列表是比较强大,它包含了很多不同类型数据:...
    67591f4f2224dfef73f4c96be0764653.png

    对于python列表的理解可以和C语言里面的数组进行比较性的记忆与对照,它们比较相似,对于python里面列表的定义可以直接用方括号里加所包含对象的方法,并且python的列表是比较强大的,它包含了很多不同类型的数据:整型数字,浮点型,字符串以及对象等。接下来将介绍如何向列表里面加元素、删减列表中的一些元素、 获取列表里面的特定元素、列表分片、常用的列表操作符、其他常见列表操作函数、列表的拷贝。

    4b6ae985184fed6193a73275b97b6e94.png

    我们首先定义一个列表。

    List = [1,2,3,4.56,'xiaoming']
    30ad66d9aa8139513e191437899942bd.png

    1、 向列表里面加元素。

    向列表中增加元素有三种方法:

    第一种,append()函数。对于列表的操作主要实现的是在特定的列表最后添加一个元素,并且只能添加一个元素,并且只能在列表最后;【向列表最后添加一个元素“student”】。

    List.append("student")
    68ade66e811368d8771aff4cdacf9f74.png

    第二种,extend()函数。对于列表的操作主要实现的是对于特定列表的扩展和增长,可以一次添加多个元素,不过也只能添加在列表的最后;【向列表最后添加元素“A”、"B"、"C"】。

     List.extend(['A','B','C'])
    6af59c013d8431c33268b3876e6468e1.png

    第三种,insert()函数对于列表的操作主要是在列表的特定位置添加想要添加的特定元素,比较常用。【向列表第一个位置添加元素“WelcomeToPython"】。

    List.insert(0,'WelcomeToPython')
    c971a69a55bcfb94405c815425337d69.png

    2、 删减列表中的一些元素。

    与之前python列表的添加元素相对,删减列表里面的一些元素也有三种方法:

    第一种,remove()函数,移除掉列表里面的特定元素;

    List.remove("xiaoming")
    f82f538284c4c9f1d513a8935e79a4c8.png

    第二种,操作语句del,删除掉列表里面的索引号位置为n的元素;

    del List[0]
    6fb225f33539fb49dd937556f8814d3e.png

    第三种,pop()函数,将列表的最后一个元素返回,并且在此基础上进行删除掉。

    temp = List.pop()
    ff8c4b0afbe8180fc44bae217cc8f74e.png

    3、 获取列表里面的特定元素。

    temp=List[n] %获取List列表第n+1位置处的元素。

    temp = List[1]print(temp)
    514718a4396a88885c809dc5b4464c66.png
    展开全文
  • 对于python列表理解可以C语言里面数组进行比较性记忆与对照,它们比较相似,对于python里面列表定义可以直接用方括号里加所包含对象方法,并且python列表是比较强大,它包含了很多不同类型数据:...
    e477166a28ce00d6a6d04c560141b04f.png

    对于python列表的理解可以和C语言里面的数组进行比较性的记忆与对照,它们比较相似,对于python里面列表的定义可以直接用方括号里加所包含对象的方法,并且python的列表是比较强大的,它包含了很多不同类型的数据:整型数字,浮点型,字符串以及对象等。接下来将介绍如何向列表里面加元素、删减列表中的一些元素、 获取列表里面的特定元素、列表分片、常用的列表操作符、其他常见列表操作函数、列表的拷贝。

    6d9af7d4471013966925257152678e2e.png

    我们首先定义一个列表。

    List = [1,2,3,4.56,'xiaoming']
    fd7e2cd4ba38ce7e86fc6c93140ff185.png

    1、 向列表里面加元素。

    向列表中增加元素有三种方法:

    第一种,append()函数。对于列表的操作主要实现的是在特定的列表最后添加一个元素,并且只能添加一个元素,并且只能在列表最后;【向列表最后添加一个元素“student”】。

    List.append("student")
    2c8e66f7cf0f19c69cf3867e91cdf0b7.png

    第二种,extend()函数。对于列表的操作主要实现的是对于特定列表的扩展和增长,可以一次添加多个元素,不过也只能添加在列表的最后;【向列表最后添加元素“A”、"B"、"C"】。

     List.extend(['A','B','C'])
    3d376111ea8b0afcb507a664f8f8055e.png

    第三种,insert()函数对于列表的操作主要是在列表的特定位置添加想要添加的特定元素,比较常用。【向列表第一个位置添加元素“WelcomeToPython"】。

    List.insert(0,'WelcomeToPython')
    11b1dfb3ddd79d65f430729350a016ee.png

    2、 删减列表中的一些元素。

    与之前python列表的添加元素相对,删减列表里面的一些元素也有三种方法:

    第一种,remove()函数,移除掉列表里面的特定元素;

    List.remove("xiaoming")
    d8e46df047ea18b3059cc9544f6029d5.png

    第二种,操作语句del,删除掉列表里面的索引号位置为n的元素;

    del List[0]
    e41c31351f96155d004c1718161de954.png

    第三种,pop()函数,将列表的最后一个元素返回,并且在此基础上进行删除掉。

    temp = List.pop()
    3a7c9e3f7361d5b3659891d7159477a0.png

    3、 获取列表里面的特定元素。

    temp=List[n] %获取List列表第n+1位置处的元素。

    temp = List[1]print(temp)
    d0f1c3ea7b468e9463b2b9bf70eadcdc.png
    展开全文
  • 6.19 连接的和非连接UDP套接 52 6.20 对UDP使用connect 52 6.21 使用UDP与服务器通信 52 6.22 关闭使用UDP套接 53 6.23 对UDP部分关闭 53 6.24 关于UDP不可靠性警告 53 6.25 小结 53 深入研究 ...
  • 问题1-13:如果用时延带宽积管道来比作传输链路,那么是否宽带链路对应时延带宽积管道就比较宽呢? 问题1-14:网络吞吐量与网络时延有何关系? 问题1-15:什么是“无缝”、“透明“虚拟”? 问题1-...
  • 微软 VB2010 源码包

    2013-05-22 02:21:18
    ImplicitLCSamples:此示例包含两个具有相似源代码源文件,这两个文件分别使用隐式显式行继续符 StatementLambdasSample:通过 lambda 语句,可以用其他过程中多个语句来声明过程 StringFormatting:演示...
  • 或许我应该把自己的经历写下来,从而可以帮助跟我相似的后来者,就这样,我编写了本书的第一版,也就是《自己动手写操作系统》。我相信,如果你也对神奇的计算机世界充满好奇,并且希望通过自己编写操作系统的方式来...
  • 或许我应该把自己的经历写下来,从而可以帮助跟我相似的后来者,就这样,我编写了本书的第一版,也就是《自己动手写操作系统》。我相信,如果你也对神奇的计算机世界充满好奇,并且希望通过自己编写操作系统的方式来...
  • Linux核心具有 Windows 无法比拟稳定性高效率,在不使用 X Windows 情况 下,它占用系统资源较少,可以使一台 Intel486摇身一变成为高效工作站。对于想要学习 UNIX用户来说,使他们熟悉 UNIX 操作环境,...
  • C++MFC教程

    热门讨论 2013-05-21 13:37:15
    例如当菜单转中之后会有WM_COMMAND消息发送,WPARAM中(HIWORD(wParam))是命令ID号,对菜单来讲就是菜单ID。当然用户也可以定义自己消息名称,也可以利用自定义消息来发送通知传送数据。 2、谁将收到...
  • 或许总有一天,现有炉灶取暖灶都会被比较节省天然气或是使用其他燃料炉灶所取代。 表2.1.3 天然气使用及其替代品 ───────────────────────────────────────...
  • 入门学习Linux常用必会60个命令实例详解doc/txt

    千次下载 热门讨论 2011-06-09 00:08:45
    这里笔者把比较重要使用频率最多命令,按照它们在系统中作用分成下面六个部分一一介绍。 ◆ 安装登录命令:login、shutdown、halt、reboot、install、mount、umount、chsh、exit、last; ◆ 文件处理命令...
  • 问题5-2:从通信起点终点来比较,TCPIP不同点是什么? 问题5-3:端口(port)套接(socket)区别是什么? 问题5-4:一个套接能否同时与远地两个套接相连? 问题5-5:数据链路层HDLC协议运输层...
  • 比较复杂系统不能画在一张纸上,逐层分解画法可以控制每一层复杂度。 顶层:将整个系统作为一个加工,描述系统边界(输入与输出)。 中间层:表示某个加工分解为一组子加工,其中子加工还需进一步分解。 ...
  • 答:褶曲基本形式只有背斜向斜,但在自然界中背斜向斜形态又是多种多样,根据它们在横剖面、纵剖面平面上形态特征,可以进一步分类,褶曲在横剖面上形态分类1)直立褶曲2)倾斜褶曲3)倒转褶曲褶曲在...
  • 软件工程教程

    热门讨论 2012-07-06 23:10:29
    传统手工方式对图书信息管理已越来越不能适应社会发展需要,尤其是随着计算机网络Internet普及,运用先进信息管理系统对信息进行科学化网络化管理,已成为图书信息管理系统发展趋势。 系统研发...
  • 1.0.7 如果一个传感器对应物理世界中一个小,如何能让多个传感器对应场景中同一个小? 2 1.0.8 什么是图像中一个像素位置亮度物理含义? 3 1.0.9 为什么图像常用512×512,256×256,128×128 等来表示...
  • 让默认就可以了,但是超频玩者是肯定不会放过任何可以提高性能东西,所以如果你想在这里让你电脑提升一点性能话,就必须慢慢试验,选择一个适当参数才能让你计算机达到性能稳定最佳状态!...
  • Windows XP(包括 Windows 2000)控制台命令是在系统出现一些意外情况下一种非常有效诊断测试以及恢复系统功能工具。小编的确一直都想把这方面命令做个总结,这次辛苦老范给我们整理了这份实用秘笈。 ...
  • s3c24x0: 上系统(SOC) (5)编译 #make fs2410_config; #make 本步骤将编译 u-boot.bin文件,但此时还无法运行在FS2410开发板上。 二、修改 cpu/arm920t/start.S文件,完成 U-Boot重定向 (1)修改中断...
  • 济宁甏肉 济南把子肉很相似 34 00:04:18,200 --> 00:04:22,520 肉一看就是肥瘦相间 有肥有瘦 35 00:04:24,360 --> 00:04:27,640 炖呢 都是特别软烂 36 00:04:28,040 --> 00:04:31,040 用...
  • 《数据结构 1800题》

    热门讨论 2012-12-27 16:52:03
    6.解释和比较以下各组概念【华南师范大学 2000 一(10分)】 (1)抽象数据类型及数据类型 (2)数据结构、逻辑结构、存储结构 (3)抽象数据类型【哈尔滨工业大学 2000 一、1(3分)】 (4)算法时间复杂性 ...
  • “花椒鱼”在做法型制上“水煮”系列相似,但又由于不像“水煮鱼”广为人知,所以其实“花椒鱼”在配料选择做法上就没有太多限制,一般在最后起锅之后泼上现炸花椒油大锅炖鱼其实都可以称之...

空空如也

空空如也

1 2
收藏数 25
精华内容 10
关键字:

和片比较相似的字