「笔记」OfferCoder：剑指Offer刷题笔记

1. 数组中重复的数字

描述：
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组[2,3,1,0,2,5,3]，那么对应的输出是2或者3。存在不合法的输入的话输出-1
答案：

    public int duplicate (int[] numbers) {
        // write code here
        if (numbers == null || numbers.length == 0) {
            return -1;
        }
        HashSet<Integer> hashSet = new HashSet<>();
        for (int i = 0; i < numbers.length; i++) {
            if (hashSet.contains(numbers[i])) {
                return numbers[i];
            } else {
                hashSet.add(numbers[i]);
            }
        }
        return -1;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

**扩展知识：**hashSet具有唯一性、无序性、允许为空、非线程安全

2. 二维数组中的查找

描述：
在一个二维数组array中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
答案：

    public boolean Find (int target, int[][] array) {
        // write code here
        if (array == null || array.length == 0 || array[0].length == 0) {
            return false;
        }
        int rows = array.length;       // 行数
        int cols = array[0].length;    // 列数
        int row = 0;                       // 起始行索引
        int col = cols - 1;                // 起始列索引
        while (row < rows && col >= 0) {
            int num = array[row][col];
            if (num == target) {
                return true;
            } else if (num > target) {
                col--;   // 目标值可能在当前元素的左侧
            } else {
                row++;   // 目标值可能在当前元素的下方
            }
        }
        return false;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

3. 替换空格

描述：
请实现一个函数，将一个字符串s中的每个空格替换成“%20”。
例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
数据范围:0≤len(s)≤1000 。保证字符串中的字符为大写英文字母、小写英文字母和空格中的一种。

答案：

    public String replaceSpace (String s) {
        // write code here
        StringBuilder sb = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (c == ' ') {
                sb.append("%20");
            } else {
                sb.append(c);
            }
        }
        return sb.toString();
    }
1
2
3
4
5
6
7
8
9
10
11
12

扩展知识：StringBuilder的特性

StringBuilder 是 Java 提供的一个可变字符串类，它具有以下特性：

1. 可变性：StringBuilder 对象的内容可以修改。与 String 类型不同，String 类型是不可变的，每次修改都会创建一个新的字符串对象。而 StringBuilder 允许直接在原地进行修改，避免了频繁创建新的对象。

2. 高效性：由于 StringBuilder 的可变性，它在执行字符串拼接、插入、删除等操作时效率更高。这是因为 StringBuilder 内部使用字符数组来存储字符串数据，并提供了一系列的方法来进行修改操作，而不需要频繁地创建新的字符串对象。

3. 线程不安全：StringBuilder 是非线程安全的，适用于单线程环境。如果在多线程环境下使用 StringBuilder 进行操作，可能会导致数据不一致或竞态条件的问题。如果在多线程环境下需要进行字符串操作，可以考虑使用线程安全的 StringBuffer
   类。

由于 StringBuilder 的特性，它通常用于动态构建字符串，例如拼接长字符串或循环中的字符串累加。它提供了一些常用的方法，如 append()、insert()、delete() 等，可以方便地进行字符串的修改操作。

4. 从尾到头打印链表

描述
输入一个链表的头节点，按链表从尾到头的顺序返回每个节点的值（用数组返回）。

如输入{1,2,3}的链表如下图:

返回一个数组为[3,2,1]

0 <= 链表长度 <= 10000