剑指 Offer 61. 扑克牌中的顺子（重点）

感觉剑指offer里面的排序题都好难。这一题的关键在于要看出来总共就五张牌，除0外重复的不行，最大值与最小值之差小于5。满足这两个条件即可

  1. class Solution {
  2. public:
  3.     bool isStraight(vector<int>& nums) {
  4.         int maxs = 0, mins = 0, jok = 0;
  5.         sort(nums.begin(), nums.end());
  6.         for(int i = 0; i < 4; i++){
  7.             if(nums[i] == 0) jok++;
  8.             if(nums[i]!=0&&nums[i] == nums[i+1]) return false;
  9.         }
  10.         return (nums[4] - nums[jok]) < 5;
  11.     }
  12. };

剑指 Offer 45. 把数组排成最小的数（必看）

这一题也有点类似脑筋急转弯。总结的就是几句话

  • 如果x比y小，想要两个拼接起来最小，只能是x在前面。
  • 因为在c++里面比较两个字符串的大小，是从首字母开始比的，如果首字母出了结果。后面的就都不会管了

  • 总结就是，直接to_string之后无脑排序然后拼接就行了。

    快排写法

    class Solution {
public:
  string minNumber(vector<int>& nums) {
      vector<string> strs;
      for(int i = 0; i < nums.size(); i++)
          strs.push_back(to_string(nums[i]));
      quickSort(strs, 0, strs.size() - 1);
      string res;
      for(string s : strs)
          res.append(s);
      return res;
  }
private:
  void quickSort(vector<string>& strs, int l, int r) {
      if(l >= r) return;
      int i = l, j = r;
      while(i < j) {
          while(strs[j] + strs[l] >= strs[l] + strs[j] && i < j) j--;
          while(strs[i] + strs[l] <= strs[l] + strs[i] && i < j) i++;
          swap(strs[i], strs[j]);
      }
      swap(strs[i], strs[l]);
      quickSort(strs, l, i - 1);
      quickSort(strs, i + 1, r);
  }
};

    sort写法

    class Solution {
public:
  string minNumber(vector<int>& nums) {
      vector<string> strs;
      string res;
      for(int i = 0; i < nums.size(); i++)
          strs.push_back(to_string(nums[i]));
      sort(strs.begin(), strs.end(), [](string& x, string& y){ return x + y < y + x; });
      for(int i = 0; i < strs.size(); i++)
          res.append(strs[i]);
      return res;
  }
};

    剑指 Offer 40. 最小的k个数（大顶堆/优先队列）

    这一题如果直接sort然后取，虽然能过，但是面试官不喜欢看到这样的答案。所以应该使用大顶堆的方法来一直维护四个最小值。

    class Solution {
public:
  vector<int> getLeastNumbers(vector<int>& arr, int k) {
      vector<int> vec(k, 0);
      if (k == 0) { // 排除 0 的情况
          return vec;
      }
      priority_queue<int> Q;//依靠堆来实现优先队列
      for (int i = 0; i < k; ++i) {
          Q.push(arr[i]);
      }
      for (int i = k; i < (int)arr.size(); ++i) {
          if (Q.top() > arr[i]) {
              Q.pop();
              Q.push(arr[i]);
          }
      }
      for (int i = 0; i < k; ++i) {
          vec[i] = Q.top();
          Q.pop();
      }
      return vec;
  }
};

    剑指 Offer 41. 数据流中的中位数（大顶堆与小顶堆/优先队列）

    这一题使用了c++优先队列的内置参数，直接定义了大顶堆与小顶堆。一个存最大值，一个存最小值。
    less 大顶堆
    greater 小顶堆
    注意始终保证大顶堆的最大值小于或等于右边堆的最小值。

    class MedianFinder {
public:
  // 最大堆，存储左边一半的数据，堆顶为最大值
  priority_queue<int, vector<int>, less<int>> maxHeap;//大顶堆
  // 最小堆， 存储右边一半的数据，堆顶为最小值
  priority_queue<int, vector<int>, greater<int>> minHeap;//小顶堆
  /** initialize your data structure here. */
  MedianFinder() {
  }

  // 维持堆数据平衡，并保证左边堆的最大值小于或等于右边堆的最小值
  void addNum(int num) {
      /*
       * 当两堆的数据个数相等时候，左边堆添加元素。
       * 采用的方法不是直接将数据插入左边堆，而是将数据先插入右边堆，算法调整后
       * 将堆顶的数据插入到左边堆，这样保证左边堆插入的元素始终是右边堆的最小值。
       * 同理左边数据多，往右边堆添加数据的时候，先将数据放入左边堆，选出最大值放到右边堆中。
       */
      if (maxHeap.size() == minHeap.size()) {
          minHeap.push(num);
          int top = minHeap.top();
          minHeap.pop();
          maxHeap.push(top);
      } else {
          maxHeap.push(num);
          int top = maxHeap.top();
          maxHeap.pop();
          minHeap.push(top);
      }
  }

  double findMedian() {
      if (maxHeap.size() == minHeap.size()) {
          return (maxHeap.top()+minHeap.top())*1.0/2;
      } else {
          return maxHeap.top()*1.0;
      }
  }
};