快捷搜索:

任意一串字符串 字符串里包含数字部分和一般的

来源:http://www.fab119.com 作者:关于我们 人气:83 发布时间:2020-01-05
摘要:#includeiostream using namespace std; int *arr; int n; void print() {     cout n " =" arr[0];     int i = 1;     while(arr[i])         cout " +" arr[i++];     cout endl; } 顺序容器: 任意一串字符串 字符串

#include<iostream>
using namespace std;
int *arr;
int n;
void print()
{
    cout << n << " = " << arr[0];
    int i = 1;
    while(arr[i])
        cout << " + " << arr[i++];
    cout << endl;
}

顺序容器:

任意一串字符串 字符串里包含数字部分和一般的字符

1、快速找出一个数组中的最大数、第二大数。     思路:如果当前元素大于最大数 max,则让第二大数等于原来的最大数 max,再把当前元素的值赋给 max。如果当前的元素大于等于第二大数secondMax的值而小于最大数max的值,则要把当前元素的值赋给 secondMax。

void process(int arr[], int max, int n)//n为剩余值,max为当前位置可以为最大的数。
{
    arr[0] = max < n ? max : n;
    if(n == 0)
    {
        print();
    }
    for(arr[0]; arr[0]>0; --arr[0])
        process(arr+1, arr[0], n-arr[0]);
    arr[0] = 0;
}
int main()
{
    cout << "Please input a integer:";
    cin >> n;
    arr = new int[n+1];//多出来一个当哨兵
    if(arr)
    {
        for (int i = 0; i != n; ++i)
            arr[i] = 0;

将单一类型元素聚集起来成为容器,然后根据位置来存储和访问这些元素,这就是顺序容器。

例如 ad2ef35adx1wewe76
注意这个字符串 里面有4个数字 分别是 1 2 35 76 不考虑大数

[cpp] view plaincopyprint?

        process(arr, n, n);

顺序容器的元素排列与元素值无关,而是由元素添加到容器里的次序决定。

将数字按照从小到大排序 组成一个新的字符串

  1. void GetSecondMaxNumber(int *arr , int n)  
  2. {  
  3.     int i , max , second_max;  
  4.     max = arr[0];  
  5.     second_max = 0x80000000;  
  6.     for(i = 1 ; i < n ; ++i)  
  7.     {  
  8.         if(arr[i] > max)  
  9.         {  
  10.             second_max = max;  
  11.             max = arr[i];  
  12.         }  
  13.         else  
  14.         {  
  15.             if(arr[i] > second_max)  
  16.                 second_max = arr[i];  
  17.         }  
  18.     }  
  19.     cout<<max<<"  "<<second_max<<endl;  
  20. }  

        delete [] arr;
    }
    else
    {
        cerr << "memory alloc error" << endl;//英语很烂
    }
    return 0;
}

标准库中定义了三种顺序容器类型:vector、list和deque(double-ended queue,双端队列),它们的差别在于访问元素的方式,以及添加或删除元素相关操作的运行代价。

要求制作一个函数来进行处理

2、试着用最小的比较次数去寻找数组中的最大值和最小值。

容器只定义了少量操作,大多数额外操作都是由算法库提供。

假设是 fun(char*src,char*des)
  {
  }

 

解法一:
扫描一次数组找出最大值;再扫描一次数组找出最小值。
比较次数2N-2
转载请标明出处,原文地址:
解法二:
将数组中相邻的两个数分在一组, 每次比较两个相邻的数,将较大值交换至这两个数的左边,较小值放于右边。
对大者组扫描一次找出最大值,对小者组扫描一次找出最小值。
比较1.5N-2次,但需要改变数组结构
 
解法三:
每次比较相邻两个数,较大者与MAX比较,较小者与MIN比较,找出最大值和最小值。
方法如下:先将一对元素互相进行比较,然后把最小值跟当前最小值进行比较,把最大值跟当前最大值进行比较。因此每两个元素需要3次比较。如果n为奇数,那么比较的次数是3*(n/2)次比较。如果n为偶数,那么比较的次数是3n/2-2次比较。因此,不管是n是奇数还是偶数,比较的次数至多是3*(n/2),具体的代码如下:

[cpp] view plaincopyprint?

  1. void GetMaxAndMin(int *arr , int n , int &max , int &min)  
  2. {  
  3.     int i = 0 ;  
  4.     if(n & 1)     // 奇数   
  5.     {  
  6.         max = min = arr[i++];  
  7.     }  
  8.     else  
  9.     {  
  10.         if(arr[0] > arr[1])  
  11.         {  
  12.             max = arr[0];  
  13.             min = arr[1];  
  14.         }  
  15.         else  
  16.         {  
  17.             max = arr[1];  
  18.             min = arr[0];  
  19.         }  
  20.         i += 2;  
  21.     }  
  22.       
  23.     for( ; i < n ; i += 2)  
  24.     {  
  25.         if(arr[i] > arr[i+1])  
  26.         {  
  27.             if(arr[i] > max)  
  28.                 max = arr[i];  
  29.             if(arr[i+1] < min)  
  30.                 min = arr[i+1];  
  31.         }  
  32.         else  
  33.         {  
  34.             if(arr[i+1] > max)  
  35.                 max = arr[i+1];  
  36.             if(arr[i] < min)  
  37.                 min = arr[i];  
  38.         }  
  39.     }  
  40. }   

vector容器:

src 输入字符串 ad2ef35adx1wewe76

3、重排问题

给定含有n个元素的整型数组a,其中包括0元素和非0元素,对数组进行排序,要求:
1、排序后所有0元素在前,所有非零元素在后,且非零元素排序前后相对位置不变
2、不能使用额外存储空间
例子如下
输入 0、3、0、2、1、0、0
输出 0、0、0、0、3、2、1
分析
此排序非传统意义上的排序,因为它要求排序前后非0元素的相对位置不变,或许叫做整理会更恰当一些。我们可以从后向前遍历整个数组,遇到某个位置i上的元素是非0元素时,如果arr[k]为0,则将arr[i]赋值给arr[k],arr[i]赋值为0。实际上i是非0元素的下标,而k是0元素的下标。

[cpp] view plaincopyprint?

  1. void Arrange(int *arr , int n)  
  2. {  
  3.     int i , k = n-1;  
  4.     for(i = n-1 ; i >=0 ; --i)  
  5.     {  
  6.         if(arr[i] != 0)  
  7.         {  
  8.             if(arr[k] == 0)  
  9.             {  
  10.                 arr[k] = arr[i];  
  11.                 arr[i] = 0;  
  12.             }  
  13.             --k;  
  14.         }  
  15.     }  
  16. }  

4、找出绝对值最小的元素

给定一个有序整数序列(非递减序),可能包含负数,找出其中绝对值最小的元素,比如给定序列 -5、-3、-1、2、8 则返回1。
分析:由于给定序列是有序的,而这又是搜索问题,所以首先想到二分搜索法,只不过这个二分法比普通的二分法稍微麻烦点,可以分为下面几种情况
    如果给定的序列中所有的数都是正数,那么数组的第一个元素即是结果。
    如果给定的序列中所有的数都是负数,那么数组的最后一个元素即是结果。
    如果给定的序列中既有正数又有负数,那么绝对值的最小值一定出现在正数和负数的分界处。
为什么?因为对于负数序列来说,右侧的数字比左侧的数字绝对值小,如上面的-5、-3、-1,而对于整整数来说,左边的数字绝对值小,比如上面的2、8,将这个思想用于二分搜索,可先判断中间元素和两侧元素的符号,然后根据符号决定搜索区间,逐步缩小搜索区间,直到只剩下两个元素。
单独设置一个函数用来判断两个整数的符号是否相同

[cpp] view plaincopyprint?

  1. bool SameSign(int m , int n)  
  2. {  
  3.     if((m>>31) == (n>>31))  
  4.         return true;  
  5.     else  
  6.         return false;  
  7. }  
  8.   
  9. // 找出一个非递减序整数序列中绝对值最小的数   
  10. int MiniNumAbsoluteValue(int *arr , int n)  
  11. {  
  12.     if(n == 1)  
  13.         return arr[0];  
  14.     if( SameSign(arr[0] , arr[n-1]) )  
  15.         return arr[0] >= 0 ? arr[0] : abs(arr[n-1]);  
  16.   
  17.     // 二分搜索   
  18.     int mid , low = 0 , high = n - 1;  
  19.     while(low < high)  
  20.     {  
  21.         if(low + 1 == high)  
  22.             return abs(arr[low]) < abs(arr[high]) ? abs(arr[low]) : abs(arr[high]);  
  23.         mid = (low + high)>>1;  
  24.         if( SameSign(arr[low] , arr[mid]) )  
  25.         {  
  26.             low = mid ;     // 有可能分界点就在mid处   
  27.             continue;  
  28.         }  
  29.         if( SameSign(arr[high] , arr[mid]) )  
  30.         {  
  31.             high = mid;  
  32.             continue;  
  33.         }  
  34.     }  
  35.     return abs(arr[low]);  
  36. }  

5、一道经典的额递归题目
函数 int func(int i ,int N);
其中i <= N,功能输出i递增到N再递减到i的整数,每行输出一个数。比如func(1,5)就是
1
2
3
4
5
4
3
2
1
要求:
1、只能有1个语句,即一个分号
2、不能使用do while until goto for if关键字,不能使用?:和逗号运算符
3、唯一能使用的库函数为printf

int func(int i , int n)
{
    return (i==n && printf("%dn",i)) || (printf("%dn",i) && func(i+1,n) && printf("%dn",i));
}

6、从长度为n的数组(元素互不相同)中任意选择m个数的所有组合。
DFS

[cpp] view plaincopyprint?

  1. /**   
  2. ** author :hackbuteer 
  3. ** date   :2012-10-01    
  4. **/  
  5. #include<iostream>   
  6. #include<vector>   
  7. using namespace std;  
  8.   
  9. int arr[] = {1,2,3,4,5,6,7,8,9,10};  
  10. int len = 10 , m = 3;  
  11.   
  12. void dfs(int num , vector<int>& vec , int curnum , int id)  
  13. {  
  14.     int i ;  
  15.     if(curnum == num)  
  16.     {  
  17.         static int k = 1 ;  
  18.         cout<<k++<<": ";  
  19.         for( i = 0; i < vec.size() ; ++i)  
  20.             cout<<vec[i]<<" ";  
  21.         cout<<endl;  
  22.         return;  
  23.     }  
  24.   
  25.     for( i = id; i < len; ++i)  
  26.     {  
  27.         vec.push_back(arr[i]);  
  28.         dfs(num , vec , curnum + 1 , i + 1);  
  29.         vec.pop_back();  
  30.     }  
  31. }  
  32.   
  33. int main(void)  
  34. {  
  35.     vector<int>vec;  
  36.     dfs(m , vec , 0 , 0);  
  37.     return 0;  
  38. }  

[cpp] view plaincopyprint?

  1. int arr[] = {1,2,3,4,5,8,5,8,9,10};  
  2. int len = 10 , m = 3;  
  3.   
  4. void dfs(int index , int num , vector<int> &vec)  
  5. {  
  6.     int i ;  
  7.     if(index == len+1)  
  8.         return ;  
  9.     if(num == 0)  
  10.     {  
  11.         static int k = 1 ;  
  12.         cout<<k++<<": ";  
  13.         for( i = 0; i < vec.size() ; ++i)  
  14.             cout<<vec[i]<<" ";  
  15.         cout<<endl;  
  16.         return;  
  17.     }  
  18.     vec.push_back(arr[index]);    // 选取第index个元素   
  19.     dfs(index + 1 , num - 1 , vec);  
  20.     vec.pop_back();               // 不选取第index个元素   
  21.     dfs(index + 1 , num , vec);  
  22. }  
  23.   
  24. int main(void)  
  25. {  
  26.     vector<int>vec;  
  27.     dfs(0 , m , vec);  
  28.     return 0;  
  29. }  

7、从长度为n的数组(元素有可能相同)中任意选择m个数的所有组合。
先对数组进行排序,然后设置一个标记pre,记录前一个选择的数字,然后进行比较。

[cpp] view plaincopyprint?

  1. /**   
  2. ** author :hackbuteer 
  3. ** date   :2012-10-01    
  4. **/  
  5. #include<iostream>   
  6. #include<vector>   
  7. #include<algorithm>   
  8. using namespace std;  
  9.   
  10. int arr[] = {1,2,3,4,5,8,5,8,9,10};  
  11. int len = 10 , m = 3;  
  12.   
  13. void dfs(int num , vector<int>& vec , int curnum , int id)  
  14. {  
  15.     int i , pre = -1;  
  16.     if(curnum == num)  
  17.     {  
  18.         static int k = 1 ;  
  19.         cout<<k++<<": ";  
  20.         for( i = 0; i < vec.size() ; ++i)  
  21.             cout<<vec[i]<<" ";  
  22.         cout<<endl;  
  23.         return;  
  24.     }  
  25.   
  26.     for( i = id; i < len; ++i)  
  27.     {  
  28.         if(pre == -1 || arr[i] > pre)  
  29.         {  
  30.             vec.push_back(arr[i]);  
  31.             dfs(num , vec , curnum + 1 , i + 1);  
  32.             vec.pop_back();  
  33.             pre = arr[i];  
  34.         }  
  35.     }  
  36. }  
  37.   
  38. int main(void)  
  39. {  
  40.     vector<int>vec;  
  41.     sort(arr , arr + len );  
  42.     dfs(m , vec , 0 , 0);  
  43.     return 0;  
  44. }  

8、三色旗排序问题
一个字符串Color,其中每个元素值为‘R‘’G’‘B’三者之一,实现把数组中元素重新排列为红、绿、蓝的顺序,所有红色在前,绿色其后,蓝色最后,要如何移动次数才会最少,编写这么一个程序。
问题的解法很简单,您可以自己想像一下在移动旗子,从绳子开头进行,遇到红色往前移,遇到绿色留在中间,遇到蓝色往后移。
设有三个指针rindex、gindex、bindex,其中gindex来遍历这个数组序列
1、gindex指向G的时候,gindex++,
2、gindex指向R的时候,与rindex交换,而后gindex++,rindex++,
3、gindex指向B的时候,与bindex交换,而后,gindex不动,bindex--。
    为什么,第三步,gindex指向B的时候,与bindex交换之后,gindex不动。
    因为你最终的目的是为了让R、G、B成为有序排列,试想,如果第三步,gindex与bindex交换之前,万一bindex指向的是R,而gindex交换之后,gindex此刻指向的是R了,此时,gindex能动么?不能动啊,指向的是R,还得与rindex交换。

[cpp] view plaincopyprint?

  1. // 三色旗排序问题   
  2. // char str[] = "RGRBRB";   
  3. void mysort(char *str , int n)  
  4. {  
  5.     int rindex = 0 , gindex = 0 , bindex = n - 1 ;  
  6.     while(gindex <= bindex)  
  7.     {  
  8.         if(str[gindex] == 'G')  
  9.             ++gindex;  
  10.         else if(str[gindex] == 'R')  
  11.         {  
  12.             swap(str[gindex] , str[rindex]);  
  13.             ++rindex , ++gindex;  
  14.         }  
  15.         else           // str[gindex] == 'B'   
  16.         {  
  17.             swap(str[gindex] , str[bindex]);  
  18.             --bindex;  
  19.             //++gindex;   
  20.         }  
  21.     }  
  22. }  

9、一个整型数组,含有N个数,将这N个数分成连续的M段,使得这M段每段的和中的最大值最小,输出最小值。(1<=N<=100000,1<=M<=N,每个数在1到10000之间)   POJ  3273
解题思路:不管分成多少段,每种分法和的最大值都在N个数的最大值和N个数的和之间,所求答案也在这之间。

我们可以以此为上下界,二分M段和的最大值进行尝试。对每次二分的值,将数组扫描累加。若当前和大于二分的这个值,则段数加一,由此统计出在当前值下,N个数能够分成的最小段数。若这个段数小于或等于M,则上界变为mid-1,并记下当前mid的值。否则,下界变为mid+1。继续二分,直到退出循环。最后记录的low值即为答案。

[cpp] view plaincopyprint?

  1. #include<iostream>   
  2. #include<cstdio>   
  3. using namespace std;  
  4.   
  5. int m , n , a[100001];  
  6.   
  7. int bsearch(int low , int high)  
  8. {  
  9.     int i , mid , group , sum;  
  10.     while(low <= high)  
  11.     {  
  12.         mid = (low + high)>>1;  
  13.         sum = 0 ,  group = 1;  
  14.         for(i = 0 ; i < n ; ++i)  
  15.         {  
  16.             if(sum + a[i] <= mid)  
  17.                 sum += a[i];  
  18.             else  
  19.             {  
  20.                 group++;  
  21.                 sum = a[i];  
  22.             }  
  23.         }  
  24.         if(group <= m)  
  25.             high = mid - 1 ;  
  26.         else if(group > m)  
  27.             low = mid + 1;  
  28.     }  
  29.     return low;  
  30. }  
  31.   
  32. int main(void)  
  33. {  
  34.     int i , max , sum;  
  35.     while(scanf("%d %d",&n,&m)!=EOF)  
  36.     {  
  37.         max = 0x80000000 , sum = 0;  
  38.         for(i = 0 ; i < n ; ++i)  
  39.         {  
  40.             scanf("%d",&a[i]);  
  41.             sum += a[i];  
  42.             if(a[i] > max)  
  43.                 max = a[i];  
  44.         }  
  45.         printf("%dn",bsearch(max, sum));  
  46.     }  
  47.     return 0;  
  48. }  

10、一个int数组,里面数据无任何限制,要求求出所有这样的数a[i],其左边的数都小于等于它,右边的数都大于等于它。
能否只用一个额外数组和少量其它空间实现。
分析:最原始的方法是检查每一个数 array[i] ,看是否左边的数都小于等于它,右边的数都大于等于它。这样做的话,要找出所有这样的数,时间复杂度为O(N^2)。
其实可以有更简单的方法,我们使用额外数组,比如rightMin[],来帮我们记录原始数组array[i]右边(包括自己)的最小值。假如原始数组为: array[] = {7, 10, 2, 6, 19, 22, 32}, 那么rightMin[] = {2, 2, 2, 6, 19, 22, 32}. 也就是说,7右边的最小值为2, 2右边的最小值也是2。
有了这样一个额外数组,当我们从头开始遍历原始数组时,我们保存一个当前最大值 max, 如果当前最大值刚好等于rightMin[i], 那么这个最大值一定满足条件,还是刚才的例子。
第一个值是7,最大值也是7,因为7 不等于 2, 继续,
第二个值是10,最大值变成了10,但是10也不等于2,继续,
第三个值是2,最大值是10,但是10也不等于2,继续,
第四个值是6,最大值是10,但是10不等于6,继续,
第五个值是19,最大值变成了19,而且19也等于当前rightMin[4] = 19, 所以,满足条件。如此继续下去,后面的几个都满足。

[cpp] view plaincopyprint?

  1. int arr[100] , rightMin[100];  
  2. void smallLarge(int *arr , int *rightMin , int n)  
  3. {  
  4.     int i , leftMax;  
  5.     rightMin[n - 1] = arr[n - 1];  
  6.     for(i = n - 2 ; i >= 0 ; --i)  
  7.     {  
  8.         if(arr[i] < arr[i+1])  
  9.             rightMin[i] = arr[i];  
  10.         else  
  11.             rightMin[i] = rightMin[i + 1];  
  12.     }  
  13.     leftMax = 0x80000000;  
  14.     for(i = 0 ; i < n ; ++i)  
  15.     {  
  16.         if(arr[i] >= leftMax)  
  17.         {  
  18.             leftMax = arr[i];  
  19.             if(leftMax == rightMin[i])  
  20.                 printf("%dn",leftMax);  
  21.         }  
  22.     }  
  23. }  

 11、整数的拆分问题
如,对于正整数n=6,可以拆分为:
6
5+1
4+2, 4+1+1
3+3, 3+2+1, 3+1+1+1
2+2+2, 2+2+1+1, 2+1+1+1+1
1+1+1+1+1+1+1
现在的问题是,对于给定的正整数n,程序输出该整数的拆分种类数(HDOJ  1028)。
DP思路:
n = n1 + n2 + n3 + n4 + .... + nk
状态表示:将n划分为k个数相加的组合方案数记为 q(n,k)。(相当于将n个苹果放入k个盘子)
状态转移:
(1)若k>n,则盘子数大于苹果数,至少有k-n个空盘子,可以将其拿掉,对组合方案数无影响。
q(n,k) = q(n,n)
(2)若k<=n,则盘子数小于等于苹果数,则分为两种情况
1.至少有一个盘子空着:q(n,k) = q(n,k-1)
2.所有盘子都不空:q(n,k) = q(n-k,k)
q(n,k) = q(n,k-1) + q(n-k,k)
方法一:DP非递归

[cpp] view plaincopyprint?

  1. int main(void)  
  2. {  
  3.     int n,i,j,dp[121][121];  
  4.     for(i = 1 ; i < 121 ; ++i)  
  5.     {  
  6.         for(j = 1 ; j < 121 ; ++j)  
  7.         {  
  8.             if(i == 1 ||  j == 1)  
  9.                 dp[i][j] = 1;  
  10.             else if(i > j)  
  11.                 dp[i][j] = dp[i][j-1] + dp[i-j][j];  
  12.             else if(i == j)  
  13.                 dp[i][j] = dp[i][j-1] + 1;  
  14.             else  
  15.                 dp[i][j] = dp[i][i];  
  16.         }  
  17.     }  
  18.   
  19.     while(scanf("%d",&n)!=EOF)  
  20.     {  
  21.         cout<<dp[n][n]<<endl;  
  22.     }  
  23.     return 0;  
  24. }  

方法二:递归思路

[cpp] view plaincopyprint?

  1. int q(int n , int m)  
  2. {  
  3.     if(n < 1 || m < 1)  
  4.         return 0;  
  5.     if(n == 1 || m == 1)  
  6.         return 1;  
  7.     if(n < m)  
  8.         return q(n , n);  
  9.     if(n == m)  
  10.         return q(n , m - 1) + 1;  
  11.     return q(n , m - 1) + q(n - m , m);  
  12. }  
  13.   
  14. int main(void)  
  15. {  
  16.     int n;  
  17.     while(scanf("%d",&n)!=EOF)  
  18.     {  
  19.         cout<<q(n,n)<<endl;  
  20.     }  
  21.     return 0;  
  22. }  

12、整数的拆分问题
接着上一题,输出整数的所有划分方案

[cpp] view plaincopyprint?

  1. void dfs(int sum , vector<int>& vec , int curnum , int id)  
  2. {  
  3.     int i;  
  4.     if(curnum == sum)  
  5.     {  
  6.         static int inum = 1 ;  
  7.         cout<<"方案 "<<inum++<<": ";  
  8.         for(i = 0; i < vec.size() ; ++i)  
  9.             cout<<vec[i]<<" ";  
  10.         cout<<endl;  
  11.         return;  
  12.     }  
  13.   
  14.     for(i = id ; i <= sum; ++i)  
  15.     {  
  16.         if(curnum + i <= sum)  
  17.         {  
  18.             vec.push_back(i);  
  19.             dfs(sum , vec , curnum + i , i);  
  20.             vec.pop_back();  
  21.         }  
  22.         else  
  23.             break;  
  24.     }  
  25. }  
  26.   
  27. void main()  
  28. {  
  29.     vector<int> vec;  
  30.     dfs(10 , vec , 0 , 1);  
  31. }  

13、在数组中寻找和为给定值的组合
思路:
代码
14、字符串移动
字符串为*号和26个字母、阿拉伯数字的任意组合,把*号都移动到最左侧,把其他字母和数字都移到最右侧并保持相对顺序不变,返回字符*的个数,要求时间和空间复杂度最小。
第一种方法:跟上面的重排问题是一样的

[cpp] view plaincopyprint?

  1. int MoveStar(char *str , int n)  
  2. {  
  3.     int i , j = n-1;  
  4.     for(i = n - 1 ; i >= 0 ; --i)  
  5.     {  
  6.         if(str[i] != '*')  
  7.         {  
  8.             if(str[j] == '*')  
  9.             {  
  10.                 str[j] = str[i];  
  11.                 str[i] = '*';  
  12.             }  
  13.             --j;  
  14.         }  
  15.     }  
  16.     return j+1;  
  17. }  

第二种方法:

[cpp] view plaincopyprint?

  1. int MoveStar(char *str , int n)  
  2. {  
  3.     int i , count = 0;  
  4.     for(i = n - 1 ; i >= 0 ; --i)  
  5.     {  
  6.         if(str[i] == '*')  
  7.             ++count;  
  8.         else if(count > 0)    // str[i] != '*'   
  9.             str[i + count] = str[i];  
  10.     }  
  11.     for(i = 0 ; i < count ; ++i)  
  12.         str[i] = '*';  
  13.     return count;  
  14. }  

时间复杂度O(N),空间复杂度O(1)
15、求数组中两个元素差的最大值
后面的元素减去前面的元素(你可以认为你在炒股票,买入价格和卖出价格就是你的盈利),要求:O(N)时间复杂度,O(1)空间复杂度
思路:首先从包含两个元素的数组开始考虑问题,当这个包含两个元素的问题解决了,那么加一个新的元素会造成什么影响?要改变哪些值?每次都添加一个元素,每次都将这些可能的改变考虑进来,这样就能做到遍历整个数组的时候,问题就解决了。

[cpp] view plaincopyprint?

  1. // 后面的元素减去前面的元素 差的最大值   
  2. int max_difference(int *arr , int n)  
  3. {  
  4.     if(arr == NULL || n < 2)    // 非法输入   
  5.         return 0;  
  6.     int min = arr[0];  
  7.     int maxDiff = arr[1] - arr[0];  
  8.     for(int i = 2 ; i < n ; ++i)  
  9.     {  
  10.         if(arr[i-1] < min)  
  11.             min = arr[i-1];  
  12.         if(arr[i] - min > maxDiff)  
  13.             maxDiff = arr[i] - min;  
  14.     }  
  15.     return maxDiff;  
  16. }  

16、求数组中两个元素差的最大值
前面的元素减去后面的元素,要求:O(N)时间复杂度,O(1)空间复杂度
思路:跟上一题的思路很相近

[cpp] view plaincopyprint?

  1. // 前面的元素减去后面的元素 差的最大值   
  2. int max_difference(int *arr , int n)  
  3. {  
  4.     if(arr == NULL || n < 2)    // 非法输入   
  5.         return 0;  
  6.     int max = arr[0];  
  7.     int maxDiff = arr[0] - arr[1];  
  8.     for(int i = 2 ; i < n ; ++i)  
  9.     {  
  10.         if(arr[i-1] > max)  
  11.             max = arr[i-1];  
  12.         if(max - arr[i] > maxDiff)  
  13.             maxDiff = max - arr[i];  
  14.     }  
  15.     return maxDiff;  
  16. }  

17、输入一个正数 n,输出所有和为 n 连续正数序列。 
例如输入 15,由于 1+2+3+4+5=4+5+6=7+8=15,所以输出 3 个连续序列 1-5、4-6 和 7-8。 
方法一:
可以发现任意自然数序列其实是公差为1的等差数列,假设从i开始的连续k个数的和为n,即[i , i+k-1],则n=k*(2*i+k-1)/2,所以转化为一元二次方程为:k*k+(2*i-1)*k-2*n=0,解得k=(1-2*i+sqrt((2*i-1)*(2*i-1)+8*n))/2
要满足k为整数,根号里面的肯定必须是平方数,且分子为偶数,否则k就是小数。

[cpp] view plaincopyprint?

  1. //转载请标明出处,原文地址:   
  2. //输入一个正数 n,输出所有和为n 连续正数序列。   
  3. void plusSequence(int n)  
  4. {  
  5.     int i , j , k , m;  
  6.     double num;  
  7.     for(i = 1 ; i <= n/2 ; ++i)  
  8.     {  
  9.         m = (2*i-1)*(2*i-1) + 8*n;  
  10.         num = sqrt(m * 1.0);  
  11.         if(num != (int)num)  
  12.             continue;  
  13.         k = 1 - 2*i + (int)num;  
  14.         if(0 == (k&1) && k > 0)  
  15.         {  
  16.             for(j = 0 ; j < k/2 ; ++j)  
  17.                 printf("%d",i + j);  
  18.             printf("n");  
  19.         }  
  20.     }  
  21. }  

方法二:
我们知道:
1+2 = 3;
4+5 = 9;
2+3+4 = 9。
等式的左边都是两个以上连续的自然数相加,那么是不是所有的整数都可以写成这样的形式呢?稍微考虑一下,我们发现,4和8等数不能写成这样的形式。
问题1:写一个程序,对于一个64位的正整数,输出它所有可能的连续自然数(两个以上)之和的算式。
问题2:大家在测试上面的程序的过程中,肯定会注意到有一些数字不能表达为一系列连续的自然数之和,例如32好像就找不到。那么,这样的数字有什么规律呢?能否证明你的结论?
问题3:在64位正整数范围内,子序列数目最多的数是哪一个?这个问题要用程序蛮力搜索,恐怕要运行很长时间,能够用数学知识推导出来?
问题1解答:对于任意的正整数n >= 3(1和2均不能写成连续的自然数序列之和)。假设n能够写成自然数序列[seqStart, seqEnd]之和,则有(seqEnd + seqStart)*(seqEnd - seqStart + 1) = 2*n。考虑左式是两个整数之积,想到对右边的2*n进行因数分解,不妨假定2*n = minFactor * maxFactor,则有
seqEnd + seqStart = maxFactor           (1)
seqEnd - seqStart = minFactor-1         (2)
解方程组(1)(2)得:
seqStart = (maxFactor - minFactor + 1) / 2
seqEnd = (maxFactor + minFactor - 1) / 2
因为maxFactor - minFactor与maxFactor + minFactor有相同的奇偶性,因此只需要判断maxFactor + minFactor的奇偶性即可,如果maxFactor + minFactor为奇数,那么seqStart和seqEnd不是分数,是整数,即这个序列存在。下面是代码:

[cpp] view plaincopyprint?

  1. //转载请标明出处,原文地址:   
  2. //输入一个正数 n,输出所有和为n 连续正数序列。   
  3. void plusSequence(int n)  
  4. {  
  5.     int i , minFactor , maxFactor , start , end;  
  6.     int sqrtn = sqrt(2.0*n);  
  7.   
  8.     for(i = 2 ; i <= sqrtn ; ++i)  
  9.     {  
  10.         if(2*n % i == 0)  
  11.         {  
  12.             minFactor = i;  
  13.             maxFactor = 2*n/i;  
  14.             if(((minFactor + maxFactor)&1) == 1)     //奇数   
  15.             {  
  16.                 start = (maxFactor - minFactor + 1)>>1;  
  17.                 end = (maxFactor + minFactor - 1)>>1;  
  18.                 printf("%d %d",start,end);  
  19.                 printf("n");  
  20.             }  
  21.         }  
  22.     }  
  23. }  

转:

vector是顺序容器,是STL中最为常用的容器。它的容器以连续的方式存放。熟练掌握vector的使用是进入STL库学习的第一道门槛。

des 输出字符串 1-2-35-76

下面通过讲例子的方式慢慢深入vector容器的学习。

view plaincopy to clipboardprint?void Convert(const char *str) 

    int res = 0; 
    vector<int> vec; 
    while (*str != '') 
    { 
        if (isdigit(*str)) 
        { 
            while (isdigit(*str)) 
            { 
                res = res * 10 + (*str - '0'); 
                str++; 
            } 
 
            vec.push_back(res); 
        } 
        else 
        { 
            res = 0; 
            str++; 
        } 
    } 
 
    sort(vec.begin(), vec.end()); 
 
    copy(vec.begin(), vec.end(), ostream_iterator<int>(cout, "-")); 
    cout<<endl; 

void Convert(const char *str)
{
 int res = 0;
 vector<int> vec;
 while (*str != '')
 {
  if (isdigit(*str))
  {
   while (isdigit(*str))
   {
    res = res * 10 + (*str - '0');
    str++;
   }

知识点预览:

   vec.push_back(res);
  }
  else
  {
   res = 0;
   str++;
  }
 }

vector<int> v;//定义一个空容器

 sort(vec.begin(), vec.end());

vector<int> v1(v);//将v通过构造函数拷贝给v1

 copy(vec.begin(), vec.end(), ostream_iterator<int>(cout, "-"));
 cout<<endl;
}

v.empty();//容器是否为空

 

vector<int>::iterator it = v.begin();//容器的首元素地址  [begin,end)

 

v.end();//容器的最后一个元素的下一个位置

一个整数数组,数组中元素按照大小先增后减,设计算法,给定元素求其在数组中的位置索引。

v.rbegin();//逆序迭代器,指向容器的最后一个元素

view plaincopy to clipboardprint?#include "stdafx.h"  
#include <iostream>  
#include <vector>  
#include <iterator>  
#include <algorithm>  
using namespace std; 
 
//利用二分查找的思想,来获得最大元素的索引  
int FindMax(int arr[], int n) 

    int low = 0;  
    int high = n - 1; 
    int mid = 0; 
    while (low + 2 <= high) 
    { 
        mid = (low + high) / 2; 
 
        if (arr[mid] > arr[mid-1] && (arr[mid] > arr[mid+1])) //the max element  
            return mid; 
        else if (arr[mid] > arr[mid-1] && (arr[mid+1] > arr[mid])) //递增部分  
            low = mid; 
        else 
            high = mid; 
    } 

 
//递增部分的二分查找  
int BinSearchLeft(int arr[], int begin, int end, int target) 

    int low = begin; 
    int high = end - 1; 
    int mid = 0; 
 
    while (low <= high) 
    { 
        mid = (low + high) / 2; 
 
        if (arr[mid] == target) 
            return mid; 
        else if (arr[mid] < target) 
            low = mid + 1; 
        else 
            high = mid - 1; 
    } 
    return -1; 

//递减部分的二分查找  
澳门新葡亰平台9411,int BinSearchRight(int arr[], int begin, int end, int target) 

    int low = begin; 
    int high = end - 1; 
    int mid = 0; 
 
    while (low <= high) 
    { 
        mid = (low + high) / 2; 
 
        if (arr[mid] == target) 
            return mid; 
        else if (arr[mid] > target) 
            low = mid + 1; 
        else 
            high = mid - 1; 
    } 
    return -1; 

//算法思想:先找到最大元素的索引,然后对左右两个部分进行二分查找  
int FindTargetIndex(int arr[], int n, int target) 

    int maxIndex = FindMax(arr, n); 
     
    if (arr[maxIndex] == target) 
        return maxIndex; 
 
    int res = 0; 
    if ((res = BinSearchLeft(arr, 0, maxIndex, target)) != -1) 
        return res; 
 
    if ((res = BinSearchRight(arr, maxIndex + 1, n, target)) != -1) 
        return res; 
 
    return -1; 

int main() 

    int arr[] = {2, 3, 4, 5, 10, 7, 6, 1}; 
    int size = sizeof(arr) / sizeof(int); 
 
    int maxIndex = FindMax(arr, size); 
    if (-1 != maxIndex) 
        cout<<"the max element's index is "<<maxIndex<<", the max elemet is "<<arr[maxIndex]<<endl; 
 
    int res = FindTargetIndex(arr, size, 3); 
    if (-1 != res) 
        cout<<"the target's position is "<<res<<endl; 
    else 
        cout<<"can not find this target!"<<endl; 
 
    return 0; 

#include "stdafx.h"
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>
using namespace std;

v.rend();//第一个元素前面的位置

//利用二分查找的思想,来获得最大元素的索引
int FindMax(int arr[], int n)
{
 int low = 0;
 int high = n - 1;
 int mid = 0;
 while (low + 2 <= high)
 {
  mid = (low + high) / 2;

v.size();//容器v当前元素的个数

  if (arr[mid] > arr[mid-1] && (arr[mid] > arr[mid+1])) //the max element
   return mid;
  else if (arr[mid] > arr[mid-1] && (arr[mid+1] > arr[mid])) //递增部分
   low = mid;
  else
   high = mid;
 }
}

v.resize(n); //调整容器的长度大小,使其能容纳n个元素

//递增部分的二分查找
int BinSearchLeft(int arr[], int begin, int end, int target)
{
 int low = begin;
 int high = end - 1;
 int mid = 0;

v.resize(n,t);//调整大小的同时将新添加的元素的值都设为t

 while (low <= high)
 {
  mid = (low + high) / 2;

v.max_size();//返回容器可容纳的最多元素个数,返回类型为v::size_type

  if (arr[mid] == target)
   return mid;
  else if (arr[mid] < target)
   low = mid + 1;
  else
   high = mid - 1;
 }
 return -1;
}
//递减部分的二分查找
int BinSearchRight(int arr[], int begin, int end, int target)
{
 int low = begin;
 int high = end - 1;
 int mid = 0;

v.capacity(); //容器v的容量,会自动增长。通常大于size(),加倍分配存储空间。

 while (low <= high)
 {
  mid = (low + high) / 2;

v.reserve(n);//预留窗外的存储空间。

  if (arr[mid] == target)
   return mid;
  else if (arr[mid] > target)
   low = mid + 1;
  else
   high = mid - 1;
 }
 return -1;
}
//算法思想:先找到最大元素的索引,然后对左右两个部分进行二分查找
int FindTargetIndex(int arr[], int n, int target)
{
 int maxIndex = FindMax(arr, n);
 
 if (arr[maxIndex] == target)
  return maxIndex;

v.push_back(10);//将值10放入容器v 中

 int res = 0;
 if ((res = BinSearchLeft(arr, 0, maxIndex, target)) != -1)
  return res;

v.insert(p,t);//在迭代器p所指元素的前面插入值为t 的元素

 if ((res = BinSearchRight(arr, maxIndex + 1, n, target)) != -1)
  return res;

v.insert(p,n,t);//在迭代器所指位置的前面插入n个值为t的元素

 return -1;
}
int main()
{
 int arr[] = {2, 3, 4, 5, 10, 7, 6, 1};
 int size = sizeof(arr) / sizeof(int);

v.insert(p,b,e);//在迭代器p指向的元素前面插入迭代器b和e标记范围内的元素

 int maxIndex = FindMax(arr, size);
 if (-1 != maxIndex)
  cout<<"the max element's index is "<<maxIndex<<", the max elemet is "<<arr[maxIndex]<<endl;

v.at(1) = 20;// 相当于v[1] = 20;

 int res = FindTargetIndex(arr, size, 3);
 if (-1 != res)
  cout<<"the target's position is "<<res<<endl;
 else
  cout<<"can not find this target!"<<endl;

v = v1;//删除v的所有元素,将v1的元素复制给v

 return 0;
}

v.assign(n,t);//将容器重新设置为存储n个值为 t 的元素

 作者“wangyangkobe的专栏”

本文由澳门新葡亰平台9411发布于关于我们,转载请注明出处:任意一串字符串 字符串里包含数字部分和一般的

关键词:

上一篇:其实也不容易,我不给你打电话

下一篇:没有了

最火资讯