数字选择问题

有一组数字,如 “1888”,“245”,“666”,“555”,“444” , 每个数中选取一个数(或跳过),构成一个新数字:其中的每个数都是递增的。

    "1888"   ---》 1"245"    ---》 2"666"    ---》 6"555"    ---》 跳过"444"    ---》 跳过

则形成为新数为126, 这也是能形成的数字个数最多的数。

要求当这组数有N个数据时(上例中有5个数据),每个数据的长度不定(上例中第1个数为4位,其它均为3位),选择规则不变,实现形成的新数字个数最多。

分析

  • 1、此问题是求最优解,因此需要全部遍历可能成的数据,然后找到最长的数。

  • 2、采用回溯算法,类似八皇后问题,可以很直观的解决这个问题。
    假设有n个数,平均长度为m,则空间为O(n*m),时间为(m^n),由于数字仅有0~9,因此在时间上是存在上限的(如果采用递归就是展开的次数)。

  • 3、一些优化点,如数据中去重,或当遇到9后,停止遍历等,可以在实现后在加入。

  • 4、存在更优的算法,通过空间来换取时间。

以下为实现参考

#include <stdio.h>#include <string.h>#include <stdlib.h>#include <sys/time.h>char *num_arry[] =    /* Input Data, Maybe Read from file. */{"1888","245","666","555","444"};int result = 0;        /* Final max Length of NEW Number. */int column = 0;         /*  Data Grops : sizeof(num_arry)/sizeof(char *) */int solution_num = 0;   /* all solution numbers */#define DEBUG 1#ifdef DEBUG#define MAX_NUMBER_GROUP (100)#define MAX_CORE_TIMES (10*10*10*10*10*10*10)int call_core_time = 0;char result_buf_tmp[MAX_NUMBER_GROUP] = {0};  /* Temp buffer to Record process. */char result_buf_max[MAX_NUMBER_GROUP] = {0};  /* Final Result.  */#endifint get_path(char chr, int depth, int hop){int i = 0;#ifdef DEBUGif(call_core_time++ > MAX_CORE_TIMES){printf("[%s][%d]error happen.\n", __FUNCTION__, __LINE__);exit(-1);}#endifif(depth >= column){#ifdef DEBUGresult_buf_tmp[depth] = '\0';printf("Get Hop = %d, path:%s\n", hop, result_buf_tmp);fflush(stdout);#endifsolution_num++;if(result < hop){#ifdef DEBUGstrcpy(result_buf_max, result_buf_tmp);#endifresult = hop;}return;}for(i = 0; i < strlen(num_arry[depth]); i++){if(num_arry[depth][i] > chr){#ifdef DEBUGresult_buf_tmp[depth] = num_arry[depth][i];#endifget_path(num_arry[depth][i], depth + 1, hop + 1);}}/* the last is '\0', just skip it. */#ifdef DEBUGresult_buf_tmp[depth] = '*';#endifget_path(chr, depth + 1, hop);}int main(void){int i = 0;struct timeval t1;struct timeval t2;column = sizeof(num_arry) / sizeof(char *);for(i = 0; i < column; i++){printf("[Input %d] %s:%d\n", i , num_arry[i], strlen(num_arry[i]));}printf("[%s][%d] Start...\n", __FUNCTION__, __LINE__);gettimeofday(&t1, NULL);/* Real work Start... */get_path(0, 0, 0);gettimeofday(&t2, NULL);printf("[%s][%d] End. Result : %d\n", __FUNCTION__, __LINE__, result);printf("Use time : %d ms\n", (t2.tv_sec - t1.tv_sec) * 1000 * 1000 + t2.tv_usec - t1.tv_usec);#ifdef DEBUGprintf("Result call_core_time: %d, all call_core_time:%d\n", solution_num, call_core_time);printf("result number is : %s\n",  result_buf_max);#endifreturn 0;}
上一篇:LeetCode刷题 -- 部分周赛题


下一篇:【图像处理】【Matlab】双边滤波Matlab代码(速度很快)