[Algorithm][综合训练][字符编码][最少的完全平方数][游游的字母串]详细讲解

本文主要是介绍[Algorithm][综合训练][字符编码][最少的完全平方数][游游的字母串]详细讲解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

  • 1.字符编码
    • 1.题目链接
    • 2.算法原理详解 && 代码实现
  • 2.最少的完全平方数
    • 1.题目链接
    • 2.算法原理详解 && 代码实现
  • 3.游游的字母串
    • 1.题目链接
    • 2.算法思路详解 && 代码实现


1.字符编码

1.题目链接

  • 字符编码

2.算法原理详解 && 代码实现

  • 解法:给一个字符串进行二进制编码,使得编码后的字符串长度最短 --> 哈夫曼编码
    #include <iostream>
    #include <string>
    #include <vector>
    #include<queue>
    using namespace std;int main()
    {string str;while(cin >> str){// 1.统计每个字符的频次int hash[300] = { 0 };for(const auto& ch : str){hash[ch]++;}// 2.将所有的频次放入堆中priority_queue<int, vector<int>, greater<>> heap;for(int i = 0; i < 300; i++){if(hash[i]){heap.push(hash[i]);}}// 3.哈夫曼编码int ret = 0;while(heap.size() > 1){int x1 = heap.top();heap.pop();int x2 = heap.top();heap.pop();ret += x1 + x2;heap.push(x1 + x2);}cout << ret << endl;}return 0;
    }
    

2.最少的完全平方数

1.题目链接

  • 最少的完全平方数

2.算法原理详解 && 代码实现

  • 思路:从一些数里面选,每个数都可以选无穷多次,在限定条件下,达到目的
  • 解法:完全背包 -> 空间优化版本
    • 状态表示dp[i][j]:从前i割数中挑选,总和恰好为j时,最少挑出来几个数

    • 状态转移方程
      请添加图片描述

    • 初始化
      请添加图片描述

    • 返回值dp[sqrt(n)][n]

    #include <iostream>
    #include <cstring>
    using namespace std;const int N = 1e4 + 10;int main()
    {int n = 0;cin >> n;int dp[N];memset(dp, 0x3f, sizeof dp);dp[0] = 0;for(int i = 1; i * i <= n; i++){for(int j = i * i; j <= n; j++){dp[j] = min(dp[j], dp[j - i * i] + 1);}}cout << dp[n] << endl;return 0;
    }
    

3.游游的字母串

1.题目链接

  • 游游的字母串

2.算法思路详解 && 代码实现

  • 解法暴力枚举所有可能变成的字符情况

    • 如何求变化次数min(abs(a - z), 26 - abs(a - z))
      请添加图片描述
    #include <iostream>
    #include <cmath>
    #include <string>
    using namespace std;int main()
    {string str;cin >> str;int ret = 0x3f3f3f3f;for(char ch = 'a'; ch <= 'z'; ch++) // 枚举变成什么字符{int sum = 0;for(auto x : str){sum += min(abs(x - ch), 26 - abs(x - ch));}ret = min(ret, sum);}cout << ret << endl;return 0;
    }
    

这篇关于[Algorithm][综合训练][字符编码][最少的完全平方数][游游的字母串]详细讲解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1123510

相关文章

C# WinForms存储过程操作数据库的实例讲解

《C#WinForms存储过程操作数据库的实例讲解》:本文主要介绍C#WinForms存储过程操作数据库的实例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、存储过程基础二、C# 调用流程1. 数据库连接配置2. 执行存储过程(增删改)3. 查询数据三、事务处

Java使用Curator进行ZooKeeper操作的详细教程

《Java使用Curator进行ZooKeeper操作的详细教程》ApacheCurator是一个基于ZooKeeper的Java客户端库,它极大地简化了使用ZooKeeper的开发工作,在分布式系统... 目录1、简述2、核心功能2.1 CuratorFramework2.2 Recipes3、示例实践3

通过Docker Compose部署MySQL的详细教程

《通过DockerCompose部署MySQL的详细教程》DockerCompose作为Docker官方的容器编排工具,为MySQL数据库部署带来了显著优势,下面小编就来为大家详细介绍一... 目录一、docker Compose 部署 mysql 的优势二、环境准备与基础配置2.1 项目目录结构2.2 基

Linux系统中配置静态IP地址的详细步骤

《Linux系统中配置静态IP地址的详细步骤》本文详细介绍了在Linux系统中配置静态IP地址的五个步骤,包括打开终端、编辑网络配置文件、配置IP地址、保存并重启网络服务,这对于系统管理员和新手都极具... 目录步骤一:打开终端步骤二:编辑网络配置文件步骤三:配置静态IP地址步骤四:保存并关闭文件步骤五:重

Centos环境下Tomcat虚拟主机配置详细教程

《Centos环境下Tomcat虚拟主机配置详细教程》这篇文章主要讲的是在CentOS系统上,如何一步步配置Tomcat的虚拟主机,内容很简单,从目录准备到配置文件修改,再到重启和测试,手把手带你搞定... 目录1. 准备虚拟主机的目录和内容创建目录添加测试文件2. 修改 Tomcat 的 server.X

Linux find 命令完全指南及核心用法

《Linuxfind命令完全指南及核心用法》find是Linux系统最强大的文件搜索工具,支持嵌套遍历、条件筛选、执行动作,下面给大家介绍Linuxfind命令完全指南,感兴趣的朋友一起看看吧... 目录一、基础搜索模式1. 按文件名搜索(精确/模糊匹配)2. 排除指定目录/文件二、根据文件类型筛选三、时间

C++快速排序超详细讲解

《C++快速排序超详细讲解》快速排序是一种高效的排序算法,通过分治法将数组划分为两部分,递归排序,直到整个数组有序,通过代码解析和示例,详细解释了快速排序的工作原理和实现过程,需要的朋友可以参考下... 目录一、快速排序原理二、快速排序标准代码三、代码解析四、使用while循环的快速排序1.代码代码1.由快

C语言字符函数和字符串函数示例详解

《C语言字符函数和字符串函数示例详解》本文详细介绍了C语言中字符分类函数、字符转换函数及字符串操作函数的使用方法,并通过示例代码展示了如何实现这些功能,通过这些内容,读者可以深入理解并掌握C语言中的字... 目录一、字符分类函数二、字符转换函数三、strlen的使用和模拟实现3.1strlen函数3.2st

Spring Boot拦截器Interceptor与过滤器Filter详细教程(示例详解)

《SpringBoot拦截器Interceptor与过滤器Filter详细教程(示例详解)》本文详细介绍了SpringBoot中的拦截器(Interceptor)和过滤器(Filter),包括它们的... 目录Spring Boot拦截器(Interceptor)与过滤器(Filter)详细教程1. 概述1

VSCode中C/C++编码乱码问题的两种解决方法

《VSCode中C/C++编码乱码问题的两种解决方法》在中国地区,Windows系统中的cmd和PowerShell默认编码是GBK,但VSCode默认使用UTF-8编码,这种编码不一致会导致在VSC... 目录问题方法一:通过 Code Runner 插件调整编码配置步骤方法二:在 PowerShell