专栏首页星月小站剑指Offer题解

剑指Offer题解

  • 不修改数组找出重复的数字

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

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++];
            }
        }
    }

}

我的博客即将同步至腾讯云+社区,邀请大家一同入驻:https://cloud.tencent.com/developer/support-plan?invite_code=t2p93xifq7dh

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Java实现基本数据结构(一)——数组

    首先,我们先设计一个静态的数组,以int数组为例。不考虑扩容,先从最简单的类来理解数组的基本功能。 数组可以表示为下图:

    星如月勿忘初心
  • Java后端面试学习知识总结——数据库:MySQL

      关系型数据库,是指采用了关系模型来组织数据的数据库,其以行和列的形式存储数据,以便于用户理解,关系型数据库这一系列的行和列被称为表,一组表组成了数据库。用户...

    星如月勿忘初心
  • Java后端面试学习知识总结——GC

    JVM之所以能够自动回收内存,是因为JVM的开发人员使用了一些垃圾回收算法,来让JVM自己判断哪些对象可以回收,哪些对象不可以回收。

    星如月勿忘初心
  • 查找数组中两数之和等于指定的数

    题目:给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

    Melody132
  • 【LeetCode】两数之和

    给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那两个整数,并返回他们的数组下标。

    弗兰克的猫
  • 哈希表-LeetCode 217、219、220、232(hashset、hashmap)

    给定一个整数数组,判断是否存在重复元素。 如果任何值在数组中出现至少两次,函数返回 true。如果数组中每个元素都不相同,则返回 false。

    算法工程师之路
  • 【LeetCode】136. Single Number

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    韩旭051
  • 【LeetCode】找出数组中重复的数字day01

    居士
  • 【LeetCode】两数之和

    Jacob丶
  • 【Leet Code】1. Two Sum

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    韩旭051

扫码关注云+社区

领取腾讯云代金券