秋招突击——算法打卡——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

相关文章

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

hdu1565(状态压缩)

本人第一道ac的状态压缩dp,这题的数据非常水,很容易过 题意:在n*n的矩阵中选数字使得不存在任意两个数字相邻,求最大值 解题思路: 一、因为在1<<20中有很多状态是无效的,所以第一步是选择有效状态,存到cnt[]数组中 二、dp[i][j]表示到第i行的状态cnt[j]所能得到的最大值,状态转移方程dp[i][j] = max(dp[i][j],dp[i-1][k]) ,其中k满足c

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

hdu4826(三维DP)

这是一个百度之星的资格赛第四题 题目链接:http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1004&cid=500 题意:从左上角的点到右上角的点,每个点只能走一遍,走的方向有三个:向上,向下,向右,求最大值。 咋一看像搜索题,先暴搜,TLE,然后剪枝,还是TLE.然后我就改方法,用DP来做,这题和普通dp相比,多个个向上

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

hdu1011(背包树形DP)

没有完全理解这题, m个人,攻打一个map,map的入口是1,在攻打某个结点之前要先攻打其他一个结点 dp[i][j]表示m个人攻打以第i个结点为根节点的子树得到的最优解 状态转移dp[i][ j ] = max(dp[i][j], dp[i][k]+dp[t][j-k]),其中t是i结点的子节点 代码如下: #include<iostream>#include<algorithm

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

hdu4865(概率DP)

题意:已知前一天和今天的天气概率,某天的天气概率和叶子的潮湿程度的概率,n天叶子的湿度,求n天最有可能的天气情况。 思路:概率DP,dp[i][j]表示第i天天气为j的概率,状态转移如下:dp[i][j] = max(dp[i][j, dp[i-1][k]*table2[k][j]*table1[j][col] )  代码如下: #include <stdio.h>#include