[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

相关文章

Python实现特殊字符判断并去掉非字母和数字的特殊字符

《Python实现特殊字符判断并去掉非字母和数字的特殊字符》在Python中,可以通过多种方法来判断字符串中是否包含非字母、数字的特殊字符,并将这些特殊字符去掉,本文为大家整理了一些常用的,希望对大家... 目录1. 使用正则表达式判断字符串中是否包含特殊字符去掉字符串中的特殊字符2. 使用 str.isa

MySql match against工具详细用法

《MySqlmatchagainst工具详细用法》在MySQL中,MATCH……AGAINST是全文索引(Full-Textindex)的查询语法,它允许你对文本进行高效的全文搜素,支持自然语言搜... 目录一、全文索引的基本概念二、创建全文索引三、自然语言搜索四、布尔搜索五、相关性排序六、全文索引的限制七

python中各种常见文件的读写操作与类型转换详细指南

《python中各种常见文件的读写操作与类型转换详细指南》这篇文章主要为大家详细介绍了python中各种常见文件(txt,xls,csv,sql,二进制文件)的读写操作与类型转换,感兴趣的小伙伴可以跟... 目录1.文件txt读写标准用法1.1写入文件1.2读取文件2. 二进制文件读取3. 大文件读取3.1

Linux内核参数配置与验证详细指南

《Linux内核参数配置与验证详细指南》在Linux系统运维和性能优化中,内核参数(sysctl)的配置至关重要,本文主要来聊聊如何配置与验证这些Linux内核参数,希望对大家有一定的帮助... 目录1. 引言2. 内核参数的作用3. 如何设置内核参数3.1 临时设置(重启失效)3.2 永久设置(重启仍生效

如何在Mac上安装并配置JDK环境变量详细步骤

《如何在Mac上安装并配置JDK环境变量详细步骤》:本文主要介绍如何在Mac上安装并配置JDK环境变量详细步骤,包括下载JDK、安装JDK、配置环境变量、验证JDK配置以及可选地设置PowerSh... 目录步骤 1:下载JDK步骤 2:安装JDK步骤 3:配置环境变量1. 编辑~/.zshrc(对于zsh

使用Node.js制作图片上传服务的详细教程

《使用Node.js制作图片上传服务的详细教程》在现代Web应用开发中,图片上传是一项常见且重要的功能,借助Node.js强大的生态系统,我们可以轻松搭建高效的图片上传服务,本文将深入探讨如何使用No... 目录准备工作搭建 Express 服务器配置 multer 进行图片上传处理图片上传请求完整代码示例

C++ vector的常见用法超详细讲解

《C++vector的常见用法超详细讲解》:本文主要介绍C++vector的常见用法,包括C++中vector容器的定义、初始化方法、访问元素、常用函数及其时间复杂度,通过代码介绍的非常详细,... 目录1、vector的定义2、vector常用初始化方法1、使编程用花括号直接赋值2、使用圆括号赋值3、ve

python连接本地SQL server详细图文教程

《python连接本地SQLserver详细图文教程》在数据分析领域,经常需要从数据库中获取数据进行分析和处理,下面:本文主要介绍python连接本地SQLserver的相关资料,文中通过代码... 目录一.设置本地账号1.新建用户2.开启双重验证3,开启TCP/IP本地服务二js.python连接实例1.

Nginx中配置HTTP/2协议的详细指南

《Nginx中配置HTTP/2协议的详细指南》HTTP/2是HTTP协议的下一代版本,旨在提高性能、减少延迟并优化现代网络环境中的通信效率,本文将为大家介绍Nginx配置HTTP/2协议想详细步骤,需... 目录一、HTTP/2 协议概述1.HTTP/22. HTTP/2 的核心特性3. HTTP/2 的优

Java图片压缩三种高效压缩方案详细解析

《Java图片压缩三种高效压缩方案详细解析》图片压缩通常涉及减少图片的尺寸缩放、调整图片的质量(针对JPEG、PNG等)、使用特定的算法来减少图片的数据量等,:本文主要介绍Java图片压缩三种高效... 目录一、基于OpenCV的智能尺寸压缩技术亮点:适用场景:二、JPEG质量参数压缩关键技术:压缩效果对比