【c++笔试强训】（第十四篇）
目录
扑克牌顺⼦（排序）
题目解析
讲解算法原理
编写代码
最⻓回⽂⼦串（回⽂串）
题目解析
讲解算法原理
编写代码
扑克牌顺⼦（排序）
题目解析
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 算法代码：
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算法代码：
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;
}
}