【c++笔试强训】(第十四篇)

news/2024/11/20 19:02:33/

目录

扑克牌顺⼦(排序)

题目解析

讲解算法原理

编写代码

最⻓回⽂⼦串(回⽂串)

题目解析

讲解算法原理

编写代码


扑克牌顺⼦(排序)

题目解析

1.题目链接:扑克牌顺子_牛客题霸_牛客

2.题目描述

描述

现在有2副扑克牌,从扑克牌中随机五张扑克牌,我们需要来判断一下是不是顺子。
有如下规则:
1. A为1,J为11,Q为12,K为13,A不能视为14
2. 大、小王为 0,0可以看作任意牌
3. 如果给出的五张牌能组成顺子(即这五张牌是连续的)就输出true,否则就输出false。
4.数据保证每组5个数字,每组最多含有4个零,数组的数取值为 [0, 13]
 

要求:空间复杂度 O(1)O(1),时间复杂度 O(nlogn)O(nlogn),本题也有时间复杂度 O(n)O(n) 的解法

输入描述:

输入五张扑克牌的值

返回值描述:

五张扑克牌能否组成顺子。

示例1

输入:

[6,0,2,0,4]

返回值:

true

说明:

中间的两个0一个看作3,一个看作5 。即:[6,3,2,5,4]
这样这五张牌在[2,6]区间连续,输出true 

示例2

输入:

[0,3,2,6,4]

返回值:

true

示例3

输入:

[1,0,0,1,0]

返回值:

false

示例4

输入:

[13,12,11,0,1]

返回值:

false

讲解算法原理

解法:
规律:

如果能够构成顺⼦的话,所有的⾮零元素应该满⾜下⾯两个条件:a. 不能出现重复元素;
b. max - min <= 4

编写代码

c++算法代码:

class Solution
{bool hash[14] = { 0 };
public:bool IsContinuous(vector<int>& numbers) {int maxVal = 0, minVal = 14;for(auto x : numbers){if(x){if(hash[x]) return false;hash[x] = true;maxVal = max(maxVal, x);minVal = min(minVal, x);}}return maxVal - minVal <= 4;}
};

java 算法代码:

java">import java.util.*;
public class Solution
{public boolean IsContinuous (int[] numbers) {boolean[] hash = new boolean[14];int maxVal = 0, minVal = 14;for(int x : numbers){if(x != 0){if(hash[x]) return false;hash[x] = true;maxVal = Math.max(maxVal, x);minVal = Math.min(minVal, x);}}return maxVal - minVal <= 4;}
}

 

最⻓回⽂⼦串(回⽂串)

题目解析

1.题目链接:最长回文子串_牛客题霸_牛客

2.题目描述

描述

对于长度为n的一个字符串A(仅包含数字,大小写英文字母),请设计一个高效算法,计算其中最长回文子串的长度。

数据范围: 1 \le n \le 10001≤n≤1000

要求:空间复杂度 O(1)O(1),时间复杂度 O(n^2)O(n2)

进阶:  空间复杂度 O(n)O(n),时间复杂度 O(n)O(n)

示例1

输入:

"ababc"

复制返回值:

3

说明:

最长的回文子串为"aba"与"bab",长度都为3

示例2

输入:

"abbba"

返回值:

5

复制

示例3

输入:

"b"

返回值:

1

讲解算法原理

解法:
算法思路:

枚举所有的中⼼点,然后向两边扩散。

编写代码

c++算法代码:

class Solution
{
public:int getLongestPalindrome(string s) {int ret = 1, n = s.size();for(int i = 1; i < n; i++){// 当⻓度是奇数的时候int left = i - 1, right = i + 1;while(left >= 0 && right < n && s[left] == s[right]){left--;right++;}ret = max(ret, right - left - 1);// 当⻓度是偶数的时候left = i - 1, right = i;while(left >= 0 && right < n && s[left] == s[right]){left--;right++;}ret = max(ret, right - left - 1);}return ret;}
};

java算法代码:

java">import java.util.*;
public class Solution
{public int getLongestPalindrome (String s) {// 中⼼扩展算法int n = s.length();int ret = 0;for(int i = 0; i < n; i++) // 枚举所有的中点{// 当⻓度为奇数的时候int left = i - 1, right = i + 1;while(left >= 0 && right < n && s.charAt(left) == s.charAt(right)){left--;right++;}ret = Math.max(ret, right - left - 1);// 当⻓度为偶数的时候left = i; right = i + 1;while(left >= 0 && right < n && s.charAt(left) == s.charAt(right)){left--;right++;}ret = Math.max(ret, right - left - 1);}return ret;}
}


http://www.ppmy.cn/news/1548542.html

相关文章

EtherNet/IP从站转ModbusTCP主网关是一款 ETHERNET/IP 从站功能的通讯网关

EtherNet/IP从站转ModbusTCP主网关是一款 ETHERNET/IP 从站功能的通讯网关。该产品主要功能是将各种 MODBUS-TCP 设备接入到 ETHERNET/IP 网络 中。本网关连接到 ETHERNET/IP 总线中做为从站使用&#xff0c;连接到 MODBUS-TCP总线中做为主站或从站使用。 来百度APP畅享高清图…

CSS3中的伸缩盒模型(弹性盒子、弹性布局)之伸缩容器、伸缩项目、主轴方向、主轴换行方式、复合属性flex-flow

简介&#xff1a; 1.伸缩盒模型简介 2.伸缩容器、伸缩项目 3-4.主轴方向 5.主轴换行方式 6.复合属性flex-flow 7.主轴的对齐方式

运维面试题.云计算面试题之四.K8S

常见的k8s运维面试题 1、简述ETCD及其特点? etcd是一个用于配置共享和服务发现的键值存储系统,能够为整个分布式集群存储关键数据,协助集群正常运转 服务端将配置信息存储在etcd中,客户端从etcd中得到配置信息,etcd监听配置信息的变化,发现配置变化通知到客户端 特点 - 安…

android 使用MediaPlayer实现音乐播放--权限请求

在Android应用中&#xff0c;获取本地音乐文件的权限是实现音乐扫描功能的关键步骤之一。随着Android版本的不断更新&#xff0c;从Android 6.0&#xff08;API级别23&#xff09;开始&#xff0c;应用需要动态请求权限&#xff0c;而到了android 13以上需要的权限又做了进一步…

十大网络安全事件

一、私有云平台遭攻击&#xff0c;美国数千家公司工资难以发放 1月&#xff0c;专门提供劳动力与人力资本管理解决方案的美国克罗诺斯&#xff08;Kronos&#xff09;公司私有云平台遭勒索软件攻击&#xff0c;事件造成的混乱在数百万人中蔓延。 克罗诺斯母公司UKG集团&#xf…

STM32G4的数模转换器(DAC)的应用

目录 概述 1 DAC模块介绍 2 STM32Cube配置参数 2.1 参数配置 2.2 项目架构 3 代码实现 3.1 接口函数 3.2 功能函数 3.3 波形源代码 4 DAC功能测试 4.1 测试方法介绍 4.2 波形测试 概述 本文主要介绍如何使用STM32G4的DAC模块功能&#xff0c;笔者使用STM32Cube工具…

验证双随机矩阵(doubly stochastic matrix) 满足C(P)=C(P^T)

验证双随机矩阵(doubly stochastic matrix) 满足C( P P P)C(P T ^T T) 双随机矩阵&#xff1a; 在数学中&#xff0c;一个双随机矩阵&#xff08;doubly stochastic matrix&#xff09;是一个满足以下条件的矩阵&#xff1a; 非负矩阵&#xff1a;矩阵中的每个元素都是非负的…

LDR6500:C to DP与DP to C视频转接线双向方案

在当前的数字时代&#xff0c;投屏技术和视频接口转换已成为连接不同设备、共享内容的常用手段。LDR6500&#xff0c;作为乐得瑞科技精心研发的USB Power Delivery&#xff08;PD&#xff09;协议芯片&#xff0c;凭借其卓越的性能和广泛的兼容性&#xff0c;在C-to-DP&#xf…