目录
扑克牌顺⼦(排序)
题目解析
讲解算法原理
编写代码
最⻓回⽂⼦串(回⽂串)
题目解析
讲解算法原理
编写代码
扑克牌顺⼦(排序)
题目解析
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;}
}
最⻓回⽂⼦串(回⽂串)
题目解析
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;}
}