Sort

package com.example.demo.lagou.sort;


/**
 * 功能描述 1：斐波那契数列
 * 斐波那契数列是：0，1，1，2，3，5，8，13，21，34，55，89，144……。你会发现，这个数列中元素的性质
 * 是，某个数等于它前面两个数的和；也就是 a[n+2] = a[n+1] + a[n]。至于起始两个元素，则分别为 0 和 1。在这个
 * 数列中的数字，就被称为斐波那契数。
 * 【题目】写一个函数，输入 x，输出斐波那契数列中第 x 位的元素。例如，输入 4，输出 2；输入 9，输出 21。要
 * 求：需要用递归的方式来实现。
 *
 * 那么，如何使用递归呢？我们需要依赖斐波那契数列的重要性质“某个数等于它前面两个数的和”。
 * 也就是说，求出某个位置 x 的数字，需要先求出 x-1 的位置的值和 x-2 的位置的值。
 * 递归同时还需要终止条件，对应于斐波那契数列的性质，就是起始两个元素，分别为 0 和 1
 *
 * @since 2022-05-12
 */
public class FibonacciFunctionDemo {

    public static void main(String[] args) {
     //   int x = 20;
        System.out.println(fun(4));
        System.out.println(fun(9));
    }

    public static int fun(int n ) {

        if (n == 1) {
            return 0;
        }
        if(n == 2) {
            return 1;
        }
        // 3 = 2 + 1 = (3 - 1) + (3 - 2)
        return fun(n-1) + fun(n-2);
    }
}

package com.example.demo.lagou.sort;

import java.util.Arrays;

/**
 * 功能描述 插入排序的原理
 * 选取未排序的元素，插入到已排序区间的合适位置，直到未排序区间为空。插入排序顾名思义，就是从左到右维护
 * 一个已经排好序的序列。直到所有的待排数据全都完成插入的动作。
 *
 * @since 2022-05-12
 */
public class InsertSortDemo {

    public static void main(String[] args) {
        int[] arr1 = {1, 0, 3, 4, 5, -6, 37, 28, 19, 10};
        insertSort(arr1);
        int[] arr2 = {10, 9, 8, 7, 6, 4, 2, 0, -2, -4};
        insertSort(arr2);
    }

    private static void insertSort(int[] arr ) {

        System.out.println("原始数据：" + Arrays.toString(arr));
        // 从第2个数开始循环
        for (int i = 1; i < arr.length; i++) {
            System.out.println("第 " + i + " 轮排序，循环：" + i + "次");
            // 取第i个数作为临时变量
            int temp = arr[i];
            // 需要循环比较的次数
            int j = i - 1;
            // 维护一个从小到大的序列
            for (; j  >= 0; j--) {
                // 如果当前数大于临时变量，则交换
                System.out.println("  临时变量：" + temp);
                if (arr[j] > temp) {
                    System.out.println("  交换前：" + arr[j] + " -> " + arr[j + 1]);
                    arr[j + 1] = arr[j];
                    System.out.println("  交换后， arr[j + 1]：" + arr[j + 1]);
                } else {
                    break;
                }
            }
            // 把临时变量赋值给临时变量的前一个数arr[j + 1]
            arr[j + 1] = temp;

            System.out.println("  临时变量赋值给：arr[j + 1] , (j+1)为：" + (j + 1) + ";temp: " + temp);

            System.out.println("第 " + i + " 轮排序后的结果：" + Arrays.toString(arr));
        }
        System.out.println("冒泡排序的最终结果：" + Arrays.toString(arr));
    }
}

package com.example.demo.lagou.sort;

import java.util.Arrays;

/**
 * 功能描述 归并排序的原理
 * 归并排序的原理其实就是我们上一课时讲的分治法。它首先将数组不断地二分，直到最后每个部分只包含 1 个数
 * 据。然后再对每个部分分别进行排序，最后将排序好的相邻的两部分合并在一起，这样整个数组就有序了。
 *
 * @since 2022-05-12
 */
public class MergeSortDemo {

    public static void main(String[] args) {
        int[] arr1 = {49, 38, 65, 97, 76, 13, 27, 50};
        System.out.println("归并排序的原始数据：" + Arrays.toString(arr1));
        customMergeSort(arr1, 0, arr1.length - 1);
        System.out.println("归并排序的最终结果：" + Arrays.toString(arr1));
        // int[] arr2 = {10, 9, 8, 7, 6, 4, 2, 0, -2, -4};
        // customMergeSort(arr2);
    }

    /**
     *
     * @param a 数组
     * @param start
     * @param end
     */
    public static void customMergeSort(int[] a, int start, int end) {
        System.out.println("当前数组状态1：" + Arrays.toString(a));
        if (start < end) {
            int mid = (start + end) / 2;
            // 对左侧子序列进行递归排序
            customMergeSort(a, start, mid);
            // 对右侧子序列进行递归排序
            customMergeSort(a, mid + 1, end);
            // 合并
            customDoubleMerge(a, start, mid, end);
        }
    }

    public static void customDoubleMerge(int[] a, int left, int mid, int right) {
        System.out.println("  当前数组状态2：" + Arrays.toString(a));
        int[] tmp = new int[a.length];
        int p1 = left, p2 = mid + 1, k = left;
        while (p1 <= mid && p2 <= right) {
            if (a[p1] <= a[p2]) {
                tmp[k++] = a[p1++];
            } else {
                tmp[k++] = a[p2++];
            }
        }
        while (p1 <= mid) {
            tmp[k++] = a[p1++];
        }
        while (p2 <= right) {
            tmp[k++] = a[p2++];
        }

        // 复制回原数组
        for (int i = left; i <= right; i++) {
            a[i] = tmp[i];
        }

    }

    private static void customMergeSort(int[] arr) {

        System.out.println("原始数据：" + Arrays.toString(arr));
        // 从第2个数开始循环
        for (int i = 1; i < arr.length; i++) {
            System.out.println("第 " + i + " 轮排序，循环：" + i + "次");
            // 取第i个数作为临时变量
            int temp = arr[i];
            // 需要循环比较的次数
            int j = i - 1;
            // 维护一个从小到大的序列
            for (; j >= 0; j--) {
                // 如果当前数大于临时变量，则交换
                System.out.println("  临时变量：" + temp);
                if (arr[j] > temp) {
                    System.out.println("  交换前：" + arr[j] + " -> " + arr[j + 1]);
                    arr[j + 1] = arr[j];
                    System.out.println("  交换后， arr[j + 1]：" + arr[j + 1]);
                } else {
                    break;
                }
            }
            // 把临时变量赋值给临时变量的前一个数arr[j + 1]
            arr[j + 1] = temp;

            System.out.println("  临时变量赋值给：arr[j + 1] , (j+1)为：" + (j + 1) + ";temp: " + temp);

            System.out.println("第 " + i + " 轮排序后的结果：" + Arrays.toString(arr));
        }
        System.out.println("冒泡排序的最终结果：" + Arrays.toString(arr));
    }
}

package com.example.demo.lagou.sort;

import java.util.Arrays;

/**
 * 功能描述 冒泡排序的原理
 * 从第一个数据开始，依次比较【相邻元素】的大小。如果前者大于后者，则进行交换操作，把大的元素往后交换。
 * 通过多轮迭代，直到没有交换操作为止。
 *
 * @since 2022-05-12
 */
public class PopSortDemo {

    public static void main(String[] args) {
        int[] arr1 = {1, 0, 3, 4, 5, -6, 37, 28, 19, 10};
        pop(arr1);
        int[] arr2 = {10, 9, 8, 7, 6, 4, 2, 0, -2, -4};
        pop(arr2);
    }

    private static void pop(int[] arr ) {

        System.out.println("原始数据：" + Arrays.toString(arr));
        // 从第2个数开始循环
        for (int i = 1; i < arr.length; i++) {
            System.out.println("第 " + i + " 轮排序，循环：" + (arr.length - i) + "次");
            // 第i个数循环比较第i个之后的所有数，最大的数放到了最后，并且左边的数一定比右边相邻的数小
            for (int j = 0; j < arr.length - i; j++) {
                // 如果当前数大于后面的数，则交换
                if (arr[j] > arr[j + 1]) {
                    System.out.println("  交换前：" + arr[j] + " -> " + arr[j + 1]);
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    System.out.println("  交换后：" + arr[j] + " -> " + arr[j + 1]);
                }
            }
            System.out.println("第 " + i + " 轮排序后的结果：" + Arrays.toString(arr));
        }
        System.out.println("冒泡排序的最终结果：" + Arrays.toString(arr));
    }
}

package com.example.demo.lagou.leetcode;

import java.util.Arrays;

/**
 * 功能描述
 *
 * @since 2022-05-12
 */
public class LC001 {

    public static int[] twoSum(int[] nums, int target) {
        int index1 = 0;
        int index2 = 0;
        boolean find = false;
        for (int i = 0; i < nums.length; i++) {
            if (!find) {
                int left = nums[i];
                index1 = i;
                for (int j = i + 1; j < nums.length; j++) {
                    int sum = left + nums[j];
                    if (sum == target) {
                        index2 = j;
                        find = true;
                        break;
                    }
                }
            }

        }
        int[] result = {index1, index2};
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {3, 2, 3};
        int target = 6;
        System.out.println(Arrays.toString(twoSum(nums, target)));

    }
}