顺时针打印矩阵
题目
描述
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵：
[[1,2,3,4],
[5,6,7,8],
[9,10,11,12],
[13,14,15,16]]
则依次打印出数字
[1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10]
数据范围:
0 <= matrix.length <= 100
0 <= matrix[i].length <= 100
牛客题目链接
思路
我们主要分析以下几种情况
- 只有一行的时候，我们只需要遍历打印即可；
- 只有一列的时候，我们同样只需要遍历打印即可；
- 对于多行多列的情况，我们需要按照规定的顺序进行打印；
代码实现
private ArrayList<Integer> result = new ArrayList<>();
public ArrayList<Integer> printMatrix(int[][] matrix) {
if (matrix == null || matrix[0] == null || matrix[0].length == 0) {
return result;
}
int tR = 0; //表示第一行下标
int tC = 0; //表示第一列下标
int index = 0; //表示当前集合下标
int dR = matrix.length - 1; //最后一行下标
int dC = matrix[0].length - 1; //最后一列下标
while (tR <= dR && tC <= dC) {
printMatrix(matrix, tR++, tC++, dR--, dC--, index); //不断往中间靠拢
}
return result;
}
private void printMatrix(int[][] matrix, int tR, int tC, int dR, int dC, int index) {
if (tR == dR) {
//只有一行的情况
for (int i = dR; i <= dC; i++) {
result.add(matrix[tR][i]);
}
} else if (tC == dC) {
//只有一列的情况
for (int i = tR; i <= dR; i++) {
result.add(matrix[i][tC]);
}
} else {
//遵守矩阵打印规则
int curR = tR;
int curC = tC;
while (curC != dC) {
result.add(matrix[curR][curC]);
curC++;
}
while (curR != dR) {
result.add(matrix[curR][curC]);
curR++;
}
while (curC != tC) {
result.add(matrix[curR][curC]);
curC--;
}
while (curR != tR) {
result.add(matrix[curR][curC]);
curR--;
}
}
}
扑克牌顺子
题目
现在有2副扑克牌，从扑克牌中随机五张扑克牌，我们需要来判断一下是不是顺子。
有如下规则：
- A为1，J为11，Q为12，K为13，A不能视为14
- 大、小王为 0，0可以看作任意牌
- 如果给出的五张牌能组成顺子（即这五张牌是连续的）就输出true，否则就输出false。
4.数据保证每组5个数字，每组最多含有4个零，数组的数取值为 [0, 13]
要求：空间复杂度 O(1)，时间复杂度 O(nlogn)，本题也有时间复杂度 O(n) 的解法；
牛客题目链接
思路
根据题目，我们可以分析出顺子需要满足以下两个条件：
- 顺子中的非零牌最大数和最小数相差不超过4；
- 顺子中的非零牌不能有重复数字；
对于重复数字判断，我们可以采用HashMap进行处理；
代码实现
public boolean IsContinuous (int[] numbers) {
HashMap<Integer,Integer> hashMap = new HashMap<>();
//定义最大值和最小值
int max = 0;
int min = 13;
for(int i = 0; i < numbers.length;i++){
if(numbers[i] > 0 ){
//用于判断是否重复
if(hashMap.get(numbers[i])!=null){
return false;
}else{
hashMap.put(numbers[i],i);
//找出最大值和最小值
if(numbers[i] > max){
max = numbers[i];
}
if(numbers[i] < min){
min = numbers[i];
}
}
}
}
//计算相差，如果大于4则不满足顺子要求
if(max - min > 4){
return false;
}
return true;
}
把字符串转换成整数
题目
描述
写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。传入的字符串可能有以下部分组成:
1.若干空格
2.（可选）一个符号字符（‘+’ 或 ‘-’）
3. 数字，字母，符号，空格组成的字符串表达式
4. 若干空格
转换算法如下:
1.去掉无用的前导空格
2.第一个非空字符为+或者-号时，作为该整数的正负号，如果没有符号，默认为正数
3.判断整数的有效部分：
3.1 确定符号位之后，与之后面尽可能多的连续数字组合起来成为有效整数数字，如果没有有效的整数部分，那么直接返回0
3.2 将字符串前面的整数部分取出，后面可能会存在存在多余的字符(字母，符号，空格等)，这些字符可以被忽略，它们对于函数不应该造成影响
3.3 整数超过 32 位有符号整数范围 [−231, 231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231的整数应该被调整为 −231 ，大于 231 − 1 的整数应该被调整为 231 − 1
4.去掉无用的后导空格；
牛客题目链接
思路
按照转换要求一步步处理；
- 首先遍历过滤掉前面的空格；
- 判断当前字符是否为"+“或”-"，用于记录数据的正负值，记得移动下标；
- 遍历获取每个字符对应的数字累加，并且过程中需要判断是否满足在32 位有符号整数范围内；
- 返回最终结果；
代码实现
public int StrToInt (String s) {
int len = s.length();
if(len == 0){
return 0;
}
int sign = 1;
long num = 0;
int i = 0;
//先跳过若干个空格
while( i < len && s.charAt(i)== ' '){
i++;
}
//判断第一位符号位是正数还是负数
if(i < len){
if(s.charAt(i) == '-'){
sign = -1;
i++;
}else if(s.charAt(i) == '+'){
i++;
}
}
//取出数字部分，判断大小是否越界以及计算结果
while(i < len){
if(s.charAt(i) >= '0' && s.charAt(i) <= '9'){
int temp = s.charAt(i) - '0';
num = num * 10 + temp;
if(sign == 1 && num > Integer.MAX_VALUE){
return Integer.MAX_VALUE;
}else if(sign == -1 && -num < Integer.MIN_VALUE){
return Integer.MIN_VALUE;
}
i++;
} else{
break;
}
}
if(sign == 1){
return (int)num;
}else{
return (int)-num;
}
表示数值的字符串
题目
描述
请实现一个函数用来判断字符串str是否表示数值（包括科学计数法的数字，小数和整数）。
科学计数法的数字(按顺序）可以分成以下几个部分:
1.若干空格
2.一个整数或者小数
3.（可选）一个 ‘e’ 或 ‘E’ ，后面跟着一个整数(可正可负)
4.若干空格
小数（按顺序）可以分成以下几个部分：
1.若干空格
2.（可选）一个符号字符（‘+’ 或 ‘-’）
3. 可能是以下描述格式之一:
3.1 至少一位数字，后面跟着一个点 ‘.’
3.2 至少一位数字，后面跟着一个点 ‘.’ ，后面再跟着至少一位数字
3.3 一个点 ‘.’ ，后面跟着至少一位数字
4.若干空格
整数（按顺序）可以分成以下几个部分：
1.若干空格
2.（可选）一个符号字符（‘+’ 或 ‘-’)
3. 至少一位数字
4.若干空格
例如，字符串[“+100”,“5e2”,“-123”,“3.1416”,“-1E-16”]都表示数值。
但是[“12e”,“1a3.14”,“1.2.3”,“±5”,“12e+4.3”]都不是数值。
牛客题目链接
思路
不需要思路，就是一堆判断直接干，静下心，耐住性子就可以搞定；
代码实现
自由发挥
public boolean isNumeric (String str) {
if (str == null || str.length() == 0) {
return false;
}
//去除字符串中的所有空格
String res = str.replaceAll(" ", "");
if (res.length() == 0) {
return false;
}
if (res.contains("e") || res.contains("E")) {
//当前可能是科学计数法
return isENum(res);
} else if (res.contains(".")) {
//当前可能是小数
return isNodeNum(res);
} else {
//当前可能是整数
return isCommonNum(res);
}
}
private boolean isENum(String res) {
if (res == null || res.length() == 0) {
return false;
}
res = res.toUpperCase();
if (res.charAt(res.length() - 1) == 'E') {
return false;
}
String[] split = res.split("E");
if (split.length != 2) {
return false;
}
return (isCommonNum(split[0]) || isNodeNum(split[0])) &&
(isCommonNum(split[1]));
}
private boolean isCommonNum(String res) {
if (res == null || res.length() == 0) {
return false;
}
if (res.charAt(0) == '+' || res.charAt(0) == '-') {
res = res.substring(1, res.length());
}
if (res.length() == 0) {
return false;
}
for (int i = 0 ; i < res.length(); i++) {
if (res.charAt(i) < '0' || res.charAt(i) > '9') {
return false;
}
}
return true;
}
private boolean isNodeNum(String res) {
if (res == null || res.length() == 0 || ".".equals(res)) {
return false;
}
int nodeNum = 0;
for (int i = 0 ; i < res.length(); i++) {
if (res.charAt(i) == '.') {
if (nodeNum == 1) {
return false;
} else {
nodeNum++;
}
}
}
String[] split = res.split("\\.");
if (split.length == 1) {
return (isCommonNum(split[0]) || "".equals(split[0]));
}
boolean isSign = "".equals(split[0]) || "+".equals(split[0]) || "-".equals(split[0]);
return (isCommonNum(split[0]) || isSign) &&
(isCommonNum(split[1]) || "".equals(split[1]));
}
