4 csuzhucong

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 344

力扣OJ 673. 最长递增子序列的个数

给定一个未排序的整数数组,找到最长递增子序列的个数。示例 1:输入: [1,3,5,4,7]输出: 2解释: 有两个最长递增子序列,分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。示例 2:输入: [2,2,2,2,2]输出: 5解释: 最长递增子序列的长度是1,并且存在5个子序列的长度为1,因此输出5。注意:给定的数组长度不超过 2000 并且结果一定是32位有符号整数。class Solution {public: int findNumbe..

2020-06-05 09:04:23

ACM总结——动态规划(5)二维DP

因为最近在写DP总结系列,所以选了一个二维DP的题目,把各种代码都写了一遍,并在此进一步探索。力扣OJ 63. 不同路径 II (二维DP)https://blog.csdn.net/nameofcsdn/article/details/106537960这里面的4个代码,涉及到递归和非递归、非递归的不同顺序、空间压缩。第一个问题来了,非递归写法有没有空间压缩写法呢?以题目中的数据和我的递归算法为例输入:[[0,0,0],[0,1,0],[0,0,0]]int ...

2020-06-04 22:48:48

力扣OJ 63. 不同路径 II (二维DP)

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?网格中的障碍物和空位置分别用 1 和 0 来表示。说明:m和 n 的值均不超过 100。示例1:输入:[[0,0,0],[0,1,0],[0,0,0]]输出: 2解释:3x3 网格的正中间有一个障碍...

2020-06-04 08:52:10

ACM总结——动态规划(4)问题的形式化描述

动态规划的核心在于分析最优子结构,其中包含如下内容:如何描述问题,如何描述子问题,问题的解和子问题的解之间的关系,即递推式,问题的解空间结构,如何遍历这个解空间,等等。问题的描述形式,取决于我们所求的答案的形式和结构.个人理解主要分三种情形:(1)完全按照题目所求来描述问题(2)按照题目的同规模子问题来描述问题(3)附加特殊规则的精确化的描述的问题对于问题本身的描述很复杂的题目,我们的描述越精确,我们的递推式也就越简洁。例如:...

2020-06-02 23:43:16

ACM总结——动态规划(3)空间压缩

动态规划的空间压缩,本质上就是用时间取代空间的其中一维,使得空间复杂度降低,但时间复杂度不变。具体来说,空间压缩就是,在同一个空间位置,不停刷新值,随着时间的推移,他的含义一直在变化,而他的值一直是对应他的含义。首先举个最简单的例子感受一下:求斐波那契数列的第1000项int ans[1005]={0,1,1};for(int i=3;i<=1000;i++)ans[i]=ans[i-1]+ans[i-2];时间复杂度和空间复杂度都是O(n)而空间压缩的写法:i.

2020-06-02 23:23:55

力扣 934. 最短的桥

在给定的二维二进制数组A中,存在两座岛。(岛是由四面相连的 1 形成的一个最大组。)现在,我们可以将0变为1,以使两座岛连接起来,变成一座岛。返回必须翻转的0 的最小数目。(可以保证答案至少是 1。)示例 1:输入:[[0,1],[1,0]]输出:1示例 2:输入:[[0,1,0],[0,0,0],[0,0,1]]输出:2示例 3:输入:[[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]...

2020-06-02 15:05:38

力扣OJ 1319. 连通网络的操作次数

用以太网线缆将n台计算机连接成一个网络,计算机的编号从0到n-1。线缆用connections表示,其中connections[i] = [a, b]连接了计算机a和b。网络中的任何一台计算机都可以通过网络直接或者间接访问同一个网络中其他任意一台计算机。给你这个计算机网络的初始布线connections,你可以拔开任意两台直连计算机之间的线缆,并用它连接一对未直连的计算机。请你计算并返回使所有计算机都连通所需的最少操作次数。如果不可能,则返回-1 。示例 1:...

2020-06-01 08:53:18

力扣周赛 5426. 重新规划路线

n 座城市,从 0 到 n-1 编号,其间共有 n-1 条路线。因此,要想在两座不同城市之间旅行只有唯一一条路线可供选择(路线网形成一颗树)。去年,交通运输部决定重新规划路线,以改变交通拥堵的状况。路线用 connections 表示,其中 connections[i] = [a, b] 表示从城市 a 到 b 的一条有向路线。今年,城市 0 将会举办一场大型比赛,很多游客都想前往城市 0 。请你帮助重新规划路线方向,使每个城市都可以访问城市 0 。返回需要变更方向的最小路线数。题目数据 保

2020-05-31 17:16:30

力扣周赛 5425. 切割后面积最大的蛋糕

矩形蛋糕的高度为 h 且宽度为 w,给你两个整数数组 horizontalCuts 和 verticalCuts,其中 horizontalCuts[i] 是从矩形蛋糕顶部到第i 个水平切口的距离,类似地, verticalCuts[j] 是从矩形蛋糕的左侧到第 j 个竖直切口的距离。请你按数组 horizontalCuts 和 verticalCuts 中提供的水平和竖直位置切割后,请你找出 面积最大 的那份蛋糕,并返回其 面积 。由于答案可能是一个很大的数字,因此需要将结果对 10^9 + 7 ..

2020-05-31 17:07:16

力扣周赛 5424. 数组中两元素的最大乘积

给你一个整数数组 nums,请你选择数组的两个不同下标 i 和 j,使 (nums[i]-1)*(nums[j]-1) 取得最大值。请你计算并返回该式的最大值。示例 1:输入:nums = [3,4,5,2]输出:12解释:如果选择下标 i=1 和 j=2(下标从 0 开始),则可以获得最大值,(nums[1]-1)*(nums[2]-1) = (4-1)*(5-1) = 3*4 = 12 。示例 2:输入:nums = [1,5,4,5]输出:16解释:选择下标 i=1...

2020-05-31 17:04:54

力扣周赛 5427. 两个盒子中球的颜色数相同的概率

桌面上有 2n 个颜色不完全相同的球,球上的颜色共有 k 种。给你一个大小为 k 的整数数组 balls ,其中 balls[i] 是颜色为i 的球的数量。所有的球都已经 随机打乱顺序 ,前 n 个球放入第一个盒子,后 n 个球放入另一个盒子(请认真阅读示例 2 的解释部分)。注意:这两个盒子是不同的。例如,两个球颜色分别为 a 和 b,盒子分别为 [] 和 (),那么 [a] (b) 和 [b] (a) 这两种分配方式是不同的(请认真阅读示例 1 的解释部分)。请计算「两个盒子中球的颜色数相.

2020-05-31 16:24:22

ACM总结——动态规划(2)问题本身的固有属性决定数据结构和算法

1,数据结构数据结构不仅取决于问题研究的对象本身的数据结构,也取决于在这个对象上,我们需要什么样的形式的一个答案。例如:力扣OJ 740. 删除与获得点数https://blog.csdn.net/nameofcsdn/article/details/106436711同样是数组,我们可以寻求很多种不同形式不同结构的答案。常规的是一种基于顺序的,或者基于子序列的答案,而本题是基于数值的。也就是说,我们访问了一个元素之后,要立即删除和他数值隔1的那些数,这个当然不能总靠暴力枚举了,.

2020-05-30 09:03:01

力扣OJ 740. 删除与获得点数

给定一个整数数组nums,你可以对它进行一些操作。每次操作中,选择任意一个nums[i],删除它并获得nums[i]的点数。之后,你必须删除每个等于nums[i] - 1或nums[i] + 1的元素。开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。示例 1:输入: nums = [3, 4, 2]输出: 6解释:删除 4 来获得 4 个点数,因此 3 也被删除。之后,删除 2 来获得 2 个点数。总共获得 6 个点数。示例2:输入: num...

2020-05-30 08:49:52

力扣OJ 1218. 最长定差子序列

给你一个整数数组arr和一个整数difference,请你找出arr中所有相邻元素之间的差等于给定difference的等差子序列,并返回其中最长的等差子序列的长度。示例 1:输入:arr = [1,2,3,4], difference = 1输出:4解释:最长的等差子序列是 [1,2,3,4]。示例2:输入:arr = [1,3,5,7], difference = 1输出:1解释:最长的等差子序列是任意单个元素。示例 3:输入:arr = [1,5,7,...

2020-05-29 08:58:26

ACM总结——动态规划(1)重叠子问题、最优子结构

动态规划(dynamic programming)简称DP。先看3个简单的问题:1,斐波那契数列1,1,2,3,5,8......求第n项int fac(int n){ if(n<3)return 1; return fac(n-1)+fac(n-2);}时间复杂度O (1.6 ^ n)递归写法(备忘录法):int ans[1000]={0};int fac(int n){ if(n<3)return 1; if(ans

2020-05-29 01:27:48

C/C++ 静态告警清理——函数入参加const

规则:函数内对入参指针指向的地址没有修改的话,入参类型设为const注意点:1,有宏的地方,要点进去看内容2,如果涉及到指针传递,要沿着调用链查看是否有修改指针指向的内容,如果有修改就不能设为const,如果没有修改,则沿着调用链依次加constvoid f1(int *p){ f2(p);}void f2(int *p){ p=0;}像这种情况,f1加了const之后, f2也要加貌似并不是很复杂?在我想了这些之后我就开干了,然而,很快,我就遇.

2020-05-29 00:37:31

力扣OJ 1248. 统计「优美子数组」

给你一个整数数组nums 和一个整数 k。如果某个 连续 子数组中恰好有 k 个奇数数字,我们就认为这个子数组是「优美子数组」。请返回这个数组中「优美子数组」的数目。示例 1:输入:nums = [1,1,2,1,1], k = 3输出:2解释:包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1] 。示例 2:输入:nums = [2,4,6], k = 1输出:0解释:数列中不包含任何奇数,所以不存在优美子数组。示例 3:输入:nums = [..

2020-05-28 09:05:15

力扣OJ 971. 翻转二叉树以匹配先序遍历

给定一个有 N 个节点的二叉树,每个节点都有一个不同于其他节点且处于 {1, ..., N} 中的值。通过交换节点的左子节点和右子节点,可以翻转该二叉树中的节点。考虑从根节点开始的先序遍历报告的 N 值序列。将这一 N 值序列称为树的行程。(回想一下,节点的先序遍历意味着我们报告当前节点的值,然后先序遍历左子节点,再先序遍历右子节点。)我们的目标是翻转最少的树中节点,以便树的行程与给定的行程voyage相匹配。如果可以,则返回翻转的所有节点的值的列表。你可以按任何顺序返回答案...

2020-05-27 21:59:48

力扣OJ 979. 在二叉树中分配硬币

给定一个有 N 个结点的二叉树的根结点 root,树中的每个结点上都对应有 node.val 枚硬币,并且总共有 N 枚硬币。在一次移动中,我们可以选择两个相邻的结点,然后将一枚硬币从其中一个结点移动到另一个结点。(移动可以是从父结点到子结点,或者从子结点移动到父结点。)。返回使每个结点上只有一枚硬币所需的移动次数。示例 1:输入:[3,0,0]输出:2解释:从树的根结点开始,我们将一枚硬币移到它的左子结点上,一枚硬币移到它的右子结点上。示例 2:输入:[0,3,0]输出:.

2020-05-26 09:02:07

力扣OJ 523. 连续的子数组和

给定一个包含非负数的数组和一个目标整数k,编写一个函数来判断该数组是否含有连续的子数组,其大小至少为 2,总和为 k 的倍数,即总和为 n*k,其中 n 也是一个整数。示例 1:输入: [23,2,4,6,7], k = 6输出: True解释: [2,4] 是一个大小为 2 的子数组,并且和为 6。示例 2:输入: [23,2,6,4,7], k = 6输出: True解释: [23,2,6,4,7]是大小为 5 的子数组,并且和为 42。说明:数组的长度不会超过10,000.

2020-05-25 22:09:26

查看更多

勋章 我的勋章
  • 专栏达人
    专栏达人
    授予成功创建个人博客专栏的用户。专栏中添加五篇以上博文即可点亮!撰写博客专栏浓缩技术精华,专栏达人就是你!
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 1024超级勋章
    1024超级勋章
    授予原创文章总数达到1024篇的博主,感谢你对CSDN社区的贡献,CSDN与你一起成长。
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。