Android 每日算法：猫扑素数、单词反转

经典算法集锦，不定时更新

一、素数（质数）算法

• 定义：

质数（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);
}