一些算法题记录

手写一个二分查找的代码
```
    public static int findNum(Integer[] nums, int num) {
    int left = 0;
    int right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == num) {
            return mid;
        } else if (nums[mid] < num) {
            left = mid + 1;
        } else if (nums[mid] > num) {
            right = mid - 1;
        }
    }
    return -1;
}
```
首先这个数组参数必须是一个长度不为0的数组.
1. 为什么right 要等于长度减一
  答:如果不减一会出现下标越界.
2. 为什么while循环中left<=right
  答: 因为right 等于数组长度减1 ,那么数组的查询范围是可以等于最右边的数据
3. 为什么要写 left + (right - left) / 2, 不写 (left+right)/2?
  答:当数组长度过大的时候,避免字节类型溢出,比如当left和right 数字非常大超过了 int 的数字类型 ( Integer.MAX_VALUE) 这个时候,返回的数据就不是int类型的数据格式能接受的,如有疑问,看上一个题.
4. 为什么要用if /else 这个几个判断类型
  答: 如果nums[mid]=num 那么就直接返回mid,如果nums[mid] < num那么就把查询范围向右移动一位(因为数组是有序的,小于目标值,说明查询范围在更右边的位置) 同理下一个else if 如果> 目标值,说明查询范围在往左的范围,那么就需要把right 往左挪动一位. 最后直到不符合while条件以后,说明没查询到目标值,就直接返回-1就可以了.

求 1!+2!+3!+4!+····+n!=?

public static long factorial(int num) {
  long sum=0;
  long init=1;
  for (int i = 1; i <= num; i++) {
     init= init*i;
     sum+=init;
  }
  return sum;
}

选择排序

    public static void main(String[] args) {
        int [] nums={12,12,312,41,31,4231212,1,112,312,12,1324,3434};
        selectionSort(nums);
        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i]+" ");
        }
        System.out.println("");
        // 结果
        //  1 12 12 12 31 41 112 312 312 1324 3434 4231212
    }


    
    public static void selectionSort(int[] nums) {
        int length = nums.length;
        if (nums == null || length < 2) {
            return;
        }
        for (int i = 0; i < length; i++) {
            // 判断当前位的数据是否比其他位置的数大
            // 1. 获取当前数位置
            int currentNumIndex = i;
            for (int j = i + 1; j < length; j++) {
                // 判断当前的这个数是否比下一个数小 ，如果是 则返回下一个数的下标 否则返回当前的下标
                currentNumIndex = nums[j] < nums[currentNumIndex] ? j : currentNumIndex;
            }
            //根据返回的下标和当前的下标进行交换
            swap(nums, i, currentNumIndex);
        }

    }

    
    private static void swap(int[] nums, int j, int currentNumIndex) {
        int temp = nums[j];
        nums[j] = nums[currentNumIndex];
        nums[currentNumIndex] = temp;
    }

冒泡排序

    public static void bubbleSort(int[] nums) {
        // 冒泡排序是不停的比较相邻两位数的值，然后进行交换 当数组最后一位值固定时，
        // 排序的区间搜索到0～n.length-2、0～n.length-3以此类推
        int length = nums.length;
        if (nums == null || length < 2) {
            return;
        }
        // 这里从最后一位开始循环的目的是找到最大的值，先放在最后，缩小下次的循环范围
        for (int i = length-1; i >=0; i--) {
            for (int second = 1; second <=i; second++) {
                // 从后往前固定值的大小后，最后位的数据则不用再循环
                if (nums[second-1]>nums[second]) {
                    swap(nums,second-1,second);
                }
            }
        }
    }

选择排序和冒泡排序的区别, 选择排序是找到一个位置然后跨越很多位置进行交换 ,冒泡排序是两个相邻的数据交换

插入排序

 public static void insterSort(int[] nums) {
        int length = nums.length;
        if (nums == null || length < 2) {
            return;
        }
        // 从数组的第二个开始排序，因为0-0 位置已经是有序的了
        // 插入排序的快捷理解 就像斗地主的时候，当手上已经整理好顺序的牌的时候，
        // 再摸上来一张牌，需要向前面的牌一张一张的往前挪动
        for (int i = 1; i < length; i++) {
            // 当j和j+1的位置交换以后  j-- 那么现在j 的位置就减少1 了，
            // 所以要判断是否大于等于0 ，并且当前下标的值大于 j+1的值
            for (int j = i - 1; j >= 0 && nums[j] > nums[j + 1]; j--) {
                swap(nums, j, j + 1);
            }
        }
    }

一些算法题记录

Java相关栏目本月热门文章