SamJ's blog

leetcode 做题记录(11)

algorithm
Word count: 1.9kReading time: 8 min
2021/04/12 Share

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

难度困难85

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

例如，

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

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

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

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

示例 1：

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

示例 2：

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

完全想不到咋做(想到的都很暴力)，看了题解知道用一个小顶堆和一个大顶堆结合。

主要有两个操作，一个是addNum，一个是findMedian，最关键是用两个堆配合，addNum时需要进行的操作。使用最小堆堆顶或者两个堆堆顶的平均值求中位数。

主要两种情况：

  • minHeap.size() == maxHeap.size()时，先入大顶堆，然后将大顶堆堆顶推给小顶堆。
  • !=时，先入小顶堆，然后小顶堆堆顶推给大顶堆。

(反过来也可以，即上文中大顶堆小顶堆互换)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class MedianFinder {
public:
    /** initialize your data structure here. */
    priority_queue<int, vector<int>, less<int>> minHeap;
    priority_queue<int, vector<int>, greater<int>> maxHeap;
    MedianFinder() {

    }
    
    void addNum(int num) {
        if(minHeap.size() == maxHeap.size())
        {
            maxHeap.push(num);
            minHeap.push(maxHeap.top());
            maxHeap.pop();
        }
        else
        {
            minHeap.push(num);
            maxHeap.push(minHeap.top());
            minHeap.pop();
        }
    }
    
    double findMedian() {
        double res;
        if(minHeap.size() == maxHeap.size()) res = (minHeap.top() + maxHeap.top())/2.0;
        else res = minHeap.top();
        return res;
    }
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */

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

难度简单178

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

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

示例1:

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

典型的动态规划问题。dp[i] = max(dp[i-1] + nums[i], nums[i])

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int dp = nums[0];
        int ans = dp;
        for(int i = 1; i < nums.size(); i ++){
            dp = max(dp + nums[i], nums[i]);
            ans = max(ans, dp);
        }
        return ans;
    }
};

剑指 Offer 43. 1～n 整数中 1 出现的次数

难度困难117

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

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

示例 1：

1
2
输入：n = 12
输出：5

示例 2：

1
2
输入：n = 13
输出：6

限制：

  • 1 <= n < 2^31

找规律的一道题。使用cur从个位开始遍历，找到这个数每个位置1出现的次数，并且加起来。

例如:

  • 1204，当cur指向十位数字0时。即我们想求从1到1204的十位上1一共出现多少次，可以知道十位上出现1的情况是：00101119, 1019 出现10次， 110119， 210219都出现10次，一直到1110~1119，所以一共是120次，刚好是把10位遮住，前面的数字乘上位的权重的值，用high*digit 表示。
  • 1214，不光出现了120次，还有1210，1212..1214。5次，即high * digit + low + 1
  • 12[2-9]4,多出现的是，1210~1219, 10(digit)次，即(high+1)*digit
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int countDigitOne(int n) {
        int cur = n % 10, high = n / 10, low = 0, res = 0;
        long digit = 1;	//注意，这里用long
        while(high != 0 || cur != 0)
        {
            if(cur == 0)
            {
                res += high * digit;
            }
            else if(cur == 1)
            {
                res += (high * digit + low + 1);
            }
            else
            {
                res += ((high + 1) * digit);
            }
            low += cur * digit;
            cur = high % 10;
            high /= 10;
            digit *= 10;
        }
        return res;
    }
};

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

难度中等78

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

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

示例 1：

1
2
输入：n = 3
输出：3

示例 2：

1
2
输入：n = 11
输出：0

限制：

  • 0 <= n < 2^31

推理的问题？一步一步推出来就OK，关键是计算下标对应的真实数字还有其位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int findNthDigit(int n) {
        if(n == 0) {return 0;}

        int digit = 1; // 数位（个位/十位/百位/...，就是1/2/3/...）
        long start = 1; // 属于该数位的所有数的起始点数（个位是1，十位是10，百位是100）
        long index_count = digit * 9 * start; // 该数位的数一共的索引个数（不是数字个数）

        while(n > index_count ) {
            // 找出 n 属于那个数位里的索引
            n -= index_count; 
            ++ digit;
            start *= 10;
            index_count = digit * 9 * start;
        }

        long num = start + (n - 1) / digit; // 算出原始的 n 到底对应哪个数字,注意要是n-1哦
        int remainder = (n - 1) % digit; // 余数就是原始的 n 是这个数字中的第几位

        string s_num = to_string(num); // 将该数字转为 string 类型
        return int(s_num[remainder] - '0'); // n 对应着第 remainder 位，再转成 int
    }
};

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

难度中等132

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

示例 1:

1
2
输入: [10,2]
输出: "102"

示例 2:

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

提示:

  • 0 < nums.length <= 100

说明:

  • 输出结果可能非常大，所以你需要返回一个字符串而不是整数
  • 拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0

不管有多少个数，也不管这些数各自分别是几位数（个位 / 十位 / 百位 / …），我们的判断方法只有一个。那就是先比较最高位，按照从小到大排即可。具体步骤如下：

先比较这些数各自的最高位，按从小到大排。比如 “1”、”32”、”100”，我们通过比较最高位可以排出：一开始是 “1” 或 “100”，然后是 “32”。
如果遇到了最高位数字相同的情况，比如上面的 “1” 和 “100”，我们自定义比较方法：比较 字符串 1 + 字符串 2 与 字符串 2 + 字符串 1 的大小，返回小的那个。
在这里我们有 “1” + “100” = “1100” 和 “100” + “1” = “1001”。
因为 “1001” < “1100”，所以我们知道应该把 “100” 放第一位，”1” 放第二位，”32” 还是在最后。
假如最高位没有相同数字，那么根据最高位的排序直接就已经排好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    string minNumber(vector<int>& nums) {
        if(nums.size() == 1) return to_string(nums[0]);
        vector<string> temp;
        for(auto num : nums)
        {
            temp.push_back(to_string(num));
        }
        sort(temp.begin(), temp.end(), comp);
        string res = "";
        for(auto str : temp)
        {
            res.append(str);
        }
        return res;
    }

    static bool comp(const string & lhs, const string & rhs){
        string temp1 = lhs + rhs;
        string temp2 = rhs + lhs;
        return temp1 < temp2;
    }
};
CATALOG
  1. 1. 剑指 Offer 41. 数据流中的中位数
  2. 2. 剑指 Offer 42. 连续子数组的最大和
  3. 3. 剑指 Offer 43. 1～n 整数中 1 出现的次数
  4. 4. 剑指 Offer 44. 数字序列中某一位的数字
  5. 5. 剑指 Offer 45. 把数组排成最小的数
Total : 27
2021
2019
C++ paper hexo algorithm algorithm,c++ linux, C japanese,anime