[Algorithm][综合训练][非对称之美][添加字符][数组变换]详细讲解

本文主要是介绍[Algorithm][综合训练][非对称之美][添加字符][数组变换]详细讲解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

  • 1.非对称之美
    • 1.题目链接
    • 2.算法原理详解 && 代码实现
  • 2.添加字符
    • 1.题目链接
    • 2.算法原理详解 && 代码实现
  • 3.数组变换
    • 1.题目链接
    • 2.算法原理详解 && 代码实现


1.非对称之美

1.题目链接

  • 非对称之美

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

  • 自己的版本:动态规划 --> 内存超限 --> 23.44%
    #include <iostream>
    #include <string>
    #include <vector>
    using namespace std;int main()
    {string str;cin >> str;int n = str.size();vector<vector<bool>> dp(n, vector<bool>(n, false));int maxLen = 0;for(int i = n - 1; i >= 0; i--){for(int j = i; j < n; j++){if(str[i] == str[j]){dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;}if(!dp[i][j]){maxLen = max(maxLen, j - i + 1);}}}cout << maxLen << endl;return 0;
    }
    
  • 优化版本:规律 + 贪心
    #include <iostream>
    #include <string>
    using namespace std;int n;
    string str;int Adjust()
    {// 1.判断是否全都是相同字符bool flag = true;for(int i = 1; i < n; i++){if(str[i] != str[0]){flag = false;break;}}if(flag){return 0;}// 2.判断本身是否是回文flag = true;int left = 0, right = n - 1;while(left < right){if(str[left] == str[right]){left++;right--;}else{flag = false;break;}}if(flag){return n - 1;}else{return n;}
    }int main()
    {cin >> str;n = str.size();cout << Adjust() << endl;return 0;
    }
    

2.添加字符

1.题目链接

  • 添加字符

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

  • 解法:暴力枚举
    #include <iostream>
    #include <string>
    using namespace std;int main()
    {string a, b;cin >> a >> b;int m = a.size(), n = b.size();int ret = m;for(int i = 0; i <= n - m; i++) // 枚举b的起始位置{int tmp = 0;for(int j = 0; j < m; j++){if(a[j] != b[i + j]){tmp++;}}ret = min(tmp, ret);}cout << ret << endl;return 0;
    }
    

3.数组变换

1.题目链接

  • 数组变换

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

  • 自己的版本:排序 + 模拟 --> 100%
    #include <iostream>
    #include <algorithm>
    #include <vector>
    using namespace std;bool Check(int small, int large)
    {while(small < large){if((small *= 2) == large){return true;}}return false;
    }int main()
    {int n = 0;cin >> n;vector<int> nums(n, 0);for(int i = 0; i < n; i++){cin >> nums[i];}sort(nums.begin(), nums.end());int r = n - 1;while(r > 0){if(Check(nums[r - 1], nums[r]) || nums[r] == nums[r - 1]){r--;}else{break;}}cout << (r == 0 ? "YES" : "NO") << endl;return 0;
    }
    
  • 优化版本:贪心 + 位运算
    • 贪心:以最大值为基准,判断较小的数都否变成最大值
    • 位运算:判断一个数是否是x 2 n 2^n 2n
      • 方法一x - (x & -x) == 0 ? true : false
        • x & -x提取出最后一个二进制为1的位
        • 如果该位为仅有的二进制位为1的位,则是
      • 方法二x & (x - 1) == 0 ? true : false
    #include <iostream>
    #include <vector>
    using namespace std;int n = 0, maxValue = 0;
    vector<int> nums;bool Check()
    {for(int i = 0; i < n; i++){if(maxValue % nums[i]){return false;}int x = maxValue / nums[i];if(x - (x & -x)){return false;}}return true;
    }int main()
    {cin >> n;nums.resize(n, 0);for(auto& x : nums){cin >> x;maxValue = max(x, maxValue);}if(Check()){cout << "YES" << endl;}else{cout << "NO" << endl;}return 0;
    }
    

这篇关于[Algorithm][综合训练][非对称之美][添加字符][数组变换]详细讲解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Java中的数组与集合基本用法详解

《Java中的数组与集合基本用法详解》本文介绍了Java数组和集合框架的基础知识,数组部分涵盖了一维、二维及多维数组的声明、初始化、访问与遍历方法,以及Arrays类的常用操作,对Java数组与集合相... 目录一、Java数组基础1.1 数组结构概述1.2 一维数组1.2.1 声明与初始化1.2.2 访问

使用Docker构建Python Flask程序的详细教程

《使用Docker构建PythonFlask程序的详细教程》在当今的软件开发领域,容器化技术正变得越来越流行,而Docker无疑是其中的佼佼者,本文我们就来聊聊如何使用Docker构建一个简单的Py... 目录引言一、准备工作二、创建 Flask 应用程序三、创建 dockerfile四、构建 Docker

Python设置Cookie永不超时的详细指南

《Python设置Cookie永不超时的详细指南》Cookie是一种存储在用户浏览器中的小型数据片段,用于记录用户的登录状态、偏好设置等信息,下面小编就来和大家详细讲讲Python如何设置Cookie... 目录一、Cookie的作用与重要性二、Cookie过期的原因三、实现Cookie永不超时的方法(一)

MySQL查询JSON数组字段包含特定字符串的方法

《MySQL查询JSON数组字段包含特定字符串的方法》在MySQL数据库中,当某个字段存储的是JSON数组,需要查询数组中包含特定字符串的记录时传统的LIKE语句无法直接使用,下面小编就为大家介绍两种... 目录问题背景解决方案对比1. 精确匹配方案(推荐)2. 模糊匹配方案参数化查询示例使用场景建议性能优

关于集合与数组转换实现方法

《关于集合与数组转换实现方法》:本文主要介绍关于集合与数组转换实现方法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、Arrays.asList()1.1、方法作用1.2、内部实现1.3、修改元素的影响1.4、注意事项2、list.toArray()2.1、方

SpringBoot整合liteflow的详细过程

《SpringBoot整合liteflow的详细过程》:本文主要介绍SpringBoot整合liteflow的详细过程,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋...  liteflow 是什么? 能做什么?总之一句话:能帮你规范写代码逻辑 ,编排并解耦业务逻辑,代码

浏览器插件cursor实现自动注册、续杯的详细过程

《浏览器插件cursor实现自动注册、续杯的详细过程》Cursor简易注册助手脚本通过自动化邮箱填写和验证码获取流程,大大简化了Cursor的注册过程,它不仅提高了注册效率,还通过友好的用户界面和详细... 目录前言功能概述使用方法安装脚本使用流程邮箱输入页面验证码页面实战演示技术实现核心功能实现1. 随机

嵌入式数据库SQLite 3配置使用讲解

《嵌入式数据库SQLite3配置使用讲解》本文强调嵌入式项目中SQLite3数据库的重要性,因其零配置、轻量级、跨平台及事务处理特性,可保障数据溯源与责任明确,详细讲解安装配置、基础语法及SQLit... 目录0、惨痛教训1、SQLite3环境配置(1)、下载安装SQLite库(2)、解压下载的文件(3)、

HTML img标签和超链接标签详细介绍

《HTMLimg标签和超链接标签详细介绍》:本文主要介绍了HTML中img标签的使用,包括src属性(指定图片路径)、相对/绝对路径区别、alt替代文本、title提示、宽高控制及边框设置等,详细内容请阅读本文,希望能对你有所帮助... 目录img 标签src 属性alt 属性title 属性width/h

CSS3打造的现代交互式登录界面详细实现过程

《CSS3打造的现代交互式登录界面详细实现过程》本文介绍CSS3和jQuery在登录界面设计中的应用,涵盖动画、选择器、自定义字体及盒模型技术,提升界面美观与交互性,同时优化性能和可访问性,感兴趣的朋... 目录1. css3用户登录界面设计概述1.1 用户界面设计的重要性1.2 CSS3的新特性与优势1.