经典算法集锦，不定时更新
一、素数（质数）算法
- 定义：
质数（prime number）又称素数，有无限个。质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数。
一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数；否则称为合数。
- Tip：
质数的定义在大于1的自然数中，所以1不是，而2是质数。
素数算法.png
1.1 计算某整数内的素数
- 计算方式1（效率较低）：遍历整数 i ，从2开始到 i -1 ，是否可以被比其小的整数整除。
private void isPrime1(int n){
boolean isPrime = true;
if(n < 2){
return;
}else {
for (int i = 2;i <= n; i++){
for(int j = 2; j < i; j++){
if(i % j == 0){ //如果能被整除，则这个数不是素数
isPrime = false;
break; //不是素数直接跳出循环
}
}
if(isPrime){
mAnswerText.append("\t"+i);
}
isPrime = true;
}
}
}
- 计算方式2（效率较高）：
在一般领域，对正整数n，如果用2到根号n之间的所有整数去除，均无法整除，则n为质数。
// 开平方根，遍历所有小于平方根的数
private void isPrime2(int num){
boolean isPrime = true;
for(int i = 2; i <= num; i ++){
int temp = (int) Math.sqrt(num);
for (int j = 2; j <= temp; j++) {
if (i % j == 0) {
isPrime = false;
break;
}
isPrime = true;
}
if(isPrime){
mAnswerText.append("\t"+i);
}
isPrime = true;
}
}
1.2 猫扑素数
- 猫扑数定义：
指以2开头，后面跟任意个3的十进制数。如：2、23、233等。
- 猫扑素数定义：
同时满足猫扑数和素数两个条件的数。猫扑素数既是素数又是猫扑数。
- 计算猫扑素数
（1）遍历整数并添加条件
private void isPrime233(int num){
for(int i = 0; i <= num; i++){
if(isMopNumber(i) && isPrime3(i))
mAnswerText.append("\t"+i);
}
}
（2）判断是否为猫扑数：
private boolean isMopNumber(int num){
if(num < 10){
// 判断除以10以后的整数是否为2，也就是首位数字
return num == 2;
} else {
// 很巧妙的算法，根据猫扑数特点：最开头是2，后面是任意个3，利用递归进行判断
// 先判定一个数除以10余数是否为3
return (num % 10 == 3) && isMopNumber (num / 10);
}
}
（3）判断是否为素数：
private boolean isPrime3(int num){
if(num < 2){
return false;
} else {
for (int i = 2; i < Math.sqrt(num); i++){
if(num % i == 0){
return false;
}
}
return true;
}
}
同事满足以上两项条件则为猫扑素数。
二、反转算法（单词和句子）
反转算法.png
2.1 反转句子
public static String reverseSentence(String sentence){
// 把句子按照空格来分割成单词数组
String[] arr = sentence.split(" ");
int length = arr.length;
// StringBuilder线程不安全但是单线程操作效率更高
StringBuilder sb = new StringBuilder();
// 倒序循环使用StringBuilder拼接，记得拼接空格
for(int i = length-1; i >= 0; i--){
sb.append(arr[i]).append(" ");
}
return "原单词为："+sentence+"\n反转后为："+sb.toString();
}
2.2 反转一串单词
- 递归实现
public static String reverseWords1(String s){
int length = s.length();
if(length <= 1){
return s;
}
// substring截取字符串，包括第一个下标不包括第二个下标
String left = s.substring(0,length/2);
String right = s.substring(length/2,length);
// 调用递归先逐个拼接右边的
return reverseWords1(right)+reverseWords1(left);
}
- 倒序循环
public static String reverseWords2(String s){
int length = s.length();
StringBuilder sb = new StringBuilder();
for(int i = length-1; i>=0; i--){
sb.append(s.charAt(i));
}
return sb.toString();
}
- 转换字符数组
public static String reverseWords3(String s){
// 转换为字符数组
char[] array = s.toCharArray();
String reverse = "";
for (int i = array.length-1; i>=0; i--){
reverse += array[i];
}
return reverse;
}
- StringBuffer和StringBuilder内置reverse方法
public static String reverseWords4(String s){
// 利用StringBuilder的reverse方法，StringBuffer同样有此方法
return new StringBuilder(s).reverse().toString();
}
- 临时变量交换
public static String reverseWords5(String s){
char[] arr = s.toCharArray();
int length = arr.length - 1;
int halfLength = length / 2;
for (int i = 0; i <= halfLength; i++){
char temp = arr[i];
arr[i] = arr[length - i];
arr[length - i] = temp;
}
return new String(arr);
}
- 位异或交换
public static String reverseWords6(String s) {
char[] str = s.toCharArray();
int begin = 0;
int end = s.length() - 1;
while (begin < end) {
str[begin] = (char) (str[begin] ^ str[end]);
str[end] = (char) (str[begin] ^ str[end]);
str[begin] = (char) (str[end] ^ str[begin]);
begin++;
end--;
}
return new String(str);
}
- 利用栈结构
public static String reverseWords7(String s) {
char[] arr = s.toCharArray();
Stack<Character> stack = new Stack<>();
// push()在栈顶添加元素
for (int i = 0; i < arr.length; i++){
stack.push(arr[i]);
}
String reversed = "";
// peek()和pop()都是返回栈顶元素，但是peek()不会删除栈顶元素
// 而pop()返回栈顶元素的同时删除栈顶元素
// empty()检查栈是否为空，search()返回元素在堆栈的位置
for (int i = 0; i < arr.length; i++){
reversed += stack.pop();
}
return reversed;
}
三、其它
3.1 从字符串提取数字
public void GetNumberFromString(View view){
String s = "1 92.168. 0. 1";
// 使用正则匹配数字
Pattern pattern = Pattern.compile("[^0-9]");
Matcher matcher = pattern.matcher(s);
String r = matcher.replaceAll("").trim();
Log.i("Result",r);
}
