动态规划入门

动规就是将复杂的问题,变成小问题,通过解决小问题来解决原问题。通过记录之前经计算过的子问题,进行下一次的使用,从而起到节约时间的目的。
一个问题必须拥有重叠子问题和最优子结构才可以使用动规。
重叠问题:一个问题可以分成多个问题,这些问题会重复出现
最优子结构:一个问题的最优解由其子问题的最优解构造出来的

1.最大连续子序列和
给定一个数字序列,求i,j使得之间加起来最大
状态转移方程: dp[i]=max{A[i],dp[i-1]+A[i]};

2.最长不下降子序列(LIS)
在一个数字序列中,找到一个最长的不下降的子序列(可以不连续)
思路:取位置i与之前的所有位置(设j)进行比较,若满足条件就使得dp[i]=dp[j]+1; 遍历所有的之前位置,取最大值为i的最长序列。
状态转移方程:dp[i]=max{dp[j]+1,1};

3.最长公共子序列(LCS)
给定两个字符串AB,求A和B的最长公共部分(可以不连续)
思路:dp[i][j] 为A的i号位置与B的j号位置的LCS的长度;
1. 如果A[I]==B[J] 即i号位置与j号位置字符相同,dp[i][j]=dp[i-1][j-1]+1;
2. 如果不相同的话,dp[i][j]继承dp[i-1][j]与dp[i][j-1]的较大值,
3. 边界dp[i][0]=dp[0][j]=0;

4.最长回文子串
给出一个字符串,求字符串的最长回文子串的长度
思路:1.Dp[i][j]为s[i]到s[j]是否为回文子串.是为1不是为0;
2.s[i]==s[j] 则只需要知道dp[s+1][j-1]是否为回文就可以
3.s[i]!=s[j] 则不是回文
4.边界dp[i][i]=1;dp[i][i+1]==(s[i]==s[i+1])? 1:0;
5.通过限定i到j之间的距离,遍历整个字符串,在不断的变大距离,最后求出结果

5.树塔
从塔顶到最下面,将路径的所有数字相加后得到的和最大是多少。
边界:dp[n][j]=f[n][j];
状态方程:dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+f[i][j];

6.01背包
N件物品,每件物品重量为w[i],价值为c[i]。现有一个容量为V的背包,问如何选取使得物品放入背包,使得价值最大。每种物品只有一件。Dp[i][j] 表示前i件物品装入容量为j的背包最大总价值。

For(int i =1;i<=n;i++)
   For(int v=w[i];v<=V;v++)
      Dp[i][j]=max(dp[i-1][v],dp[i-1][v-w[i]]+c[i]);

优化后 使用一维数组时,v为逆序

For(int i =1;i<=n;i++)
   For(int v=V;v>=w[i];v--)
      Dp[v]=max(dp[v],dp[v-w[i]]+c[i]);

7.完全背包
N件物品,每件物品重量为w[i],价值为c[i]。现有一个容量为V的背包,问如何选取使得物品放入背包,使得价值最大。每种物品有无数件。ps:01和完全背包看似只是代码第二行发生了变化,在完全背包中,后面的dp可以调用之前已经选过该物品的dp,从而达到物品无限次选的目的。而01将顺序反过来使得每个物品只能够选择一次。

For(int i =1;i<=n;i++)
   For(int v=w[i];v<=V;v++)
      Dp[v]=max(dp[v],dp[v-w[i]]+c[i]);

当题目与序列或者字符串相关时,可以考虑吧状态设计成下面两种形式,然后根据断电特点来考虑状态方程。
Dp[i] 表示以i为结尾(开头的)xxx;
Dp[i][j]表示从i到j的区间的xxx;

排序

 

1.冒泡排序

通过两个数之间进行大小比较,较大的数下沉,较小的数上浮,通过不断的比较来调整位置。

Void bubblesort(int arr[] )
{
  Int temp;
  For(int i=0;i<arr.length()-1;i++)
    For(int j=arr.length()-;j>I;j--)
      If(arr[j]<arr[i]){
        swap(arr[i],arr[j]);
      }
}

时间复杂度:O(n^2)

2.简单选择排序

从开始一直枚举到最后,每次取其中最小的的元素,放在最前面,不断形成一个有序的排列。

void selectcode(){
for(int i=0;i<n;i++){
   k=i;
   for(int j=i;j<n;j++)
      if(a[k]>a[j]) k=j;
   swap(a[k],a[i]);
}

逻辑简单,在不考虑时间复杂度的情况下,可以不用动脑子,但是时间复杂度相对来讲比较高为,O(n^2)

3.直接插入排序

从第二位开始,每次从无序的数组中,取出第一个在有序的数组中找到它的位置,将它放在其中,在它后面的数都往后移一个位置。

void insertcode(){
   for(int i=1;i<n;i++){
      int temp=a[i],j=i;//temp为需要变化的数
      while(j>1&&temp<a[j-1]){
         a[j]=a[j-1];   //数组往后移一位
         j--;
      }
      a[j]=temp;
   }
}

4.归并排序

简单的来讲一下2-路归并排序。原理就是就序列两两分组,组内先进行排序;然后将这些组再两两归并,组内在排序;一直进行下去只到只剩下一个组为止。时间复杂度为O(nlogn)

void merge(int a[], int l1,int r1,int l2,int r2) //两个序列合并
void mergesort(int a[], int left ,int rght)
{
   if(left<right){
      int mid = (left + right)/2;
      mergesort(a, left ,mid);
      mergesort(a, mid+1 ,right);
      merge(a, left ,mid+1,right);
}
      

5.快速排序

通过选定一个元素,左右调换位置(先从右边开始一直找到一个小于该元素的一个数,放到该元素的位置,这个元素放到小于该元素的数的位置上面,先从左边开始一直找到一个大于该元素的一个数,放到该元素的位置,这个元素放到大于该元素的数的位置上面,),使得它的左侧元素都不超过它,它右侧元素都不小于它,不断的调整使得每一个元素最终处在自己的位置上。

int partition(int a[], int left, int right)
{
   int temp = a[left];
   while(left < right){
      while(left < right && a[right] > temp) right--;
      a[left] = a[right];
      while(left < right && a[right] <= temp) left++;
      a[right] = a[left];
   }
   a[left] = temp ;
   return left;    //返回这个元素的正确位置
}

void quicksort(int a[], int left, int right){
   if(left < right){
      int pos = partition(a, left, right);
      quicksort(a ,left, pos -1);
      quicksort(a ,pos+1, right);
   }
}

 

PAT乙级完成

终于在今天把PAT乙级的所有题目都写完了,虽然有些题目比较难,需要去查看柳神的代码分析,找出自己的错误,但是总体上来讲难度不是特别的大,但是都需要花时间去弄。里面的内容更多的偏向于STL的运用等,很少涉及到诸如动规、贪心等算法,还需要在去其他的平台上面多练练专项的题目。之后找个时间将PAT的代码发上来参考。

C++ 指针与动态内存分配

动态分配内存

例: int * ptr_int = new int ; 在运行阶段为一个int分配未命名的内存

使用指针来访问这个值

Delete ptr_int;//释放内存(删除数组时要在delete后面加[])

在运行的时候,才给它分配空间

Ps:不要创建两个指向同一内存块的指针,有可能误删两次

 

栈区(stack)

由编译器自动分配释放,一般存放函数参数值、局部变量值

操作方式类似数据结构中的栈

堆区(heap)

程序员自己分配释放,若程序不释放,程序结束可能由操作系统回收

分配方式类似链表

全局区(static)

全局变量和静态变量是存储在一起的

程序结束后由系统释放

文字常量区

存放常量字符串,结束后由系统释放

程序代码区

存放函数体的二进制代码

例:

Int num1 =0;//全局初始化区
Int * ptr1;//全局未初始化区
Int main()
{
	Int num2;//栈区
	Char str[] =”123”;//栈区
	Char * ptr2;//栈区
	Char * ptr3 =”13”;//13在常量区、ptr3在栈区
	Static int num3 =1024;//全局区
	ptr1 = new int[10];
	ptr2 = new char[20];//两者分配的内存在堆区
	return 0;
}

指针用来存放一个内存地址  内存大小4B

定义一个一维数组 数组名为数组的首地址

首地址:一段内存空间中第一个存储单元的地址。最大的存储单元

Int a[5]; a指向a[0],a的类型就是            int*

&a 这个地址指向整个人数组的类型  int(*)[5]

当指针加上*的时候,可以想成读取这个指针所指向的这个地址的值

数组指针  是数组首元素地址的指针,同时也是指向整个数组的指针 &a的

访问数组元素  下标法:a[i]

指针法:*p++

数组名是这个数组的首地址不能够随意改变

二维数组 int a[3][4]={1,2,3,4,5,6,7,8,9,10,11,12};

A是指想a[0]这个一维数组。Int(*)[4]

a[0]指向a[0][0]  a[0]的类型是int*

二维数组表达 a[m][n]

*(a[m]+n)

*(*(a+m)+n)

Int a[3][4]

a      int(*)[4];

&a    int(*)[3][4]

a[0]   int*

a[0][0] int

野指针:不能明确指向的指针变量(危险)

指针变量的运算  更多用于指针偏移,去访问地址旁边的一些内存

指针的加减以指针所指向的类型空间为单位进行偏移

Python入门

由于自己有一点c语言的基础,所以对于pyhton这门有点类似于c的语言来说,有许多相通的地方。

从变量上来讲,python不分什么int、double、char、string,对于c来说简单了许多,不会因为输入错误的格式而导致文件报错。

从赋值的角度来看与c++不一样的地方在于可以几个变量同时赋值不会报错 例如:a,b,c=1,2,3

在c当中每次的结束都需要使用‘;’来进行分隔,在python中只有在for、while、if之后才需要用到‘:’不需要任何的结束符号,但是它对于代码的结构有一定的要求,他需要每个语句都从在正确的位置上面,不允许多一个或者少一个空格

if 可以从(x<y&&y<z)改成(x<y<z)更加的方便
else if改成elif
可以同时判断x<y<z

def: 定义函数 function(a,b)可以在定义函数的时候设置默认参数
当需要在函数中调用全局变量时,首先需要在外面先定义好全局变量 然后在函数内变量前加上global,即可以使用

文件的写入open()

Class  一个大的集合可以理解成类型
在class 中的函数要调用class中的变量时要用self
_Init_ :初始化相当于实例化时定义的参数
可以理解为提前输入想要的属性(默认)

class s:
    def _init_(self,name,age):
       self.name=name
       self.age=age
    def add(self,a,b):
       result=a+b
       return(result)

sample = s('Bob',12)

input 输入(返回的是一个字符串)
int(input())

continue、break的性质和c一样就不多说了

List

  • .index第一次出现该值的索引(索引-1 为最后一位)
  • .append添加
  • .remove除去列表中第一次出现的值
  • .count 元素出现的次数
  • .sort排序(reverse=true 为增序)默认从小到大
  • .reverse 倒序输出

字典{ key:value } ==map  del 删除字典中的元素

Import xx as x 重命名
from xx import  x  从xx中调用某个功能
from x import *为所有功能

Try 有点像ifelse 从而找到错误

Zip 将几个list合并
Lambda 跟简单def相似  减少代码的复杂程度

g = lambda x : x**2
print g(4)

Map根据提供的函数操作对指定的序列使用功能

map(lambda x: x ** 2, [1, 2, 3, 4, 5])

Deepcopy 复制所有的不会处在一个空间 copy第二层在同一个空间

Set() :将列表中重复元素删除

  • .clear()清除所有元素
  • .remove去除某个元素并返回None
  • .discard去除某个元素返回剩余列表
  • .difference 找到两个集合不一样的地方
  • .intersection 交叉的元素

 

第一篇blog

本来,考研结束以后就兴致冲冲的查找资料,然后就搭建了一个基于hexo的静态博客,打算专心写题目弄弄PAT什么的,后来就没有怎么上过博客了。再加上后台管理过于麻烦,界面不会调整,所以这几天抽空弄了下这个blog,以后这就是我的私密空间了,哈哈哈,今天就随随便便发下东西不知道说啥,那就祝自己新年快乐吧!!