常用算法的总结

分治

在排序算法中，快速排序和归并排血都用到了分治的思想，所谓分治就是分而治之，再利用递归，将一份比较大的任务分成若干个小任务去完成。

快速排序

快速排序，采用了挖坑填坑的方法来完成每一趟排序，每一次小排序后都会分成左边一组和右边一组，分别小于和大于一个分界数（一般是数组第一个数字）再分别对这两组进行排序。相当于对左右两组分而置之，直到完成排序。

adjustarray(每一趟排序的函数)

private static int adjustarray(int[] array,int l,int r) {
  int i=l;//l和r分别是数组的左指针和右指针
  int j=r;//将其赋给i，j，进行指针的移动
  while(i<j){
  while(i<j && array[j]>=array[l]){
      j--;
  }
  if(i<j){
      array[i]=array[j];
      i++;
  }//先是右指针向左移动找到比临界值小的数，填入上一个坑中
  while(i<j && array[i]<=array[l]){
      i++;
  }
  if(i<j){
      array[j]=array[i];
      j--;
  }//接着左指针向右移动找到比临界值大的数，填入上一个坑中
  
  }    
  array[j]=array[l];//最后把临界值的数填入i=j也就是临街位置的坑中，该值不会再改变
  return i;
}

接下来是quick_sort的主调用函数

quick_sort

prviate static void quick_sort(int[] array,int l,int r) {
  if(l<r){
  int mid = adjustarray(array,l,r);
  for(int i=0;i<r;i++){
      System.out.print(array[i]+" ");
  }
  System.out.println();
  quick_sort(array,l,mid-1);
  quick_sort(array,mid+1,r);
  }
  //这个函数就是分治思想的函数，思想明白了这个函数也就没有什么不能理解的了
}

归并排序

归并排序是先分再和的思想，其重点和难点是在和（merge）的函数上，对一趟数组，先将其按中间数字的数值等分为左右两部分，比其小的在左，大的在右（从小到大的顺序），直到其为一个数字，相对有序之后，接着进行合并，将数组两两形成有序数组。

merge操作

private static void merge(int[] array,int l,int mid,int r){
  int temp[] = new int[r-l+1];//创建一个临时数组用来承接两个数组合并后的结果
  int i=l;
  int j=mid+1;
  while(i<=mid && j<=r){//比较左右两个数组元素大小，按大小顺序重新排序在临时数组中
      if(array[i]<array[j]){
              temp[k++] = array[i++];
          }
          else{
              temp[k++] = array[j++];
          }
  }
      while(i<=mid){
          temp[k++] = array[i++];
      }
      while(j<=r){
          temp[k++] = array[j++];      
      }
      for(int k1 = 0 ; k1<temp.length;k1++){//将数组还给ararry
          array[k1+l] = temp[k1];
      }
}

接下来是主调用函数依然是采用了分治的思想

merge_sort

private static void merge_sort(int[] array, int l, int r) {
  int mid = (l+r)/2;
  if(l<r){//分治思想
  merge_sort(array,l,mid);//将左边有序（直到一个元素）
  merge_sort(array,mid+1,r);//使右边有序（直到一个元素）
  merge(array,l,mid,r);//合并
  }
}

动态规划

跳石板问题 && 背包问题

跳石板问题：

小易来到了一条石板路前，每块石板上从1挨着编号为：1、2、3……. 这条石板路要根据特殊的规则才能前进：对于小易当前所在的编号为K的石板，小易单次只能往前跳K的一个约数(不含1和K)步，即跳到K+X(X为K的一个非1和本身的约数)的位置。小易当前处在编号为N的石板，他想跳到编号恰好为M的石板去，小易想知道最少需要跳跃几次可以到达。例如： N = 4，M = 24： 4->6->8->12->18->24 于是小易最少需要跳跃5次，就可以从4号石板跳到24号石板输入描述: 输入为一行，有两个整数N，M，以空格隔开。 (4 ≤ N ≤ 100000) (N ≤ M ≤ 100000)

输出描述: 输出小易最少需要跳跃的步数,如果不能到达输出-1

输入例子: 4 24

输出例子: 5

这道题可以采用动态规划的思想,规划的量是从起点到每一个点的最小的距离。因为每一个点往前前进的步数只能是他的约数，那么到下一个点为这个点加上他的一个约数，所以从起点到这个点的最短距离就是取上个点的最小距离+1 或者是到这个点的最小距离中的最小值。每个点的最短距离设为dp[i] x为i的约数那么 dp【i+x】 = Math.min(dp[i+x],dp[i]+1)

跳石板问题

 public static void main(String[] args) {
      Scanner scanner = new Scanner(System.in);
      while(scanner.hasNext()){
          int from = scanner.nextInt();
          int to = scanner.nextInt();
          int result = calresult(from,to);
          System.out.println(result);
      }
 } 

  private static int calresult(int from, int to) {
      if(from == to){
          return 0;
      }
      int[] dp = new int[to-from+1]; //将规划的量存为dp数组内
      int step = to-from+1;
      dp[0] = 0;                       
      for(int i=1;i<step;i++){
          dp[i] = Integer.MAX_VALUE;
      }
      for(int i=0;i<step;i++){
          if(dp[i] == Integer.MAX_VALUE){
              dp[i]=0; 
              continue;
          }
          
          ArrayList<Integer> list = getyinshu(i + from);//求因数的函数
          
          for (int j = 0; j < list.size(); j++) {
                int x = list.get(j);
              if(i+from+x<=to){
                  dp[i+x] = Math.min(dp[i+x], dp[i]+1);//整个算法的关键，将这个语句弄懂这个算法显得十分简单              
              }
          }
          
      }
      if(dp[to-from] == 0){
          return -1;
      }else{
          return dp[to-from];
      }
  }
  private static ArrayList<Integer> getyinshu(int num) {//求因数的函数
      ArrayList<Integer> list = new ArrayList<Integer>();
      for(int i=2;i<=Math.sqrt(num);i++){
          if(num%i==0){
              list.add(i);
              if(num/i!=i){//注意这里在写程序的时候出错了，排除其平方数的情况
                  list.add(num/i);
              }
          }
          
      }
      return list;
  }

背包问题

题目描述：

有编号分别为a,b,c,d,e的五件物品，它们的重量分别是2,2,6,5,4，它们的价值分别是6,3,5,4,6，现在给你个承重为10的背包，如何让背包里装入的物品具有最大的价值总和？

Algo

分治