[322] 重新安排行程

题目描述

322 重新安排行程

解题思路

前提：……
思路：回溯。
重点：……。

代码实现

C语言

回溯 + 链表自实现

超出时间限制！！

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

#define NAME_LEN 4
#define INVALID_NUM 1000

typedef struct airlist {
    char *start;
    char **end;
    int endSize;
    bool *used;
} airList;

struct airlist *list;
int listSize;
char **path;
int pathSize;

int findListLoc(char *start, int ticketsSize)
{
    int j = INVALID_NUM;
    for (j = 0; j < ticketsSize; j++) {
        if ((list[j].start == NULL) || (0 == strcmp(start, list[j].start))) {
            return j;
        }
    }
    return j;
}

void insertListLoc(char *end, int loc)
{
    int endS = list[loc].endSize;
    int serLoc = endS;
    if (list[loc].endSize > 0) {
    }
    for (int k = endS - 1; k >= 0; k--) {
        if (0 > strcmp(end, list[loc].end[k])) {
            strncpy(list[loc].end[k + 1], list[loc].end[k], NAME_LEN);
            serLoc = k;
        }
    }
    strncpy(list[loc].end[serLoc], end, NAME_LEN);
    (list[loc].endSize)++;
    return ;
}

void init(char*** tickets, int ticketsSize)
{
    // 开辟空间
    // 初始化list
    list = (struct airlist *)malloc(sizeof(struct airlist) * ticketsSize);
    memset(list, 0, sizeof(struct airlist) * ticketsSize);
    listSize = 0;
    for (int i = 0; i < ticketsSize; i++) {
        // 初始化start
        int loc = findListLoc(tickets[i][0], ticketsSize);
        if (list[loc].start == NULL) {
            list[loc].start = (char *)malloc(sizeof(char) * NAME_LEN);
            strncpy(list[loc].start, tickets[i][0], NAME_LEN);
        }
        // 初始化end，按字典序排列
        if (list[loc].end == NULL) {
            list[loc].end = (char **)malloc(sizeof(char *) * ticketsSize);
            for (int v= 0; v < ticketsSize; v++) {
                list[loc].end[v] = (char *)malloc(sizeof(char) * NAME_LEN);
                memset(list[loc].end[v], 0, sizeof(char) * NAME_LEN);
            }
        }
        insertListLoc(tickets[i][1], loc);
        // 初始化used数组
        if (list[loc].used == NULL) {
            list[loc].used = (bool *)malloc(sizeof(bool) * ticketsSize);
            memset(list[loc].used, 0, sizeof(bool) * ticketsSize);
        }
        listSize = (listSize < (loc + 1)) ? (loc + 1) : listSize;
    }
    // 初始化path
    path = (char **)malloc(sizeof(char *) * (ticketsSize + 1));
    for (int l = 0; l < (ticketsSize + 1); l++) {
        path[l] = (char *)malloc(sizeof(char) * NAME_LEN);
        memset(path[l], 0, sizeof(char) * NAME_LEN);
    }
    pathSize = 0;
    return ;
}

bool backtracking(char *start, int  ticketsSize)
{
    // 退出条件
    if (pathSize == (ticketsSize + 1)) {
        return true;
    }
    // 递归
    int loca = findListLoc(start, ticketsSize);
    if (loca >= listSize) {
        return false;
    }
    bool result = false;
    for (int m = 0; (m < list[loca].endSize); m++) {
        // 去重
        if (list[loca].used[m] == true) {
            continue;
        }
        // 保存该路径
        strncpy(path[pathSize], list[loca].end[m], NAME_LEN);
        pathSize++;
        list[loca].used[m] = true;
        bool res = backtracking(list[loca].end[m], ticketsSize);
        if (res == false) {
            // 回溯
            pathSize--;
            list[loca].used[m] = false;
            result = false;
        }
        else
        {
            return true;
        }
    }
    return result;
}

char** findItinerary(char*** tickets, int ticketsSize, int* ticketsColSize, int* returnSize) {
    if (*ticketsColSize != 2) {
        return NULL;
    }
    // 初始化
    init(tickets, ticketsSize);
    strncpy(path[pathSize], "JFK", strlen("JFK"));
    pathSize++;
    (void)backtracking("JFK", ticketsSize);
    *returnSize = pathSize;
    return path;
}

回溯 + 哈希

C的哈希函数好难~

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

typedef struct {
    char *name;        /* key */
    int cnt;           /* 记录到达机场是否飞过了 */
    UT_hash_handle hh; /* makes this structure hashable */
} to_airport_t;

typedef struct {
    char *name; /* key */
    to_airport_t *to_airports;
    UT_hash_handle hh; /* makes this structure hashable */
} from_airport_t;

void to_airport_destroy(to_airport_t *airports) {
    to_airport_t *airport, *tmp;
    HASH_ITER(hh, airports, airport, tmp) {
        HASH_DEL(airports, airport);
        free(airport);
    }
}

void from_airport_destroy(from_airport_t *airports) {
    from_airport_t *airport, *tmp;
    HASH_ITER(hh, airports, airport, tmp) {
        to_airport_destroy(airport->to_airports);
        HASH_DEL(airports, airport);
        free(airport);
    }
}

int name_sort(to_airport_t *a, to_airport_t *b) {
    return strcmp(a->name, b->name);
}

bool backtracking(from_airport_t *airports, int target_path_len, char **path,
                  int path_len) {
    if (path_len == target_path_len) return true;

    from_airport_t *from_airport = NULL;
    HASH_FIND_STR(airports, path[path_len - 1], from_airport);
    if (!from_airport) return false;

    for (to_airport_t *to_airport = from_airport->to_airports;
         to_airport != NULL; to_airport = to_airport->hh.next) {
        if (to_airport->cnt == 0) continue;
        to_airport->cnt--;
        path[path_len] = to_airport->name;
        if (backtracking(airports, target_path_len, path, path_len + 1))
            return true;
        to_airport->cnt++;
    }
    return false;
}

char **findItinerary(char ***tickets, int ticketsSize, int *ticketsColSize,
                     int *returnSize) {
    from_airport_t *airports = NULL;

    // 记录映射关系
    for (int i = 0; i < ticketsSize; i++) {
        from_airport_t *from_airport = NULL;
        to_airport_t *to_airport = NULL;
        HASH_FIND_STR(airports, tickets[i][0], from_airport);
        if (!from_airport) {
            from_airport = malloc(sizeof(from_airport_t));
            from_airport->name = tickets[i][0];
            from_airport->to_airports = NULL;
            HASH_ADD_KEYPTR(hh, airports, from_airport->name,
                            strlen(from_airport->name), from_airport);
        }
        HASH_FIND_STR(from_airport->to_airports, tickets[i][1], to_airport);
        if (!to_airport) {
            to_airport = malloc(sizeof(to_airport_t));
            to_airport->name = tickets[i][1];
            to_airport->cnt = 0;
            HASH_ADD_KEYPTR(hh, from_airport->to_airports, to_airport->name,
                            strlen(to_airport->name), to_airport);
        }
        to_airport->cnt++;
    }

    // 机场排序
    for (from_airport_t *from_airport = airports; from_airport != NULL;
         from_airport = from_airport->hh.next) {
        HASH_SRT(hh, from_airport->to_airports, name_sort);
    }

    char **path = malloc(sizeof(char *) * (ticketsSize + 1));
    path[0] = "JFK";  // 起始机场
    backtracking(airports, ticketsSize + 1, path, 1);

    from_airport_destroy(airports);

    *returnSize = ticketsSize + 1;
    return path;
}

[51] N皇后

题目描述

51 N皇后

解题思路

前提：……
思路：回溯
重点：……

代码实现

C语言

回溯 + 使用used数组区分是否同列 + 使用path保存q位置，并判断是否为斜线

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */

char ***ans;
int ansSize;
int *length;
int *path;
char pathSize;
bool *used;

#define INVALID_DATA  100

void init(int n)
{
    ans = (char ***)malloc(sizeof(char **) * 1000);
    memset(ans, 0, sizeof(char **) * 1000);
    ansSize = 0;
    length = (int *)malloc(sizeof(int) * 1000);
    memset(length, 0, sizeof(int) * 1000);
    path = (int *)malloc(sizeof(int) * n);
    memset(path, INVALID_DATA, sizeof(int) * n);
    pathSize = 0;
    used = (bool *)malloc(sizeof(bool) * n);
    memset(used, 0, sizeof(bool) * n);
    return ;
}

bool isValid(int col, int loc)
{
    // 同一行在递归处保证
    // 同一列
    if (used[loc] == true) {
        return false;
    }
    // 斜线
    int k = 0;
    while (k < pathSize) {
        if ((loc == path[k] + (col - k)) || (loc == path[k] - (col - k))) {
            return false;
        }
        k++;
    }
    return true;
}

void collect(int n)
{
    ans[ansSize] = (char **)malloc(sizeof(char *) * n);
    for (int i = 0; i < n; i++) {
        ans[ansSize][i] = (char *)malloc(sizeof(char) * (n + 1));
        for (int j = 0; j < n; j++) {
            if (path[i] != j) {
                ans[ansSize][i][j] = '.';
            } else {
                ans[ansSize][i][j] = 'Q';
            }
        }
        // 需要加结束符，否则会报错heap-buffer-overflow
        ans[ansSize][i][n] = '\0';
    }
    length[ansSize] = n;
    ansSize++;
    return;
}

void backtracking(int n)
{
    // 退出条件
    if (pathSize == n) {
        collect(n);
        return;
    }
    // 递归
    for (int k = 0; k < n; k++) {
        // 判断是否合理
        if (isValid(pathSize, k) == false) {
            continue;
        }
        // 保存该数据
        path[pathSize] = k;
        used[k] = true;
        pathSize++;
        backtracking(n);
        // 回溯
        pathSize--;
        used[k] = false;
        path[pathSize] = INVALID_DATA;
    }
    return ;
}

char*** solveNQueens(int n, int* returnSize, int** returnColumnSizes) {
    // 全局变量初始化
    init(n);

    backtracking(n);

    // 输出赋值
    *returnSize = ansSize;
    *returnColumnSizes = length;
    return ans;
}