常见算法

介绍

开发以及平常阅读中所遇到的算法总结

猫扑素数(Mop primes)

名词解释

• 素数: 即质数,有无限个. 质数定义为在大于1的自然数中,除了1和它本身以外不在有其他因数
• 猫扑素数: 形如以2开头,之后跟任意多个3的十进制整数并且是素数,则它就是猫扑素数. 如 2, 23, 233, 2333, 23333都是猫扑素数. 而233333则不是,它可以分解为353 x 661

代码实现

	public class Dmeo {
    public static void main(String[] args) {
        for (int i = 0; i < 1000000000; i++) {
            if (isMop(i)) {
                if (isPrimes(i)) {
                    System.out.printlnln(i);
                }
            }
        }
    }
//判断是否是2333...的猫扑数
    public static Boolean isMop(int num) {
        if (num < 10) return num == 2;
        else return num % 10 == 3 && isMop(num / 10); //递归检测
    }

// 判断是否是素数
    public static Boolean isPrimes(int num) {
        if (num < 2) { //素数不能小于2
            return false;
        } else {
		//只需要判断到Math.sqrt(num),因为y= x1 * x2,那么x1或者x2中一定有一个数小于√y. 
            for (int i = 2; i < Math.sqrt(num); i++) {
                if (num % i == 0)  //可以被整除,所以不是素数
                    return false;
            }
        }
        return true;
    }
}

输出结果:
	2
	23
	233
	2333
	23333

冒泡排序

名词解释

• 冒泡排序: 重复的走访要排序的数列,一次比较两个相邻的元素,如果他们的顺序错误,就把他们交换过来.直到不在需要交换即排序完成

代码

	public class Dmeo {
    public static void main(String[] args) {
        int[] arr = {23, 44, 12, 3, 5, 66, 9};
        bubbleSort(arr);
        System.out.printlnln(Arrays.toString(arr));
    }

    //冒泡排序
    public static void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) { // 外层控制趟数
            for (int j = 0; j < arr.length - 1 - i; j++) { //内增循环控制每趟排多少次
                if (arr[j] > arr[j + 1]) { //如果前一位大于后一位则交换(可控制升序降序)
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
}
输出结果:
[3, 5, 9, 12, 23, 44, 66]

选择排序

名词解释

• 选择排序:每一次从待排序的数据元素中选取最小(或最大)的一个元素,存放在序列的起始位置(或者末端位置),知道全部排序的数据元素排完

代码实现

//选择排序
   public static void bubbleSort(int[] arr) {
       for (int i = 0; i < arr.length - 1; i++) {
           for (int j = i + 1; j < arr.length; j++) {
               if (arr[j] < arr[i]) {
                   int temp = arr[i];
                   arr[i] = arr[j];
                   arr[j] = temp;
               }
           }
       }
   }

斐波那契数列(兔子数列)

名词解释

• 菲波那切数列指的是这样一个数列: 1,1,2,3,5,8,13,21,34…

代码实现

//递归实现
public int FibonacciSequence(int month){
	if(month<=2){
		return 1;
	}else{
	return FibonacciSequence(n-1) + FibonacciSequence(n-2);
	}
}

//递推方式实现
public  int FibonacciSequence2(int month) {
        if (month <= 2) {
            return 1;
        }
        int month1 = 1, month2 = 1, sum = 0;
        for (int i = 0; i < month - 2; i++) {
            sum = month1 + month2;
            month1 = month2;
            month2 = sum;
        }
        return sum;
    }

水仙花数

名词解释

• 水仙花数是指一个三位数,其各位数字的立方和等于该数本身.例如153是一个”水仙花”数,因为153 = 1³+5³+3³;

代码实现

public static boolean isNarcissusNumber(int num) {
        if (num < 100 || num > 999) return false;
        int geWei = num % 10;
        int shiWei = (num % 100) / 10;
        int baiWei = num / 100;
        int sum = (geWei * geWei * geWei) + (shiWei * shiWei * shiWei) + (baiWei * baiWei * baiWei);
        return sum == num;
    }

二叉树以及相关算法

二叉树是每个节点最多有两个子树的树结构. 通常子树被称为”左子树”(left subtree) 和”右子树”(right subtree).二叉树常被用于实现二叉查找树和二叉堆.

树

树是n个结点组成的有限集合T,当n=0时称为空树.任一非空树满足以下两个条件

• 有且只有一个特定的结点,称为跟结点;
• 其余的结点分成m(m>=0)个互不相交的有限集合T1,T2,…Tm,其中每个集合又都是一颗树 称为根结点的子树.

根为第一层,根的孩子在第2层一次类推,若某结点在第i层,则其孩子结点在第i+1层.一个树最大的层次数称为树的高度或深度.

术语

• 结点的度: 一个结点的子树数目称为该结点的度(次数)
• 树的度:树中各结点度的最大值称为该树的度
• 叶子结点: 度为0的结点称为叶子结点
• 分支结点: 除叶子以外的结点称为分支结点
• 内部结点: 除根结点和叶子结点以外的结点称为内部结点

树的遍历

前序遍历

首先访问根节点,然后从左到右按前序遍历跟结点的各棵子树.亦称先序(先根)遍历

图1 前序遍历的结果为: 1,2,5,6,7,8,3,4,9,a,b

层次遍历

自上而下,从左到右逐层访问树种各层次上的结点

图1 层次遍历的结果为: 1,2,3,4,5,6,7,8,9,a,b

后序遍历

首先从左到右按后序遍历根结点的各棵子树,然后访问根结点.亦称后序遍历

图1 后序遍历的结果为: 5,6,7,8,2,3,a,b,9,4,1

二叉树

二叉树是一个有限的结点集合,该集合或者为空,或者有一个跟结点及其两棵互不相交的分别称为左右子树的二叉树所组成.二叉树有递归性质,有严格的顺序,左右不能颠倒.有5种基本形态

• 空二叉树
• 只有根的二叉树
• 右子树为空的二叉树
• 左右子树均为空的二叉树
• 左子树为空的二叉树

性质

• 在二叉树的第i层至多有2^(i-1)个结点 (i>=1)
• 深度为k的二叉树至多有2^{k - 1}个结点(k>=1)
• 对于任何一棵二叉树,如果其叶子结点数为n₀,度为2的结点数为n₂,则n₀ = n₂ + 1 ,推导如下:

设二叉树中度为1的结点的个数为n₁,总节点数为n,那么显然有n=n₀ + n₁ + n₂,

除了跟结点外其余结点均有连线射入,设连线数为B,显然n = B+1.而这些连线是从度为1或为2的结点射出的,所以又有B = n₂+ 2n₂.

根据这两个等式便可得出结论 n₀ = n₂ +1

• 具有n个结点的完全二叉树的深度为[㏒₂n] +1 (注:[m]表示不大于m的最大整数,如[4] = 4,[4.1] = 4,[4.9] =4,也称为向下取整)

一棵深度为k且有2^k - 1个结点的二叉树称为满二叉树,这种树各层均是满的. 第1层至倒数第2层各层均满,最后一层的结点连续紧挨靠左的二叉树称为完全二叉树.可见满二叉树是完全二叉树的特例

• 如果对一棵有n个结点的完全二叉树的结点按自上而下,从左到右的顺序编号,则对应任一结点i(1<= i <= n),有

  1. 如果i = 1,则结点i无双亲,是二叉树的根; 如果i>1,则其双亲结点为[i/2]

  2. 如果2i>n,则结点i为叶子结点,无左孩子;否则,其做左孩子为2i.

  3. 如果2i + 1 > n,则该结点无右孩子; 否则,其右孩子为2i + 1

二叉树的遍历

java定义结点如下

public class Node {
	public int value;
	public Node left;
	public Node right;
	public Node(int value){
		this.value = value
	}
}

前序遍历(先根遍历,先序遍历):

首先访问根节点然后按前序遍历根结点的左子树,再按前序遍历根结点的右子树.图2的遍历顺序:1,2,4,5,7,8,3,6
代码如下:

public void preOrder(Node node){
	if(null != node){
		System.out.println(node.value);//先输出根结点
		preOrder(node.left); //在输出左边
		preOrder(node.right); // 在输出右边	
	}
}

中序遍历(中根遍历):

首先按中序遍历根结点的左子树,然后访问根结点,再按中序遍历根结点的右子树.图2的遍历顺序为:4,2,7,8,5,1,3,6

public void middleOrder(Node node){
	if(null != node){
		middleOrder(node.left); // 先输出左边
		System.out.println(node.value); // 输出根节点
		middleOrder(node.right); //输出右边	
	}
}

后序遍历:

首先按后序遍历跟结点的左子树,然后后序遍历根节点的右子树,再访问根结点.图2的遍历顺序为:4,8,7,5,2,6,3,1

public void afterOrder(Node node){
	if(null != node){
		afterOrder(node.left);//先输出左边
		afterOrder(node.right);//再输出右边
		System.out.println(node.value);//再输出根节点
	}
}

层次遍历:

根树遍历一样.图2的遍历顺序为:1,2,3,4,5,6,7,8

public void levelOrder(Node node){
	if (null == node) return;
	LinkedList<Node> list = new LinkedList<>();
	list.add(node);
	Node currentNode;
	while(!list.isEmpty()){printlnln
		currentNode = list.poll();
		System.out.println(currentNode.value);
		if(null != currentNode.left){
			list.add(currentNode.left);
		}
		if(null != currentNode.right){
			list.add(currentNode.right);
		}
	}
}