經(jīng)典算法集錦舌菜，不定時(shí)更新
一萌壳、素?cái)?shù)（質(zhì)數(shù)）算法
- 定義：
質(zhì)數(shù)（prime number）又稱素?cái)?shù)，有無限個(gè)日月。質(zhì)數(shù)定義為在大于1的自然數(shù)中袱瓮，除了1和它本身以外不再有其他因數(shù)。
一個(gè)大于1的自然數(shù)爱咬，除了1和它自身外尺借，不能被其他自然數(shù)整除的數(shù)叫做質(zhì)數(shù)；否則稱為合數(shù)精拟。
- Tip：
質(zhì)數(shù)的定義在大于1的自然數(shù)中燎斩，所以1不是虱歪，而2是質(zhì)數(shù)。
素?cái)?shù)算法.png
1.1 計(jì)算某整數(shù)內(nèi)的素?cái)?shù)
- 計(jì)算方式1（效率較低）：遍歷整數(shù) i 瘫里，從2開始到 i -1 实蔽，是否可以被比其小的整數(shù)整除。
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){ //如果能被整除谨读，則這個(gè)數(shù)不是素?cái)?shù)
isPrime = false;
break; //不是素?cái)?shù)直接跳出循環(huán)
}
}
if(isPrime){
mAnswerText.append("\t"+i);
}
isPrime = true;
}
}
}
- 計(jì)算方式2（效率較高）：
在一般領(lǐng)域局装，對正整數(shù)n，如果用2到根號n之間的所有整數(shù)去除劳殖，均無法整除铐尚，則n為質(zhì)數(shù)。
// 開平方根哆姻，遍歷所有小于平方根的數(shù)
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 貓撲素?cái)?shù)
- 貓撲數(shù)定義：
指以2開頭宣增，后面跟任意個(gè)3的十進(jìn)制數(shù)。如：2矛缨、23爹脾、233等。
- 貓撲素?cái)?shù)定義：
同時(shí)滿足貓撲數(shù)和素?cái)?shù)兩個(gè)條件的數(shù)箕昭。貓撲素?cái)?shù)既是素?cái)?shù)又是貓撲數(shù)灵妨。
- 計(jì)算貓撲素?cái)?shù)
（1）遍歷整數(shù)并添加條件
private void isPrime233(int num){
for(int i = 0; i <= num; i++){
if(isMopNumber(i) && isPrime3(i))
mAnswerText.append("\t"+i);
}
}
（2）判斷是否為貓撲數(shù)：
private boolean isMopNumber(int num){
if(num < 10){
// 判斷除以10以后的整數(shù)是否為2，也就是首位數(shù)字
return num == 2;
} else {
// 很巧妙的算法落竹，根據(jù)貓撲數(shù)特點(diǎn)：最開頭是2泌霍，后面是任意個(gè)3，利用遞歸進(jìn)行判斷
// 先判定一個(gè)數(shù)除以10余數(shù)是否為3
return (num % 10 == 3) && isMopNumber (num / 10);
}
}
（3）判斷是否為素?cái)?shù)：
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;
}
}
同事滿足以上兩項(xiàng)條件則為貓撲素?cái)?shù)述召。
二朱转、反轉(zhuǎn)算法（單詞和句子）
反轉(zhuǎn)算法.png
2.1 反轉(zhuǎn)句子
public static String reverseSentence(String sentence){
// 把句子按照空格來分割成單詞數(shù)組
String[] arr = sentence.split(" ");
int length = arr.length;
// StringBuilder線程不安全但是單線程操作效率更高
StringBuilder sb = new StringBuilder();
// 倒序循環(huán)使用StringBuilder拼接，記得拼接空格
for(int i = length-1; i >= 0; i--){
sb.append(arr[i]).append(" ");
}
return "原單詞為："+sentence+"\n反轉(zhuǎn)后為："+sb.toString();
}
2.2 反轉(zhuǎn)一串單詞
- 遞歸實(shí)現(xiàn)
public static String reverseWords1(String s){
int length = s.length();
if(length <= 1){
return s;
}
// substring截取字符串积暖，包括第一個(gè)下標(biāo)不包括第二個(gè)下標(biāo)
String left = s.substring(0,length/2);
String right = s.substring(length/2,length);
// 調(diào)用遞歸先逐個(gè)拼接右邊的
return reverseWords1(right)+reverseWords1(left);
}
- 倒序循環(huán)
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();
}
- 轉(zhuǎn)換字符數(shù)組
public static String reverseWords3(String s){
// 轉(zhuǎn)換為字符數(shù)組
char[] array = s.toCharArray();
String reverse = "";
for (int i = array.length-1; i>=0; i--){
reverse += array[i];
}
return reverse;
}
- StringBuffer和StringBuilder內(nèi)置reverse方法
public static String reverseWords4(String s){
// 利用StringBuilder的reverse方法藤为，StringBuffer同樣有此方法
return new StringBuilder(s).reverse().toString();
}
- 臨時(shí)變量交換
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);
}
- 利用棧結(jié)構(gòu)
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()返回棧頂元素的同時(shí)刪除棧頂元素
// empty()檢查棧是否為空夺刑，search()返回元素在堆棧的位置
for (int i = 0; i < arr.length; i++){
reversed += stack.pop();
}
return reversed;
}
三凉蜂、其它
3.1 從字符串提取數(shù)字
public void GetNumberFromString(View view){
String s = "1 92.168. 0. 1";
// 使用正則匹配數(shù)字
Pattern pattern = Pattern.compile("[^0-9]");
Matcher matcher = pattern.matcher(s);
String r = matcher.replaceAll("").trim();
Log.i("Result",r);
}
