剑指Offer

1 数组中重复的数字

1、找出数组中重复的数字

• 在一个长度为n的数组里的所有数字都在0~(n-1)的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组{2, 3, 1, 0, 2, 5, 3}，那么对应的输出是重复的数字2或者3。

2、思路

• 每遍历数组中的一个数字，就让其归位（放在正确的数组下标）。当在归位的过程中，发现该数组下标所存放的数字和当前要归为的数字相同时，则发生了重复，返回该数字。
• 空间复杂度O(1)，时间复杂度O(n)。

3、代码

public class FindDuplicateNum {
    public static boolean findDuplicationNum(int[] arr, int length, int[] dup) {
        if (arr == null || length <= 0) {
            return false;
        }
        for (int i = 0; i < length; i++) {
            while (arr[i] != i) {
                if (arr[i] == arr[arr[i]]) {
                    dup[0] = arr[i];
                    return true;
                }
                swap(arr, i, arr[i]);
            }
        }
        return false;
    }

    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

2 不修改数组找出重复数字

1、题目

• 在一个长度为n+1的数组里的所有数字都在1~n的范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的输入。例如，如果输入长度为8的数组{2, 3, 5, 4, 3, 2, 6, 7}，那么对应的输出是重复的数字2或者3。

2、思路

• 类似二分查找：将1n上的数字划分为两块：1m和(m+1)~n，然后统计数组中该区间上的数字的个数，如果数字个数大于区间长度，则发生了重复，然后在该区间上继续二分，直至区间长度等于1。
• 空间复杂度O(1)，时间复杂度O(nlogn)。

3、代码

public class FindDuplicateNumNoEdit {
    public static int findDuplicateNumNoEdit(int[] arr, int length) {
        if (arr == null || length <= 0) {
            return -1;
        }
        int start = 1;
        int end = length - 1;
        while (start <= end) {
            int mid = start + ((end - start) >> 1);
            int count = getCount(arr, length, start, mid);
            if (start == end) {
                if (count > 1) {
                    return start;
                } else {
                    return -1;
                }
            }
            if (count > (mid - start + 1)) {
                end = mid;
            } else {
                start = mid + 1;
            }
        }
        return -1;
    }

    private static int getCount(int[] arr, int length, int start, int end) {
        int count = 0;
        for (int i = 0; i < length; i++) {
            if (arr[i] >= start && arr[i] <= end) {
                count++;
            }
        }
        return count;
    }
}

3 二维数组查找

1、题目

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

2、思路

• 从左下或者右上角开始查找，每次判断可以剔除一行或者是一列。
• 时间复杂度O(n+m)。

3、代码

public class Q3 {
    public static boolean find(int target, int[][] array) {
        int rows = array.length;
        if (rows == 0) {
            return false;
        }
        int columns = array[0].length;
        if (columns == 0) {
            return false;
        }
        int column = 0;
        int row = rows - 1;
        while (row >= 0 && column < columns) {
            if (target == array[row][column]) {
                return true;
            } else if (target < array[row][column]) {
                row--;
            } else {
                column++;
            }
        }
        return false;
    }
}

4 替换空格

1、题目

• 请实现一个函数，把字符串中的每个空格替换成“%20”。例如，输入“We are happy.”，则输出“We%20are%20happy.”。

2、思路

• 先统计出字符串中的空格数量，然后计算出替换后的字符串长度，从后往前遍历字符串，依次填充。

3、代码

public class Q4 {
    public static String replaceBlankSpace(String str) {
        if (str == null) {
            return null;
        }
        char[] chars = str.toCharArray();
        int count = 0;
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == ' ') {
                count++;
            }
        }
        int newLength = chars.length + (count << 1);
        int p1 = chars.length - 1;
        int p2 = newLength - 1;
        char[] newChars = new char[newLength];
        while (p1 >= 0) {
            if (chars[p1] == ' ') {
                newChars[p2--] = '0';
                newChars[p2--] = '2';
                newChars[p2--] = '%';
                p1--;
            } else {
                newChars[p2--] = chars[p1--];
            }
        }
        return String.valueOf(newChars);
    }
}

5 从尾到头打印链表

1、题目

• 输入一个链表的头节点，从尾到头反过来打印出每个节点的值。

2、思路

• 方式一：使用栈，遍历一遍链表，将链表中的节点压栈，然后输出栈中的节点。
• 方式二：递归。

3、代码

import java.util.Stack;

public class Q5 {
    private class ListNode {
        int key;
        ListNode next;

        public ListNode(int key) {
            this.key = key;
        }
    }

    public static void fromHeadtoTailPrintLinkedListbyStack(ListNode head) {
        if (head == null) {
            return;
        }
        ListNode cur = head;
        Stack<ListNode> stack = new Stack<>();
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        while (!stack.isEmpty()) {
            System.out.print(stack.pop().key + " ");
        }
    }

    public static void fromHeadtoTailPrintLinkedListByRecursion(ListNode head) {
        if (head == null) {
            return;
        }
        ListNode cur = head;
        fromHeadtoTailPrintLinkedListByRecursion(head.next);
        System.out.print(cur.key + " ");
    }
}

6 重建二叉树

1、题目

• 输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如，输入前序遍历序列{1, 2, 3, 7, 3, 5, 6, 8}和中序遍历序列{4, 7, 2, 1, 5, 3, 8, 6}，则重建二叉树并输出它的头结点。

2、思路

• 根据前序和中序遍历，可以确定每棵子树根节点所在的位置，然后根据根节点，划分左右子树，之后再分别在左右子树中重复之前的划分过程。

3、代码

public class Q6 {
    private static class BinaryTreeNode {
        int value;
        BinaryTreeNode left;
        BinaryTreeNode right;

        public BinaryTreeNode(int value) {
            this.value = value;
        }
    }

    public static BinaryTreeNode construct(int[] preOrder, int[] inOrder, int preOrder_start, int inOrder_start, int length) {
        if (length == 0) {
            return null;
        }
        int rootInorderIndex = 0;
        for (int i = inOrder_start; i < inOrder_start + length; i++) {
            if (preOrder[preOrder_start] == inOrder[i]) {
                rootInorderIndex = i;
                break;
            }
        }
        int left_length = rootInorderIndex - inOrder_start;
        int right_lengh = length - left_length - 1;
        BinaryTreeNode root = new BinaryTreeNode(preOrder[preOrder_start]);
        root.left = construct(preOrder, inOrder, preOrder_start + 1, inOrder_start, left_length);
        root.right = construct(preOrder, inOrder, preOrder_start + left_length + 1, rootInorderIndex + 1, right_lengh);
        return root;
    }
}

7 二叉树的下一个节点

1、题目

• 给定一棵二叉树和其中的一个节点，如何找出中序遍历序列的下一个节点？树中的节点除了有两个分别指向左、右子节点的指针，还有一个指向父节点的指针。

2、思路

• 分三种情况：
  1. 当前节点有右子树，下一个节点是右子树的最左的节点。
  2. 无右子树：
     1. 当前节点是父节点的左孩子，下一个节点是该父节点。
     2. 遍历该节点的父节点，直到父节点的左孩子是当前节点，下一个节点是父节点。

3、代码

import java.lang.reflect.WildcardType;

public class Q7 {
    private static class TreeNode {
        int value;
        TreeNode left;
        TreeNode right;
        TreeNode parent;

        TreeNode(int value) {
            this.value = value;
        }
    }

    public static TreeNode findNextNode(TreeNode treeNode) {
        if (treeNode.right != null) {
            TreeNode cur = treeNode.right;
            while (cur.left != null) {
                cur = cur.left;
            }
            return cur;
        } else {
            TreeNode par = treeNode.parent;
            if (par.left == treeNode) {
                return par;
            } else {
                while (par.left != treeNode) {
                    par = par.parent;
                    treeNode = treeNode.parent;
                }
                return par;
            }
        }
    }
}

8 用两个栈实现队列

1、题目

• 用两个栈实现一个队列。队列的声明如下，请实现它的两个函数appendTail和deleteHead，分别完成在队列尾部插入节点和在队列头部删除节点的功能。

2、思路

• 构建两个栈：pushStack、popStack，分别用于入栈、出栈功能。
• 入栈随时都可以进行。
• 出栈需要判断当前popStack是否为空：若不为空，则直接出栈；若为空，则需要将pushStack中的所有数据转移过来（相当于将栈中的顺序进行一个翻转），再进行出栈。

3、代码

import java.util.Stack;

public class Q8<T> {
    private Stack<T> pushStack;
    private Stack<T> popStack;

    public Q8() {
        pushStack = new Stack<>();
        popStack = new Stack<>();
    }

    public void appendTail(T node) {
        pushStack.push(node);
    }

    public T deleteHead() {
        if (pushStack.isEmpty() && popStack.isEmpty()) {
            throw new RuntimeException("Queue is empty!");
        } else {
            if (popStack.isEmpty()) {
                while (!pushStack.isEmpty()) {
                    popStack.push(pushStack.pop());
                }
            }
            return popStack.pop();
        }
    }

    public T getHead() {
        if (pushStack.isEmpty() && popStack.isEmpty()) {
            throw new RuntimeException("Queue is empty!");
        } else {
            if (popStack.isEmpty()) {
                while (!pushStack.isEmpty()) {
                    popStack.push(pushStack.pop());
                }
            }
            return popStack.peek();
        }
    }
}

9 用两个队列实现栈

1、思路

• 构建两个队列：dataQueue、tmpQueue，分别用来存放数据、数据中转。
• 出栈随时都可以进行。
• 入栈时，需要先将dataQueue中的所有数据转移到tmpQueue，将新增数据入队列置于队首，最后将tmpQueue中的数据转移回来。

2、代码

import java.util.LinkedList;
import java.util.Queue;

public class Q9<T> {
    private Queue<T> dataQueue;
    private Queue<T> tmpQueue;
    public Q9() {
        dataQueue = new LinkedList<>();
        tmpQueue = new LinkedList<>();
    }

    public T pop() {
        if (dataQueue.isEmpty()) {
            throw new RuntimeException("Stack is empty!");
        }
        return dataQueue.poll();
    }

    public T peek() {
        if (dataQueue.isEmpty()) {
            throw new RuntimeException("Stack is empty!");
        }
        return dataQueue.peek();
    }

    public void push(T node) {
        while (!dataQueue.isEmpty()) {
            tmpQueue.add(dataQueue.poll());
        }
        dataQueue.add(node);
        while (!tmpQueue.isEmpty()) {
            dataQueue.add(tmpQueue.poll());
        }
    }
}

10 斐波那契数列

1、题目

• 写一个函数，输入n，求斐波那契（Fibonacci）数列的第n项。斐波那契数列：0, 1, 1, 2, 3, 5, ……

2、思路

• 递归。
• 循环。

3、代码

public class Q10 {
    public static int byRecursive(int n) {
        if (n < 0) {
            throw new RuntimeException("Wrong number!");
        }
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        return byRecursive(n - 1) + byRecursive(n - 2);
    }

    public static int byFor(int n) {
        if (n < 0) {
            throw new RuntimeException("Wrong number!");
        }
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        int a = 0;
        int b = 1;
        int result = 0;
        for (int i = 1; i < n; i++) {
            result = a + b;
            a = b;
            b = result;
        }
        return result;
    }
}

11 旋转数组的最小数字

1、题目

• 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转，该数组的最小值为1。

2、思路

• 方式一：暴力查找，时间复杂度O(n)。
• 方式二：二分查找，时间复杂度O(logn)。

3、代码

public class Q11 {
    public static int find(int[] arr) {
        int length = arr.length;
        if (length == 0) {
            return 0;
        }
        int left = 0;
        int right = length - 1;
        int mid = 0;
        while (left < right) {
            if (arr[left] < arr[right]) {
                return arr[left];
            }
            mid = (left + right) >> 1;
            if (arr[mid] < arr[right]) {
                right = mid;
            } else if (arr[mid] > arr[right]) {
                left = mid + 1;
            } else {
                left++;
            }
        }
        return arr[left];
    }
}

12 矩阵中的路径

1、题目

• 请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如，在下面的3x4的矩阵中包含一条字符串“bfce”的路径。但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。

  a b t g
  c f c s
  j d e h

2、思路

• 回溯法。

3、代码

public class Q12 {
    public static boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
        if (matrix == null || str == null || rows <= 0 || cols <= 0) {
            return false;
        }
        boolean[][] mark = new boolean[rows][cols];
        char[][] chars = toArray(matrix, rows, cols);
        for (int i = 0; i < rows; i++) {
            for (int j = 0; i < cols; j++) {
                if (process(chars, str, 0, mark, i, j)) {
                    return true;
                }
            }
        }
        return false;
    }

    private static char[][] toArray(char[] matrix, int rows, int cols) {
        char[][] chars = new char[rows][cols];
        for (int i = 0, index = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                chars[i][j] = matrix[index++];
            }
        }
        return chars;
    }

    private static boolean process(char[][] chars, char[] str, int pathLength, boolean[][] mark, int row, int column) {
        if (pathLength == str.length) {
            return true;
        }
        if (row < 0 || column < 0 || row >= chars.length || column >= chars[0].length
                || chars[row][column] != str[pathLength] || mark[row][column]) {
            return false;
        }
        mark[row][column] = true;
        if (process(chars, str, pathLength + 1, mark, row - 1, column) ||
                process(chars, str, pathLength + 1, mark, row + 1, column) ||
                process(chars, str, pathLength + 1, mark, row, column - 1) ||
                process(chars, str, pathLength + 1, mark, row, column + 1)) {
            return true;
        }
        mark[row][column] = false;
        return false;
    }
}

13 机器人的运动范围

1、题目

• 地上有一个m行n列的方格。一个机器人从坐标(0, 0)的格子开始移动，它每次可以像左、右、上、下移动一格，但不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格(35, 37)，以内3+5+3+7=18。但它不能进入方格(35, 38)，以内3+5+3+8=19。请问该机器人能够到达多少个格子？

2、思路

• 图的深度优先遍历。

3、代码

public class Q13 {
    public static int movingCount(int threshold, int rows, int cols) {
        boolean[][] mark = new boolean[rows][cols];
        int[][] matrix = new int[rows][cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                matrix[i][j] = getValue(i) + getValue(j);
            }
        }
        return process(threshold, matrix, mark, 0, 0, rows, cols);
    }

    private static int process(int threshold, int[][] matrix, boolean[][] mark, int i, int j, int rows, int cols) {
        int count = 0;
        if (i < 0 || j < 0 || i >= rows || j >= cols || matrix[i][j] > threshold || mark[i][j]) {
            return 0;
        }
        mark[i][j] = true;
        count = 1 + process(threshold, matrix, mark, i - 1, j, rows, cols) +
                process(threshold, matrix, mark, i + 1, j, rows, cols) +
                process(threshold, matrix, mark, i, j - 1, rows, cols) +
                process(threshold, matrix, mark, i, j + 1, rows, cols);
        return count;
    }

    private static int getValue(int num) {
        int res = 0;
        int tmp = 0;
        while (num / 10 > 0) {
            tmp = num / 10;
            res += num - tmp * 10;
            num = tmp;
        }
        res += num;
        return res;
    }
}

14 剪绳子

1、题目

• 给你一根长度为n的绳子，请把绳子剪成m段（m、n都是整数，n>1并且m>1），每段绳子的长度记为k[0]，k[1]，……，k[m]。请问k[0]×k[1]×……×k[m]可能的最大乘积是多？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

2、思路

• 方式一：递归。
• 方式二：动态规划。
• 方式三：贪心算法。

3、代码

import java.util.Properties;

public class Q14 {
    // 方式一：递归
    public static int recursion(int target) {
        if (target < 2) {
            return 0;
        }
        if (target == 2) {
            return 1;
        }
        if (target == 3) {
            return 2;
        }
        int max = 0;
        for (int i = 1; i <= (target - 1) / 2; i++) {
            max = Math.max(max, process(i) * process(target - i));
        }
        return max;
    }

    private static int process(int target) {
        if (target < 4) {
            return target;
        }
        int max = 0;
        for (int i = 1; i <= (target - 1) / 2; i++) {
            max = Math.max(max, process(i) * process(target - 1));
        }
        return max;
    }

    // 方式二：动态规划
    public static int dynamic(int target) {
        if (target < 2) {
            return 0;
        }
        if (target == 2) {
            return 1;
        }
        if (target == 3) {
            return 2;
        }
        int[] dp = new int[target + 1];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        for (int i = 4; i <= target; i++) {
            for (int j = 1; j <= i / 2; j++) {
                dp[i] = Math.max(dp[i], dp[j] * dp[i - j]);
            }
        }
        return dp[target];
    }

    // 方式三：贪心算法
    public static int greedy(int target) {
        if (target < 2) {
            return 0;
        }
        if (target == 2) {
            return 1;
        }
        if (target == 3) {
            return 2;
        }
        int timeOf3 = target / 3;
        if (target - timeOf3 * 3 == 1) {
            timeOf3--;
        }
        int timeOf2 = (target - timeOf3 * 3) / 2;
        int res = (int) (Math.pow(3, timeOf3) * Math.pow(2, timeOf2));
        return res;
    }
}

15 二进制中1的个数

1、题目

• 请实现一个函数，输入一个整数，输出该数二进制表示中1的个数。例如，把9表示成二进制是1001，有2位是1。因此，如果输入9，则该函数输出2。

2、思路

• (n-1)&n：将n中二进制表示最右边的1变为0。

3、代码

public class Q15 {
    public int count(int n) {
        int res = 0;
        while (n != 0) {
            n = (n - 1) & n;
            res++;
        }
        return res;
    }
}

16 数值的整数次方

1、题目

• 实现函数double power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。

2、代码

public class Q16 {
    public double power1(double base, int exponent) {
        if (base == 0 && exponent < 0) {
            throw new RuntimeException("input number error!");
        }
        double res = 1;
        double tmp = exponent;
        if (exponent < 0) {
            exponent = -exponent;
        }
        for (int i = 1; i <= exponent; i++) {
            res = res * base;
        }
        if (tmp < 0) {
            res = 1 / res;
        }
        return res;
    }

    public double power2(double base, int exponent) {
        if (base == 0 && exponent < 0) {
            throw new RuntimeException("input number error!");
        }
        double res = 1;
        double tmp = exponent;
        if (exponent % 2 == 0) {
            for (int i = 1; i <= exponent / 2; i++) {
                res = res * base;
            }
        } else {
            for (int i = 1; i <= (exponent - 1) / 2; i++) {
                res = res * base;
            }
            res = res * res * base;
        }
        if (tmp < 0) {
            res = 1 / res;
        }
        return res;
    }
}

17 打印从1到最大的n位数

1、题目

• 输入数字n，按顺序打印出从1到最大的n位十进制数。比如输入3，则打印出1、2、3一直到最大的3位数999。

2、思路

• 本质上是0~9的全排列顺序输出问题，用递归实现。
• 大数问题，一般使用字符串来表示数字。

3、代码

public class Q17 {
    public void print(int n) {
        if (n <= 0) {
            throw new RuntimeException("error input!");
        }
        char[] nums = new char[n];
        for (int i = 0; i < 10; i++) {
            nums[0] = (char) ('0' + i);
            process(nums, 0, n);
        }
    }

    public void process(char[] nums, int index, int len) {
        if (index == len - 1) {
            print(nums);
            return;
        }
        for (int i = 0; i < 10; i++) {
            nums[index + 1] = (char) ('0' + i);
            process(nums, index + 1, len);
        }
    }

    private void print(char[] nums) {
        int flag = 0;
        String str = "";
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != '0') {
                flag = 1;
                str += nums[i];
            }
            if (nums[i] == '0' && flag == 1) {
                str += nums[i];
            }
            System.out.print(str + " ");
        }
    }
}

18 删除链表中的节点

1、题目

• 给定单向链表的头指针和一个节点指针，定义一个函数在O(1)时间内删除该节点。

2、代码

public class Q18 {
    private static class Node {
        int value;
        Node next;

        Node(int value) {
            this.value = value;
        }
    }

    public static Node deleteNode(Node head, Node deleteNode) {
        if (deleteNode.next != null) {
            deleteNode.value = deleteNode.next.value;
            deleteNode.next = deleteNode.next.next;
        } else {
            if (head == deleteNode) {
                head = null;
            } else {
                Node cur = head;
                while (cur.next != deleteNode) {
                    cur = cur.next;
                }
                cur.next = null;
            }
        }
        return head;
    }
}

19 正则表达式匹配

1、题目

• 请实现一个函数用来匹配包含'.'和''的正则表达式。模式中的字符'.'表示任意一个字符，而''表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串“aaa”与模式"a.a“和”abacc“匹配，但与"aa.a"和"ab*a"均不匹配。

2、思路

• 当模式中的第二个字符不是“*”时：
  1. 如果字符串第一个字符和模式中的第一个字符相匹配，那么字符串和模式都后移一个字符，然后匹配剩余的。
  2. 如果字符串第一个字符和模式中的第一个字符不匹配，直接返回false。
• 当模式中的第二个字符是“*”时：
  • 如果字符串第一个字符跟模式第一个字符不匹配，则模式后移2个字符，继续匹配。
  • 如果字符串第一个字符跟模式第一个字符匹配，可以有3种匹配方式：
    1. 模式后移2字符，相当于x*被忽略；
    2. 字符串后移1字符，模式后移2字符；
    3. 字符串后移1字符，模式不变，即继续匹配字符下一位，因为*可以匹配多位。

3、代码

public class Q19 {

    public boolean match(char[] str, char[] pattern) {
        if (str == null || pattern == null) {
            return false;
        }
        int strIndex = 0;
        int patternIndex = 0;
        return core(str, strIndex, pattern, patternIndex);
    }

    /**
     * @param str          字符串
     * @param strIndex     字符串索引
     * @param pattern      正则表达式
     * @param patternIndex 正则表达式索引
     * @return
     */
    public boolean core(char[] str, int strIndex, char[] pattern, int patternIndex) {
        // 当字符串索引、正则表达式索引同时到达末尾，匹配成功
        if (strIndex == str.length && patternIndex == pattern.length) {
            return true;
        }
        // 当字符串索引未到达末尾，但正则表达式索引到达末尾，匹配失败
        if (strIndex != str.length && patternIndex == pattern.length) {
            return false;
        }
        // 模式第2个是*，且字符串第1个跟模式第1个匹配，分3种匹配模式；如果不匹配，模式后移2位
        if (patternIndex + 1 < pattern.length && pattern[patternIndex + 1] == '*') {
            if ((strIndex != str.length && pattern[patternIndex] == str[strIndex]) ||
                    strIndex != str.length && (pattern[patternIndex] == '.')) {
                return core(str, strIndex, pattern, patternIndex + 2) ||
                        core(str, strIndex + 1, pattern, patternIndex + 2) ||
                        core(str, strIndex + 1, pattern, patternIndex);
            } else {
                return core(str, strIndex, pattern, patternIndex + 2);
            }
        }
        // 模式第2个不是*，且字符串第1个跟模式第1个匹配，则都后移1位，否则直接返回false
        if ((strIndex != str.length && pattern[patternIndex] == str[strIndex]) ||
                (strIndex != str.length && pattern[patternIndex] == '.')) {
            return core(str, strIndex + 1, pattern, patternIndex + 1);
        }
        return false;
    }
}

20 表示数值的字符串

1、题目

• 请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串“+100”、“5e2”，“-123”、”3.1416“及“-1E-16”都表示数值，但“12e"、”1a3.14"、“1.2.3”、“+-5”及“12e+5.4"都不是。

2、思路

• 使用正则表达式进行匹配：

  []：字符集合
  ()：分组
  ?：重复01次
  +：重复1n次
  *：重复0~n次
  .：任意字符
  \.：转义后的.
  \d：数字

3、代码

public class Q20 {
    public boolean judge(String str) {
        if (str == null || str.length() == 0) {
            return false;
        }
        return str.matches("[+-]?\\d*(\\.\\d+)?([eE][+-]?\\d+)?");
    }
}

21 调整数组顺序使奇数位于偶数前面

1、题目

• 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。

2、思路

• 使用两个索引，从数组两头开始遍历，将奇数与偶数位置交换。

3、代码

package com.xianhuii.practice1;

import org.junit.Test;
import java.util.Arrays;

public class O21 {
public void adjust(int[] arr) {
    if (arr == null) {
        throw new RuntimeException("arr is null!");
    }
    int left = 0;
    int right = arr.length - 1;
    while (left < right) {
        while (arr[left] % 2 != 0 && left < right) {
            left++;
        }
        while (arr[right] % 2 == 0 && left < right) {
            right--;
        }
        swap(arr, left, right);
    }
}

private void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

@Test
public void test() {
    int[] arr = new int[]{1, 2, 3, 4, 5, 6, 7};
    adjust(arr);
    System.out.println(Arrays.toString(arr));
}

}

22 链表中倒数第k个节点

1、题目

• 输入一个链表，输出该链表中倒数第k个节点。为了复合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头结点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。

2、思路

• 设置两个指针p1、p2，p1=p2=head。
• 让p1先走k-1步，然后p1和p2同时走，p1走到链表尾节点时，p2正好走到倒数第k个节点。

3、代码

package com.xianhuii.practice1;

import org.junit.Test;

public class O22 {
private class ListNode {
    int value;
    ListNode next;

    ListNode(int value) {
        this.value = value;
    }
}

public ListNode find(ListNode root, int k) {
    if (root == null) {
        throw new RuntimeException("root is null!");
    }
    if (k <= 0) {
        throw new RuntimeException("error k!");
    }
    ListNode p1 = root;
    ListNode p2 = root;
    while (p1 != null) {
        if (k <= 0) {
            p2 = p2.next;
        }
        p1 = p1.next;
        k--;
    }
    if (k > 0) {
        throw new RuntimeException("k > length");
    } else {
        return p2;
    }
}

@Test
public void test() {
    ListNode node1 = new ListNode(1);
    ListNode node2 = new ListNode(2);
    ListNode node3 = new ListNode(3);
    ListNode node4 = new ListNode(4);
    ListNode node5 = new ListNode(5);
    ListNode node6 = new ListNode(6);
    node1.next = node2;
    node2.next = node3;
    node3.next = node4;
    node4.next = node5;
    node5.next = node6;
    System.out.println(find(node1, 1).value);
}}

23 链表中环的入口节点

1、题目

• 如果一个链表中包含环，如何找出环的入口节点？

2、思路

• 先判断链表是否存在环，使用快慢指针，快指针一次走两步，慢指针一次走一步，两个指针相遇，则说明链表有环，记录下相遇时的节点loopNode。
• 计算环中的节点个数，从loopNode节点出发，再次回到loopNode，就得到了环中节点的个数k。
• 设置两个指针p1和p2，让p1先走k步，然后p1和p2同时走，相遇时节点entryNode即为环的入口节点。

3、代码

package com.xianhuii.practice1;

import org.junit.Test;

public class O23 {
private class LinkedList {
    int value;
    LinkedList next;

    LinkedList(int value) {
        this.value = value;
    }
}

public LinkedList find(LinkedList root) {
    if (root == null) {
        throw new RuntimeException("root is null!");
    }
    LinkedList p1 = root;
    LinkedList p2 = root;
    LinkedList loopNode = null;
    int count = 0;
    while (p1.next != null) {
        p1 = p1.next;
        if (p1.next != null) {
            p1 = p1.next;
        }
        p2 = p2.next;
        if (p1 == p2) {
            loopNode = p1;
            break;
        }
    }
    if (loopNode == null) {
        return null;
    }
    LinkedList tmpNode = loopNode;
    while (loopNode != tmpNode) {
        count++;
        loopNode = loopNode.next;
    }
    p1 = root;
    p2 = tmpNode;
    while (p1 != p2) {
        p1 = p1.next;
        p2 = p2.next;
    }
    return p1;
}

@Test
public void test() {
    LinkedList list1 = new LinkedList(1);
    LinkedList list2 = new LinkedList(2);
    LinkedList list3 = new LinkedList(3);
    LinkedList list4 = new LinkedList(4);
    LinkedList list5 = new LinkedList(5);
    LinkedList list6 = new LinkedList(6);
    LinkedList list7 = new LinkedList(7);
    LinkedList list8 = new LinkedList(8);
    list1.next = list2;
    list2.next = list3;
    list3.next = list4;
    list4.next = list5;
    list5.next = list6;
    list6.next = list7;
    list7.next = list8;
    list8.next = list4;
    System.out.println(find(list1).value);
}

}

24 反转链表

1、题目

• 定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

2、思路

• 非递归：使用一个newHead节点来记录逆向之后的头节点。
• 递归：每次递归，head.next要设置为null。

3、代码

public class Q24 {
    private static class LinkedList {
        int value;
        LinkedList next;

        LinkedList(int value) {
            this.value = value;
        }
    }

    public static LinkedList reverse(LinkedList head) {
        LinkedList newHead = new LinkedList(0);
        while (head != null) {
            LinkedList next = head.next;
            head.next = newHead.next;
            newHead.next = head;
            head = next;
        }
        return newHead.next;
    }

    public static LinkedList reverseByRecursive(LinkedList head) {
        if (head == null || head.next == null) {
            return head;
        }
        LinkedList next = head.next;
        head.next = null;
        LinkedList newHead = reverseByRecursive(next);
        next.next = head;
        return newHead;
    }
}

25 合并两个排序的链表

1、题目

• 输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增的。

2、代码

public class Q25 {
    private static class LinkedList {
        int value;
        LinkedList next;

        LinkedList(int value) {
            this.value = value;
        }
    }

    public static LinkedList merge(LinkedList head1, LinkedList head2) {
        LinkedList head = new LinkedList(0);
        LinkedList cur = head;
        while (head1 != null && head2 != null) {
            if (head1.value <= head2.value) {
                cur.next = head1;
                head1 = head1.next;
            } else {
                cur.next = head2;
                head2 = head2.next;
            }
            cur = cur.next;
        }
        if (head1 != null) {
            cur.next = head1;
        }
        if (head2 != null) {
            cur.next = head2;
        }
        return head.next;
    }

    public static LinkedList mergeByRecursive(LinkedList head1, LinkedList head2) {
        if (head1 == null) {
            return head2;
        }
        if (head2 == null) {
            return head1;
        }
        if (head1.value <= head2.value) {
            head1.next = mergeByRecursive(head1.next, head2);
            return head1;
        } else {
            head2.next = mergeByRecursive(head1, head2.next);
            return head2;
        }
    }
}

26 树的子结构

1、题目

• 输入两棵二叉树A和B，判断B是不是A的子结构。

2、代码

public class Q26 {
    private static class BinaryTreeNode {
        double value;
        BinaryTreeNode left;
        BinaryTreeNode right;

        BinaryTreeNode(int value) {
            this.value = value;
        }
    }

    public static boolean hasSubTree(BinaryTreeNode tree1, BinaryTreeNode tree2) {
        boolean result = false;
        if (tree1 != null && tree2 != null) {
            if (tree1.value == tree2.value) {
                result = judge(tree1, tree2);
            }
            if (!result) {
                result = hasSubTree(tree1.left, tree2);
            }
            if (!result) {
                result = hasSubTree(tree1.right, tree2);
            }
        }
        return result;
    }

    public static boolean judge(BinaryTreeNode tree1, BinaryTreeNode tree2) {
        if (tree1 == null) {
            return false;
        }
        if (tree2 == null) {
            return true;
        }
        if (!equals(tree1.value, tree2.value)) {
            return false;
        } else {
            return judge(tree1.left, tree2.left) && judge(tree1.right, tree2.right);
        }
    }

    public static boolean equals(double a, double b) {
        if (Math.abs(a - b) < 0.0000001) {
            return true;
        } else {
            return false;
        }
    }
}

27 二叉树的镜像

1、题目

• 请完成一个函数，输入一棵二叉树，该函数输出它的镜像。

2、思路

• 前序遍历，递归依次交换左右节点。

3、代码

public class Q27 {
    private class BinaryTreeNode {
        int value;
        BinaryTreeNode left;
        BinaryTreeNode right;
    }

    public void mirror(BinaryTreeNode root) {
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null) {
            return;
        }
        BinaryTreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        if (root.left != null) {
            mirror(root.left);
        }
        if (root.right != null) {
            mirror(root.right);
        }
    }
}

28 对称的二叉树

1、题目

• 请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

2、思路

• 比较二叉树的根左右和根右左遍历的序列。

3、代码

public class Q28 {
    private class BinaryTreeNode {
        int value;
        BinaryTreeNode left;
        BinaryTreeNode right;
    }

    public boolean isSymmetry(BinaryTreeNode root) {
        return process(root, root);
    }

    public boolean process(BinaryTreeNode root1, BinaryTreeNode root2) {
        if (root1 == null && root2 == null) {
            return true;
        }
        if (root1 == null || root2 == null) {
            return false;
        }
        if (root1.value != root2.value) {
            return false;
        }
        return process(root1.left, root2.right) && process(root1.right, root2.left);
    }
}

29 顺时针打印矩阵

1、题目

• 输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

2、思路

• 每次打印一个圈。

3、代码

public class Q29 {
    public static void print(int[][] arr) {
        if (arr == null) {
            return;
        }
        print(arr, 0, 0, arr.length - 1, arr[0].length - 1);
    }

    public static void print(int[][] arr, int leftX, int leftY, int rightX, int rightY) {
        if (leftX > rightX || leftY > rightY) {
            return;
        }
        if (leftX == rightX) {
            for (int i = leftY; i <= rightY; i++) {
                System.out.print(arr[leftX][i] + " ");
            }
        } else if (leftY == rightY) {
            for (int i = leftX; i <= rightX; i++) {
                System.out.print(arr[i][leftY] + " ");
            }
        } else {
            for (int i = leftY; i < rightY; i++) {
                System.out.print(arr[leftX][i] + " ");
            }
            for (int i = leftX; i <= rightX; i++) {
                System.out.print(arr[i][rightY] + " ");
            }
            for (int i = rightY - 1; i >= leftY; i--) {
                System.out.print(arr[rightX][i] + " ");
            }
            for (int i = rightX - 1; i > leftX; i--) {
                System.out.print(arr[i][leftY] + " ");
            }
            print(arr, ++leftX, ++leftY, --rightX, --rightY);
        }
    }
}

30 包含min函数的栈

1、题目

• 定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的min函数。在该栈中，调用min、push及pop的时间复杂度都是O(1)。

2、思路

• 使用两个栈：dataStack（存放数据）、minStack（存放最小值）。

3、代码

package com.xianhuii.practice1;

import java.util.Stack;

public class O30 {
    Stack<Integer> dataStack = new Stack<>();
    Stack<Integer> minStack = new Stack<>();

    public void push(int data) {
        dataStack.push(data);
        if (minStack.isEmpty()) {
            minStack.push(data);
        } else {
            if (minStack.peek() < data) {
                minStack.push(minStack.peek());
            } else {
                minStack.push(data);
            }
        }
    }

    public int pop() {
        minStack.pop();
        return dataStack.pop();
    }

    public int min() {
        return minStack.peek();
    }
}

31 栈的压入、弹出序列

1、题目

• 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。
• 例如序列1，2，3，4，5是某栈的压入顺序，序列4，5，3，2，1是该压栈序列对应的一个弹出序列，但4，3，5，1，2就不可能是该压栈序列的弹出序列。

2、思路

• 先往栈压入pushSequence的第一个数字pushSequenct[0]，然后将栈顶的数字和popSequence[index]的数字进行比较，相同就弹出栈顶元素，popIndex+；否则，pushIndex++，压入pushSequence[pushIndex]到栈。

3、代码

import java.util.Stack;

public class Q31 {
    public static boolean judge(int[] pushSequence, int[] popSequence) {
        Stack<Integer> stack = new Stack<>();
        int n = pushSequence.length;
        if (pushSequence == null || popSequence == null || n == 0) {
            return false;
        }
        for (int pushIndex = 0, popIndex = 0; pushIndex < n; pushIndex++) {
            stack.push(pushSequence[pushIndex]);
            while (!stack.isEmpty() && popIndex < n && stack.peek() == popSequence[popIndex]) {
                stack.pop();
                popIndex++;
            }
        }
        return stack.isEmpty();
    }
}

32 从上到下打印二叉树

1、题目

• 从上往下打印出二叉树的每个节点，同层节点从左至右打印。

2、思路

• 使用队列，先将根节点压入队列，然后开始遍历队列，每弹出一个节点就输出节点的值，然后将该节点的左右孩子压入队列，重复此过程直到队列为空。

3、代码

package com.xianhuii.practice1;

import org.junit.Test;

import java.util.LinkedList;
import java.util.Queue;

public class O32 {
    private class BinaryTree {
        int value;
        BinaryTree left;
        BinaryTree right;

        BinaryTree(int value) {
            this.value = value;
        }
    }

    public void print(BinaryTree root) {
        if (root == null) {
            return;
        }
        Queue<BinaryTree> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            BinaryTree binaryTree = queue.poll();
            if (binaryTree.left != null) {
                queue.add(binaryTree.left);
            }
            if (binaryTree.right != null) {
                queue.add(binaryTree.right);
            }
            if (!queue.isEmpty()) {
                System.out.print(binaryTree.value + ", ");
            } else {
                System.out.print(binaryTree.value);
            }
        }
    }

    @Test
    public void test() {
        BinaryTree node1 = new BinaryTree(1);
        BinaryTree node2 = new BinaryTree(2);
        BinaryTree node3 = new BinaryTree(3);
        BinaryTree node4 = new BinaryTree(4);
        BinaryTree node5 = new BinaryTree(5);
        BinaryTree node6 = new BinaryTree(6);
        BinaryTree node7 = new BinaryTree(7);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        print(node1);
    }
}

33 分行从上到下打印二叉树

1、题目

• 从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

2、思路

• 使用map来记录节点对应的层数，从0层开始计数。

3、代码

package com.xianhuii.practice1;

import org.junit.Test;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

public class O33 {
    private class BinaryTree {
        int value;
        BinaryTree left;
        BinaryTree right;

        BinaryTree(int value) {
            this.value = value;
        }
    }

    public void print(BinaryTree root) {
        if (root == null) {
            return;
        }
        Queue<BinaryTree> queue = new LinkedList<>();
        int index = 0;
        Map<BinaryTree, Integer> map = new HashMap<>();
        map.put(root, index);
        queue.add(root);
        int pre = index;
        while (!queue.isEmpty()) {
            BinaryTree binaryTree = queue.poll();
            index = map.get(binaryTree);
            index++;
            if (binaryTree.left != null) {
                map.put(binaryTree.left, index);
                queue.add(binaryTree.left);
            }
            if (binaryTree.right != null) {
                map.put(binaryTree.right, index);
                queue.add(binaryTree.right);
            }
            if (pre != map.get(binaryTree)) {
                System.out.println();
                pre = map.get(binaryTree);
                System.out.print(binaryTree.value);
            } else {
                if (map.get(binaryTree) == 0) {
                    System.out.print(binaryTree.value);
                } else {
                    System.out.print(" " + binaryTree.value);
                }
            }
        }
    }

    @Test
    public void test() {
        BinaryTree node1 = new BinaryTree(1);
        BinaryTree node2 = new BinaryTree(2);
        BinaryTree node3 = new BinaryTree(3);
        BinaryTree node4 = new BinaryTree(4);
        BinaryTree node5 = new BinaryTree(5);
        BinaryTree node6 = new BinaryTree(6);
        BinaryTree node7 = new BinaryTree(7);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        print(node1);
    }
}

34 之字形打印二叉树

1、题目

• 请实现一个函数，按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

2、思路

• 使用两个栈，一个栈存储当前层的节点，另一个栈存储下一层的节点。设置一个标志位flag，用于调整每一层节点的存储顺序。

3、代码

package com.xianhuii.practice1;

import org.junit.Test;

import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Stack;

public class O34 {
    private class BinaryTree {
        int value;
        BinaryTree left;
        BinaryTree right;

        BinaryTree(int value) {
            this.value = value;
        }
    }

    public void print(BinaryTree root) {
        if (root == null) {
            return;
        }
        Stack<BinaryTree> stack1 = new Stack<>();
        Stack<BinaryTree> stack2 = new Stack<>();
        Map<BinaryTree, Integer> map = new LinkedHashMap<>();
        int index = 0;
        map.put(root, index);
        stack1.push(root);
        int pre = index;
        boolean flag = true;
        while (!stack1.isEmpty() || !stack2.isEmpty()) {
            if (flag) {
                while (!stack1.isEmpty()) {
                    BinaryTree node = stack1.pop();
                    index = map.get(node);
                    if (pre != index) {
                        System.out.println();
                        pre = index;
                    }
                    System.out.print(node.value + " ");
                    index++;
                    if (node.left != null) {
                        stack2.push(node.left);
                        map.put(node.left, index);
                    }
                    if (node.right != null) {
                        stack2.push(node.right);
                        map.put(node.right, index);
                    }
                }
            } else {
                while (!stack2.isEmpty()) {
                    BinaryTree node = stack2.pop();
                    index = map.get(node);
                    if (pre != index) {
                        System.out.println();
                        pre = index;
                    }
                    System.out.print(node.value + " ");
                    index++;
                    if (node.right != null) {
                        stack1.push(node.right);
                        map.put(node.right, index);
                    }
                    if (node.left != null) {
                        stack1.push(node.left);
                        map.put(node.left, index);
                    }
                }
            }
            flag = !flag;
        }
    }

    @Test
    public void test() {
        BinaryTree node1 = new BinaryTree(1);
        BinaryTree node2 = new BinaryTree(2);
        BinaryTree node3 = new BinaryTree(3);
        BinaryTree node4 = new BinaryTree(4);
        BinaryTree node5 = new BinaryTree(5);
        BinaryTree node6 = new BinaryTree(6);
        BinaryTree node7 = new BinaryTree(7);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        print(node1);
    }
}

35 二叉搜索树的后序遍历序列

1、题目

• 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。假设输入的数组的任意两个数字都互不相同。

2、思路

• 递归，后序遍历根节点在最后面，而二叉搜索树的特征是“左小右大”，以此为条件，来以此遍历左右子树。

3、代码

import java.util.Properties;

public class Q35 {
    public static boolean judge(int[] arr) {
        if (arr.length == 0) {
            return false;
        }
        return process(arr, 0, arr.length - 1);
    }

    public static boolean process(int[] arr, int start, int end) {
        if (end - start <= 0) {
            return false;
        }
        int root = arr[end];
        int cur = start;
        while (cur < end && arr[cur] < root) {
            cur++;
        }
        for (int i = cur; i < end; i++) {
            if (arr[i] < root) {
                return false;
            }
        }
        return process(arr, start, cur - 1) && process(arr, cur, end - 1);
    }
}

36 二叉树中和为某一值的路径

1、题目

• 输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

2、思路

• 递归遍历

3、代码

package com.xianhuii.practice1;

import org.junit.Test;

public class O36 {
    private class BinaryTree {
        int value;
        BinaryTree left;
        BinaryTree right;

        BinaryTree(int value) {
            this.value = value;
        }
    }

    private void process(BinaryTree binaryTree, int target, String str) {
        if (binaryTree == null) {
            return;
        }
        target = target - binaryTree.value;
        if (target > 0) {
            str = str + binaryTree.value + "-";
        } else {
            str = str + binaryTree.value;
        }
        if (target == 0 && binaryTree.left == null && binaryTree.right == null) {
            System.out.println(str);
        }
        process(binaryTree.left, target, str);
        process(binaryTree.right, target, str);
    }

    public void path(BinaryTree binaryTree, int target) {
        process(binaryTree, target, "");
    }

    @Test
    public void test() {
        BinaryTree node1 = new BinaryTree(1);
        BinaryTree node2 = new BinaryTree(2);
        BinaryTree node3 = new BinaryTree(3);
        BinaryTree node4 = new BinaryTree(4);
        BinaryTree node5 = new BinaryTree(5);
        BinaryTree node6 = new BinaryTree(3);
        BinaryTree node7 = new BinaryTree(7);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        path(node1, 7);
    }
}

37 复杂链表的复制

1、题目

• 请实现函数复制一个复杂链表。在复杂链表中，每个节点除了有一个next指针指向下一个节点，还有一个random指针指向链表中的任意节点或者null。

2、思路

• 第一步：在每个节点的后面插入复制的节点。
• 第二步：对复制节点的random链接进行赋值。
• 第三步：拆分。

3、代码

public class Q37 {
    private static class ComplexListNode {
        int value;
        ComplexListNode next;
        ComplexListNode random;

        public ComplexListNode(int value) {
            this.value = value;
        }
    }

    public static ComplexListNode copy(ComplexListNode head) {
        if (head == null) {
            return null;
        }
        // 第一步：复制节点
        ComplexListNode cur = head;
        while (cur != null) {
            ComplexListNode copyNode = new ComplexListNode(cur.value);
            copyNode.next = cur.next;
            cur.next = copyNode;
            cur = copyNode.next;
        }
        // 第二步：建立random链接
        cur = head;
        while (cur != null) {
            ComplexListNode copyNode = cur.next;
            if (cur.random != null) {
                copyNode.random = cur.random.next;
            }
            cur = copyNode.next;
        }
        // 第三步：拆分
        cur = head;
        ComplexListNode copyHead = head.next;
        while (cur.next != null) {
            ComplexListNode next = cur.next;
            cur.next = next.next;
            cur = next;
        }
        return copyHead;
    }
}

38 二叉搜索树与双向链表

1、题目

• 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。

2、思路

• 二叉搜索树的中序遍历是一个从小到大的有序序列，因此，只需要在二叉树的中序遍历上做修改。

3、代码

public class Q38 {
    private class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    private TreeNode cur = null;

    public TreeNode convert(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode head = convert(root.left);
        if (head == null) {
            head = root;
        }
        root.left = cur;
        if (cur != null) {
            cur.right = root;
        }
        cur = root;
        convert(root.right);
        return head;
    }
}

39 序列化二叉树

1、代码

import java.util.LinkedList;
import java.util.Queue;

public class Q39 {
    private static class BinaryTree {
        int value;
        BinaryTree left;
        BinaryTree right;

        BinaryTree(int value) {
            this.value = value;
        }
    }

    public static String serialize(BinaryTree root) {
        if (root == null) {
            return "$,";
        }
        String res = root.value + ",";
        res += serialize(root.left);
        res += serialize(root.right);
        return res;
    }

    public static BinaryTree unSerialize(String str) {
        String[] strings = str.split(",");
        Queue<String> queue = new LinkedList<>();
        for (int i = 0; i < strings.length; i++) {
            queue.add(strings[i]);
        }
        return unSerializeByPreOrder(queue);
    }

    public static BinaryTree unSerializeByPreOrder(Queue<String> queue) {
        String str = queue.poll();
        if (str == "$") {
            return null;
        }
        BinaryTree head = new BinaryTree(Integer.valueOf(str));
        head.left = unSerializeByPreOrder(queue);
        head.right = unSerializeByPreOrder(queue);
        return head;
    }

}

40 字符串的排列

1、题目

• 输入一个字符串，打印出该字符串中字符的所有排列。例如，输入字符串abc，则打印出由字符a、b、c所能排列出来的所有字符串abc、acb、bac、bca、cab和ba。

2、思路

1. 求出所有可能出现在第一个位置的字符。
2. 固定第一个字符，求后面的所有字符的全排列，递归求解。

3、代码

public class Q40 {
    public static void print(char[] chars) {
        print(chars, 0);
    }

    private static void print(char[] chars, int index) {
        if (index == chars.length - 1) {
            System.out.print(String.valueOf(chars) + " ");
            return;
        }
        for (int i = index; i < chars.length; i++) {
            swap(chars, index, i);
            print(chars, index + 1);
            swap(chars, index, i);
        }
    }

    private static void swap(char[] chars, int index, int i) {
        char c = chars[index];
        chars[index] = chars[i];
        chars[i] = c;
    }
}

41 八皇后问题

1、题目

• 如何能够在8×8的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任何两个皇后都不能处于同一条横行、纵行或斜线上。
• 八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为n×n，而皇后个数也变成n。当且仅当n=1或n≥4时问题有解。

2、代码

package com.xianhuii.practice1;

import org.junit.Test;

public class O41 {
    private int count = 0;

    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    private void process(int[] arr, int index) {
        if (index == arr.length - 1) {
            for (int i = 0; i < arr.length; i++) {
                for (int j = 0; j < arr.length; j++) {
                    if (i != j && Math.abs(i - j) == Math.abs(arr[i] - arr[j])) {
                        return;
                    }
                }
            }
            count++;
            return;
        }
        for (int i = index; i < arr.length; i++) {
            swap(arr, index, i);
            process(arr, index + 1);
            swap(arr, index, i);
        }
    }

    public void process(int[] arr) {
        process(arr, 0);
    }

    public int getCount() {
        int[] arr = new int[]{1, 2, 3, 4, 5, 6, 7, 8};
        process(arr);
        return count;
    }

    @Test
    public void test() {
        System.out.println(getCount());
    }

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

1、题目

• 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
• 例如：输入一个长度为9的数组{1, 2, 3, 2, 2, 2, 5, 4, 2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。

2、思路

• 摩尔投票算法。

3、代码

package com.xianhuii.practice1;

import org.junit.Test;

public class O42 {
    public int find(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int majority = nums[0];
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            count = nums[i] == majority ? count + 1 : count - 1;
            if (count == 0) {
                majority = nums[i];
                count = 1;
            }
        }
        count = 0;
        for (int i = 0; i < nums.length; i++) {
            count = majority == nums[i] ? count + 1 : count;
        }
        return count > nums.length >> 1 ? majority : -1;
    }

    @Test
    public void test() {
        int[] arr = new int[]{1, 2, 3, 2, 2, 2, 5, 4, 2};
        System.out.println(find(arr));
    }
}

43 数组中出现次数超过n/3的数字

1、题目

• 找出数组中出现次数大于n/3次的所有元素。

2、思路

• 最多只有两个，使用投票法，将可能符合要求的两个元素找出来，然后再看他们是否都超过了n/3。

3、代码

import java.util.ArrayList;
import java.util.List;

public class Q43 {
    public static List<Integer> find(int[] nums) {
        if (nums == null || nums.length == 0) {
            return new ArrayList<>();
        }
        int[] majority = new int[2];
        int count1 = 0, count2 = 0;
        majority[0] = nums[0];
        majority[1] = -1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != majority[0]) {
                majority[1] = nums[i];
                break;
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == majority[0]) {
                count1++;
            } else if (nums[i] == majority[1]) {
                count2++;
            } else if (count1 == 0) {
                majority[0] = nums[i];
                count1 = 1;
            } else if (count2 == 0) {
                majority[1] = nums[i];
                count2 = 1;
            } else {
                count1--;
                count2--;
            }
        }
        count1 = 0;
        count2 = 0;
        for (int i = 0; i < nums.length; i++) {
            count1 = majority[0] == nums[i] ? count1 + 1 : count1;
            count2 = majority[1] == nums[i] ? count2 + 1 : count2;
        }
        List<Integer> list = new ArrayList<>();
        if (count1 > nums.length / 3) {
            list.add(majority[0]);
        }
        if (count2 > nums.length / 3) {
            list.add(majority[1]);
        }
        return list;
    }
}

44 最小的k个数

1、题目

• 输入n个整数，找出其中最小的k个数。例如，输入4、5、1、6、2、7、3、8这8个数，则最小的4个数字是1、2、3、4。

2、思路

• 使用最大堆来存储数据，维持最大堆的节点个数为k个。

3、代码

import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Q44 {
    public static ArrayList<Integer> getMinNumbers(int[] nums, int k) {
        if (k > nums.length || k <= 0) {
            return new ArrayList<>();
        }
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        for (int i = 0; i < nums.length; i++) {
            maxHeap.add(nums[i]);
            if (maxHeap.size() > k) {
                maxHeap.poll();
            }
        }
        return new ArrayList<>(maxHeap);
    }
}

45 数据流中的中位数

1、题目

• 如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

2、代码

package com.xianhuii.practice1;

import java.util.Comparator;
import java.util.PriorityQueue;

public class O45 {
    private PriorityQueue<Integer> minHeap = new PriorityQueue<>(new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o1 - o2;
        }
    });
    private PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2 - o1;
        }
    });

    public void add(int number) {
        if (maxHeap.isEmpty()) {
            maxHeap.add(number);
        } else {
            if (maxHeap.peek() >= number) {
                maxHeap.add(number);
            } else if (minHeap.isEmpty()) {
                minHeap.add(number);
            } else if (minHeap.peek() <= number) {
                minHeap.add(number);
            } else {
                maxHeap.add(number);
            }
        }
        modifyHeap();
    }

    private void modifyHeap() {
        if (maxHeap.si***Heap.size() + 2) {
            minHeap.add(maxHeap.poll());
        }
        if (minHeap.size() == maxHeap.size() + 2) {
            maxHeap.add(minHeap.poll());
        }
    }

    public double getMedian() {
        int minHeapSi***Heap.size();
        int maxHeapSize = maxHeap.size();
        double median = 0;
        if ((minHeapSize + maxHeapSize) % 2 == 0) {
            median = (minHeap.peek() + maxHeap.peek()) / 2.0;
        } else {
            median = minHeapSize > maxHeapSi***Heap.peek() : maxHeap.peek();
        }
        return median;
    }
}

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

1、题目

• 请实现一个函数用来找出字符流中第一个只出现一次的字符。
• 例如，当从字符流中只读出前面两个字符“go”时，第一个只出现一次的字符是“g”。当从该字符流中读出前六个字符“google”时，第一个只出现一次的字符是“l”。

2、思路

• 使用队列来存储字符，因为队列先进先出的特性，所以可以从第一个字符开始判断。然后使用一个int[256]的数组，用来存储字符出现的个数。

3、代码

import java.util.LinkedList;
import java.util.Queue;

public class Q46 {
    private Queue<Character> queue = new LinkedList<>();
    private int[] chars = new int[256];

    public void insert(char ch) {
        chars[ch]++;
        queue.add(ch);
    }

    public char find() {
        while (!queue.isEmpty()) {
            if (chars[queue.peek()] == 1) {
                return queue.peek();
            } else {
                queue.poll();
            }
        }
        return '#';
    }
}

47 连续子数组的最大和

1、题目

• 输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个正数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。
• 例如，输入的数组为{1, -2, 3, 10, -4,, 7, 2, -5}，和最大的子数组为{3, 10, -4, 7, 2}，因此输出为该子数组的和18。

2、思路

• 动态规划。

3、代码

package com.xianhuii.practice1;

import org.junit.Test;

public class O47 {
    /**
     *      {1, -2,  3, 10, -4,  7,  2, -5}
     * sum: 0,   1, -1, 10,  6, 13, 15, 10
     * max: MIN, 1,  1, 10, 10, 13, 15, 15
     */
    public int find1(int[] arr) {
        int max = Integer.MIN_VALUE;
        int sum = 0;
        for (int i = 0; i < arr.length; i++) {
            if (sum < 0) {
                max = arr[i] > max ? arr[i] : max;
                sum = arr[i];
            } else {
                sum += arr[i];
                max = sum > max ? sum : max;
            }
        }
        return max;
    }

    public int find2(int[] arr) {
        int[] s = new int[arr.length];
        int sum = 0;
        for (int i = 0; i < arr.length; i++) {
            if (sum < 0) {
                s[i] = arr[i] > s[i] ? arr[i] : s[i];
                sum = arr[i];
            } else {
                sum += arr[i];
                s[i] = sum > s[i] ? sum : s[i];
            }
        }
        int max = s[0];
        for (int i = 0; i < s.length; i++) {
            max = s[i] > max ? s[i] : max;
        }
        return max;
    }

    @Test
    public void test() {
        int[] arr = new int[]{1, -2, 3, 10, -4, 7, 2, -5};
        System.out.println(find1(arr));
        System.out.println(find2(arr));
    }
}

48 从1到n整数中1出现的次数

1、题目

• 输入一个整数n，求1~n这n个整数的十进制表示中1出现的次数。
• 例如，输入12，1~12这些整数中包含1的数字有1、10、11、12，1一共出现了5次。

2、代码

package com.xianhuii.practice1;

import org.junit.Test;

public class O48 {
    /**
     * n: 12
     * num: 1, 10
     * pre: 1, 0
     * cur: 2, 1
     * suf: 0, 2
     * sum: 2, 5
     */
    public int count(int n) {
        long sum = 0;
        long num = 1;
        long pre = 0;
        long cur = 0;
        long suf = 0;
        while (num <= n) {
            suf = n % num;
            cur = n % (num * 10) / num;
            pre = n / (num * 10);
            if (cur > 1) {
                sum += num * (pre + 1);
            } else if (cur == 1) {
                sum += num * pre + suf + 1;
            } else {
                sum += num * pre;
           }
            num *= 10;
        }
        return (int) sum;
    }

    @Test
    public void test() {
        System.out.println(count(12));
    }
}

49 数字序列中某一位数字

1、题目

• 数字以0123456789101112131415……的格式序列化到一个字符序列中。在这个序列中，第5位（从0开始计数）是5，第13位是1，第19位是4，等等。
• 请写一个函数，求任意第n位对应的数字。

2、代码

package com.xianhuii.practice1;

import org.junit.Test;

public class O49 {
    /**
     * 返回digit位数的第一个值
     *
     * @param digit
     * @return
     */
    private int getBeginNumber(int digit) {
        if (digit == 1) {
            return 0;
        }
        return (int) Math.pow(10, digit - 1);
    }

    /**
     * 返回所有digit位数的数字的总长度
     *
     * @param digit
     * @return
     */
    private int getDigitSum(int digit) {
        if (digit == 1) {
            return 10;
        } else {
            return digit * 9 * (int) (Math.pow(10, digit - 1));
        }
    }

    /**
     * @param index
     * @param digit
     * @return
     */
    private int digitAt(int index, int digit) {
        int begin = getBeginNumber(digit);
        int shiftNumber = index / digit;
        String number = (begin + shiftNumber) + "";
        int count = index % digit;
        return number.charAt(count) - '0';
    }

    public int getDigitAt(int index) {
        if (index < 0) {
            return -1;
        }
        int digit = 1;
        while (true) {
            if (index < getDigitSum(digit)) {
                return digitAt(index, digit);
            } else {
                index -= getDigitSum(digit);
                digit++;
            }
        }
    }

    @Test
    public void test() {
        System.out.println(getDigitAt(5));
        System.out.println(getDigitAt(13));
        System.out.println(getDigitAt(19));
    }
}

50 把数组排成最小的数

1、题目

• 输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
• 例如输入数组{3, 32, 321}，则打印出这三个数字能排成的最小数字为321323。

2、思路

• 可以看成是一个排序问题，在比较两个字符串s1和s2的大小时，应该比较的是s1+s2和s2+s1的大小，如果s1+s2<s2+s1，那么应该把s1排在前面，否则应该把s2排在前面。

3、代码

package com.xianhuii.practice1;

import org.junit.Test;

import java.util.Arrays;
import java.util.Comparator;

public class O50 {
    public String print(int[] nums) {
        if (nums == null || nums.length == 0) {
            return "";
        }
        String[] strings = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            strings[i] = nums[i] + "";
        }
        Arrays.sort(strings, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return (o1 + o2).compareTo(o2 + o1);
            }
        });
        String res = "";
        for (int i = 0; i < strings.length; i++) {
            res += strings[i];
        }
        return res;
    }

    @Test
    public void test() {
        int[] nums = new int[]{3, 32, 321};
        System.out.println(print(nums));
    }
}

51 把数字翻译成字符串

1、题目

• 给定一个数字，按照如下规则翻译成字符串：1翻译成“a”， 2翻译成“b”……26翻译成“z”。
• 一个数字有多种翻译可能，例如12258一共有5种，分别是abbeh，lbeh，aveh，abyh，lyh。
• 实现一个函数，用来计算一个数字有多少种不同的翻译方法。

2、代码

public class Q51 {
    // 递归
    public int count1(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        return count1(s, 0);
    }

    private int count1(String s, int start) {
        if (s.length() == start) {
            return 1;
        }
        if (s.charAt(start) == '0') {
            return 0;
        }
        int ans1 = count1(s, start + 1);
        int ans2 = 0;
        if (start < s.length() - 1) {
            int ten = (s.charAt(start) - '0') * 10;
            int one = s.charAt(start + 1) - '0';
            if (ten + one <= 26) {
                ans2 = count1(s, start + 2);
            }
        }
        return ans1 + ans2;
    }

    // 动态规划
    public int count2(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int len = s.length();
        int[] dp = new int[len + 1];
        dp[len] = 1;
        if (s.charAt(len - 1) == '0') {
            dp[len - 1] = 0;
        } else {
            dp[len - 1] = 1;
        }
        for (int i = len - 2; i >= 0; i--) {
            if (s.charAt(i) == '0') {
                dp[i] = 0;
                continue;
            }
            if (((s.charAt(i) - '0') * 10 + (s.charAt(i + 1) - '0')) <= 26) {
                dp[i] = dp[i + 1] + dp[i + 2];
            } else {
                dp[i] = dp[i + 1];
            }
        }
        return dp[0];
    }
}

52 礼物的最大价值

1、题目

• 在一个m×n的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一个，直到到达棋盘的右下角。给定一个棋盘及其上面的礼物，请计算你最多能拿到多少价值的礼物？

2、代码

public class Q52 {
    // 递归
    public int count1(int[][] board) {
        if (board == null || board.length == 0 || board[0].length == 0) {
            return 0;
        }
        return count1(board, 0, 0);
    }

    private int count1(int[][] board, int i, int j) {
        int res = board[i][j];
        if (i == board.length - 1 && j == board[0].length - 1) {
            return res;
        }
        if (i == board.length - 1) {
            return res + count1(board, i, j + 1);
        }
        if (j == board[0].length - 1) {
            return res + count1(board, i + 1, j);
        }
        return res + Math.max(count1(board, i + 1, j), count1(board, i, j + 1));
    }

    // 动态规划
    public int count2(int[][] board) {
        if (board == null || board.length == 0 || board[0].length == 0) {
            return 0;
        }
        int rows = board.length;
        int columns = board[0].length;
        int[][] dp = new int[rows][columns];
        dp[0][0] = board[0][0];
        for (int i = 1; i < rows; i++) {
            dp[i][0] = dp[i - 1][0] + board[i][0];
        }
        for (int i = 1; i < columns; i++) {
            dp[0][i] = dp[0][i - 1] + board[0][i];
        }
        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < columns; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + board[i][j];
            }
        }
        return dp[rows - 1][columns - 1];
    }
}

53 最长不含重复字符的子字符串

1、题目

• 输入一个字符串（只包含a~z的字符），求其最长不含重复字符的子字符串的长度。
• 例如对于arabcacfr，最长不含重复字符的子字符串为acfr，长度为4。

2、思路

• 动态规划。
• f(i)：以第i个字符为结尾的不包含重复字符的子字符串的最长长度。
• 如果第i个字符之前没有出现过，那么f(i)=f(i-1)+1；
• 如果第i个字符出现过，先计算两个同样字符之间的距离d：如果d>f(i-1)，说明第i个字符没有在f(i-1)的最长字符串中出现过，f(i)=f(i-1)+1；如果d≤f(i-1)，则说明第i个字符在f(i-1)的最长子字符串中出现过，f(i)=d。

3、代码

public class Q53 {
    public int maxLength(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int[] pre = new int[128];
        for (int i = 0; i < pre.length; i++) {
            pre[i] = -1;
        }
        int maxLen = 0;
        int curLen = 0;
        for (int i = 0; i < s.length(); i++) {
            int c = s.charAt(i);
            int preIndex = pre[c];
            if (preIndex == -1 || i - preIndex > curLen) {
                curLen++;
                maxLen = Math.max(curLen, maxLen);
            } else {
                maxLen = Math.max(curLen, maxLen);
                int d = i - preIndex;
                curLen = d;
            }
            pre[c] = i;
        }
        return maxLen;
    }
}

54 丑数

1、题目

• 把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。习惯上我们把1当做是第一个丑数。
• 求按小到大的顺序的第N个丑数。

2、代码

public class Q54 {
    // 顺序查找
    public int get1(int index) {
        if (index == 0) {
            return 0;
        }
        int res = 0;
        int count = 0;
        int i = 1;
        while (true) {
            if (judge(i)) {
                count++;
                if (count == index) {
                    res = i;
                    break;
                }
            }
            i++;
        }
        return res;
    }

    private Boolean judge(int num) {
        while (num % 2 == 0) {
            num /= 2;
        }
        while (num % 3 == 0) {
            num /= 3;
        }
        while (num % 5 == 0) {
            num /= 5;
        }
        if (num == 1) {
            return true;
        }
        return false;
    }

    // 动态规划
    public int get2(int index) {
        if (index == 0) {
            return 0;
        }
        int i2 = 0, i3 = 0, i5 = 0;
        int[] dp = new int[index];
        dp[0] = 1;
        for (int i = 1; i < index; i++) {
            int next2 = dp[i2] * 2, next3 = dp[i3] * 3, next5 = dp[i5] * 5;
            dp[i] = Math.min(next2, Math.min(next3, next5));
            if (dp[i] == next2) {
                i2++;
            }
            if (dp[i] == next3) {
                i3++;
            }
            if (dp[i] == next5) {
                i5++;
            }
        }
        return dp[index - 1];
    }
}

55 第一个只出现一次的字符位置

1、题目

• 在一个字符串中找到第一个只出现一次的字符，并返回它的位置。
• 例如：对于abacc，输出为b。

2、思路

• 使用数组来记录字符出现的次数，遍历两遍，时间复杂度O(n)。

3、代码

public class Q55 {
    public int find(String str) {
        int[] counts = new int[256];
        for (int i = 0; i < str.length(); i++) {
            counts[str.charAt(i)]++;
        }
        for (int i = 0; i < str.length(); i++) {
            if (counts[str.charAt(i)] == 1) {
                return i;
            }
        }
        return -1;
    }
}

56 字符流中第一个只出现一次的字符

1、题目

• 请实现一个函数，用来找出字符流中第一个只出现一次的字符。
• 例如，当从字符流中读出前两个字符“go”时，第一个只出现一次的字符是'g'；当从该字符流中读出前6个字符“google"时，第一个只出现一次的字符是”l“。

2、代码

public class Q56 {
    private int[] codes = new int[256];
    private int index;

    public Q56() {
        index = 0;
        for (int i = 0; i < codes.length; i++) {
            codes[i] = -1;
        }
    }

    public void insert(char ch) {
        if (codes[ch] == -1) {
            codes[ch] = index;
        } else {
            codes[ch] = -2;
        }
        index++;
    }

    public char find() {
        char ch = 0;
        int minIndex = Integer.MAX_VALUE;
        for (int i = 0; i < 256; i++) {
            if (codes[i] >= 0 && codes[i] < minIndex) {
                ch = (char) i;
                minIndex = codes[i];
            }
        }
        return ch;
    }
}

57 数组中的逆序对

1、题目

• 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。
• 输入一个数组，求出这个数组中的逆序对的总数。

2、代码

public class Q57 {
    // 循序查找，O(n^2)
    public int count1(int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
        long res = 0;
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] > arr[j]) {
                    res++;
                }
            }
        }
        return (int) (res % 1000000007);
    }

    // 归并，O(nlogn)
    private int[] help;

    public int count2(int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
        return (int) (mergeSort(arr, 0, arr.length - 1) % 1000000007);
    }

    private long mergeSort(int[] arr, int left, int right) {
        if (left == right) {
            return 0;
        }
        int mid = left + ((right - left) >> 1);
        return mergeSort(arr, left, mid) + mergeSort(arr, mid + 1, right) + merge(arr, left, mid, right);
    }

    private long merge(int[] arr, int left, int mid, int right) {
        help = new int[right - left + 1];
        int i = 0;
        int p1 = left;
        int p2 = mid + 1;
        long res = 0;
        while (p1 <= mid && p2 <= right) {
            if (arr[p1] > arr[p2]) {
                for (int j = p2; j <= right; j++) {
                    res++;
                }
            }
            help[i++] = arr[p1] > arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= mid) {
            help[i++] = arr[p1++];
        }
        while (p2 <= right) {
            help[i++] = arr[p2++];
        }
        for (int j = 0; j < help.length; j++) {
            arr[left + j] = help[j];
        }
        return res;
    }
}

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

1、思路

• 方式一：使用HashSet。
• 方式二：获取两个链表的长度，计算得到两者长度差值k。先让较长的链表头指针先移动k步，然后一起移动。当两者指针相同时，即为第一个公共节点。

2、代码

import java.util.HashSet;
import java.util.Set;

public class Q58 {
    private class ListNode {
        int val;
        ListNode next;

        ListNode(int val) {
            this.val = val;
        }
    }

    // 方式一：使用HashSet
    public ListNode find1(ListNode pHead1, ListNode pHead2) {
        Set<ListNode> set = new HashSet<>();
        ListNode cur1 = pHead1;
        ListNode cur2 = pHead2;
        while (cur1 != null) {
            set.add(cur1);
            cur1 = cur1.next;
        }
        while (cur2 != null) {
            if (set.contains(cur2)) {
                return cur2;
            }
            cur2 = cur2.next;
        }
        return null;
    }

    // 方式二：
    public ListNode find2(ListNode pHead1, ListNode pHead2) {
        int len1 = 0, len2 = 0;
        ListNode cur1 = pHead1;
        ListNode cur2 = pHead2;
        while (cur1 != null) {
            len1++;
            cur1 = cur1.next;
        }
        while (cur2 != null) {
            len2++;
            cur2 = cur2.next;
        }
        int max = Math.max(len1, len2);
        int move1 = max - len2;
        int move2 = max - len1;
        cur1 = pHead1;
        cur2 = pHead2;
        while (move1 != 0) {
            cur1 = cur1.next;
            move1--;
        }
        while (move2 != 0) {
            cur2 = cur2.next;
            move2--;
        }
        while (cur1 != null && cur2 != null) {
            if (cur1.val == cur2.val) {
                return cur1;
            }
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return null;
    }
}

59 数字在排序数组中出现的次数

1、题目

• 输入：nums = 1, 2, 3, 3, 3, 3, 4, 6；k = 3
• 输出：4

2、代码

public class Q59 {
    public int count(int[] arr, int k) {
        int first = getFirstIndex(arr, k);
        int last = getLastIndex(arr, k);
        return last - first + 1;
    }

    private int getFirstIndex(int[] data, int k) {
        int start = 0, end = data.length - 1;
        int mid = (start + end) >> 1;
        while (start <= end) {
            if (data[mid] < k) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
            mid = (start + end) >> 1;
        }
        return start;
    }

    private int getLastIndex(int[] data, int k) {
        int start = 0, end = data.length - 1;
        int mid = (start + end) >> 1;
        while (start <= end) {
            if (data[mid] <= k) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
            mid = (start + end) >> 1;
        }
        return end;
    }
}

60 0~(n-1)中缺失的数字

1、题目

• 一个长度为(n-1)的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0~(n-1)之内。
• 在范围0~(n-1)内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

2、代码

public class Q60 {
    public int find(int[] arr, int len) {
        if (arr == null || len <= 0) {
            return -1;
        }
        int left = 0;
        int right = len - 1;
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (arr[mid] != mid) {
                if (mid == 0 || arr[mid - 1] == mid - 1) {
                    return mid;
                }
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        if (left == len) {
            return left;
        }
        return -1;
    }
}

61 数组中数值和下标相等的元素

1、题目

• 假设一个单调递增的数组里的每个元素都是整数并且是唯一的。请编写一个函数，找出数组中任意一个数值等于其下标的元素。
• 例如，在数组{-3, -1, 1, 3, 5}中，数字3和它的下标相等。

2、代码

public class Q61 {
    public int find(int[] arr) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (arr[mid] == mid) {
                return mid;
            } else if (arr[mid] > mid) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }
}

62 二叉查找树的第k个节点

1、题目

• 给定一棵二叉搜索树，请找出其中第k大的节点。

2、思路

• 二叉搜索树的中序遍历是一个递增序列。

3、代码

public class Q62 {
    private class TreeNode {
        int val = 0;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    private int count = 0;
    private TreeNode res;

    public TreeNode find(TreeNode root, int k) {
        inOrder(root, k);
        return res;
    }

    private void inOrder(TreeNode root, int k) {
        if (root == null || count > k) {
            return;
        }
        inOrder(root.left, k);
        count++;
        if (count == k) {
            res = root;
        }
        inOrder(root.right, k);
    }
}

63 二叉树的深度

1、思路

• 递归遍历，根节点的深度是左子树和右子树中较大的深度+1。

2、代码

public class Q63 {
    private class TreeNode {
        int val = 0;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public int depth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return 1 + Math.max(depth(root.left), depth(root.right));
    }
}

64 平衡二叉树

1、代码

public class Q64 {
    private class TreeNode {
        int val = 0;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public boolean isBalanced(TreeNode root) {
        return height(root) != -1;
    }

    private int height(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = height(root.left);
        if (left == -1) {
            return -1;
        }
        int right = height(root.right);
        if (right == -1) {
            return -1;
        }
        return Math.abs(left - right) > 1 ? -1 : Math.max(left, right) + 1;
    }
}

65 数组中只出现一次的两个数字

1、题目

• 一个整型数组里除了两个数字值出现一次之外，其他的数字都出现了两次，找出这两个只出现一次的数字。

2、思路

• 异或：a ^ a = 0；a ^ 0 = a。

3、代码

package com.xianhuii.practice1;

import org.junit.Test;

import java.util.Arrays;

public class O65 {
    public int[] find(int[] arr) {
        int[] nums = new int[2];
        int diff = 0;
        for (int num : arr) {
            diff ^= num;
        }
//        System.out.println(diff); // 3 ^ 4
        diff = diff & (-diff);
        for (int num : arr) {
            if ((num & diff) == 0) {
                nums[0] ^= num;
            } else {
                nums[1] ^= num;
            }
        }
        return nums;
    }

    @Test
    public void test() {
        int[] arr = new int[]{1, 1, 2, 2, 3, 4, 5, 5, 6, 6};
        int[] nums = find(arr);
        System.out.println(Arrays.toString(nums));
    }
}

66 数组中唯一只出现一次的数字

1、题目

• 一个整型数组里除了1个数字只出现一次之外，其他的数字都出现了3次，找出只出现一次的数字。

2、代码

package com.xianhuii.practice1;

import org.junit.Test;

public class O66 {
    public int find(int[] arr) {
        if (arr == null || arr.length == 0) {
            throw new RuntimeException("input error!");
        }
        int[] bitArr = new int[32];
        int bitMask = 1;
        for (int i = 31; i >= 0; i--) {
            for (int j = 0; j < arr.length; j++) {
                int bit = bitMask & arr[j];
                if (bit != 0) {
                    bitArr[i] += 1;
                }
            }
            bitMask = bitMask << 1;
        }
        int res = 0;
        for (int i = 0; i < 32; i++) {
            res = res << 1;
            res += bitArr[i] % 3;
        }
        return res;
    }

    @Test
    public void test() {
        int[] arr = new int[]{1, 1, 1, 2, 2, 2, 3, 4, 4, 4, 5, 5, 5};
        System.out.println(find(arr));
    }
}

67 和为s的数字

1、题目

• 输入一个递增排序的数组和一个数字sum，在数组中查找两个数，使得它们的和正好是s。
• 如果有多对数字的和等于sum，则输出任意一对即可。

2、代码

package com.xianhuii.practice1;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;

public class O67 {
    public ArrayList<Integer> find(int[] arr, int sum) {
        ArrayList<Integer> list = new ArrayList<>();
        int length = arr.length;
        for (int i = 0; i < length; i++) {
            for (int j = i + 1; j < length; j++) {
                if (arr[i] + arr[j] == sum) {
                    list.add(arr[i]);
                    list.add(arr[j]);
                    return list;
                }
            }
        }
        return list;
    }

    @Test
    public void test() {
        int[] arr = new int[]{1,2,3,4,5,6,7,8};
        ArrayList<Integer> arrayList = find(arr, 8);
        for (int num : arrayList) {
            System.out.println(num);
        }
    }
}

68 和为s的连续正数序列

1、题目

• 输入一个正数s，打印出所有和为s的连续正数序列（至少含有两个数）。
• 例如，输入15，由于1+2+3+4+5=4+5+6=7+8=15，所以打印出3个连续序列1~5、4~6和7~8。

2、代码

package com.xianhuii.practice1;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

public class O68 {
    private int getCurSum(int small, int big) {
        return (big - small + 1) * (small + big) / 2;
    }

    public List<List<Integer>> find(int sum) {
        int small = 1;
        int big = 2;
        List<List<Integer>> lists = new ArrayList<>();
        while (small <= (1 + sum) >> 1) {
            int curSum = getCurSum(small, big);
            if (curSum == sum) {
                List<Integer> list = new ArrayList<>();
                for (int i = small; i <= big; i++) {
                    list.add(i);
                }
                lists.add(list);
                big++;
            } else if (curSum < sum) {
                big++;
            } else {
                small++;
            }
        }
        return lists;
    }

    @Test
    public void test() {
        List<List<Integer>> lists = find(15);
        for (List<Integer> list : lists) {
            for (int num : list) {
                System.out.print(num + " ");
            }
            System.out.println();
        }
    }
}

69 翻转单词顺序

1、题目

• 输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为了简单起见，表单符号和普通字母一样处理。
• 例如输入字符串“I am a student."，则输出”student. a am I"。

2、代码

package com.xianhuii.practice1;

import org.junit.Test;

public class O69 {
    private void reverse(char[] chars, int begin, int end) {
        char tmp = 0;
        while (begin < end) {
            tmp = chars[begin];
            chars[begin] = chars[end];
            chars[end] = tmp;
            begin++;
            end--;
        }
    }

    public String revSentence(String str) {
        if (str == null || str.length() == 0) {
            return str;
        }
        char[] chars = str.toCharArray();
        reverse(chars, 0, chars.length - 1);
        int begin = 0;
        int end = 0;
        while (begin < chars.length) {
            if (chars[end] == ' ' || end == chars.length - 1) {
                int tmp_end = end;
                if (chars[end] == ' ') {
                    tmp_end = end - 1;
                }
                reverse(chars, begin, tmp_end);
                end++;
                begin = end;
            } else {
                end++;
            }
        }
        return String.valueOf(chars);
    }

    @Test
    public void test() {
        String str = "I am a student.";
        System.out.println(revSentence(str));
    }
}

70 左旋转字符串

1、题目

• 字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。
• 请定义一个函数实现字符串左旋转的功能。比如，输入字符串“abcdefg”和数字2，该函数将返回左旋转两位得到的结果“cdefgab”。

2、思路

• 翻转三次，根据n把字符串分成两部分，然后分别对这两部分进行翻转，最后再对整个字符串进行翻转。

3、代码

package com.xianhuii.practice1;

import org.junit.Test;

public class O70 {
    private void reverse(char[] chars, int begin, int end) {
        char tmp = 0;
        while (begin < end) {
            tmp = chars[begin];
            chars[begin] = chars[end];
            chars[end] = tmp;
            begin++;
            end--;
        }
    }

    public String leftRotate(String str, int n) {
        if (str == null || str.length() == 0) {
            return str;
        }
        if (n <= 0 || n >= str.length()) {
            throw new RuntimeException("error n!");
        }
        char[] chars = str.toCharArray();
        reverse(chars, 0, n - 1);
        reverse(chars, n, chars.length - 1);
        reverse(chars, 0, chars.length - 1);
        return String.valueOf(chars);
    }

    @Test
    public void test() {
        String str = "abcdefg";
        System.out.println(leftRotate(str, 2));
    }
}

71 滑动窗口的最大值

1、题目

• 给定一个数组和滑动窗口的大小，请找出所有滑动窗口里的最大值。
• 例如，如果输入数组{2, 3, 4, 2, 6, 2, 5, 2}及滑动窗口的大小3，那么一共存在6个滑动窗口，它们的最大值分别为{4, 4, 6, 6, 6, 5}。

2、代码

import java.util.ArrayDeque;
import java.util.ArrayList;

public class Q71 {
    // 方式一：遍历
    public ArrayList<Integer> max1(int[] num, int size) {
        ArrayList<Integer> res = new ArrayList<>();
        if (num == null || num.length == 0) {
            return res;
        }
        if (size <= 0 || size > num.length) {
            throw new RuntimeException("error size!");
        }
        int index = 0;
        while (index + size <= num.length) {
            int max = Integer.MIN_VALUE;
            for (int i = index; i < size + index; i++) {
                max = Math.max(max, num[i]);
            }
            res.add(max);
            index++;
        }
        return res;
    }

    // 方式二：双端队列
    public ArrayList<Integer> max2(int[] num, int size) {
        ArrayList<Integer> res = new ArrayList<>();
        if (num == null || num.length == 0) {
            return res;
        }
        if (size <= 0 || size > num.length) {
            throw new RuntimeException("error size!");
        }
        ArrayDeque<Integer> deque = new ArrayDeque<>();
        int begin = 0;
        for (int i = 0; i < num.length; i++) {
            begin = i - size + 1;
            if (deque.isEmpty()) {
                deque.addLast(i);
            } else if (begin > deque.peekFirst()) {
                deque.pollFirst();
            }
            while (!deque.isEmpty() && num[deque.peekLast()] <= num[i]) {
                deque.pollLast();
            }
            deque.addLast(i);
            if (begin >= 0) {
                res.add(num[deque.peekFirst()]);
            }
        }
        return res;
    }
}

72 队列的最大值

1、题目

• 请定义一个队列并实现函数max得到队列里的最大值。
• 要求函数max、push、pop的时间复杂度都是O(1)。

2、思路

• 定义两个双端队列data、maxData，分别用来存储队列的元素和当前队列里的最大值。

3、代码

import java.util.ArrayDeque;

public class Q72 {
    public class MaxQueue {
        class InternalData {
            int number;
            int index;

            public InternalData(int number, int index) {
                this.number = number;
                this.index = index;
            }
        }

        ArrayDeque<InternalData> data;
        ArrayDeque<InternalData> maxData;
        int curIndex;

        public MaxQueue() {
            curIndex = 0;
        }

        public int max() {
            if (maxData.isEmpty()) {
                throw new RuntimeException("maxData is empty!");
            }
            return maxData.pollFirst().number;
        }

        public void push(int number) {
            while (!maxData.isEmpty() && maxData.peekLast().number <= number) {
                maxData.pollLast();
            }
            InternalData internalData = new InternalData(number, curIndex);
            data.addLast(internalData);
            maxData.addLast(internalData);
            curIndex++;
        }

        public void pop() {
            if (maxData.isEmpty()) {
                throw new RuntimeException("maxData is empty");
            }
            if (maxData.peekFirst() == data.peekFirst()) {
                maxData.pollFirst();
            }
            data.pollFirst();
        }
    }
}

73 n个骰子的点数

1、题目

• 把n个骰子仍在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。

2、代码

import java.util.AbstractMap;
import java.util.ArrayList;
import java.util.List;
import java.util.Map;

public class Q73 {
    // 方式一：动态规划
    public List<Map.Entry<Integer, Double>> count1(int n) {
        List<Map.Entry<Integer, Double>> res = new ArrayList<>();
        long[][] dp = new long[n + 1][6 * n + 1];
        for (int i = 1; i <= 6; i++) {
            dp[1][i] = 1;
        }
        for (int i = 2; i <= n; i++) {
            for (int j = 1 * i; j <= 6 * n; j++) {
                for (int k = 1; k <= 6 && k <= j; k++) {
                    dp[i][j] += dp[i - 1][j - k];
                }
            }
        }
        double totalNum = Math.pow(6, n);
        double p = 0;
        for (int i = n; i <= 6 * n; i++) {
            p = dp[n][i] / totalNum;
            p = Double.valueOf(String.format("%.2f", p));
            res.add(new AbstractMap.SimpleEntry<>(i, p));
        }
        return res;
    }

    // 方式二：递归
    public List<Map.Entry<Integer, Double>> count2(int n) {
        List<Map.Entry<Integer, Double>> res = new ArrayList<>();
        double totalNum = Math.pow(6, n);
        double p = 0;
        long count = 0;
        for (int i = n; i <= 6 * n; i++) {
            count = getCount(n, i);
            p = count / totalNum;
            p = Double.valueOf(String.format("%.2f", p));
            res.add(new AbstractMap.SimpleEntry<>(i, p));
        }
        return res;
    }

    private long getCount(int num, int sum) {
        if (num < 1 || sum > 6 * num || sum < num) {
            return 0;
        }
        if (num == 1) {
            return 1;
        }
        long count = getCount(num - 1, sum - 1) + getCount(num - 1, sum - 2)
                + getCount(num - 1, sum - 3) + getCount(num - 1, sum - 4)
                + getCount(num - 1, sum - 5) + getCount(num - 1, sum - 6);
        return count;
    }
}

74 扑克牌中的顺子

1、题目

• 从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2~10为数字本身，A为1，J为11，Q为12，K为13，而大、小王可以看成任意数字。

2、代码

import java.util.Arrays;

public class Q74 {
    public boolean isContinuous(int[] numbers) {
        if (numbers.length < 5) {
            return false;
        }
        Arrays.sort(numbers);
        int countZero = 0;
        for (int i = 0; i < numbers.length; i++) {
            if (numbers[i] == 0) {
                countZero++;
            }
        }
        for (int i = countZero; i < numbers.length - 1; i++) {
            if (numbers[i] == numbers[i + 1]) {
                return false;
            }
            countZero = countZero - (numbers[i + 1] - numbers[i] - 1);
        }
        return countZero >= 0;
    }
}

75 圆圈中最后剩下的数字

1、题目

• 0，1，……，n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。

2、代码

package com.xianhuii.practice1;

public class O75 {
    // 方式一：数组模拟
    public int last1(int n, int m) {
        if (n == 0 || m == 0) {
            return -1;
        }
        int[] arr = new int[n];
        int count = n;  // 圆圈中剩下的数字
        int index = 0;  // 当前索引
        while (count != 1) {
            for (int i = 1; i < m; index++) {   // 每次往后数m个数字
                if (index == n) {   // 如果索引到头，重新开始
                    index = 0;
                }
                while (arr[index] == 1) {   // 跳过已访问的索引
                    index++;
                    if (index == n) {
                        index = 0;
                    }
                }
                i++;
            }
            if (index == n) {
                index = 0;
            }
            for (int i = index; i <= n; i++) { // 将当前索引的值置为1
                if (i == n) {
                    i = 0;
                }
                if (arr[i] == 0) {
                    arr[i] = 1;
                    index = i;
                    break;
                }
            }
            count--;
        }
        for (int i = 0; i < n; i++) {   // 遍历得到最后一个未访问的值
            if (arr[i] != 1) {
                return i;
            }
        }
        return -1;
    }

    // 方式二：f(n, m) = (f(n-1, m) + m) % n
    public int last2(int n, int m) {
        if (n == 0 || m == 0) {
            return -1;
        }
        if (n == 1) {
            return 0;
        }
        return (last2(n - 1, m) + m) % n;
    }
}

76 股票的最大利润

1、题目

• 假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？
• 例如，一只股票在某些时间节点的价格为{9, 11, 8, 5, 7, 12, 16, 14}。如果我们能在价格为5的时候买入并在价格为16时卖出，则能收获最大的利润11。

2、代码

public class Q76 {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length < 2) {
            return 0;
        }
        int min = prices[0];
        int maxProfit = prices[1] - prices[0];
        for (int i = 1; i < prices.length; i++) {
            maxProfit = maxProfit > prices[i] - min ? maxProfit : prices[i] - min;
            if (prices[i] < min) {
                min = prices[i];
            }
        }
        if (maxProfit < 0) {
            return 0;
        }
        return maxProfit;
    }
}

77 买卖股票的最佳时机II

1、题目

• 给定一个数组，它的第i个元素是一支给定股票第i天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
• 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

2、思路

• 计算连续递增的子序列之和，时间复杂度O(n)。

3、代码

public class Q77 {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length < 2) {
            return 0;
        }
        int maxProfit = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1]) {
                maxProfit += prices[i] - prices[i - 1];
            }
        }
        return maxProfit;
    }
}

78 求1+2+3+……+n

1、题目

• 不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句A ? B : C。

2、代码

public class Q78 {
    public int sum(int n) {
        int sum = n;
        boolean b = (n > 0) && ((sum += sum(n - 1)) > 0);
        return sum;
    }
}

79 不用加减乘除做加法

1、题目

• 写一个函数，求两个整数之和，要求不得使用+、-、*、/四则运算符号。

2、思路

• a ^ b表示没有考虑进位的情况下两数的和，(a & b) << 1就是进位。

3、代码

public class Q79 {
    // 方式一：使用位运算符（循环）
    public int add1(int num1, int num2) {
        int res = num1 ^ num2;
        int flag = (num1 & num2) << 1;
        int tmp;
        while (flag != 0) {
            tmp = res;
            res = tmp ^ flag;
            flag = (tmp & flag) << 1;
        }
        return res;
    }

    // 方式二：使用位运算符（递归）
    public int add2(int a, int b) {
        return b == 0 ? a : add1(a ^ b, (a & b) << 1);
    }
}

80 构建乘积数组

1、题目

• 给定一个数组A[0, 1, ……, n-1]，请构建一个数组B[0, 1, ……, n-1]，其中B中的元素B[i]=A[0]A[1]……A[i-1]A[i+1]……A[n-1]。
• 要求不能使用除法。

2、代码

public class Q80 {
    public int[] mul(int[] A) {
        if (A == null || A.length == 0) {
            return A;
        }
        int[] B = new int[A.length];
        int[] C = new int[A.length];
        int[] D = new int[A.length];
        C[0] = 1;
        D[D.length - 1] = 1;
        for (int i = 1; i < C.length; i++) {
            C[i] = C[i - 1] * A[i - 1];
        }
        for (int i = D.length - 2; i >= 0; i--) {
            D[i] = D[i + 1] * A[i + 1];
        }
        for (int i = 0; i < B.length; i++) {
            B[i] = C[i] * D[i];
        }
        return B;
    }
}

81 把字符串转换成整数

1、题目

• 将一个字符串转换成一个整数，字符串不是一个合法的数值则返回0，要求不能使用字符串转换整数的库函数。

2、代码

public class Q81 {
    public int transfer(String str) {
        if (str == null || str.length() == 0) {
            return 0;
        }
        char[] chars = str.toCharArray();
        long res = 0;
        boolean isNegative = str.charAt(0) == '-';
        for (int i = 0; i < chars.length; i++) {
            if (i == 0 && (chars[i] == '+') || chars[i] == '-') {
                continue;
            }
            if (chars[i] >= '0' && chars[i] <= '9') {
                res += Math.pow(10, chars.length - i - 1) * (chars[i] - '0');
            } else {
                return 0;
            }
        }
        res = isNegative ? -res : res;
        if (res > Integer.MIN_VALUE || res > Integer.MAX_VALUE) {
            return 0;
        }
        return (int) res;
    }
}

82 二叉搜索树的最近公共祖先

1、题目

• 给定一个二叉搜索树，找到该树中两个指定节点的最近公共祖先。

2、思路

• 从根节点开始遍历。
• 如果p、q都在左子树上，那么以左孩子为根节点继续遍历。
• 如果p、q都在右子树上，那么以右孩子为根节点继续遍历。
• 否则，当前节点即为最近公共祖先。

3、代码

public class Q82 {
    private class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int val) {
            this.val = val;
        }
    }

    public TreeNode find(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return root;
        }
        if (root.val > p.val && root.val > q.val) {
            return find(root.left, p, q);
        }
        if (root.val < p.val && root.val < q.val) {
            return find(root.right, p, q);
        }
        return root;
    }
}