摘要
一、模拟算法原理与解题方法
二、模拟算法练习题目
2.1 顺时针打印矩阵
解题思路:
递归的思想和非递归的思想相差不大,递归是首先打印最外层的元素,将内层的矩阵作为一个全新的矩阵进行递归。对于每层,从左上方开始以顺时针的顺序遍历所有元素。假设当前层的左上角位于 (top,left),右下角位于(bottom,right),按照如下顺序遍历当前层的元素。
1、从左到右遍历上侧元素,依次为(top,left) 到(top,right)。
2、从上到下遍历右侧元素,依次为(top+1,right) 到 (bottom,right)。
3、如果 left<right 且top<bottom,则从右到左遍历下侧元素,依次为(bottom,right−1) 到 (bottom,left+1),以及从下 到上遍历左侧元素,依次为(bottom,left) 到(top+1,left)。
遍历完当前层的元素之后,将left 和top 分别增加 1,将 right 和 bottom 分别减少 11,进入下一次递归,直到遍历完所有元素为止。
package 模拟算法;
import java.util.ArrayList;
/**
* @Classname JZ29顺时针打印矩阵
* @Description TODO
* @Date 2022/2/5 13:46
* @Created by xjl
*/
public class JZ29顺时针打印矩阵 {
ArrayList<Integer> res = new ArrayList<>();
public ArrayList<Integer> printMatrix(int[][] matrix) {
if (matrix == null || matrix.length == 0) {
return res;
}
int m = matrix.length;
int n = matrix[0].length;
print(0, n - 1, 0, m - 1, matrix);
return res;
}
public void print(int left, int right, int top, int bottom, int[][] matrix) {
// 从左到右
for (int i = left; i <= right; i++) {
res.add(matrix[top][i]);
}
// 下一层
top++;
if (left > right || top > bottom) {
return;
}
// 从上到下
for (int i = top; i <= bottom; i++) {
res.add(matrix[i][right]);
}
right--;
if (left > right || top > bottom) {
return;
}
// 从右到左
for (int i = right; i >= left; i--) {
res.add(matrix[bottom][i]);
}
bottom--;
if (left > right || top > bottom) {
return;
}
// 从下到上
for (int i = bottom; i >= top; i--) {
res.add(matrix[i][left]);
}
left++;
// 递归
print(left, right, top, bottom, matrix);
}
}
2.2 扑克牌的顺子
1. 除0外没有重复的数
2. max - min < 5
package 模拟算法;
import org.junit.Test;
import java.util.Arrays;
/**
* @Classname JZ61扑克牌顺子
* @Description TODO
* @Date 2022/2/5 15:53
* @Created by xjl
*/
public class JZ61扑克牌顺子 {
/**
* @description 判断什么是顺子
* 1 除0外没有重复的数据
* <p>
* 2 max - min < 5
* @param: numbers
* @date: 2022/2/5 15:59
* @return: boolean
* @author: xjl
*/
public boolean IsContinuous(int[] numbers) {
Arrays.sort(numbers);
int index = 0;
while (numbers[index] == 0) {
index++;
}
for (int i = index + 1; i < numbers.length; i++) {
if (numbers[i] == numbers[i - 1]) {
return false;
}
}
if (numbers[numbers.length - 1] - numbers[index] > 4) {
return false;
}
return true;
}
@Test
public void test() {
int[] array={3,0,0,0,0};
boolean b = IsContinuous(array);
}
}
2.3 把字符转换为整数
package 模拟算法;
/**
* @Classname JZ67把字符串转换成整数
* @Description TODO
* @Date 2022/2/5 16:20
* @Created by xjl
*/
public class JZ67把字符串转换成整数 {
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,表明为负数
sign = -1;
i++;//定位到下一个字符
} else if (s.charAt(i) == '+') {
//第一个非空格字符是正号
i++;
}
}
//非正负号,则进入下面while循环的处理
while (i < len) {
if (s.charAt(i) >= '0' && s.charAt(i) <= '9') {
num = num * 10 + (s.charAt(i) - '0');
if (sign == -1 && num * (-1) < Integer.MIN_VALUE) {
return Integer.MIN_VALUE;
}
/*
* 注意如果上面与逻辑后写的是num>(-1)*Integer.MIN_VALUE,结果是错的,经测试(-1)*Integer.MIN_VALUE结果
* 仍为Integer.MIN_VALUE,原因溢出
*/
else if (sign == 1 && num > Integer.MAX_VALUE) {
return Integer.MAX_VALUE;
}
i++;
} else {
break;//不是有效数字}
}
}
int res = (int) num;//返回值要求是int,所以需要做一个强制类型转换
res *= sign;//带上它的符号
return res;
}
}
2.4 表示数值的字符串
package 模拟算法;
import org.junit.Test;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
/**
* @Classname JZ20表示数值的字符串
* @Description TODO
* @Date 2022/2/5 17:08
* @Created by xjl
*/
public class JZ20表示数值的字符串 {
public boolean isNumeric(String str) {
if (str.indexOf('.') != str.lastIndexOf('.')) {
return false;
}
String pattern = "^\\s*[+-]?[.]?\\d+([.]\\d*)?([Ee][+-]?\\d+)?\\s*$";
Pattern p = Pattern.compile(pattern);
Matcher matcher = p.matcher(str);
return matcher.matches();
}
public boolean isNumeric2(String str) {
if (str == "e") {
return false;
}
try {
Float.valueOf(str);
} catch (Exception e) {
return false;
}
return true;
}
@Test
public void test() {
boolean numeric = isNumeric("123.45e+6");
System.out.println(numeric);
}
}