剑Java代码

Posted on | In

作者：白夜行的博客 博客地址：****https://blog.csdn.net/baiye_xing/

思路及代码实现
代码中用到的数据结构

  • 链表

    1
    2
    3
    4
    5
    6
    7
    public class ListNode {
        int val;
        ListNode next;
        ListNode(int val) {
            this.val = val;
        }
    }

  • 二叉树

    1
    2
    3
    4
    5
    6
    7
    8
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) {
            val = x;
        }
    }

赋值运算函数

思路：

  • 将返回值类型声明为该类型的引用

    在方法声明中，使用该类型作为方法的返回类型。例如：

    1
    2
    3
    4
    public MyClass getMyClass() {
        // 方法体
        return new MyClass();
    }

  • 把传入的参数类型声明为常量引用

    在方法声明中，使用final关键字来声明参数为常量引用。例如：

    1
    2
    3
    public void processInput(final String input) {
        // 方法体
    }

  • 释放实例自身已有的内存

    Java使用垃圾回收机制自动回收不再使用的内存。一般情况下，你不需要手动释放实例内存。当对象不再被引用时，垃圾回收器会自动回收它所占用的内存。

  • 判断传入的参数和当前的实例是不是同一个实例

    使用关键字this来引用当前实例，可以与传入的参数进行比较。例如：

    1
    2
    3
    public boolean isSameInstance(MyClass other) {
        return this == other;
    }

单例设计模式

题目描述：设计一个类，只能生成该类的一个实例。

思路：非线程安全与线程安全

代码实现：

• 线程安全的懒汉式：静态内部类

1
2
3
4
5
6
7
8
9
10
11
12
public class Singleton {
    private static class SingletonHodler {
        private static Singleton ourInstance = new Singleton();
    }

    public static Singleton getInstance() {
        return SingletonHodler.ourInstance;
    }

    private Singleton() {
    }
}

二维数组中查找目标值

题目描述：在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列

都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一

个整数，判断数组中是否含有该整数。

思路：从右上角或左下角开始找，逐行排除，或者用二分法查找

代码实现：

• 解法一：双指针，时间复杂度：O(mn)，空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static boolean find1(int[][] array, int target) {
    if (array == null || array.length == 0) {
        return false;
    }

    int row = 0;
    int column = array[0].length - 1;
    while (row < array.length && column >= 0) {
        if (array[row][column] == target) {
            return true;
        }
        if (array[row][column] > target) {
            column--;
        } else {
            row++;
        }
    }
    return false;
}

• 解法二：二分法，时间复杂度：O(log mn)，空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public boolean find2(int[][] array, int target) {
    if (array == null || array.length == 0) {
        return false;
    }

    int left = 0;
    int right = array.length * array[0].length - 1;
    int col = array[0].length;
    while (left <= right) {
        int mid = (left + right) / 2;
        int value = array[mid / col][mid % col];
        if (value == target) {
            return true;
        } else if (value < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return false;
}

替换字符串中的空格

从尾到头打印链表

由前序和中序遍历重建二叉树

用两个栈实现队列

求旋转数组的最小数字

斐波那契数列的应用

输出斐波那契数列的第 n 项

青蛙跳台阶(1 或 2 级)

小矩形无重叠覆盖大矩形

青蛙跳台阶(n 级)

二进制中 1 的个数

数值的整数次方

求 1 到最大的 n 位数

O(1)时间删除链表节点

将数组中的奇数放在偶数前

求链表中倒数第K个节点

输出反转后的链表

合并两个有序链表

判断二叉树A中是否包含子树B

二叉树的镜像

顺时针打印矩阵

包含 main 函数的栈

判断一个栈是否是另一个栈的弹出序列

层序遍历二叉树

后序遍历二叉搜索树

二叉树中和为某值的路径

复杂链表的复制

二叉搜索树转换为双向链表

打印字符串中所有字符的排列

数组中出现次数超过一半的数字

找出最小的 K 个数

连续子数组的最大和

从 1 到非负整数 n 中 1 出现的次数

把数组中的数排成一个最小的数

#求第 N 个丑数

第一个出现一次的字符

数组中逆序对的个数

两个链表的第一个公共节点

求某个数在数组中出现次数

二叉树的深度

求某个二叉树的深度

判断某二叉树是否是平衡二叉树

找出只出现一次的数字

整数序列的查找

和为 S 的连续整数序列

求两个乘积最小的数

字符串中字符的移动

反转字符串

将字符串循环左移 K 位

n 个骰子的点数及出现的概率

扑克牌的顺子

圆圈中最后剩下的数

求 1 到 n 的和

不用加减乘除做加法

不能被继承的类

将字符串转换为整数

树中两个节点的最低公共祖先

找出重复的数

构建乘积数组

正则表达式匹配

表示数值的字符串

字符流中第一个不重复的字符

链表中环的入口节点

删除链表中重复的节点

二叉树的下一个节点

对称的二叉树

按之字形顺序打印二叉树

把二叉树打印成多行

序列化二叉树

求二叉搜索树的第 K 小的节点

数据流中的中位数

滑动窗口的最大值

矩阵中的路径

机器人的运动范围