算法总结----数组弄巧

秒速五厘米 2022-03-31 12:28 114阅读 0赞

1. 求一个数组中后边的元素减去前边的元素的最大值

例如

数组 [3, 2, -1, 5, 4]
    后减前最大值为：5 - （-1）=6

思路

定义局部最大值tmpMax(初始化为负无穷)，局部最小值tmpLow（初始化为数组第一个元素）

从第二个元素开始遍历，如果（该元素-tmpLow ）< 0说明该元素比tmpLow还小呢，那么就把tmpLow替换成该元素，同时比较该差值与tmpMax的大小，用大的替换tmpMax；否则（>=0）只需比较该差值与tmpMax的大小，用大的替换tmpMax。

参考代码

#include <iostream>
    using namespace std;
    int MAX_INT = ((unsigned)(-1)) >> 1;
    int MIN_INT = -MAX_INT;
    
    int getMaxGap(int A[], int lens)
    {
        if (A == NULL || lens <= 0)
            return -1;
        int tmpMax = MIN_INT;
        int tmpLow = A[0];
        for (int i = 1; i < lens; ++i)
        {
            int tmp = A[i] - tmpLow;
            if (tmp > tmpMax)
                tmpMax = tmp;
            if (tmp < 0)
                tmpLow = A[i];
        }
        return tmpMax;
    }
    
    
    int main()
    {
        int a[] = {
        3, 2, -1, 5, 4};
        cout << getMaxGap(a, sizeof(a) / sizeof(int)) << endl;
    }

结果

2. 删除字符串开始及末尾的空白符，并且把数组中间的多个空格（如果有）符转化为1个。

思路：两个指针往后走

参考代码

#include <iostream>
    #include <algorithm>
    #include <vector>
    #include <string>
    using namespace std;
    
    void getNewStr(char a[])
    {
        int new_cur = 0;
        int Isbeg = 1;
        int i = 0;
        for (i = 0; a[i] != '\0'; )
        {
            if (a[i] != ' ')
            {
                Isbeg = 0;
                a[new_cur++] = a[i++];
            }
            else
            {
                if (Isbeg == 1)
                {
                    while (a[i] != '\0' && a[i] == ' ')
                        ++i;
                }
                else
                {
                    a[new_cur++] = a[i++];
                    while (a[i] != '\0' && a[i] == ' ')
                        ++i;
                }
            }
        }
        cout << "new_cur:" << new_cur << endl;
        if (a[i-1] == ' ')
            a[new_cur-1] = '\0';
        else
            a[new_cur] = '\0';
    }
                
    int main()
    {
        char a[] = "  hello    hi      ";
        cout << a << endl;
        cout << sizeof(a) / sizeof(char) << endl;
        getNewStr(a);
        cout << a << endl;
        cout << sizeof(a) / sizeof(char) << endl;
        for (int i = 0; a[i] != '\0'; ++i)
            cout << a[i] << endl;
    }