算法题汇总

骑猪看日落 2022-10-07 05:52 165阅读 0赞

# 1.冒泡排序 #

[https://juejin.cn/post/6948814177179795487][https_juejin.cn_post_6948814177179795487]

private static void bubbleSort(int[] arr) {
            // 最外层控制冒泡的轮数 n个数只需要n-1趟即可
            for (int i = 0; i < arr.length - 1; i++) {
                /**
                 * 里面内层依次比较,替换
                 * arr.length-i因为每一次排序都会将最大值放到最后,所以排序完i轮，就说明i个数已经排序好了，就不需要再比较，替换
                 * arr.length-1因为我们是使用下标j元素和j+1元素比较，防止下标越界
                 */
                for (int j = 0; j < arr.length - i - 1; j++) {
                    if (arr[j] > arr[j+1]) {
                        int temp = arr[j+1];
                        arr[j+1] = arr[j];
                        arr[j] = temp;
                    }
                }
            }
        }
    
    
    private static void bubbleSort(int[] arr) {
            if (arr == null || arr.length < 2) {
                return;
            }
            //开辟一个新的空间,存放交换的中间值
            int temp = 0;
            //设置一个标志位
            boolean flag = false;
            //用来记录最后一次交换的位置
            int pos = 0;
            int k = arr.length - 1;
            /**
             * 外层冒泡的轮数
             * 因为有arr.length个数组元素,所以只需要比较arr.length-1轮
             */
            for (int i = 0; i < arr.length - 1; i++) {
                pos = 0;
                flag = false;
    
                System.out.format("第 %d 轮:\n", i + 1);
                for (int j = 0; j < k; j++) {
                    /**
                     * 判断下标j和下标j+1的大小
                     * 当我们改变下标j和j+1判断的符号为<,就会从大到小排序
                     */
                    if (arr[j] > arr[j + 1]) {
                        /**
                         * 当j的值大于j+1的值,交换j和j+1
                         * 则比较大的值放到后面
                         */
                        temp = arr[j];
                        arr[j] = arr[j + 1];
                        arr[j + 1] = temp;
    
                        //发生交换,标志位修改为true
                        flag = true;
                        //记录最后一次交换的位置
                        pos = j;
    
                    }
                    System.out.format("第 %d 轮的第 %d 次交换：", i + 1, j + 1);
                    System.out.format(Arrays.toString(arr));
                    System.out.println("");
                }
                System.out.format("第 %d 轮最终结果：", i + 1);
                System.out.format(Arrays.toString(arr));
                System.out.println("\n#########################");
    
                //如果某一轮,没有交换元素,说明已经有序
                if (!flag) {
                    return;
                }
                //下一次比较到记录位置即可
                k = pos;
            }
        }

# 2.快速排序 #

[https://juejin.cn/post/6844903640340267022][https_juejin.cn_post_6844903640340267022]

public static void quickSort(int[] a, int low, int high) {
            if (low < high) {
                // partition方法对序列进行排序
                int partition = partition(a, low, high);
                // 分割两个序列继续进行快排操作
                quickSort(a, low, partition - 1);
                quickSort(a, partition+1, high);
            }
        }
    
        public static int partition(int[] a, int low, int high) {
            // 取每个序列的第一个值作为基准值
            int pivot = a[low];
    
            while (low < high) {
                // 从序列的右边开始往左遍历，直到找到小于基准值的元素
                while (low < high && a[high] >= pivot) {
                    high--;
                }
    
                // 将元素直接赋予给左边第一个，即pivotkey所在的位置
                a[low] = a[high];
    
                // 从序列的左边边开始往右遍历，直到找到大于基准值的元素
                while (low < high && a[low] <= pivot) {
                    low++;
                }
    
                //此时的a[high]<pivotkey,已经被赋予到左边，所以可以将元素赋予给a[high]
                a[high] = a[low];
            }
    
            // 最后的low是基准值所在的位置
            a[low] = pivot;
            // 返回基准值所在的索引位置
            return low;
        }

# 3.二分查找 #

// 非递归
        public int search(int[] array, int target) {
            int low = 0;
            int high = array.length - 1;
            /**
             * 这里为什么要用小于等于
             * 如果数组个数是奇数个，并且查找目标元素正好是最后一个 while循环条件如果是小于
             * 那么使用二分查找无法判断最后一个元素
             * 例如 search(new int[]{0, 1, 2, 3, 4}, 4)通过debug可以验证
             */
            while (low <= high) {
                int mid = low + (high - low) / 2;
    
                if (target == array[mid]) {
                    return mid;
                } else if (array[mid] > target) {
                    high = mid -1;
                } else if (array[mid] < target) {
                   low = mid + 1;
                }
            }
            return -1;
        }

# 算法 求二叉树根节点到指定节点的路径 #

[https://blog.csdn.net/qq\_41512783/article/details/109516464][https_blog.csdn.net_qq_41512783_article_details_109516464]

public static boolean getPathToTarget(TreeNode node, TreeNode target, LinkedList<TreeNode> path) {
            if (node == null) {
                return false;
            }
    
            if (node == target) {
                return true;
            }
            path.push(node);
    
            if (getPathToTarget(node.left, target, path)) {
                return true;
            }
    
            if (getPathToTarget(node.right, target, path)) {
                return false;
            }
    
            // 需要在递归查找过程中进行回溯，pop 这些不需要的节点
            path.pop();
            return false;
        }

[https_juejin.cn_post_6948814177179795487]: https://juejin.cn/post/6948814177179795487
[https_juejin.cn_post_6844903640340267022]: https://juejin.cn/post/6844903640340267022
[https_blog.csdn.net_qq_41512783_article_details_109516464]: https://blog.csdn.net/qq_41512783/article/details/109516464