Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1100800
  • 博文数量: 185
  • 博客积分: 495
  • 博客等级: 下士
  • 技术积分: 1418
  • 用 户 组: 普通用户
  • 注册时间: 2012-09-02 15:12
个人简介

治肾虚不含糖,专注内核性能优化二十年。 https://github.com/KnightKu

文章分类

全部博文(185)

文章存档

2019年(1)

2018年(12)

2017年(5)

2016年(23)

2015年(1)

2014年(22)

2013年(82)

2012年(39)

分类:

2012-12-26 12:57:46

原文地址:DP练习代码 作者:runningdark

1.最长递增子串(codepad.org已验证)
2.最长不连续公共子串(codepad.org已验证)
3.字符串的编辑距离(codepad.org已验证)
4.上下两个等长数组,可互换同下标元素,求上下两数组和可能的最小差值(codepad.org已验证)
5.连续子数组的最大和(codepad.org已验证)
 
代码都为简单实现版,均为递归算法,用作练手和思路记录。
 
1.最长递增子串

点击(此处)折叠或打开

  1. #define MAX 10000
  2. #include
  3. #include
  4. int getMaxIncrease(int * input, int size){
  5.     if(input == NULL) return 0;
  6.     int maxLen = 1;
  7.     int pre[MAX] = {0};
  8.     int cur[MAX] = {0};
  9.     //fill pre
  10.     int i;
  11.     pre[0] = input[0];
  12.     for(i = 1; i<size; i ){
  13.         pre[i] = input[i]<pre[i-1]? input[i] : pre[i-1];
  14.     }
  15.     //fill cur
  16.     int startIndex = 1;
  17.     for(;startIndex< size; startIndex ){
  18.         for(i = 0; i<size; i ){
  19.             if(i<startIndex){
  20.                 cur[i] = 0;
  21.                 continue;
  22.             }
  23.                 
  24.             if(cur[i-1] == 0 ){
  25.                 if(input[i]>pre[i-1] && pre[i-1]!=0)
  26.                     cur[i] = input[i];
  27.                 else
  28.                     cur[i] = 0;
  29.             }
  30.             else{
  31.                 cur[i] = cur[i-1];
  32.                 if(input[i]< cur[i] && input[i]>pre[i-1])
  33.                     cur[i] = input[i];
  34.             }
  35.         }
  36.         memcpy(pre,cur, sizeof(int)*MAX);
  37.         cur[size-1]!=0? maxLen : 1;
  38.     }
  39.         return maxLen;
  40. }
  41. int main(){
  42.     int input[] = {1,3,2,3,5,6};
  43.     printf("maxLen = %d \n", getMaxIncrease(input,sizeof(input)/sizeof(int)));
  44. }

2.最长不连续公共子串

点击(此处)折叠或打开

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. int LCS(const char* src, const char* dest, int sIndex, int dIndex){
  5.         if(src == NULL || dest == NULL) return -1;
  6.     if(sIndex <0 || dIndex<0)
  7.         return 0;
  8.     int equal, backsrc, backdest;
  9.     equal = backsrc = backdest = 0;
  10.     if( *(src sIndex) == *(dest dIndex)){
  11.           equal = LCS(src, dest, sIndex-1, dIndex-1) 1;
  12.     }
  13.     backsrc = LCS(src, dest, sIndex-1, dIndex);
  14.     backdest = LCS(src, dest, sIndex, dIndex-1);
  15.     int max = equal;
  16.     max = max>backsrc ? max : backsrc;
  17.     max = max>backdest ? max : backdest;
  18.     return max;
  19. }
  20. int main(){
  21.     char* src = "aabbcc";
  22.     char* dest = "abc";
  23.     printf("%d", LCS(src, dest, strlen(src) -1 ,strlen(dest) -1));
  24. }

3.字符串的距离
precondition: strlen(src)>= strlen(dest);

点击(此处)折叠或打开

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>


  4. int getDis(const char* src, const char* dest){
  5.         printf("src = %s dest = %s \n", src, dest);
  6.     if(src == NULL || dest == NULL) return -1;
  7.         if(!*dest || !*src){
  8.         return strlen(src) + strlen(dest);
  9.         }    
  10.     if(*src == *dest){
  11.         src++;
  12.         dest++;
  13.         return getDis(src,dest);
  14.     }
  15.     if(*src== *(dest+1)){
  16.                 dest++;
  17.                 src++;
  18.         return getDis(src,dest) + 1;
  19.     }
  20.         if(*(src+1)== *dest){
  21.                 src++;
  22.         return getDis(src,dest) + 1;
  23.     }

  24.     src++;
  25.         return getDis(src,dest)+1;
  26. }
  27. int main(){
  28.     char* src = "aabbcc";
  29.     char* dest = "abc";
  30.     printf("%d \n", getDis(src, dest));
  31.     printf("%d \n", getDis(src, "ec"));
  32.     printf("%d \n", getDis(src, "ac"));
  33.     printf("%d \n", getDis(src, "acce"));

  34. }
4.交换元素求最小差值

点击(此处)折叠或打开

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #define MAX 10000

  5. int getMin(int sum, int *up, int *down, int size){
  6.     int min = sum;
  7.     int record[MAX] = {sum};
  8.     int i = 0;
  9.     int count = 1;
  10.     for(;i<size;i++){
  11.         int tmpcount = count;
  12.         int c = 0;
  13.         for(;c<tmpcount ;c++){
  14.                         count++;
  15.             record[count] = record[c] - 2*(up[i]-down[i]);
  16.             //printf("-----------%d\n", record[count]);
  17.             int tsum = record[count];
  18.             if(tsum<0) tsum*=-1;
  19.             min = min>tsum?tsum:min;
  20.                         if(min == 0) return min;
  21.         }
  22.     }    
  23.     return min;
  24. }
  25. int main(){
  26.     int up[] = {1,4,5,3};
  27.     int down[] = {3,2,2,0};
  28.     int i = 0;
  29.     int sum = 0;
  30.     for(;i<sizeof(up)/sizeof(int);i++){
  31.         sum+=(up[i]-down[i]);
  32.     }
  33.     printf("%d \n", getMin(sum,up,down, sizeof(up)/sizeof(int)));

  34. }

5.连续子数组最大和

点击(此处)折叠或打开

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <memory.h>

  4. #define MAX 10000
  5. int getMaxSum(int *input, int size){
  6.     if(input == NULL) return -1;
  7.     int maxsum = -MAX;
  8.     int pre[MAX] = {0};
  9.     int cur[MAX] = {0};
  10.     int i;
  11.     for(i=0;i<size;i++)
  12.         pre[i] = input[i];
  13.     int end = 1;
  14.     for(;end<size;end++){
  15.         for(i = 0; i<size; i++){
  16.             if(i<end) cur[i] = -1*MAX;
  17.             else{
  18.                 cur[i] = input[i] + pre[i-1];
  19.             }
  20.             maxsum = maxsum>cur[i]?maxsum:cur[i];
  21.         
  22.         }
  23.         memcpy(pre, cur, sizeof(int)*MAX);
  24.     }
  25.     return maxsum;
  26. }

  27. int main(){
  28.     int input[] = {4,-3,10,4,-4,5};
  29.     printf("%d \n", getMaxSum(input,sizeof(input)/sizeof(int)));
  30. }

阅读(1131) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~