1、爬楼梯问题

一个台阶总共有n 级，如果一次可以跳1 级，也可以跳2 级，求总共有多少种跳法。

• 如果只有1 级台阶，那显然只有一种跳法；
• 如果有2 级台阶，那就有两种跳的方法了：一种是分两次跳，每次跳1 级；另外一种就是一次跳2 级。
• 当台阶数>2 级时，第一次跳的时候就有两种不同的选择：一种是 第一次只跳1 级，此时跳法数目等于后面剩下的n-1 级台阶的跳法数目，即为f(n-1)；另外一种选择是第一次跳2 级，此时跳法数目等于后面剩下的n-2 级台阶的跳法数目，即为f(n-2)。 所以，n 级台阶时的不同跳法的总数 f(n) = f(n-1) + f(n-2)。
  　　 　　/ 1 　　　　　 (n=1)
  　　即：f(n) = 2 　　　　 (n=2)
  　　 　　 \ f(n-1) + (f-2) (n>2)
  其实，这就是Fibonacci 序列。算法复杂度为：(O(n))。

/**
 * 爬楼梯问题: 实质就是斐波那契数列.
 * 
 * @author X-knight
 *
 */
public class ClimbTheStairs {
    int total;

    // 递归调用
    public int fib01(int n) {
        if (n == 1 || n == 2)
            total = n;
        else
            total = fib01(n - 2) + fib01(n - 1);
        return total;
    }

    // 三目运算符
    public int fib02(int n) {
        return (n == 1 || n == 2) ? n : fib02(n - 2) + fib02(n - 1);
    }

    // 备忘录法
    public int dfs(int n, int[] array) {
        if (array[n] != 0) {
            return array[n];
        } else {
            array[n] = dfs(n - 1, array) + dfs(n - 2, array);
            return array[n];
        }
    }

    public int fib03(int n) {
        if (n == 0) {
            return 1;
        }
        if (n == 1 || n == 2) {
            return n;
        } else {
            int[] array = new int[n + 1];
            array[1] = 1;
            array[2] = 2;
            return dfs(n, array);
        }
    }

    // 动态规划法 (利用数组来存储)
    public int fib04(int n) {
        if (n == 0)
            return 1;
        int[] array = new int[n + 1];
        array[0] = 1;
        array[1] = 1;
        for (int i = 2; i <= n; i++) {
            array[i] = array[i - 1] + array[i - 2];
        }
        return array[n];
    }

    // 状态压缩法(又称滚动数组、滑动窗口，用于优化动态规划法的空间复杂度)
    public int fib05(int n) {
        if (n == 1 || n == 0)
            return 1;
        n = n - 1;
        int result = 0;
        int zero = 1;
        int first = 1;
        while (n > 0) {
            result = zero + first;
            zero = first;
            first = result;
            n--;
        }
        return result;
    }

}

一个台阶总共有n 级，如果一次最多可以跳n级，求总共有多少种跳法。
解析：f(n) = f(n-1) + f(n-2) + f(n-3) + ... + f(n-(n-1)) + f(n-n)
f(n-1) = f(0) + f(1)+f(2)+f(3) + ... + f((n-1)-1) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2)
f(n) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2) + f(n-1) = f(n-1) + f(n-1)
可以得出：
f(n) = 2*f(n-1)

2、有n个人围成一圈，顺序排号。从第一个人开始报数（从1到3报数），凡报到3的人退出圈子，问最后留下的是原来第几号的那位？

boolean[] per = new boolean[p];// boolean数组表示站成一圈的人，false表示退出
for (int i = 0; i < per.length; i++) {
    per[i] = true;
}
int t = 0, len = per.length;
while (len > 1) {
    for (int i = 0; i < per.length; i++) {
       if (per[i]) {
          t++;
          if (t == 3) {
               t = 0;
               per[i] = false;
               len--;
          }
       }
    }
 }

3、排序算法 image.png

• 快速排序

 public static void quickSort(int[] arr,int low,int high){
        int i,j,temp,t;
        if(low>high){
            return;
        }
        i=low;
        j=high;
        //temp就是基准位
        temp = arr[low];
 
        while (i<j) {
            //先看右边，依次往左递减
            while (temp<=arr[j]&&i<j) {
                j--;
            }
            //再看左边，依次往右递增
            while (temp>=arr[i]&&i<j) {
                i++;
            }
            //如果满足条件则交换
            if (i<j) {
                t = arr[j];
                arr[j] = arr[i];
                arr[i] = t;
            }
 
        }
        //最后将基准为与i和j相等位置的数字交换
         arr[low] = arr[i];
         arr[i] = temp;
        //递归调用左半数组
        quickSort(arr, low, j-1);
        //递归调用右半数组
        quickSort(arr, j+1, high);
    }

• 冒泡排序

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;
　　　　　　　　}
　　　　　　}
　　　　} 

• 插入排序

public static void InsertSort(int[] arr)
{
    int i, j;
    int n = arr.Length;
    int target;
 
    //假定第一个元素被放到了正确的位置上
    //这样，仅需遍历1 - n-1
    for (i = 1; i < n; i++)
    {
        j = i;
        target = arr[i];
 
        while (j > 0 && target < arr[j - 1])
        {
            arr[j] = arr[j - 1];
            j--;
        }
 
        arr[j] = target;
    }
}

• 选择排序

public void chooseSort(){
        for(int i=0; i<length-1; i++){
            int minIndex = i;
            for(int j=minIndex+1;j<length;j++){
                if(array[j]<array[minIndex]){
                    minIndex = j;
                }
            }
            int temp = array[i];
            array[i] = array[minIndex];
            array[minIndex] = temp; 
        }
    }

• 希尔排序
  image.png
• 堆排序
  每个节点的值都大于或等于其左右孩子节点的值称为大顶堆；相反称为小顶堆。 image.png
  一般升序采用大顶堆，降序采用小顶堆。
• 归并排序

public static int[] sort(int[] a,int low,int high){
        int mid = (low+high)/2;
        if(low<high){
            sort(a,low,mid);
            sort(a,mid+1,high);
            //左右归并
            merge(a,low,mid,high);
        }
        return a;
    }
     
    public static void merge(int[] a, int low, int mid, int high) {
        int[] temp = new int[high-low+1];
        int i= low;
        int j = mid+1;
        int k=0;
        // 把较小的数先移到新数组中
        while(i<=mid && j<=high){
            if(a[i]<a[j]){
                temp[k++] = a[i++];
            }else{
                temp[k++] = a[j++];
            }
        }
        // 把左边剩余的数移入数组 
        while(i<=mid){
            temp[k++] = a[i++];
        }
        // 把右边边剩余的数移入数组
        while(j<=high){
            temp[k++] = a[j++];
        }
        // 把新数组中的数覆盖nums数组
        for(int x=0;x<temp.length;x++){
            a[x+low] = temp[x];
        }
    }

4、二分查找

public static int recursionBinarySearch(int[] arr,int key,int low,int high){
        
        if(key < arr[low] || key > arr[high] || low > high){
            return -1;              
        }
        
        int middle = (low + high) / 2;          //初始中间位置
        if(arr[middle] > key){
            //比关键字大则关键字在左区域
            return recursionBinarySearch(arr, key, low, middle - 1);
        }else if(arr[middle] < key){
            //比关键字小则关键字在右区域
            return recursionBinarySearch(arr, key, middle + 1, high);
        }else {
            return middle;
        }   
}

public static int commonBinarySearch(int[] arr,int key){
        int low = 0;
        int high = arr.length - 1;
        int middle = 0;         //定义middle
        
        if(key < arr[low] || key > arr[high] || low > high){
            return -1;              
        }
        
        while(low <= high){
            middle = (low + high) / 2;
            if(arr[middle] > key){
                //比关键字大则关键字在左区域
                high = middle - 1;
            }else if(arr[middle] < key){
                //比关键字小则关键字在右区域
                low = middle + 1;
            }else{
                return middle;
            }
        }
        
        return -1;      //最后仍然没有找到，则返回-1
    }

5、给定一个整数数组，找出其中两个数相加等于目标值

public int[] sum(int[] numbers, int target) {
    HashMap<Integer,Integer> map = new HashMap<Integer, Integer>();
    for(int i = 0; i < numbers.length; i++)
       map.put(numbers[i], i+1);
    for(int i = 0; i < numbers.length; i++){
        int value = target - numbers[i];
        if(map.containsKey(value) && map.get(value) != i+1){
            int index = map.get(value) ;
            if(i+1 < index) 
                return new int[]{i+1, index};
            return new int[]{index, i+1}; 
        }
    }   
    return new int[0];
}

6、链表反转

public Node reverse(Node node) {
    Node prev = null;
    Node now = node;
    while (now != null) {
      Node next = now.next;
      now.next = prev;
      prev = now;
      now = next;
    }
    return prev;
  }

public Node reverse3(Node node) {
    if(node.next==null)return node;
    Node next = node.next;
    node.next = null;
    Node re = reverse3(next);
    next.next = node;
    return re;
  }

7、给定一个字符串 s，找到 s 中最长的回文子串。

   public String longestPalindrome(String s) {
        int curstart = 0;//current start 当前开始位置
        int curend = 0;//current end
        int current = 0;//current length 
        int max = 0;//最大的回文串长度
        int maxstart = 0;//最大的开始位置
        int len = s.length();
        int i = 0;
        for (i = 0; i < len; i++) {//从第i个位置开始向两面依次便利
            curstart = i;//假设回文串长度是奇数
            curend = i;//从第i个位置开始向两面依次便利
            while (curstart >= 00 && curend < len) {
                if (s.charAt(curstart) == s.charAt(curend)) {
                    curstart--;
                    curend++;
                } else
                    break;
            }
            current = curend - curstart - 1;//当前长度 
            if (current > max) {//替换最长回文串
                max = current;
                maxstart = curstart + 1;
            }
            curstart = i;//假设回文串长度是偶数数
            curend = i + 1;//从第i，i+1个位置开始向两面依次便利
            while (curstart >= 00 && curend < len) {
                if (s.charAt(curstart) == s.charAt(curend)) {
                    curstart--;
                    curend++;
                } else
                    break;
            }
            current = curend - curstart - 1;
            if (current > max) {
                max = current;
                maxstart = curstart + 1;
            }
        }
        String result = s.substring(maxstart, maxstart + max);
        return result;
    }