1. 打印从1到最大的n位数

  • 输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999


  1. 输入: n = 1
  2. 输出: [1,2,3,4,5,6,7,8,9]

思路:

  • 使用java的Math工具类，将n位数-1的int型算出来
  • 以上述计算出来的整数作为长度初始化一个数组作为返回结果
  • for循环i将这个数组填充i+1
class Solution {
    public int[] printNumbers(int n) {
        int num = (int)Math.pow(10,n)-1;
        int[] arr = new int[num];
        for(int i=0;i<arr.length;i++){
            arr[i] = i+1;
        }
        return arr;
    }
}

2. 快速排序（运用递归思想）

思路：（这里以顺序排列为例）

  • 找到中间位置 mid = （left + right）/ 2，获取arr[mid]作为中间值pivot
  • 根据 mid 进行左右递归
    • 左边从左向右扫描，当扫描到一个大于pivot值停止
    • 右边从右向左扫描，当扫描到一个小于pivot值停止
    • 创建一个辅助int变量进行对这两个位置的值进行交换
  • 如果此时左指针 l 与右指针 r 值相等，左指针右移，右指针左移

  • 如果leftl, 向右递归；

      public static void quickSort(int[] arr,int left,int right){
      int l = left;
      int r = right;
      int pivot = arr[(left+right)/2];
      int temp;

      while(l<r){
          while(arr[l]<pivot) l++;
          while(arr[r]>pivot) r--;
          if (l>=r) break;
          temp = arr[l];
          arr[l] = arr[r];
          arr[r] = temp;
          if (arr[l] == pivot) r--;
          if (arr[r] == pivot) l++;
      }
      if (l==r){
          l++;
          r--;
      }
      if (left<r) quickSort(arr,left,r);
      if (right>l) quickSort(arr,l,right);
  }

3. 归并排序（运用递归思想）

思路：（这里以顺序排列为例）

  • “分” 与 “治” 的处理
  • 分， 将一个整体数组进行拆解，先从中间位置mid = （left+right）/ 2 分为（left，mid） 和 （mid+1，right）
  • 治，从两个整体出发（left，mid） 和 （mid+1，right），使用两个指针i，j进行从左向右扫描；边扫描边进行比较，小的放入辅助数组temp（与arr数组长度相同）中；比较完毕后，将两个整体部分剩余的全部放入temp；最后从temp中复制到arr中
    public static void mergeSort(int[] arr,int left,int right,int[] temp){
        // 保证最终分到单个时停止
        if (left<right){
            int mid = (left+right)/2;
            mergeSort(arr,left,mid,temp);
            mergeSort(arr,mid+1,right,temp);
            merge(arr,left,mid,right,temp);
        }
    }

    public static void merge(int[] arr,int left,int mid,int right,int[] temp){
        int i = left;
        int j = mid + 1;
        int t = 0;
        // 第一步: 通过i,j扫描,比较分出来两个部分的元素大小;将小的放入到temp辅助数组中
        while(i<=mid && j<=right){
            if (arr[i] <= arr[j]){
                temp[t] = arr[i];
                i++;
            } else {
                temp[t] = arr[j];
                j++;
            }
            t++;
        }
        // 第二步: 将剩余部分全部放入temp中
        while(i<=mid){
            temp[t] = arr[i];
            i++;
            t++;
        }
        while(j<=right){
            temp[t] = arr[j];
            j++;
            t++;
        }
        // 第三步: 拷贝temp数组到arr中
        t = 0;
        int tempLeft = left;
        while(tempLeft<=right){
            arr[tempLeft] = temp[t];
            t++;
            tempLeft++;
        }
    }