2017年11月26日00:08:06

2017年11月26日00:11:18 发表评论 236 views

时间总是容自己控制,本来很早就能把报告总结完,案例分析完,就是期间有重要的聊天,最后匆匆的写完报告去睡觉了。

以下是word内容:

我理解中的动态规划:

把一个问题分解成多个问题,按顺序求解子问题,前一子问题的解,为后一子问题提供有用的信息。求每个子问题是,解出各个局部的解,通过决策达到那些最优的局部解,其他的解丢弃。依次解决各个子问题,解到最后一个就是厨师问题的解。

动态规划使用的情况:

采用动态规划求解的问题一般需要3个性质:

  1. 最优化原理:如果问题的最优解所包含的子问题的解也是最优的,就称该问题具有最优子结构,既满足最优化原理。
  2. 无后效性:即某阶段状态一旦确定,就不受这个状态以后决策的影响。也就是说,某状态以后的过程不会影响以前的状态,只与当前状态有关。
  3. 有重叠子问题:即子问题之间是不独立的,一个子问题在下一阶段决策中可能被多次使用到。

动态规划算法题:

首先,我们看一下这道题(此题目来源于北大POJ):

 数字三角形(POJ1163)

    2017年11月26日00:08:06

    在上面的数字三角形中寻找一条从顶部到底边的路径,使得路径上所经过的数字之和最大。路径上的每一步都只能往左下或 右下走。只需要求出这个最大和即可,不必给出具体路径。 三角形的行数大于1小于等于100,数字为 0 - 99

样式输入:

5      //表示三角形的行数    接下来输入三角形

7

3   8

8   1   0

2   7   4   4

4   5   2   6   5

样式输出

30

   解题思路:

要求输出最大和

首先,肯定得用二维数组来存放数字三角形

然后建一个数组来存放子问题的解。

利用max(a,b)+arr[i][j],解除算一个子问题,max(a,b)是去出重复的计算。

实现代码:

2017年11月26日00:08:06

 

下午的模拟考试8道题做出三道,做出了三道题中有一道题有那么点难,其他题用代码不知道怎么实现,但是想法却有的。

描述

传说某凡学长在给学弟出题的时候,总是会自认为题的数据量很大,然而每次都会让学弟轻松的拿暴力跑过去,因此每次凡学长的心态都十分崩溃。而这次,学弟本是想回敬一道数据量灰常大的主席树,套水仙花数,套最小生成树,套伸展树,但是出于照顾凡学长心态的考虑, 就换成了这道防AK题。^_^

正如一般的算法题一样,我这里也在前面说了一堆废话。

在一天凡学长给”炸酱面”同学为了这次编程大赛做算法训练时,突然向这位同学提出了q个问题!假如有n道题,每道题做对会拿到Ai块钱,

(1<=i<=n), (-10^9 <= A[i] <= 10^9),凡学长每次问这位学弟假如他会做从第i道题开始(包括i在内),在这之后(包括第i道题)总共连续的k道题,他想知道他会收到多少钱。

输入

Input
第1行:一个数N,N为数组的长度(2 <= N <= 50000)。
第2 至 N + 1行:数组的N个元素。(-10^9 <= A[i] <= 10^9)
第N + 2行:1个数Q,Q为查询的数量。Q<=1000000
第N + 3 至 N + Q + 2行:每行2个数,i,K(1 <= i <= N,0<=K+ i -1 <= N)

输出

对于每个询问。输出可以拿到的钱数。

样例输入1

5

1

3

7

9

-1

4

1 2

2 2

3 2

1 5

样例输出1

4

10

16

19

解题思路:

用一维数组去装Ai,用二维数组去装i和k。

解题的时候就用i和k的二维数组去一维数组中遍历,从i开始遍历K次。

解题代码:

2017年11月26日00:08:06

2017年11月26日00:08:06

Array和arrayList

新学的数组方法

2017年11月26日00:08:06

2017年11月26日00:08:06

1)Java中Array与ArrayList的主要区别:
可以将 ArrayList想象成一种“会自动扩增容量的Array”。

2)Array([]):最高效;但是其容量固定且无法动态改变;
ArrayList:  容量可动态增长;但牺牲效率;

3)基于效率和类型检验,应尽可能使用Array无法确定数组大小时才使用ArrayList
不过当试着解决更一般化的问题时,Array的功能就可能过于受限。

4)Java中一切皆对象,Array也是对象。不论所使用得Array型别为何,

Array名称本身实际上是个reference,指向heap之内得某个实际对象。

这个对象可经由“Array初始化语法”被自动产生,也可以以new表达式手动产生。

5)Array可做为函数返回值,因为它本身是对象的reference;

6)对象数组与基本类型数组在运用上几乎一模一样,唯一差别在于,前者持有得是reference,后者直接持有基本型别之值;
例如:
string [] staff=new string[100];
int [] num=new int[10];

7)对数组的一些基本操作,像排序、搜索与比较等是很常见的。因此在Java中提供了Arrays类协助这几个操作:sort(),binarySearch(),equals(),fill(),asList().

不过Arrays类没有提供删除方法,而ArrayList中有remove()方法,不知道是否是不需要在Array中做删除等操作的原因(因为此时应该使用链表)。

8)ArrayList的使用也很简单:产生ArrayList,利用add()将对象置入,利用get(i)配合索引值将它们取出。这一切就和Array的使用方式完全相同,只不过少了[]而已。

2.参考资料:
1)效率:
数组扩容是对ArrayList效率影响比较大的一个因素。
每当执行Add、AddRange、Insert、InsertRange等添加元素的方法,都会检查内部数组的容量是否不够了,如果是,它就会以当前容量的两倍来重新构建一个数组,将旧元素Copy到新数组中,然后丢弃旧数组,在这个临界点的扩容操作,应该来说是比较影响效率的。

ArrayList是Array的复杂版本
ArrayList内部封装了一个Object类型的数组,从一般的意义来说,它和数组没有本质的差别,甚至于ArrayList的许多方法,如Index、IndexOf、Contains、Sort等都是在内部数组的基础上直接调用Array的对应方法。

2)类型识别:
ArrayList存入对象时,抛弃类型信息,所有对象屏蔽为Object,编译时不检查类型,但是运行时会报错。
ArrayList与数组的区别主要就是由于动态增容的效率问题了

3)ArrayList可以存任何Object,如String等。

  • 我的微信
  • 这是我的微信扫一扫
  • weinxin
  • 我的支付宝红包
  • 支付宝红包扫一扫打赏
  • weinxin

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: