01-常见算法

选择排序  
冒泡排序 
折半查找  

斐波那契数列 
水仙花数  
杨辉三角  
交换二个数的三种方法  

模拟一个栈  
二进制中一个数的相反数的表示 

2^n-1的二进制特点是：所有位数都为1

一.排序

1.选择排序

    private static void selectSort(int[] targetArr){
        for(int i=0; i<targetArr.length-1;i++){
            for(int j=i+1; j<targetArr.length; j++){
                if (targetArr[i]>targetArr[j]) {
                    int temp = targetArr[i];
                    targetArr[i] = targetArr[j];
                    targetArr[j] = temp;
                }
            }
        }
    }

2.冒泡排序

    private static void bubbleSort(int[] targetArr){
        for(int i=0;i<targetArr.length;i++){
            for(int j=0;j<targetArr.length-1-i;j++){
                if (targetArr[j]>targetArr[j+1]) {
                    int temp = targetArr[j];
                    targetArr[j] = targetArr[j+1];
                    targetArr[j+1] = temp;
                }
            }
        }
    }

3.折半查找

    /**
     * 折半查找：查找目标元素在已经去重排序的数组当中的位置索引，如果没有查找到返回-1
     * 折半查找传入的数组是要求已经排序的
     * @param target
     * @param arr
     * @return
     */
    private static int halfSearch(int target, int[] arr){
        int start = 0;
        int end = arr.length;
        while(start<end){
            int midIndex = (start+end)/2;
            if (target==arr[midIndex]) {
                return midIndex;
            }else if(target<arr[midIndex]){
                end = midIndex;
            }else {
                start = midIndex;
            }
        }
        return -1;
    }

二.斐波那契数列 （又称兔子数列）

    /**
     * 输出指定n的斐波那契数组
     * @param fnArr 
     * @param n
     * @return result
     */
    private static int[] fibonacciSequeue(int[] fnArr, int n){
        if (n<=0) {
            throw new IllegalArgumentException("参数错误：n必须是大于0的整数");
        }
        if (fnArr==null) {
            fnArr = new int[n];
        }
        int fn;
        if (n==1||n==2) {
            fn = 1;
        }else {
            fn=fibonacciSequeue(fnArr, n-1)[n-2]+fibonacciSequeue(fnArr, n-2)[n-3];
        }
        fnArr[n-1]=fn;
        return fnArr;
    }

三.求出水仙花数

    /**
     * 求出水仙花数
     * 水仙花数：个位、十位、百位 各位数的立方和等于自身的三位数
     */

    private static void narcissisticNumber(){
        for(int i=100; i<1000; i++){
            int ge = i%10;
            int shi = i/10%10;
            int bai = i/10/10;
            if (ge*ge*ge+shi*shi*shi+bai*bai*bai==i) {
                System.out.println(i);
            }
        }
    }

四.杨辉三角

    /**
     * 输出杨辉三角的第n行
     * @param n
     * @return
     */
    private static int[] pascalTriangle(int n){
        if (n<0) {
            throw new IllegalArgumentException("参数错误：n必须是大于0的整数");
        }
        int[] arr = new int[n];
        if (n==1) {
            arr[0]=1;
        }else if(n==2){
            arr[0]=1;
            arr[1]=1;
        }else{
            arr[0]=1;
            arr[n-1]=1;
            int [] tempArr = pascalTriangle(n-1);
            for(int i=0; i<tempArr.length-1; i++){
                arr[i+1]=tempArr[i]+tempArr[i+1];
            }
        }
        return arr;
    }

五.交换二个数

    public class SwapTwoNum {
        static int a =15;
        static int b =20;

        public static void main(String[] args) {
            method1();
            System.out.println("method1----->a="+a+",b="+b);

            method2();
            System.out.println("method2----->a="+a+",b="+b);

            method3();
            System.out.println("method3----->a="+a+",b="+b);
        }
        /**
         * 不使用中间变量
         */
        private static void method2(){
            a = a+b;
            b = a-b;
            a = a-b;
        }
        /**
         * 使用中间变量
         */
        private static void method1( ){
            int temp =a;
            a = b;
            b = temp;
        }
        /**
         * 不使用中间变量，效率最高，位运算
         */
        private static void method3( ){
            a = a^b;
            b = a^b;
            a = a^b;
        }
    }

六.模拟一个栈

    /**
     * 模拟栈
     * @author lqs
     */
    public class MockStack {
        LinkedList<Object> list = new LinkedList<>();
        /**
         * 压栈
         * @param obj
         * @return
         */
        public Object push(Object obj){
            list.add(obj);
            return obj;
        }
        /**
         * 弹栈
         * @return
         */
        public Object pop(){
            return list.removeLast();
        }
        /**
         * 获取栈顶的但不移除
         * @return
         */
        public Object peek(){
            return list.getLast();
        }
        public int size(){
            return list.size();
        }
        public boolean isEmpty(){
            return list==null? true:list.size()<0;
        }
        public int search(Object obj) {
            int index = list.lastIndexOf(obj);
            if (index >= 0) {
                return size() - index;
            }
            return -1;
        }
        public static void main(String[] args) {
            MockStack mockStack = new MockStack();
            mockStack.push(1);
            mockStack.push(2);
            mockStack.push(3);
            mockStack.push(4);
            mockStack.push(5);
            System.out.println(mockStack.pop());
            System.out.println("size="+mockStack.size());

            System.out.println(mockStack.pop());
            System.out.println("size="+mockStack.size());

            System.out.println(mockStack.pop());
            System.out.println("size="+mockStack.size());

            System.out.println(mockStack.pop());
            System.out.println("size="+mockStack.size());
        }
    }

七. 求一个数的相反数

八. 2^n-1的二进制特点是：从低到高位有值 位数都为1

例如：

2^2=4    2^2-1=3    二进制为    00000011  
2^3=8    2^3-1=7    二进制为    00000111  
2^4=16  2^4-1=15 二进制为 00001111