前言
思路及算法思维，指路 代码随想录。
题目来自 LeetCode。
day 30，周四，好难，会不了一点~
题目详情
[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皇后
题目描述
解题思路
前提：……
思路：回溯
重点：……
代码实现
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;
}
今日收获
- 收获不了一点，已晕菜。