【LeetCode】《剑指Offer》第Ⅴ篇⊰⊰⊰ 39 - 47题

逃离我推掉我的手 2022-11-04 05:25 40阅读 0赞

## 【LeetCode】《剑指Offer》第Ⅴ篇⊰⊰⊰ 39 - 47题 ##

### 文章目录 ###

*   *  【LeetCode】《剑指Offer》第Ⅴ篇⊰⊰⊰ 39 - 47题
     *   *  39. 数组中出现次数超过一半的数字（easy）
         *  40. 最小的k个数（easy）
         *  41. 数据流中的中位数（hard）
         *  42. 连续子数组的最大和（easy）
         *  43. 1～n 整数中 1 出现的次数（hard）
         *  44. 数字序列中某一位的数字（medium）
         *  45. 把数组排成最小的数（medium）
         *  46. 把数字翻译成字符串（medium）
         *  47. 礼物的最大价值（medium）

### 39. 数组中出现次数超过一半的数字（easy） ###

[剑指 Offer 39. 数组中出现次数超过一半的数字][Offer 39.]

【**题目**】数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

**限制：**

`1 <= 数组长度 <= 50000`

【**示例**】

输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
    输出: 2

【**解题思路**】

摩尔投票法

class Solution {
        
        public int majorityElement(int[] nums) {
        
            int count = 0, res = 0;
            for (int num : nums) {
        
                if (num == res) {
        
                    count++;
                } else {
        
                    if (count > 0) {
        
                        count--;
                    } else {
        
                        count = 1;
                        res = num;
                    }
                }
            }
            return res;
        }
    }

--------------------

### 40. 最小的k个数（easy） ###

[剑指 Offer 40. 最小的k个数][Offer 40. _k]

【**题目**】输入整数数组 `arr` ，找出其中最小的 `k` 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

**限制：**

*  `0 <= k <= arr.length <= 10000`
 *  `0 <= arr[i] <= 10000`

【**示例**】

输入：arr = [3,2,1], k = 2
    输出：[1,2] 或者 [2,1]

【**解题思路**】

方法很多，选择排序、快排、堆排序，

此处采用**大根堆**

class Solution {
        
        public int[] getLeastNumbers(int[] arr, int k) {
        
            PriorityQueue<Integer> queue = new PriorityQueue<>();
            for (int x : arr) queue.offer(x);
            int[] res = new int[k];
            for (int i = 0; i < k; i++) {
        
                res[i] = queue.poll();
            }
            return res;
        }
    }

--------------------

### 41. 数据流中的中位数（hard） ###

[剑指 Offer 41. 数据流中的中位数][Offer 41.]

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

例如，

\[2,3,4\] 的中位数是 3

\[2,3\] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构：

`void addNum(int num)` \- 从数据流中添加一个整数到数据结构中。  
`double findMedian()` \- 返回目前所有元素的中位数。

**限制：**

*  最多会对 `addNum、findMedian` 进行 `50000` 次调用。

【**示例**】

输入：
    ["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
    [[],[1],[2],[],[3],[]]
    输出：[null,null,null,1.50000,null,2.00000]

【**解题思路**】

**堆**

详细见往期博客总结[【LeetCode】求中位数（数据流、滑动窗口、两个正序数组）][LeetCode]

class MedianFinder {
        
        PriorityQueue<Integer> left;   //大根堆
        PriorityQueue<Integer> right;  //小根堆
       
        /** initialize your data structure here. */
        public MedianFinder() {
        
            left  = new PriorityQueue<Integer>((o1, o2) -> o2 - o1);
            right = new PriorityQueue<Integer>();
        }
        
        public void addNum(int num) {
        
            left.offer(num);
            right.offer(left.poll());
            if (left.size() + 1 < right.size()) {
        
                left.offer(right.poll());
            }
        }
        
        public double findMedian() {
        
            if (right.size() > left.size()) {
        
                return (double)right.peek();
            } else {
        
                return (double)(left.peek() + right.peek()) / 2;
            }
        }
    }

--------------------

### 42. 连续子数组的最大和（easy） ###

[剑指 Offer 42. 连续子数组的最大和][Offer 42.]

【**题目**】输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

**提示：**

*  `1 <= arr.length <= 10^5`
 *  `-100 <= arr[i] <= 100`

【**示例**】

输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
    输出: 6
    解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

【**解题思路**】

贪心+动态规划

class Solution {
        
        public int maxSubArray(int[] nums) {
        
            int res = nums[0];
            for (int i = 1; i < nums.length; i++) {
        
                if (nums[i - 1] > 0) {
        
                    nums[i] += nums[i - 1];
                }
                res = Math.max(res, nums[i]);
            }
            return res;
        }
    }

--------------------

### 43. 1～n 整数中 1 出现的次数（hard） ###

[剑指 Offer 43. 1～n 整数中 1 出现的次数][Offer 43. 1_n _ 1]

【**题目**】输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。

例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。

**限制：**

*  `1 <= n < 2^31`

【**示例**】

输入：n = 12
    输出：5

【**解题思路**】

找规律,

9—1个1,

99—20个1,

999—300个1，

9999—4000个1

参考热评@细b

class Solution {
        
        public int countDigitOne(int n) {
        
           return f(n);
        }
        private int f(int n) {
        
            if (n == 0) {
        
                return 0;
            }
            if (n < 10) {
        
                return 1;
            }
            String sn = String.valueOf(n);
            int high = sn.charAt(0) - '0';
            int base = (sn.length() - 1) * (int)Math.pow(10, sn.length() - 2);
            int cur  = (int)Math.pow(10, sn.length() - 1);
            if (high == 1) {
        
                return base + n - cur + 1 + f(n - high * cur);
            } else {
        
                return base * high + cur + f(n - high * cur);
            }
        }
    }

--------------------

### 44. 数字序列中某一位的数字（medium） ###

[剑指 Offer 44. 数字序列中某一位的数字][Offer 44.]

【**题目**】数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。

请写一个函数，求任意第`n`位对应的数字。

**限制：**

*  `0 <= n < 2^31`

【**示例**】

输入：n = 3
    输出：3
    ------------------------
    输入：n = 11
    输出：0

【**解题思路**】

找规律

class Solution {
        
        public int findNthDigit(int n) {
        
            int k = 0;
            for (int i = 1; i < 10; i++) {
        
                long t = (i == 1) ? 10 : (long)Math.pow(10, i - 1) * 9 * i;
                if (n < t) {
        
                    k = i;
                    break;
                }
                n -= t;
            }
            int d = 0, r = 0;
            // 加1是因为下标是从0开始算的
            if ((n + 1) % k == 0) {
        
                d = n / k;
                r = k;
            } else {
        
                d = (n + 1) / k;
                r = (n + 1) % k;
            }
            int num = (int)Math.pow(10, k - 1) + d;
            if (k == 1) num -= 1;
            return String.valueOf(num).charAt(r - 1) - '0';
        }
    }

--------------------

### 45. 把数组排成最小的数（medium） ###

[剑指 Offer 45. 把数组排成最小的数][Offer 45.]

【**题目**】输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个

**提示:**

*  `0 < nums.length <= 100`

【**示例**】

输入: [3,30,34,5,9]
    输出: "3033459"

【**解题思路**】

字符串排序，

关键点： 比较 `(a + b)`与 `(b + a)`

class Solution {
        
        public String minNumber(int[] nums) {
        
            ArrayList<String> list = new ArrayList<>();
            for (int num : nums) {
        
                list.add(String.valueOf(num));
            }
            Collections.sort(list, (o1, o2) -> {
        
                return (o1 + o2).compareTo(o2 + o1);
            });
            return String.join("", list);
        }
    }

--------------------

### 46. 把数字翻译成字符串（medium） ###

[剑指 Offer 46. 把数字翻译成字符串][Offer 46.]

【**题目**】给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法

**提示：**

*  `0 <= num < 231`

【**示例**】

输入: 12258
    输出: 5
    解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"

【**解题思路**】

方法一：

递归

class Solution {
        
        public int translateNum(int num) {
        
            if (num <= 9) return 1;
            int t = num % 100;
            if (t <= 9 || t >= 26) return translateNum(num / 10);
            return translateNum(num / 10) + translateNum(num / 100);
        }
    }

方法二：

动态规划

class Solution {
        
        public int translateNum(int num) {
        
            if (num <= 9) return 1;
            String str = String.valueOf(num);
            int[] dp = new int[str.length() + 1];
            dp[0] = dp[1] = 1;
            for (int i = 2; i <= str.length(); i++) {
        
                String part = str.substring(i - 2, i);
                if (part.compareTo("10") >= 0 && part.compareTo("25") <= 0) {
        
                    dp[i] = dp[i - 1] + dp[i - 2];
                } else {
        
                    dp[i] = dp[i - 1];
                }
            }
            return dp[str.length()];
        }
    }

--------------------

### 47. 礼物的最大价值（medium） ###

[剑指 Offer 47. 礼物的最大价值][Offer 47.]

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

【**示例**】

输入: 
    [
      [1,3,1],
      [1,5,1],
      [4,2,1]
    ]
    输出: 12
    解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物

【**解题思路**】

动态规划

class Solution {
        
        public int maxValue(int[][] grid) {
        
            int []dp = new int[grid[0].length + 1];
            for (int i = 1; i <= grid.length; i++) {
        
                for (int j = 1; j <= grid[0].length; j++) {
        
                    dp[j] = Math.max(dp[j], dp[j - 1]) + grid[i - 1][j - 1];
                }
            }
            return dp[grid[0].length];
        }
    }

[Offer 39.]: https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/
[Offer 40. _k]: https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/
[Offer 41.]: https://leetcode-cn.com/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof/
[LeetCode]: https://blog.csdn.net/weixin_44368437/article/details/112860683
[Offer 42.]: https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/
[Offer 43. 1_n _ 1]: https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/
[Offer 44.]: https://leetcode-cn.com/problems/shu-zi-xu-lie-zhong-mou-yi-wei-de-shu-zi-lcof/
[Offer 45.]: https://leetcode-cn.com/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof/
[Offer 46.]: https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/
[Offer 47.]: https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof/