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

前言

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

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

题目详情

[322] 重新安排行程

题目描述

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皇后
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;
}

今日收获

  1. 收获不了一点，已晕菜。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/705579.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

ABB控制主板3BHE024855R0101 UF C921 A101

ABB控制主板3BHE024855R0101 UF C921 A101

控制板也是一种电路板&#xff0c;其运用的范围虽不如电路板来的宽泛&#xff0c;但却比普通的电路板来的智能、自动化。简单的说&#xff0c;能起到控制作用的电路板&#xff0c;才可称为控制板。大到厂家的自动化生产设备&#xff0c;小到孩童用的玩具遥控汽车&#xff0c;内…
阅读更多...
【OpenCV】opencv-4.9.0源码编译（二）

【OpenCV】opencv-4.9.0源码编译（二）

很高兴在雪易的CSDN遇见你 VTK技术爱好者 QQ&#xff1a;870202403 公众号&#xff1a;VTK忠粉 前言 本文分享OpenCV源码编译时所遇到的问题&#xff0c;希望对各位小伙伴有所帮助&#xff01; 感谢各位小伙伴的点赞关注&#xff0c;小易会继续努力分享&#xff0c;一…
阅读更多...
一文教会你静态住宅代理IP的优势和选择技巧，跨境小白收好这份指南！

一文教会你静态住宅代理IP的优势和选择技巧，跨境小白收好这份指南！

一、什么是静态住宅代理IP&#xff1f; 静态住宅代理IP是指分配给个人住宅网络的IP地址&#xff0c;这些IP地址在长时间内保持不变。它们是从互联网服务提供商&#xff08;ISP&#xff09;获取的&#xff0c;因此拥有更高的可信度和较低的被封禁风险。静态住宅代理IP因其独特的…
阅读更多...
基于 Python 解析 XML 文件并将数据存储到 MongoDB 数据库

基于 Python 解析 XML 文件并将数据存储到 MongoDB 数据库

1. 问题背景 在软件开发中&#xff0c;我们经常需要处理各种格式的数据。XML 是一种常用的数据交换格式&#xff0c;它可以存储和传输结构化数据。很多网站会提供 XML 格式的数据接口&#xff0c;以便其他系统可以方便地获取数据。 我们有这样一个需求&#xff1a;我们需要从…
阅读更多...
Python界面编辑器Tkinter布局助手 使用体验

Python界面编辑器Tkinter布局助手 使用体验

一、发现 我今天在网上搜关于Python Tkinter方面的信息时&#xff0c;发现了Python界面编辑器 Tkinter布局助手 的使用说明。 https://blog.csdn.net/weixin_52777652/article/details/135291731?spm1001.2014.3001.5506 这个编辑器是个开源的项目&#xff0c;个人用户可以…
阅读更多...
Ecahrts横向柱状图自动滚动

Ecahrts横向柱状图自动滚动

1.定义一个定时器标识 let timer: NodeJS.Timer; // 定时器 2.定义展示的数据的条数 const dataZoomEndValue 5; // 数据窗口范围的结束数值(一次性展示几个) 3.设置datazoom的相关参数 dataZoom: [{show: false, // 是否显示滑动条xAxisIndex: 0, // 表示从X轴的零刻度线…
阅读更多...
香橙派 AIpro 评测与使用心得

香橙派 AIpro 评测与使用心得

引言 香橙派 AIpro&#xff08;OrangePi AIpro&#xff09;是一款尺寸小巧却功能强大的AI边缘设备&#xff0c;其仅有107*68mm的超小尺寸使得它在各种场景下都能轻松部署。它支持两种流行的操作系统&#xff0c;包括Ubuntu和openEuler&#xff0c;为用户提供了更多的选择和灵活…
阅读更多...
Windows同一文件夹下支持大小写同名文件

Windows同一文件夹下支持大小写同名文件

举例&#xff1a;同一文件目录下需要存在A.java, a.java, Windows是不支持的&#xff0c;这时候需要建一个Linux子系统的文件夹 创建教程 1、在启用或关闭Windows功能下面找到 适用于Linux系统的Windows子系统 2、cmd 执行命令 fsutil file SetCaseSensitiveInfo 文件夹路径 …
阅读更多...
新注册与新核准有什么区别？在哪可以找到新注册新核准的企业名单？

新注册与新核准有什么区别？在哪可以找到新注册新核准的企业名单？

新注册&#xff1a;指的是公司刚刚完成工商注册登记&#xff0c;成为法律意义的经营实体。 新核准&#xff1a;指的是企业通过证券监管机构的审核&#xff0c;获得公开发行股票或债券的资格。 注册主要关注企业的基本资质和合规性&#xff0c;而核准是已经注册的公司进行财务…
阅读更多...
【React】如何使用npm run start命令运行两个服务

【React】如何使用npm run start命令运行两个服务

我们开发前端项目时&#xff0c;有时候需要本地 mock 数据&#xff0c;这样就需要启动两个服务&#xff0c;一个是接口服务&#xff0c;一个是前端项目。可以安装一个插件来帮助我们通过一个命令启动两个服务。 方法一 添加& npm run server 注意&#xff1a;Windows系统…
阅读更多...
人脸匹配——OpenCV

人脸匹配——OpenCV

人脸匹配 导入所需的库加载dlib的人脸识别模型和面部检测器读取图片并转换为灰度图比较两张人脸选择图片并显示结果比较图片创建GUI界面运行GUI主循环运行显示全部代码 导入所需的库 cv2&#xff1a;OpenCV库&#xff0c;用于图像处理。 dlib&#xff1a;一个机器学习库&#x…
阅读更多...
用Python绘制yolo训练结果比较图-论文需要

用Python绘制yolo训练结果比较图-论文需要

代码内容来自于网络用博客记录 利用训练生成的result.csv中数据&#xff0c;形成多模型的比较图。 代码中演示的是map50、map50-95、losss的比较图 import matplotlib.pyplot as plt import pandas as pd import numpy as npif __name__ __main__:# 列出待获取数据内容的…
阅读更多...
webstorm自定义vue模板

webstorm自定义vue模板

<!--* Description: ${COMPONENT_NAME} 页面* Author: * Date: ${DATE} --> <template><div>${COMPONENT_NAME} </div> </template><script> export default {name: "${COMPONENT_NAME}",components: {},data() {return {};},co…
阅读更多...
【数据结构】单链表（C语言）

【数据结构】单链表（C语言）

在数据结构和算法中&#xff0c;链表是一种常见的数据结构&#xff0c;它由一系列节点组成&#xff0c;每个节点包含数据和指向下一个节点的指针。在C语言中&#xff0c;我们可以使用指针来实现单向链表。下面将详细讲述如何利用C语言实现单向链表。 1.单链表的概念和结构 概…
阅读更多...
Yolo-World训练过程中使用wandb进行可视化

Yolo-World训练过程中使用wandb进行可视化

训练过程可视化有两种方式&#xff1a;wandb和tensorboard&#xff0c;这里我采用的是wandb&#xff0c;想要在训练过程中调用wandb只需要在要训练的配置文件&#xff08;如yolo_world_v2_l_vlpan_bn_sgd_1e-3_40e_8gpus_finetune_coco.py&#xff09;中加上一行代码即可&#…
阅读更多...
美业门店管理系统Java源码分享-【库存管理】的功能和作用

美业门店管理系统Java源码分享-【库存管理】的功能和作用

美业收银系统在美容行业中的作用和重要性体现在提高管理效率、提升客户满意度、降低成本、促进业务增长等方面。它为连锁美业提供了一个全面的管理工具&#xff0c;能够更好地应对市场挑战&#xff0c;提升竞争力。 美业系统中的【库存管理】在整个美容行业中起着非常重要的作…
阅读更多...
【机器学习】以DIFY为例分享一种使用dockerhub镜像的方法

【机器学习】以DIFY为例分享一种使用dockerhub镜像的方法

目录 一、引言 二、Dify在dockerhub被禁用后&#xff0c;如何部署、升级 2.1 网络及硬件条件 2.2 docker部署、升级方案 三、总结 一、引言 关于dify&#xff0c;之前力推过&#xff0c;大家可以跳转 AI智能体研发之路-工程篇&#xff08;二&#xff09;&#xff1a;Dify…
阅读更多...
LayUI使用（二）处理表格会出现下拉框的问题

LayUI使用（二）处理表格会出现下拉框的问题

一、问题描述 如下&#xff0c;layui的表格渲染后&#xff0c;当鼠标悬停在表格项时会出现右侧的下拉框&#xff0c;layui版本较老&#xff0c;原因未知 二、处理办法 在cols里面加上width&#xff0c;也不用每个都加&#xff0c;加一部分表格项即可 注意&#xff1a;若想禁止…
阅读更多...
18. 四数之和 - 力扣

18. 四数之和 - 力扣

1. 题目 给你一个由 n 个整数组成的数组 nums &#xff0c;和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] &#xff08;若两个四元组元素一一对应&#xff0c;则认为两个四元组重复&#xff09;&#xff1a; 0 …
阅读更多...
# RocketMQ 实战：模拟电商网站场景综合案例（十一）

# RocketMQ 实战：模拟电商网站场景综合案例（十一）

RocketMQ 实战&#xff1a;模拟电商网站场景综合案例&#xff08;十一&#xff09; 一、RocketMQ 实战&#xff1a;模拟电商网站场景综合案例-- web 端项目开发 1、在 shop-order-web 工程模块中&#xff0c;创建 Controller 类 OrderControllre.java /*** shop\shop-order…
阅读更多...
最新文章

Copyright @ 2022~2023