剑指offer——第十六天

• • 第一题：
  • • 问题描述
    • 思路
    • 代码
    • 疑难函数
    • • PriorityQueue
      • compareTo
  • 第二题：剑指 Offer 61. 扑克牌中的顺子
  • • 问题描述
    • 思路
    • 代码

利用堆排序可

class Solution {
    public String minNumber(int[] nums) {
        Queue  queue = new PriorityQueue<>(new Comparator(){       
        public int compare(String a,String b){
            return (a+b).compareTo(b+a);
        }
        });
        for(int num : nums){
            queue.add("" + num);
        }
        StringBuilder res = new StringBuilder();
        while(!queue.isEmpty()){
            res.append(queue.poll());
        }
        return res.toString();
    }
}

特殊的队列叫做PriorityQueue，即优先队列。优先队列的作用是能保证每次取出的元素都是队列中权值最小的（Java的优先队列每次取最小元素，C++的优先队列每次取最大元素）。这里牵涉到了大小关系，元素大小的评判可以通过元素本身的自然顺序（natural ordering），也可以通过构造时传入的比较器（Comparator，类似于C++的仿函数）。
Java中PriorityQueue实现了Queue接口，不允许放入null元素；其通过堆实现，具体说是通过完全二叉树（complete binary tree）实现的小顶堆（任意一个非叶子节点的权值，都不大于其左右子节点的权值），也就意味着可以通过数组来作为PriorityQueue的底层实现。

compareTo() 方法用于两种方式的比较：

字符串与对象进行比较。
按字典顺序比较两个字符串。

class Solution {
    public boolean isStraight(int[] nums) {
        Arrays.sort(nums);
        int count = 0;
        for(int i=0;i<4;i++){
            if(nums[i]==0) count++;
            else if(nums[i] == nums[i+1]) return false; 
        }
        return nums[4]-nums[count] < 5;
    }
}