一、求最小公倍数题目解析题目很简单给定两个数a和b求它们的最小公倍数。算法思路对于求两个数的最小公倍数问题想必已经非常熟悉了在之前学校上课时记得老师提起过最小公倍数 两个数的乘积 除以最大公约数。所以我们现在只需要找到两个数的最大公约数然后就可以求出最小公倍数。求a和b的最大公约数定义tmpa%b这里a b循环去执行取%操作每次把b的值赋给atmp的值赋给btmp继续取a%b。当tmp的值为0是循环就结束了此时b的值就是这两个数的最大公约数。返回结果求出来了最大公约数最后返回a*b / 最大公约数即可。代码实现#includeiostreamusingnamespacestd;//求最大公约数intgcd(inta,intb){if(ab){intta;ab;bt;}inttmpa%b;while(tmp){ab;btmp;tmpa%b;}returnb;}intmain(){inta,b;cinab;intggcd(a,b);couta*b/gendl;return0;}二、数组中最长的连续子序列题目解析本题题目给定一个无序的数组arr让我们返回其中最长连续序列的长度要求数值连续位置可以不连续就例如3,5,6,4只要数值是连续的自然数就可以。算法思路对于这道题暴力解法枚举出来所以的子序列找出最长的连续序列求出来长度即可。这里不多描述了回超时。现在我们在回过去看题目要求我们找连续序列的长度(该序列数值是连续的对位置没有要求)只要求我们返回长度所以我们现在可以先让整个数组有序让这些连续的数放到一块这样就方便我们计算长度了。整体思路如下先让数组有序再利用双指针去寻找连续序列使用count来记录序列的长度即可排序数组调用库里面sort即可双指针遍历i记录连续数组开始位置的下标,j向后遍历如果j位置数值等于j-1位置数值1,就count继续向后遍历如果j位置数值等于j-1位置数值j继续向后遍历如果j位置数值不等于等于j-1位置数值1也不等于j-1位置的值就更新当前结果。更新完结果后i变道j位置j从下一个位置继续遍历直到遍历完整个数组。这里需要注意可以存在相等的值我们count计数的同时也要完成去重操作代码实现classSolution{public:intMLS(vectorintarr){//排序数组sort(arr.begin(),arr.end());intnarr.size();intret0;for(inti0;in;){intji1;intcount1;while(jn){if(arr[j]-arr[j-1]1){j;count;}elseif(arr[j]-arr[j-1]0){j;}else{break;}}if(countret)retcount;ij;}returnret;}};三、字母收集题目解析题目给了一个n*m的字符数组方阵让我们选择一条路径获取最多的分数得分规则遇到l字母得4分、遇到o字母得3分、遇到v字母得2分、遇到e字母得1分其他的字母都不得分在我们选择路径的时候我们只能从当前节点向右或者向下走。整个很重要所以我们就要从1,1位置开始。算法思路初次遇见这道题博主以为是搜索题就直接使用bfs深度遍历完整个数组找到当前位置向左和向右走能够获得的分数然后取其中最大值。但是题目中给定范围1n,m500深层递归就要执行2^500次可以说十分恐怖了。这里直接来看这道题的解题思路dp动态规划。这里我们dp[i][j]就表示走到该位置最大的得分dp状态转移方程dp[i][j] max(dp[i][j-1],dp[i-1][j])t其中t表示dp[i][j]位置的得分。这里为什么呢题目上说了我们只能向下和向右走所以我们只能从dp[i][j-1]和dp[i-1][j]两个位置走到dp[i][j]而我们的dp[i][j]表示的就是到当前位置的最大得分所以我们就找**dp[i][j-1]和dp[i-1][j]两个位置那个位置的值也就是到哪个位置的最大得分两个值中最大的子再加上当前位置得分即可。**代码实现这里写代码有几个注意的点第一个就是我们使用dp时通常下标从1开始这里我们填写dp[1][1]时要用到d[1][0]和dp[0][1]下标从1开始就不需要先自己填入数据了因为未初始化未知的值都是0不会影响我们的结果第二个就是这里的填表顺序我们填dp[i][j]时需要用到dp[i][j-1]和dp[i-1][j]两个位置的值所以要从左到右从上到下依次填写。#includeiostreamusingnamespacestd;constintN501;intdp[N][N]{0};charstr[N][N];intmain(){intm,n;cinmn;for(inti1;im;i){for(intj1;jn;j){cinstr[i][j];}}//初始化dpfor(inti1;im;i){for(intj1;jn;j){intt0;if(str[i][j]l)t4;elseif(str[i][j]o)t3;elseif(str[i][j]v)t2;elseif(str[i][j]e)t1;dp[i][j]max(dp[i-1][j],dp[i][j-1])t;}}coutdp[m][n]endl;return0;}** 到这里本篇文章就结束了继续加油**我的博客即将同步至腾讯云开发者社区邀请大家一同入驻https://cloud.tencent.com/developer/support-plan?invite_code2oul0hvapjsws
【C++】 —— 笔试刷题day_8
一、求最小公倍数题目解析题目很简单给定两个数a和b求它们的最小公倍数。算法思路对于求两个数的最小公倍数问题想必已经非常熟悉了在之前学校上课时记得老师提起过最小公倍数 两个数的乘积 除以最大公约数。所以我们现在只需要找到两个数的最大公约数然后就可以求出最小公倍数。求a和b的最大公约数定义tmpa%b这里a b循环去执行取%操作每次把b的值赋给atmp的值赋给btmp继续取a%b。当tmp的值为0是循环就结束了此时b的值就是这两个数的最大公约数。返回结果求出来了最大公约数最后返回a*b / 最大公约数即可。代码实现#includeiostreamusingnamespacestd;//求最大公约数intgcd(inta,intb){if(ab){intta;ab;bt;}inttmpa%b;while(tmp){ab;btmp;tmpa%b;}returnb;}intmain(){inta,b;cinab;intggcd(a,b);couta*b/gendl;return0;}二、数组中最长的连续子序列题目解析本题题目给定一个无序的数组arr让我们返回其中最长连续序列的长度要求数值连续位置可以不连续就例如3,5,6,4只要数值是连续的自然数就可以。算法思路对于这道题暴力解法枚举出来所以的子序列找出最长的连续序列求出来长度即可。这里不多描述了回超时。现在我们在回过去看题目要求我们找连续序列的长度(该序列数值是连续的对位置没有要求)只要求我们返回长度所以我们现在可以先让整个数组有序让这些连续的数放到一块这样就方便我们计算长度了。整体思路如下先让数组有序再利用双指针去寻找连续序列使用count来记录序列的长度即可排序数组调用库里面sort即可双指针遍历i记录连续数组开始位置的下标,j向后遍历如果j位置数值等于j-1位置数值1,就count继续向后遍历如果j位置数值等于j-1位置数值j继续向后遍历如果j位置数值不等于等于j-1位置数值1也不等于j-1位置的值就更新当前结果。更新完结果后i变道j位置j从下一个位置继续遍历直到遍历完整个数组。这里需要注意可以存在相等的值我们count计数的同时也要完成去重操作代码实现classSolution{public:intMLS(vectorintarr){//排序数组sort(arr.begin(),arr.end());intnarr.size();intret0;for(inti0;in;){intji1;intcount1;while(jn){if(arr[j]-arr[j-1]1){j;count;}elseif(arr[j]-arr[j-1]0){j;}else{break;}}if(countret)retcount;ij;}returnret;}};三、字母收集题目解析题目给了一个n*m的字符数组方阵让我们选择一条路径获取最多的分数得分规则遇到l字母得4分、遇到o字母得3分、遇到v字母得2分、遇到e字母得1分其他的字母都不得分在我们选择路径的时候我们只能从当前节点向右或者向下走。整个很重要所以我们就要从1,1位置开始。算法思路初次遇见这道题博主以为是搜索题就直接使用bfs深度遍历完整个数组找到当前位置向左和向右走能够获得的分数然后取其中最大值。但是题目中给定范围1n,m500深层递归就要执行2^500次可以说十分恐怖了。这里直接来看这道题的解题思路dp动态规划。这里我们dp[i][j]就表示走到该位置最大的得分dp状态转移方程dp[i][j] max(dp[i][j-1],dp[i-1][j])t其中t表示dp[i][j]位置的得分。这里为什么呢题目上说了我们只能向下和向右走所以我们只能从dp[i][j-1]和dp[i-1][j]两个位置走到dp[i][j]而我们的dp[i][j]表示的就是到当前位置的最大得分所以我们就找**dp[i][j-1]和dp[i-1][j]两个位置那个位置的值也就是到哪个位置的最大得分两个值中最大的子再加上当前位置得分即可。**代码实现这里写代码有几个注意的点第一个就是我们使用dp时通常下标从1开始这里我们填写dp[1][1]时要用到d[1][0]和dp[0][1]下标从1开始就不需要先自己填入数据了因为未初始化未知的值都是0不会影响我们的结果第二个就是这里的填表顺序我们填dp[i][j]时需要用到dp[i][j-1]和dp[i-1][j]两个位置的值所以要从左到右从上到下依次填写。#includeiostreamusingnamespacestd;constintN501;intdp[N][N]{0};charstr[N][N];intmain(){intm,n;cinmn;for(inti1;im;i){for(intj1;jn;j){cinstr[i][j];}}//初始化dpfor(inti1;im;i){for(intj1;jn;j){intt0;if(str[i][j]l)t4;elseif(str[i][j]o)t3;elseif(str[i][j]v)t2;elseif(str[i][j]e)t1;dp[i][j]max(dp[i-1][j],dp[i][j-1])t;}}coutdp[m][n]endl;return0;}** 到这里本篇文章就结束了继续加油**我的博客即将同步至腾讯云开发者社区邀请大家一同入驻https://cloud.tencent.com/developer/support-plan?invite_code2oul0hvapjsws
