剑指offer每日一练

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

题目：

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

示例：

输入：[3,? 30,? 34,? 5,? 9]

输出："3033459"

解题思路：?

求拼接数的大小问题可以转化成字符串的拼接问题。

拼接字符串：

1. x + y > y + x 可得：x 大于 y

2.?x + y <?y + x 可得：x 小于 y

例如：x =? "12" , y = "30" ,? ?"1230" < "3012"所以"12"排在"30"的前面。

C++代码：

class Solution {
public:
    string minNumber(vector<int>& nums) {
        vector<string> str;
        for(int i = 0; i < nums.size(); i++)
        {
            //to_string 将整数转化为字符串
            str.push_back(to_string(nums[i]));
        }
        quick_sort(str, 0, str.size()-1);
        string res;
        for(auto item: str)
            res.append(item);
        return res;
    }

private:
    void quick_sort(vector<string> &str, int l, int r){
        if(l >= r) return ;
        int i = l - 1, j = r + 1;
        //正确
        string x = str[(l+r)/2];
        while(i < j)
        {
            do j--; while(str[j] + x > x + str[j]);
            do i++; while(str[i] + x < x + str[i]);
            
            if(i < j) swap(str[i], str[j]);
        }
        quick_sort(str, l, j);
        quick_sort(str, j+1, r);
    }
};

二. 剑指 Offer 61. 扑克牌中的顺子

题目：

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

示例：

输入：[1, 2, 3, 4, 5]

输出：True

解题思路：?

将抽出来的五张牌进行排序,? 循环遍历判读nums[i] = nums[i + 1] 是否成立进行判重。

C++代码：

class Solution {
public:
    bool isStraight(vector<int>& nums) {
       sort(nums.begin(), nums.end());
       //存储大小王的个数
       int temp = 0; 
       for(int i = 0; i < 4; i++)
       {
           if(nums[i] == 0)
                temp++;
           else if(nums[i] == nums[i+1])
                return false;
       }
       
       return nums[4] - nums[temp] < 5;
    }
};

三. 剑指 Offer 40. 最小的 k 个数

题目：

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

示例：

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

输出：[1, 2] 或者 [2, 1]

解题思路：?

快排+遍历

快排模板：

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int i = l - 1, j = r + 1, x = q[l + r >> 1];

    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }

    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

C++代码：

class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        quicksort(arr, 0, arr.size()-1);
        vector<int> res;
        for(int i = 0; i < k; i++)
        {
            res.push_back(arr[i]);
        }
        return res;
    }

private:
    void quicksort(vector<int> &arr, int l, int r){
        if(l >= r) return ;
        int i = l - 1, j = r + 1;
        int x = arr[(l + r) / 2];
        while(i < j)
        {
            do i++; while(arr[i] < x);
            do j--; while(arr[j] > x);
            if(i < j) swap(arr[i], arr[j]);
        }

        quicksort(arr, l, j);
        quicksort(arr, j+1, r);
    }
};

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

题目：

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

例如，

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

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

示例：

输入：

["MedianFinder",? "addNum",? ?"addNum",? "findMedian",? "addNum",? "findMedian"]
[[],? [1],? [2],? [],? [3],? []]

输出：[null,? null,? null,? 1.50000,? null,? 2.00000]

解释：

MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

解题思路：?

建立小顶堆 A 和大顶堆 B，其中 B 放较小的一半数、A 放较大的一半数

????????如果 A.size() == B.size() ，则中位数为(A?的堆顶元素 +?B?的堆顶元素) / 2；

????????如果 A.size() != B.size()，则中位数为A 的堆顶元素

小堆顶的建立：

priority_queue<int,? vector<int>,? greater<int>> A;

大堆顶的建立：

priority_queue<int,? vector<int>,? less<int>> B;

C++代码：

class MedianFinder {
public:
    /** initialize your data structure here. */

    //升序队列, 小顶堆, 存储较大的一部分
    priority_queue<int, vector<int>, greater<int>> A;
    //降序队列, 大顶堆, 存储较小的一部分
    priority_queue<int, vector<int>, less<int>> B;

    MedianFinder() {

    }

    //从数据流中添加一个整数到数据结构中
    void addNum(int num) {
        if(A.size() == B.size())
        {
            B.push(num);
            A.push(B.top());
            B.pop();
        }
        else
        {
            A.push(num);
            B.push(A.top());
            A.pop();
        }

    }
    
    //返回目前所有元素的中位数
    double findMedian() {
        if(A.size() != B.size()) return A.top();
        else return (A.top() + B.top())/2.0;
    }
};

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