首页 文章 精选 留言 我的

精选列表

搜索[词元],共10003篇文章
优秀的个人博客,低调大师

“动态规划”这太吓人,其实可以叫“状态缓存”

摘要:平时练习算法题学习算法知识时,经常会发现题解里写着“动态规划”,里面一上来就是一个复杂的dp公式,对于新人来说除了说声“妙啊”,剩下就是疑惑,他是怎么想到这个公式的?我能想到吗?这玩意工作中有用吗? 本文分享自华为云社区《动态规划究竟是怎么想到的?【奔跑吧!JAVA】》,原文作者:breakDraw。 平时练习算法题学习算法知识时,经常会发现题解里写着“动态规划”,里面一上来就是一个复杂的dp公式,对于新人来说除了说声 剩下就是疑惑,他是怎么想到这个公式的?我能想到吗?这玩意工作中有用吗? 加上“动态规划”这高端的名字,然后就劝退了不少试图去理解他的人。 动态规划听起来太吓人,可以换个说法 我在内心更喜欢叫他“状态缓存” 如果是服务开发,相信很熟悉这个词语, 利用缓存来加快一些重复的请求的响应速度。 而这个缓存的特点是和其他缓存有所关联。 比如我们的服务要计算7天内的某金钱总和,计算后要缓存一下。 后来又收到一个请求,要计算8天内的金钱总和 那我们只需要取之前算过的7天内的金钱综合,加上第8天的金钱就行了。 1+4的思考套路 自己针对动态规划总结了一个自己的思考套路,我叫他1组例子4个问题,就叫1+4好了,通过这5个过程,可以站在普通人的角度(就是非acm大佬那种的角度),去理解动态规划是如何被思考出来的 在超时的思路上写出一组计算过程的例子 在超时例子的基础上,有哪些重复、浪费的地方? 如何定义dp数组 状态的变化方向是什么,是怎么变化的 边界状态是什么 简单例子 以一道简单题为例: 爬楼梯: https://leetcode-cn.com/problems/climbing-stairs/ 这时候就要静下心,观察这个解法的例子中是否有重复经历的场景,而这个重复经历的场景就叫状态。 我处理动态规划的题目时, 都会问自己3个问题,一般就能顺利地解决。 ①在超时的思路上写出一组计算过程的例子 如果我们考虑最简单的解法, 就是从起点开始,每次选择走1步或者走2步,看下能否走到终点,能走到则方法数+1。 但这种方法注定超时(O(n^2)) 但我还是照着这个过程模拟了一下,随便列了几个 1 ->2-> 3-> 4-> 5 1 ->2 ->3-> 5 1->3->4->5 1->3->5 ②在超时例子的基础上,有哪些重复、浪费的地方? 在上面,我发现了重复的地方 也就是说 从3到5总共就2种路线,已经在1->2之后计算过了,我后面从1走到3再往后走时,没必要再去算了。 换言之,当我走到3的时候,其实早就可以知道后面还剩下多少种走法。 发现重复的地方后,就可以开始建立dp公式了。 ③如何定义dp数组? 定义dp数组,也就是定义上面提到的重复的地方。重新看下之前的那句话 当我走到3的时候,其实早就可以知道后面还剩下多少种走法。 所以dp[3]代表的就是从3往后,有多少种可走的方法。 ④状态的变化方向是什么,是怎么变化的 首先思考状态的变化方向 重新看这句话: 当我走到3的时候,其实早就可以知道后面还剩下多少种走法 说明结果取决于往后面的状态 因此我们要先计算后面的状态, 即从后往前算 接着思考这个后面的状态和当前的状态有什么联系,是怎么变化的 这个一般都包含在题目条件中 根据题意,要么走2步,要么走1步,因此每当我走到一层时,下一次就2种状态可以变化。 那么对于第3层而言,他后续有2种走法,走1步或者走2步 那么他的情况就是dp[3] = dp[3+1] + dp{3+2} 如果层数设为i,那么这个变化情况就是 dp[i] = dp[i+1] + dp[i+2] ⑤边界状态是什么? 边界状态就是不需要依赖后面的状态了,直接可以得到结果的状态。 在这里肯定就是最后一层dp[n], 最后一层默认是一种走法。 dp[n]=1 实现 根据上面的过程,自己便定义了这个状态和变化 定义:dp[i] : 代表从第i层往后,有多少种走法 方向和变化:dp[i] = dp[i+1] + dp[i+2]; 边界: dp[n] = 1 根据这个写代码就很容易了 代码: public int climbStairs(int n) { int[] dp = new int[n + 1]; dp[n] = 1; dp[n-1] = 1; for(int i = n-2; i >=0;i--) { dp[i] = dp[i+1] + dp[i+2]; } return dp[0]; } 进阶版,二维的动态规划 https://leetcode-cn.com/problems/number-of-ways-to-stay-in-the-same-place-after-some-steps/ ①在超时的思路上写出一组计算过程的例子 超时的思路肯定是像搜索一样模拟所有的行走过程。 先假设1个steps=5, arrlen=3的情况 随便先列几个。模拟一下不断走的位置。数字指的是当前位置。 0->1->2->1->0->0 0->1->2->1->1->0 0->1->1->1->1->0 0->1->1->1->0->0 0->0->1->1->1->0 …… ②在超时例子的基础上,有哪些重复、浪费的地方? 0->1->2->1->0->0 0->1->2->1->1->0 0->1->1->1->1->0 0->1->1->1->0->0 0->0->1->1->1->0 0->0->1->1->0->0 我发现这部分标粗的部分重复了, 换句话说 当我还剩2步且当前位置为1的时候,后面还有多少种走法,其实早就知道了。 ③如何定义dp数组? 重新看这句话: 当我还剩2步且当前位置为1的时候,后面还有多少种走法,其实早就知道了。 涉及了2个关键因素: 剩余步数和当前值,所以得用二维数组 因此 dp[realstep][index] 就代表了 剩余步数为step且位置为index时, 后续还剩多少种走法。 ④状态的变化方向是什么,是怎么变化的 先思考变化方向 “当我还剩2步且当前位置为1的时候,后面还有多少种走法,其实早就知道了。” 这个后面是指啥, 后面会怎么变? 后面肯定是步数越来越少的情况, 并且位置会根据规律变化。 所以变化方向是步数变少,位置则按照规定去变。 那么这个固定越来越少的这个“剩余步数”,就是核心的变化方向。 我们计算时,可以先计算小的剩余步数的状态, 再去算大的剩余步数。 如何变化 根据题意和方向,剩余步数肯定-1, 然后位置有3种选择(减1,不变,加1), 那么方法就是3种选择的相加。 dp[step][index] = dp[step-1][index-1] + dp[step-1][index] + dp[step-1][index+1] ⑤边界状态是什么? 剩余步数为0时,只有当前位置为0才是我们最终想要的方案,把值设为1并提供给后面用,其他位置且步数为0时都认为是0。 dp[0][0] = 1; dp[0][index] = 0;(index>0) 实现 那么最终出来了 定义:dp{realstep][index]: 剩余步数为step且位置为index时, 后续还剩多少种走法。 方向和变化:dp[step][index] = dp[step-1][index-1] + dp[step-1][index] + dp[step-1][index+1] 边界: dp[0][0] = 1; 内存溢出处理 不过这题因为是困难题,所以给上面这个公式设立了一个小难度: 数组长度非常大,导致如果index的范围我们选择为0~arrLen-1, 那么最大情况dp[500][10^6]注定超时内存范围。 这时候就要去思考index设那么大是不是没必要 一般我们可以自己列这种情况的小例子,例如 step=2, arr=10 然后看下index有没有必要设成0~9,随便走几步 0->1->0 0->1->0 0->0->0 嗯?我发现就3种情况,arr后面那么长不用啦? 于是发现规律: 剩余的步数,必须支撑他返回原点! 也就是说,其实index的最大范围最多就是step/2, 不能再多了,再多肯定回不去了。 于是问题解决。 其他类似题目练习 https://leetcode-cn.com/problems/minimum-cost-for-tickets/ 点击关注,第一时间了解华为云新鲜技术~

优秀的个人博客,低调大师

关于大数据你必须了解的几个关键

摘要:大数据分析,即对规模巨大的数据进行分析,能够高效存储和处理海量数据、并有效达成多种分析目标的工具及技术的集合。 大数据分析的定义: 大数据分析,即对规模巨大的数据进行分析,能够高效存储和处理海量数据、并有效达成多种分析目标的工具及技术的集合。Gartner将大数据分析定义为追求显露模式检测和发散模式检测,以及强化对过去未连接资产的使用的实践和方法,意即一套针对大数据进行知识发现的方法。通俗地讲,大数据分析技术就是大数据的收集、存储、分析和可视化的技术,是一套能够解决大数据的4V【海量(Volume)、高速(Velocity)、多变(Variety)、真实(Veracity)】问题,分析出高价值(Value)的信息的工具集合。 大数据 大数据的特点:数据量大、数据种类多、 要求实时性强、数据所蕴藏的价值大。在各行各业均存在大数据,但是众多的信息和咨询是纷繁复杂的,需要搜索、处理、分析、归纳、总结其深层次的规律。 数据量:这个参数表示数据的数量,随着科学技术及互联网的发展,推动着大数据时代的来临,各行各业每天都在产生数量巨大的数据碎片,数据计量单位已从从Byte、KB、MB、GB、TB发展到PB、EB、ZB、YB甚至BB、NB、DB来衡量。 数据类型: 传统企业数据(Traditionalenterprisedata):包括CRMsystems的消费者数据,传统的ERP数据,库存数据以及账目数据等。 机器和传感器数据(Machine-generated/sensordata):包括呼叫记录(CallDetailRecords),智能仪表,工业设备传感器,设备日志(通常是Digitalexhaust),交易数据等。 社交数据(Socialdata):包括用户行为记录,反馈数据等。如Twitter,Facebook这样的社交媒体平台。 处理速度: 1秒定律,这一点也是和传统的数据挖掘技术有着本质的不同,物联网,云计算、移动互联网、车联网、手机、平板电脑、PC以及遍布地球各个角落的各种各样的传感器,无一不是数据来源或者承载的方式。 大数据分析工具: 数据来自各个方面,在面对庞大而复杂的大数据,选择一个合适的处理工具显得很有必要,几款好用的处理工具如Hadoop、HPCC、Storm、Apache Drill、RapidMiner和Pentaho BI。工欲善其事,必须利其器,一个好的工具不仅可以使我们的工作事半功倍,也可以让我们在竞争日益激烈的云计算时代,挖掘大数据价值,及时调整战略方向。 大数据的应用: 大数据可应用于各行各业,将人们收集到的庞大数据进行分析整理,实现资讯的有效利用。 营销: 主要用于管理和优化各种营销活动,如交叉销售、追加销售以及基于位置的一对一营销,并及时对客户需求进行完整评估等。 财政: 使用大数据技术可以预防欺诈检查、进行风险估计和管理、贸易监视、反洗钱、防止信贷风险等。 保险: 为规避风险,防止欺诈行为,由大数据分析师及时分析调整工作负荷,客户价值等。 零售: 1、分析商品 2、供应链管理分析 3、优化消费 通讯: 推进网络优化规划,满足不同客户需求,研发并推出新产品。 分析引擎:提供连接器,处理数据库。 支持大数据分析法: 面对庞杂而复杂的数据,必须有许多有效的解决方案,普通分析和高级分析都可以轻松提供集成,集中分析数据,在一个单一的平台上,满足分析引擎对营销方案的需求。 电子表格工具: ODBC连接器将客户与Microsoft Excel连接在一起,利用精湛的分析工具如Qlik,MicroStrategy,TIBCO、Jaspersoft,Tableau等,在ODBC/REST APIS的帮助下,将协调R统计编程语言添加到金属板。 CRM和在线营销方案: Salesforce.com提供的著名的CRM和在线营销解决方案适合处理业务,并及时提供必要的网络分析对策。 大数据的意义和前景: 总的来说,大数据是对大量、动态、能持续的数据,通过运用新系统、新工具、新模型进行挖掘,从而获得具有洞察力和新价值的东西。以前,面对庞大的数据,我们可能会一叶障目、可见一斑,因此不能了解到事物的真正本质,从而在科学工作中得到错误的推断,而大数据时代的来临,一切真相将会展现在人们面前。 本文转自d1net(转载)

资源下载

更多资源
Nacos

Nacos

Nacos /nɑ:kəʊs/ 是 Dynamic Naming and Configuration Service 的首字母简称,一个易于构建 AI Agent 应用的动态服务发现、配置管理和AI智能体管理平台。Nacos 致力于帮助您发现、配置和管理微服务及AI智能体应用。Nacos 提供了一组简单易用的特性集,帮助您快速实现动态服务发现、服务配置、服务元数据、流量管理。Nacos 帮助您更敏捷和容易地构建、交付和管理微服务平台。

Spring

Spring

Spring框架(Spring Framework)是由Rod Johnson于2002年提出的开源Java企业级应用框架,旨在通过使用JavaBean替代传统EJB实现方式降低企业级编程开发的复杂性。该框架基于简单性、可测试性和松耦合性设计理念,提供核心容器、应用上下文、数据访问集成等模块,支持整合Hibernate、Struts等第三方框架,其适用范围不仅限于服务器端开发,绝大多数Java应用均可从中受益。

Rocky Linux

Rocky Linux

Rocky Linux(中文名:洛基)是由Gregory Kurtzer于2020年12月发起的企业级Linux发行版,作为CentOS稳定版停止维护后与RHEL(Red Hat Enterprise Linux)完全兼容的开源替代方案,由社区拥有并管理,支持x86_64、aarch64等架构。其通过重新编译RHEL源代码提供长期稳定性,采用模块化包装和SELinux安全架构,默认包含GNOME桌面环境及XFS文件系统,支持十年生命周期更新。

Sublime Text

Sublime Text

Sublime Text具有漂亮的用户界面和强大的功能,例如代码缩略图,Python的插件,代码段等。还可自定义键绑定,菜单和工具栏。Sublime Text 的主要功能包括:拼写检查,书签,完整的 Python API , Goto 功能,即时项目切换,多选择,多窗口等等。Sublime Text 是一个跨平台的编辑器,同时支持Windows、Linux、Mac OS X等操作系统。

用户登录
用户注册