# 剑指offer-3~9

# 题3-数组中重复的数

在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的，也不知道每个数字重复几次。请找出数组中任意一个重复的数字。

Input:
{2, 3, 1, 0, 2, 5}

Output:
2

1
2
3
4
5

解题思路

1. 要求时间复杂度 O(N)，空间复杂度 O(1)。因此不能使用排序的方法，也不能使用额外的标记数组。

2. 对于这种数组元素在 [0, n-1] 范围内的问题，可以将值为 i 的元素调整到第 i 个位置上进行求解。

3. 以 (2, 3, 1, 0, 2, 5) 为例，遍历到位置 4 时，该位置上的数为 2，但是第 2 个位置上已经有一个 2 的值了，因此可以知道 2 重 复。

实现代码

public class Three{

    public int[] nums = {2, 3, 1, 0, 2, 5};
    public int length = 6;
    public int[] duplication = {-1}; //不存在的话返回值为-1

    public boolean duplicate(int[] nums, int length, int[] duplication) {
        if (nums == null || length <= 0) //排除不符合条件的
            return false;
        for (int i = 0; i < length; i++) {
            if (nums[i] != i) { //判断数组下标和数组元素是否相等
                if (nums[i] == nums[nums[i]]) { //判断是否有相同的元素已经存在
                    duplication[0] = nums[i]; //村在则将值记录下来
                    System.out.println(duplication[0]);
                    return true;
                } else {
                    swap(nums, i, nums[i]); //不存相同元素的话，将对应的数组元素交换到对应的位置
                }
            }
        }
        return false;
    }

    //交换元素位置
    private void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }

    public static void main(String[] args) {
        Three three= new three();
        boolean duplicate = three.duplicate(three.nums, three.length, three.duplication);
        System.out.println(duplicate);
    }

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

# 题4-二维数组中的查找

二维数组中的查找给定一个二维数组，其每一行从左到右递增排序，从上到下也是递增排序。给定一个数，判断这个数是否在该二维数组中。

 Consider the following matrix:
 [
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
   [18, 21, 23, 26, 30]
 ]

 Given target = 5, return true.
 Given target = 20, return false.

1
2
3
4
5
6
7
8
9
10
11

解题思路

要求时间复杂度为O(M+N)，空间复杂度O(1)。其中M为行数，N为列数该二维数组中的一个数，小于它的数一定在其左边，大于它的数一定在其下边。因此，从右上角开始查找，就可以根据 target 和当前元素的大小关系来缩小查找区间，当前元素的查找区间为左下角的所有元素。

public class Four {
   
    public boolean Find(int target, int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0)//排除不符合条件的
            return false;
        int rows = matrix.length, cols = matrix[0].length;//定义rows和cols
        int r = 0, c = cols - 1; //从右上角开始
        while (r <= rows - 1 && c >= 0) {
            if (target == matrix[r][c]) {
                System.out.println("rows=" + r + ";cols=" + c);
                return true;
            } else if (target > matrix[r][c])
                r++;
            else
                c--;
        }
        return false;
    }

    public int target = 5;
    public int[][] matrix = {{1, 4, 7, 11, 15}, {2, 5, 8, 12, 19}, {3, 6, 9, 16, 22}, {10, 13, 14, 17, 24}, {18, 21, 23, 26, 30}};

    public static void main(String[] args) {
        Four four = new Four();
        boolean find = four.Find(four.target, four.matrix);
        System.out.println(find);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

# 题5-替换空格

将一个字符串中的空格替换成 "%20"。

 Input:
 "A B"

 Output:
 "A%20B"

1
2
3
4
5

解题思路

在字符串尾部填充任意字符，使得字符串的长度等于替换之后的长度。因为一个空格要替换成三个字符（%20），因此当遍历到一个空格时，需要在尾部填充两个任意字符。令 P1 指向字符串原来的末尾位置，P2 指向字符串现在的末尾位置。 P1 和 P2 从后向前遍历，当 P1 遍历到一个空格时，就需要令 P2 指向的位置依次填充 02%（注意是逆序的），否则就填充上 P1 指向字符的值。从后向前遍是为了在改变 P2 所指向的内容时，不会影响到 P1 遍历原来字符串的内容。

    public String replaceSpace(StringBuffer str) {
        int P1 = str.length() - 1; //P1为原来字符串的长度
        for (int i = 0; i <= P1; i++)
            if (str.charAt(i) == ' ')//找到有空格的位置
                str.append("  ");//在末尾添加两个空位

        int P2 = str.length() - 1; //P2为现在字符串的长度
        while (P1 >= 0 && P2 > P1) {
            char c = str.charAt(P1--);
            if (c == ' ') { //找到后倒叙插入
                str.setCharAt(P2--, '0');
                str.setCharAt(P2--, '2');
                str.setCharAt(P2--, '%');
            } else {
                str.setCharAt(P2--, c); //将末尾的值向后移动两个单位
            }
        }
        return str.toString();
    }

    StringBuffer stringBuffer = new StringBuffer("A BC");

    public static void main(String[] args) {
        Five five = new Five();
        System.out.println(five.replaceSpace(five.stringBuffer));
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

# 题六-从尾到头打印链表

从尾到头反过来打印出每个结点的值。

 输入1->2->3
 输出3->2->1

1
2

解题思路

思路1：使用递归要逆序打印链表 1->2->3（3,2,1)，可以先逆序打印链表 2->3(3,2)，最后再打印第一个节点 1。而链表 2->3 可以看成一个新的链表，要逆序打印该链表可以继续使用求解函数，也就是在求解函数中调用自己，这就是递归函数。

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

    public static void main(String[] args) {
        ListNode first = new ListNode(1);
        ListNode a1 = new ListNode(2);
        ListNode a2 = new ListNode(3);
        first.next = a1;
        a1.next = a2;
        first.printList(first);

        Six six = new Six();
        ArrayList<Integer> integers = six.printListFromTailToHead(first);
        System.out.println(integers);
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 题七-重建二叉树

根据二叉树的前序遍历和中序遍历的结果，重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

解题思路

前序遍历的第一个值为根节点的值，使用这个值将中序遍历结果分成两部分，左部分为树的左子树中序遍历结果，右部分为树的右子树中序遍历的结果。

private Map<Integer, Integer> indexForInOrders = new HashMap<>();

    public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        for (int i = 0; i < in.length; i++)
            indexForInOrders.put(in[i], i);
        return reConstructBinaryTree(pre, 0, pre.length - 1, 0);
    }

    private TreeNode reConstructBinaryTree(int[] pre, int preL, int preR, int inL) {
        if (preL > preR)
            return null;
        TreeNode root = new TreeNode(pre[preL]);
        int inIndex = indexForInOrders.get(root.val);
        int leftTreeSize = inIndex - inL;
        root.left = reConstructBinaryTree(pre, preL + 1, preL + leftTreeSize, inL);
        root.right = reConstructBinaryTree(pre, preL + leftTreeSize + 1, preR, inL + leftTreeSize + 1);
        return root;
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 题八-二叉树的下一个结点

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

解题思路

1.如果一个节点的右子树不为空，那么该节点的下一个节点是右子树的最左节点； 2.否则，向上找第一个左链接指向的树包含该节点的祖先节点。

    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        if (pNode.right != null) {
            TreeLinkNode node = pNode.right;
            while (node.left != null)
                node = node.left;
            return node;
        } else {
            while (pNode.next != null) {
                TreeLinkNode parent = pNode.next;
                if (parent.left == pNode)
                    return parent;
                pNode = pNode.next;
            }
        }
        return null;
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 题九-用两个栈实现队列

用两个栈来实现一个队列，完成队列的 Push 和 Pop 操作。

解题思路

in 栈用来处理入栈（push）操作，out 栈用来处理出栈（pop）操作。一个元素进入 in 栈之后，出栈的顺序被反转。当元素要出栈时，需要先进入 out 栈，此时元素出栈顺序再一次被反转，因此出栈顺序就和最开始入栈顺序是相同的，先进入的元素先退出，这就是队列的顺序。

    Stack<Integer> in = new Stack<>();
    Stack<Integer> out = new Stack<>();

    public void push(int node) {
        in.push(node);
    }

    public int pop() throws Exception {
        if (out.isEmpty())
            while (!in.isEmpty())
                out.push(in.pop());

        if (out.isEmpty())
            throw new Exception("queue is empty");

        return out.pop();
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

← leetcode：8-字符串转换整数-atoi