牛客剑指offer刷题模拟篇

顺时针打印矩阵

题目

描述
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下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
牛客题目链接

思路

我们主要分析以下几种情况

1. 只有一行的时候，我们只需要遍历打印即可；
2. 只有一列的时候，我们同样只需要遍历打印即可；
3. 对于多行多列的情况，我们需要按照规定的顺序进行打印；

代码实现

    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副扑克牌，从扑克牌中随机五张扑克牌，我们需要来判断一下是不是顺子。
有如下规则：

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(nlogn)，本题也有时间复杂度 O(n) 的解法；
牛客题目链接

思路

根据题目，我们可以分析出顺子需要满足以下两个条件：

1. 顺子中的非零牌最大数和最小数相差不超过4；
2. 顺子中的非零牌不能有重复数字；
   对于重复数字判断，我们可以采用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.去掉无用的后导空格；
牛客题目链接

思路

按照转换要求一步步处理；

1. 首先遍历过滤掉前面的空格；
2. 判断当前字符是否为"+“或”-"，用于记录数据的正负值，记得移动下标；
3. 遍历获取每个字符对应的数字累加，并且过程中需要判断是否满足在32 位有符号整数范围内；
4. 返回最终结果；

代码实现

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]));}