秋招突击——算法打卡——6/3——复习{最低通行费、(状态压缩DP)小国王}——新做:{罗马数字转整数、最长公共前缀}

本文主要是介绍秋招突击——算法打卡——6/3——复习{最低通行费、(状态压缩DP)小国王}——新做:{罗马数字转整数、最长公共前缀},希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

    • 复习
      • 背包模型——最低通行费
        • 题目内容
        • 实现代码
      • (状态压缩DP)小国王
        • 检查状态本身是否存在两个连续的1
        • 计算所有的合法状态已经所有合法状态之间的转移
        • 动态规划过程
    • 新作
      • 罗马数字转整数
        • 个人实现
          • 实现代码
        • 参考做法
          • 实现代码
      • 最长公共前缀
        • 个人实现
        • 参考思路
    • 总结

复习

背包模型——最低通行费

题目内容

在这里插入图片描述

实现代码
  • 首先规定了步数是2n-1,相当于只能往右下那个方向出发,只能往下或者往右走
  • 最小花费,那么f[i][j],就表示到达第i和j的格子中若干方案中最低的代码。
  • 完全可以使用动态规划,但是边界条件确定还是有点问题,并不知道怎么弄。
    • 真牛,我还不确定这样写对不对,结果跟参考代码写的一模一样。
    • 就是从最初的那个单元格进行遍历,发现有一个单元格始终是空的,所以就对那个单元格进行赋值就行了,然后再往下继续便利赋值即可。
#include <iostream>
#include <algorithm>using namespace std;
const int N = 110;
int w[N][N],f[N][N];
int n;
int main(){cin>>n;// 记录矩阵信息for (int i = 1; i <= n ; ++i) {for (int j = 0; j <= n ; ++j) {cin>>w[i][j];}}// 根据状态转换方程进行变动  f[i][j] = max(f[i - 1][j],f[i][j - 1]) + w[i][j]for (int i = 1; i <= n; ++i) {for (int j = 1; j <= n; ++j) {if (i == 1 && j == 1)   f[i][j] = w[i][j];else f[i][j] = INT_MAX;if (i - 1 >= 0) f[i][j] = min(f[i][j],f[i -1][j]) + w[i][j];if (j - 1 >= 0) f[i][j] = min(f[i][j],f[i][j - 1]) + w[i][j];}}cout<<f[n][n]<< endl;
}

(状态压缩DP)小国王

  • 上半场题解链接
  • 上次讲到要验证状态是否合法,所以需要写一下状态合法的判定情况,然后在计算一下有哪些状态是合法,那些状态转换是合法的。
检查状态本身是否存在两个连续的1
  • 实际上可以使用错位相与,不等于零就是错的
bool check(int state){// 检查是否存在连续的两个一,如果存在就是不合法for(int i = 0;i < n;i ++)if ((state >> i & 1) && (state >> i + 1 & 1))return false;return true;
}

请添加图片描述

  • 可以改成如下形式
bool check(int state){// 检查是否存在连续的两个一,如果存在就是不合法return !(state & (state  >> 1));
//    for(int i = 0;i < n;i ++)
//        if ((state >> i & 1) && (state >> (i + 1) & 1))
//            return false;
//    return true;
}
计算所有的合法状态已经所有合法状态之间的转移
  • 这里每一行有n个格子,每一个格子是两种状态,相当于是2的n次方,所以移位运算就是乘以2倍数。遍历所有状态就是可以的。
  • 这里判定两个状态是否是合法,需要好好画一下图,具体如下
    • a:100101
    • b:010000
    • 按位或:110101,如果他出现相邻的1,就是不合格的状态,所以需要进行判定。
// 这里是遍历所有的情况,并将所有的状态保存起来for (int i = 0; i < 1 << n; ++i) {if (check(i)){state.push_back(i);id[i] = state.size() - 1; // 存储每一个合法状态的坐标cnt[i] = count(i); // 计算当前合法状态中1的个数,也就是国王的个数}}
// 这里是相邻两种状态能不能实现转移的判定条件,就是相同的位置不能为一,交叉位置不能为1.for (int i = 0; i < state.size(); ++i) {for (int j = 0; j < state.size(); ++j) {int a = state[i], b = state[j];  // 统计两个合法状态if ((a & b) == 0 && check(a | b))   // 不能有交集,并且不能有斜插head[a].push_back(b);   // 保存a所有能够转移的合法的b的状态}}
动态规划过程
  • 需要理解这个动态规划的坐标f[i][j][k]
    • i:表示第i行
    • j:表示总共放j个国王
    • k:表示第k个状态
f[0][0][0] = 1;
// 这里是总共有n行,然后逐行进行遍历
for (int i = 1; i <= n + 1; ++i) {// 假设一开始是要求放j个国王for (int j = 0; j <= m ; ++j) {// 遍历当前位置所有的合法情况for (int a = 0; a < state.size(); ++a) {// 遍历当前位置的所有合法情况for (int b:head[a]) {int c = cnt[state[a]];if (j >= c){f[i][j][a] += f[i - 1][j - c][b];}}}}
}cout<<f[n + 1][m][0];

新作

罗马数字转整数

题目链接

个人实现
  • 数字转罗马,就是中等,从罗马转数字,就是中等
  • 正常进行遍历,遇到不同的数字进行不同的操作
    • 特殊情况,如果右边的数字比左边的大,那就执行特殊情况,想减
实现代码
  • 不知道如何往unordered_map中添加多个元素
方法一:std::unordered_map<std::string, int> umap;// 使用insert方法和initializer_list一次性添加多个元素umap.insert({{"one", 1},{"two", 2},{"three", 3}});方法二:std::unordered_map<std::string, int> umap = {{"one", 1},{"two", 2},{"three", 3}};
  • string.at返回的是string还是char?
    • 返回的是char型数据

在这里插入图片描述

#include <iostream>
#include <string>
#include <unordered_map>using namespace std;int romanToInt(string s){unordered_map<char ,int> rep;rep['I'] = 1;rep['V'] = 5;rep['X'] = 10;rep['L'] = 50;rep['C'] = 100;rep['D'] = 500;rep['M'] = 1000;int res = 0;for (int i = 0; i < s.size(); ++i) {res += rep[s[i]];if (i + 1 < s.size()){if (s.substr(i,2) == "IV" || s.substr(i,2) == "IX")res -= 2;if (s.substr(i,2) == "Xl" || s.substr(i,2) == "XC")res -= 20;if (s.substr(i,2) == "CD" || s.substr(i,2) == "CM")res -= 200;}}return res;
}int main(){cout<<romanToInt("MMMXLV");
}
参考做法
  • 这里是判定,当前数字是大于等于下一个数字,就是默认直接替换,如果小于,那就减去当前的数字,具体实现方式如下
实现代码
#include <iostream>
#include <string>
#include <unordered_map>using namespace std;int romanToInt(string s){unordered_map<char ,int> rep = {{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}};int res = 0;for (int i = 0; i < s.size(); ++i) {if (i + 1 < s.size() && s[i] < s[i + 1])res -= rep[i];else res += rep[i];}return res;
}int main(){cout<<romanToInt("MMMXLV");
}

最长公共前缀

题目链接

  • 一看就知道是动态规划,那是最长公共子序列
个人实现
  • 具体一看,这道题并不是动态规划,应该是简单版的,直接遍历就行了,具体实现代码如下
    • 直接那第一个字符串,然后遍历第一个字符串的所有字符,然后和后续所有的字符串比较,相同跳过,不同直接突出,返回。如果是自然到末尾,就是需要加一。
class Solution {
public:string longestCommonPrefix(vector<string>& s) {if (s.size() == 1) return s[0];int r = 0;bool flag = true;for(int i = 0;i < s[0].size();i ++){r = i;for(int j = 1;j < s.size();j ++){if(i < s[j].size() && s[0][i] == s[j][i])continue;else{flag = false;break;}}if(!flag)   break;}if (flag)return s[0].substr(0,r + 1);elsereturn s[0].substr(0,r);}
};
参考思路
  • 思路是一样的,但是他的代码比我的简洁,是这样的,直接遍历所有的i,然后获取第一个字符串的i,然后在判定其他的,相同再加上去,不同的话,直接返回
class Solution {
public:string longestCommonPrefix(vector<string>& s) {if (s.size() == 1) return s[0];string r;for (int i = 0; ; ++i) {if (i >= s[0].size())   return r;char t = s[0][i];for (int j = 1; j < s.size(); ++j) {if (t != s[j][i])   return r;}r += t;}}
};

在这里插入图片描述

总结

  • 今天这道题DP问题就花了很多时间,完全就没有必要,所以下次还是规定一下时间超过了,就明天再来。
  • 今天两道简单题,还行。

这篇关于秋招突击——算法打卡——6/3——复习{最低通行费、(状态压缩DP)小国王}——新做:{罗马数字转整数、最长公共前缀}的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

SpringBoot使用GZIP压缩反回数据问题

《SpringBoot使用GZIP压缩反回数据问题》:本文主要介绍SpringBoot使用GZIP压缩反回数据问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录SpringBoot使用GZIP压缩反回数据1、初识gzip2、gzip是什么,可以干什么?3、Spr

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

SpringSecurity JWT基于令牌的无状态认证实现

《SpringSecurityJWT基于令牌的无状态认证实现》SpringSecurity中实现基于JWT的无状态认证是一种常见的做法,本文就来介绍一下SpringSecurityJWT基于令牌的无... 目录引言一、JWT基本原理与结构二、Spring Security JWT依赖配置三、JWT令牌生成与

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

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

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n

关于WebSocket协议状态码解析

《关于WebSocket协议状态码解析》:本文主要介绍关于WebSocket协议状态码的使用方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录WebSocket协议状态码解析1. 引言2. WebSocket协议状态码概述3. WebSocket协议状态码详解3

SpringBoot3实现Gzip压缩优化的技术指南

《SpringBoot3实现Gzip压缩优化的技术指南》随着Web应用的用户量和数据量增加,网络带宽和页面加载速度逐渐成为瓶颈,为了减少数据传输量,提高用户体验,我们可以使用Gzip压缩HTTP响应,... 目录1、简述2、配置2.1 添加依赖2.2 配置 Gzip 压缩3、服务端应用4、前端应用4.1 N

一文详解SpringBoot响应压缩功能的配置与优化

《一文详解SpringBoot响应压缩功能的配置与优化》SpringBoot的响应压缩功能基于智能协商机制,需同时满足很多条件,本文主要为大家详细介绍了SpringBoot响应压缩功能的配置与优化,需... 目录一、核心工作机制1.1 自动协商触发条件1.2 压缩处理流程二、配置方案详解2.1 基础YAML

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时