剑指offer自学系列(四)

题目描述：

输入一个正整数数组，把数组里面所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个，例如输入数组{3,32,321}，输出的最小数字为321323

题目分析：

如果采用穷举法，把每一种可能都列举一遍，然后比较得到最小的一个字符串，那么将会有n的全排列个组合，也就是n的阶乘种情况，当n值很大时，时间复杂度是爆炸的，所以我们需要采用一种更小的方法，首先我们知道这样一个规律，对于字符串连接(+表示连接)，如果A+B<B+A，则A<B，如果A+B>B+A，则A>B，如果A+B=B+A，则A=B，所以排序的时候按照从小到大的顺序，最后依次连接得到的值最小，下面按照这个思路得到代码：

#include<iostream>

#include<vector>

#include<string>

#include<algorithm>

using namespace std;

bool cmp(int a, int b) {

    string strA = to_string(a) + to_string(b);

    string strB = to_string(b) + to_string(a);

    return strA < strB;

}

string MinNumber(vector<int>matrix) {

    int length = matrix.size();

    if (length == 0) { return “”; }

    sort(matrix.begin(), matrix.end(), cmp);

    string res;

    for (int i = 0; i < length;i++) {

        res += to_string(matrix[i]);

    }

    return res;

}

int main() {

    vector<int> num = {23,1,456};

    string result = MinNumber(num);

    cout << result << endl;

}

题目描述：

请实现一个函数，将一个字符串中所有的空格替换成“%20”，例如，将字符串“We Are Happy”替换成“We%20Are%20Happy”

题目分析：

我们依然先考虑从头到尾找到一个空格就插入”%20”这样一组符号，假如找到一个空格，我们会想将后面的值往后移两格，但是数组必然初始空间得设很大，如果采用向量，则需要扩容，如果我们首先通过一轮循环找到有多少个空格，然后计算需要用多大的空间也是可行的，比如有两个空格，那么我们就设比初值长度大4的空间，我们采用双指针控制，由于中间的值如果空格替换后会往后移，所以我们让指针从后往前检索

#include<iostream>

using namespace std;

char *SpaceToStr(char a[], int start,int len){

    int i = len;

    int j = start;

    while (j>=0) {

        if (a[j]!=' ') {

            a[i] = a[j];

            i--;

            j--;

        }

        else {

            a[i] = '0';

            a[i - 1] = '2';

            a[i - 2] = '%';

            i = i - 3;

            j--;

        }

    }

    return a;

}

int main() {

    char a[] = { "We Are Happy" };

    int i = 0;

    int count = 0;

    while (a[i]!='\0') {

        if (a[i] == ' ')

            count += 1;

        i++;

    }

    cout << i << endl;

    char *b;

    b = SpaceToStr(a, i, i+2*count);

    cout << b << endl;

    return 0;

}

巴特西

剑指offer自学系列(四)

最新文章

热门文章