算法-三角形最小路径和

题目

思路

代码

char* getPermutation(int n, int k) {
    char* result = (char*)malloc((n + 1) * sizeof(char));
    bool* flag = (bool*)calloc(n, sizeof(bool));
    int temp[10] = { 0 };
    temp[n] = 1;
    temp[n - 1] = 1;
    int i = 0, t = 0, idx = 0, j = 0;
    for(i = n - 2; i > 0; i--)
        temp[i] = temp[i + 1] * (n - i);
    for(i = 1; i <= n; i++) {
        t = (k - 1) / temp[i];
        idx = t;
        for(j = 1; j <= n; j++) {
            //取当前最小的未使用的数值
            if(!flag[j]) {
                t--;
                if(t == -1)
                    break;
            }
        }
        result[i - 1] = '0' + j;
        flag[j] = true;
        k -= idx * temp[i];
    }
    result[n] = '\0';
    free(flag);
    return result;
}