剑指Offer题解

public class Sl {

    /**
     * 思路：二路计数，由于n+1长度的数组都在1-n之间，所以可以用区间个数来找重复的数
     * 比如，如果数组长度为8，则数字都在1-7之间，将数字的区间分为[1-4]和[5-7]
     * 然后如果数组中的数在[1-4]中的数超过了4个，则重复的数一定在这个区间中。
     * 否则就在[5-7]中。然后对区间再次划分，比如如果重复的数在[1-4]中，将区间划分为[1-2]和[3-4]，重复上述步骤。
     * 最后如果发现重复数字在[3-4]中，就查找3出现的次数和4出现的次数，就能找到那个重复的数
     */
    public int findRepeatNumber(int[] nums) {
        if (nums.length < 2 || nums == null) {
            return -1;
        }
        //定义初始区间
        int start = 1;
        int end = nums.length - 1;
        while (start <= end) {
            // 中位数
            int mid = ((end - start) >> 1) + start;
            // 统计区间中的数字的数量
            int count = countRange(nums, start, mid);
            // 如果此时区间只有一个数，判断count是否>1，大于一说明就是这个数重复，不大于一说明找不到重复的数
            if (start == end) {
                if (count > 1)
                    return start;
                else
                    return -1;
            }

            if (count > mid - start + 1) {
                end = mid;
            } else {
                start = mid + 1;
            }
        }
        return -1;
    }

    // 用来统计[start，end]中的数组个数
    private int countRange(int[] nums, int start, int end) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= start && nums[i] <= end) {
                count++;
            }
        }
        return count;
    }
}

/**
 * 找出数组中重复的数字。
 * <p>
 * 在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
 * <p>
 * 示例 1：
 * 输入：
 * [2, 3, 1, 0, 2, 5, 3]
 * 输出：2 或 3
 * <p>
 * 限制：
 * 2 <= n <= 100000
 */
public class 剑指Offer03数组中重复的数字 {

    /**
     * 思路：利用哈希桶思想，从头开始遍历数组，如果nums[i] == i，说明放置正确，跳过
     * 如果nums[i] != i;就把nums[i]放到nums[nums[i]]上去，一直到nums[i] == i为止。
     * 如果在放置nums[i]的过程中发现nums[nums[i]] == nums[i]，说明nums[i]重复了
     */
    public int findRepeatNumber(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            while (nums[i] != i) {
                if (nums[nums[i]] == nums[i]) {
                    return nums[i];
                }

                int temp = nums[i];
                nums[i] = nums[temp];
                nums[temp] = temp;
            }
        }
        return -1;
    }

}

/**
 * 在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
 * 请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
 * <p>
 * 示例:
 * 现有矩阵 matrix 如下：
 * [
 * [1,   4,  7, 11, 15],
 * [2,   5,  8, 12, 19],
 * [3,   6,  9, 16, 22],
 * [10, 13, 14, 17, 24],
 * [18, 21, 23, 26, 30]
 * ]
 * 给定 target = 5，返回 true。
 * 给定 target = 20，返回 false。
 * 限制：
 * 0 <= n <= 1000
 * 0 <= m <= 1000
 */
public class 剑指Offer04二维数组中的查找 {
    /**
     * 思路：nums[0].leng = n。选取数组右上角的数字nums[0][n-1]，比较target和nums[0][n-1]的大小。
     * 如果target > nums[0][n-1],说明target只能在nums[0][n-1]的下面，于是排除第一行，即nums[0]。
     * 如果target < nums[0][n-1],说明target只能在nums[0][n-1]的左边，于是排除最后一列，即nums[i][n-1]。
     * 依次类推，每次选择右上角进行排除，直到找到target为止
     */
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        boolean found = false;
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return found;
        // 先定义指针
        int downMax = matrix.length - 1; // 往下搜索的边界
        int rightMax = matrix[0].length - 1; // 往右搜索的边界
        int downCurr = 0;
        int rightCurr = matrix[0].length - 1; // 初始化一开始从右上角搜索
        while (downCurr >= 0 && rightCurr >= 0 && downCurr <= downMax && rightCurr <= rightMax) {
            if (matrix[downCurr][rightCurr] == target) {
                found = true;
                break;
            } else if (matrix[downCurr][rightCurr] < target) {
                downCurr++;
            } else {
                rightCurr--;
            }
        }
        return found;
    }

}

/**
 * 输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
 * 示例 1：
 * 输入：head = [1,3,2]
 * 输出：[2,3,1]
 */
public class 剑指Offer06从尾到头打印链表 {

    /**
     * 思路:利用栈先进后出来倒序打印
     */
    public int[] reversePrint(ListNode head) {
        Stack<ListNode> stack = new Stack<>();
        ListNode curr = head;
        while (curr != null) {
            stack.push(curr);
            curr = curr.next;
        }
        int[] res = new int[stack.size()];
        for (int i = 0; i < res.length; i++){
            res[i] = stack.pop().val;
        }
        return res;
    }

}

class CQueue {

    private Stack<Integer> stack1, stack2;

    public CQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }

    public void appendTail(int value) {
        stack1.push(value);
    }

    public int deleteHead() {
        if (!stack2.isEmpty()) {
            return stack2.pop();
        } else if (!stack1.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
            return stack2.pop();
        } else {
            return -1;
        }
    }
}

/**
 * 写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下：
 * F(0) = 0,   F(1) = 1
 * F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
 * 斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
 * 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class 剑指Offer10_I斐波那契数列 {

    public int fib1(int n) {
        if (n == 0) return 0;
        if (n <= 2) return 1;
        int[] arr = new int[2];
        arr[1] = 1;
        for (int i = 2; i <= n; i++) {
            arr[i % 2] = (arr[(i - 1) % 2] + arr[(i - 2) % 2]) % 1000000007;
        }
        return arr[n % 2];
    }

    public int fib(int n) {
        if (n == 0 || n == 1) return n;

        int f1 = 0;
        int f2 = 1;
        for (int i = 2; i <= n; i++) {
            int temp = (f1 + f2) % 1000000007;
            f1 = f2;
            f2 = temp;
        }
        return f2;
    }

}

/**
 * 请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。
 * 路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。
 * 如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。
 * 例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用加粗标出）。
 * <p>
 * [["a","b","c","e"],
 * ["s","f","c","s"],
 * ["a","d","e","e"]]
 * <p>
 * 但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
 * 输出：true
 * 示例 2：
 * <p>
 * 输入：board = [["a","b"],["c","d"]], word = "abcd"
 * 输出：false
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class 剑指Offer12矩阵中的路径 {

    /**
     * 思路，DFS
     *
     * @param board
     * @param word
     * @return
     */
    public boolean exist(char[][] board, String word) {
        if (word.length() == 0 || word == null) {
            return true;
        }
        int x = board.length;
        int y = board[0].length;
        char[] wordArr = word.toCharArray();
        boolean[][] used = new boolean[x][y];
        for (int i = 0; i < x; i++) {
            for (int j = 0; j < y; j++) {
                if (board[x][y] == wordArr[0] && dfs(board, wordArr, used, 0, x, y)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, char[] wordArr, boolean[][] used, int path, int x, int y) {
        boolean res = false;
        if (path == wordArr.length) {
            return true;
        }

        if (x >= 0 && y >= 0 && x < board.length && y < board[0].length
                && board[x][y] == wordArr[path] && !used[x][y]) {
            used[x][y] = true;
            res = dfs(board, wordArr, used, path + 1, x - 1, y)
                    || dfs(board, wordArr, used, path + 1, x, y + 1)
                    || dfs(board, wordArr, used, path + 1, x + 1, y)
                    || dfs(board, wordArr, used, path + 1, x, y - 1);
            used[x][y] = false;
        }
        return res;
    }


}

/**
 * 地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。
 * 一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），
 * 也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，
 * 因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？
 *
 *  
 *
 * 示例 1：
 *
 * 输入：m = 2, n = 3, k = 1
 * 输出：3
 * 示例 2：
 *
 * 输入：m = 3, n = 1, k = 0
 * 输出：1
 * 提示：
 *
 * 1 <= n,m <= 100
 * 0 <= k <= 20
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class 剑指Offer13机器人的运动范围 {

    public int movingCount(int m, int n, int k) {
        if (m == 0 || n == 0) {
            return 0;
        }
        boolean[][] visited = new boolean[n][m];
        return dfs(0, 0, n, m, k, visited);
    }

    private int dfs(int x, int y, int xMax, int yMax, int k, boolean[][] visited) {
        if (x < 0 || y < 0 || x >= xMax || y >= yMax || sum(x) + sum(y) > k || visited[x][y]) {
            return 0;
        }
        visited[x][y] = true;
        return 1 + dfs(x + 1, y, xMax, yMax, k, visited) + dfs(x, y + 1, xMax, yMax, k, visited);
    }

    private int sum(int x) {
        int sum = 0;
        while(x != 0) {
            sum += x % 10;
            x = x / 10;
        }
        return sum;
    }

}

/**
 * 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
 * 示例 1:
 * 输入: [7,5,6,4]
 * 输出: 5
 */
public class 剑指Offer51数组中的逆序对 {

    /**
     * 利用归并排序的思想，在合并排序的时候，如果右边数组的数小于左边数组的数，那么右边数组的这个数一定小于左边数组的所有数
     */
    int[] leftArray;
    int res;

    public int reversePairs(int[] nums) {
        res = 0;
        int n = nums.length;
        leftArray = new int[n >> 1];
        sort(nums, 0, n);
        for (int i : nums) {
            System.out.print(i + " ");
        }
        return res;
    }

    private void sort(int[] nums, int begin, int end) {
        if ((end - begin) < 2) return;
        int mid = begin + ((end - begin) >> 1);
        sort(nums, begin, mid);
        sort(nums, mid, end);
        merge(nums, begin, mid, end);
    }

    private void merge(int[] nums, int begin, int mid, int end) {
        int leftBegin = 0;
        int leftEnd = mid - begin;
        int rightBegin = mid;
        int rightEnd = end;
        int sortPoint = begin;

        for (int i = 0; i < leftEnd; i++) {
            leftArray[i] = nums[begin + i];
        }

        while (leftBegin < leftEnd) {
            if (rightBegin < rightEnd && nums[rightBegin] < leftArray[leftBegin]) {
                nums[sortPoint++] = nums[rightBegin++];
                res += leftEnd - leftBegin;
            } else {
                nums[sortPoint++] = leftArray[leftBegin++];
            }
        }
    }

}