《剑指Offer》编程题目 Java 实现(01-10)

Author Avatar
wshunli 9月 11, 2018
  • 在其它设备中阅读本文章

《剑指Offer》编程题目 Java 实现,老是看书学习理论知识不太行,还得动手写代码啊。

笔试中的重要性不必多说,面试官还总是喜欢让手写代码。

1、赋值运算函数

2、单例设计模式

在设计模式中有详细的介绍,这里不再赘述,请移步:

https://www.wshunli.com/posts/d1c4534.html

3、二维数组中查找目标值

在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。

(1)直接暴力查找

public boolean Find(int target, int[][] array) {
    for (int[] anArray : array) {
        for (int anAnArray : anArray) {
            if (anAnArray == target) return true;
        }
    }
    return false;
}

(2)从右上角/左下角的元素出发

public boolean Find(int target, int[][] array) {
    int row = array.length;
    int col = array[0].length;
    for (int i = 0, j = col - 1; i < row && j >= 0; ) {
        int value = array[i][j];
        if (value == target) return true;
        if (value < target) i++;
        if (value > target) j--;
    }
    return false;
}

4、替换字符串中的空格

请实现一个函数,将一个字符串中的每个空格替换成 “%20” 。

public String replaceSpace(StringBuffer str) {
    return str.toString().replaceAll(" ", "%20");
}

这个太偷懒了,不那么偷懒:

public String replaceSpace(StringBuffer str) {
    StringBuilder builder = new StringBuilder();
    String string = str.toString();
    for (int i = 0; i < string.length(); i++) {
        char charAt = string.charAt(i);
        if (charAt == ' ') {
            builder.append("%20");
        } else {
            builder.append(charAt);
        }
    }
    return builder.toString();
}

5、从尾到头打印链表

输入一个链表,按链表值从尾到头的顺序返回一个 ArrayList 。

(1)借助堆栈的“后进先出”实现

/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*/
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
    Stack<Integer> integers = new Stack<>();
    while (listNode != null) {
        integers.push(listNode.val);
        listNode = listNode.next;
    }
    ArrayList<Integer> arrayList = new ArrayList<>();
    while (!integers.isEmpty()) {
        arrayList.add(integers.pop());
    }
    return arrayList;
}

(2)借助递归实现

ArrayList<Integer> arrayList = new ArrayList<>();
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
    if (listNode != null) {
        this.printListFromTailToHead(listNode.next);
        arrayList.add(listNode.val);
    }
    return arrayList;
}

(3)使用 Collections 的 reverse 方法

public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
    ArrayList<Integer> arrayList = new ArrayList<>();
    while (listNode != null) {
        arrayList.add(listNode.val);
        listNode = listNode.next;
    }
    Collections.reverse(arrayList);
    return arrayList;
}

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

7、用两个栈实现队列
8、求旋转数组的最小数字
9、斐波那契数列的第n项(青蛙跳台阶)
10、二进制中1的个数
11、数值的整数次方
12、打印1到最大的n位数
13、O(1)时间删除链表节点
14、使数组中的奇数位于偶数前面
15、找链表中倒数第K个节点
16、输出反转后的链表
17、合并两个有序链表
18、判断二叉树A中是否包含子树B
19、二叉树的镜像
20、顺时针打印矩阵
21、包含min函数的栈
22、判断一个栈是否是另一个栈的弹出序列
23、层序遍历二叉树
24、后序遍历二叉搜索树
25、二叉树中和为某值的路径
26、复杂链表的复制
27、二叉搜索树转换为双向链表
28、打印字符串中所有字符的排列
29、数组中出现次数超过一半的数字
30、找出最小的K个数
31、连续子数组的最大和
32、从1到整数n中1出现的次数
33、把数组中的数排成一个最小的数
34、求第N个丑数
35、第一个出现一次的字符
36、数组中逆序对的个数
37、两个链表的第一个公共节点
38、数字在排序数组中出现的次数
39、二叉树的深度
40、数组中只出现一次的两个数,而其他数都出现两次。
41、和为s的连续整数序列
42、翻转字符串
43、n个骰子的点数及出现的概率44. 扑克牌的顺子
44、圆圈中最后剩下的数
45、1+2+3+…+n的和
46、不用加减乘除做加法
47、不能被继承的类
48、字符串转换为整数
49、树中两个节点的最低公共祖先
50、找出重复的数
51、构建乘积数组
52、正则表达式匹配
53、表示数值的字符串
54、字符流中第一个不重复的字符
55、链表中环的入口节点
56、删除链表中重复的节点
57、二叉树的下一个节点
58、对称的二叉树
59、按之字形顺序打印二叉树
60、把二叉树打印成多行
61、序列化二叉树
62、二叉搜索树的第K个节点
63、数据流中的中位数
64、滑动窗口的最大值
65、矩阵中的路径
66、机器人的运动范围

参考资料
1、剑指Offer编程题牛客网
https://www.nowcoder.com/ta/coding-interviews
2、【剑指offer】Java版代码(完整版) - CSDN博客
https://blog.csdn.net/baiye_xing/article/details/78428561

如果本文对您有所帮助,且您手头还很宽裕,欢迎打赏赞助我,以支付网站服务器和域名费用。 https://paypal.me/wshunli 您的鼓励与支持是我更新的最大动力,我会铭记于心,倾于博客。
本文链接:https://www.wshunli.com/posts/25842bb5.html