嗯..! 2020 年 05 月 共 3 篇日志。 继续努力。

常见算法总结 - 二叉树篇

本文总结了常见高频的关于二叉树的算法考察。

1.计算一个给定二叉树的叶子节点数目。

可以采用递归的方式进行累加

public static int calculateTreeNodeNumber(TreeNode treeNode) {

        if (treeNode == null) {
            return 0;
        }

        return calculateTreeNodeNumber(treeNode.left) + calculateTreeNodeNumber(treeNode.right) + 1;

}

2.计算二叉树的深度。

跟上题一样采用递归的方式,但需返回左右子树中较深的深度。

public static int getTreeDepth(TreeNode tree) {

        if (tree == null) {
            return 0;
        }

        int left = getTreeDepth(tree.left);
        int right = getTreeDepth(tree.right);

        return left >= right ? left + 1 : right + 1;
}

阅读全文 »

常见算法总结 - 排序篇

本文总结了常见高频的关于排序的算法考察。

1.冒泡排序

冒泡排序的思想是元素两两比较,将较大或者较小的元素往一端进行移动

 public static void bubble(int[] array) {

        for (int i = 0; i < array.length - 1; i++) {

            for (int j = 0; j + 1 < array.length - i; j++) {

                if (array[j] > array[j + 1]) {

                    int tmp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = tmp;

                }

            }

        }

}

阅读全文 »

常见算法总结 - 链表篇

本文总结了常见高频的关于链表的算法考察。

1.如何找到链表的中间元素?

我们可以采用快慢指针的思想,使用步长为1的慢指针和步长为2的快指针,当快指针抵达链表末尾时,此时慢指针指向的即为中点位置。


public static LinkNode findMiddleByPointer(LinkNode node) {

    LinkNode slow = node;
    LinkNode fast = node;
    // 检测快指针是否可以安全移动
    while (fast.next != null && fast.next.next != null) {

        slow = slow.next;
        fast = fast.next.next;

    }

    return slow;

}

我们还可以采用递归的方式,当递归到最末尾的时候,我们已经能知道链表的长度,此时当递归回去的时候,判断当前递归层级等于链表长度一半的时候,即为链表的重点。

public static void findMiddleByRecursion(LinkNode node, int recursionIndex) {

        if (node.next != null) {
            findMiddleByRecursion(node.next, recursionIndex + 1);
        } else {
            middleIndex = recursionIndex % 2 == 0 ? recursionIndex / 2 : recursionIndex / 2 + 1;
        }

        if (middleIndex == recursionIndex) {
            System.out.println(node.value);
        }

        return;

    }
阅读全文 »