劍指Offer ：字元串的排列

文章目錄

• • 1. 題目 1
  • • 1.1 示例
    • 1.2 解題思路
    • 1.3 代碼實作
  • 2. 題目 2
  • • 2.1 示例
    • 2.2 解題思路
    • 2.3 代碼實作
  • 3. 題目 3
  • • 3.1 解題思路
    • 3.2 代碼實作

1. 題目 1

輸入一個字元串，列印出該字元串中字元的所有排列。例如，輸入字元串 abc，則列印出由字元a、b、c所能排列出來的所有字元串abc、acb、bac、bca、cab和cba。

1.1 示例

輸入：

abc
           

輸出：

abc
acb
bac
bca
cba
cab
           

1.2 解題思路

可以把一個字元串看成由兩部分組成：第一部分是它的第一個字元；第二部分是後面的所有字元。求整個字元串的排列，可以看成兩步。

1.求所有可能出現在第一個位置的字元。

2.固定第一個字元，求後面所有字元的排列。這時仍把後面所有字元分成兩部分：後面字元的第一個字元，以及這個字元之後的所有字元。

1.3 代碼實作

#include <stdio.h>

void Permutation(char* string, char* strBegin);

void Permutation(char* string)
{
    if (string == NULL) {
        return;
    }
    
    Permutation(string, string);
}

void swap(char* strA, char* strB)
{
    char temp = *strA;
    *strA = *strB;
    *strB = temp;
}

void Permutation(char* string, char* strBegin)
{
    if (*strBegin == '\0') {
        printf("%s\n", string);
    } else {
        for (char* strCh = strBegin; *strCh != '\0'; ++strCh) {
            // 有重複字元時，跳過
            if ((*strCh == *strBegin) && (strCh != strBegin)) {
                continue;
            }

            swap(strCh, strBegin);
            Permutation(string, strBegin + 1);
            swap(strCh, strBegin);
        }
    }
}

int main(void)
{
    char string[] = "abc";
    Permutation(string);

    return 0;
}
           

2. 題目 2

如果不是求字元的所有排列，而是求字元的所有組合，應該怎麼辦呢？還是輸入三個字元 a、b、c，則它們的組合有 a、b、c、ab、ac、bc、abc。當交換字元串中的兩個字元時，雖然能得到兩個不同的排列，但卻是同一個組合。比如 ab 和 ba 是不同的排列，但隻算一個組合。

2.1 示例

輸入：

abc
           

輸出：

a
b
c
ab
ac
bc
abc
           

2.2 解題思路

可以把這 n 個字元分成兩部分：第一個字元和其餘的所有字元。如果組合裡包含第一個字元，則下一步在剩餘的字元裡選取 m-1個字 符：如果組合裡不包含第一個字元，則下一步在剩餘的 n-1 個字元裡選取 m 個字元。也就是說，我們可以把求 n 個字元組成長度為 m 的組合的問題分解成兩個子問題。

1.求 n-1 個字元串中長度為 m-1 的組合。

2.求 n-1 個字元的長度為 m 的組合。

2.3 代碼實作

#include <cstdio>
#include <cstring>
#include <vector>

void Combination(char* string, int number, std::vector<char>& result);

void Combination(char* string)
{
    if (string == nullptr) {
        return;
    }

    std::vector<char> result;

    for (int i = 1; i <= strlen(string); ++i) {
        Combination(string, i, result);
    }
}

void Combination(char* string, int number, std::vector<char>& result)
{
    if (number == 0) {
        std::vector<char>::iterator iter = result.begin();
        for (; iter < result.end(); ++iter) {
            printf("%c", *iter);
        }
        printf("\n");

        return;
    }
    
    if (*string == '\0') {
        return;
    }

    result.push_back(*string);
    Combination(string + 1, number - 1, result);
    result.pop_back();
    Combination(string + 1, number, result);
}

int main(void)
{
    char string[] = "abc";
    Combination(string);

    return 0;
}
           

3. 題目 3

輸入一個含有 8 個數字的數組，判斷有沒有可能把這8個數字分别放到正方體的8個頂點上，使得正方體上三組相對的面上的4個頂點的和都相等。

3.1 解題思路

相當于先得到a1、a2、a3、a4、a5、a6、a7和a8這 8 個數字的排列，然後判斷有沒有某一個排列符合題目給定的條件，即 a1+a2+a3+a4 == a5+a6+a7+a8，a1+a3+a5+a7 == a2+a4+a6+a8，并且a1+a2+a5+a6 == a3+a4+a7+a8。

3.2 代碼實作

#include <stdio.h>
#include <stdbool.h>

void swap(int* a, int*b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

bool CubVertex(int* A, int length, int begin)
{
    if ((A == NULL) || (length != 8)) {
        return false;
    }

    bool result = false;
    int i = 0;
    
    if (begin == length - 1) {
        if ((A[0] + A[1] + A[2] + A[3] ==A[4] + A[5] + A[6] + A[7]) &&
            (A[0] + A[2] + A[4] + A[6] == A[1] + A[3] + A[5] + A[7]) &&
            (A[0] + A[1] + A[4] + A[5] == A[2] + A[3] + A[6] + A[7])) {

            for (i = 0; i < length; ++i) {
                printf("%d ", A[i]);
            }
            printf("\n");
            result = true;
        }
    } else {
        for (i = begin; i < length; ++i) {
            swap(&A[begin], &A[i]);
            result = CubVertex(A, length, begin + 1);
            if (result) {
                break;
            }

            swap(&A[begin], &A[i]);
        }
    }

    return result;
}

int main(void)
{
    int A[8] = {1, 2, 3, 1, 2, 3, 2, 2};
    int B[8] = {1, 2, 3, 1, 8, 3, 2, 2};

    if (CubVertex(A, 8, 0)) {
        printf("Yes!\n");
    } else {
        printf("No!\n");
    }

    if (CubVertex(B, 8, 0)) {
        printf("Yes!\n");
    } else {
        printf("No!\n");
    }
    
    return 0;
}
/* 運作結果
 * 1 2 3 2 3 2 1 2 
 * Yes!
 * No!
 */
           

個人部落格：

www.codeapes.cn