【代码随想录】【算法训练营】【第30天】 [322]重新安排行程 [51]N皇后 [37]解数独

前言

思路及算法思维，指路代码随想录。
题目来自 LeetCode。

day 30，周四，好难，会不了一点~

题目详情

[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;
}